头像

yxc

北京大学




离线:8小时前


最近来访(154368)
用户头像
acwing_40357
用户头像
平A
用户头像
Rainiver
用户头像
cyber_algorithmer
用户头像
valude_hht
用户头像
ZUO_0
用户头像
长路
用户头像
Tao_34
用户头像
逆风直接投
用户头像
Zaln
用户头像
ohzjackie
用户头像
D_72
用户头像
皓月长歌
用户头像
小鹿不乱撞
用户头像
只吃肉不吃菜
用户头像
酒徒ᝰ.
用户头像
goodzhou
用户头像
davidxiaodong
用户头像
神经蛙_406
用户头像
._5045

活动打卡代码 AcWing 5034. 配对

yxc
1天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int n;
char sex[N];
int w[N];
struct Data
{
    int d, a, b;
    bool operator< (const Data& t)const
    {
        if (d != t.d) return d > t.d;
        return a > t.a;
    }
};
priority_queue<Data> heap;
int l[N], r[N];
bool st[N];

Data get_data(int a, int b)
{
    return {abs(w[a] - w[b]), a, b};
}

void remove(int k)
{
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main()
{
    scanf("%d", &n);
    scanf("%s", sex + 1);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    w[0] = w[n + 1] = 1e9;
    for (int i = 0; i <= n + 1; i ++ ) l[i] = i - 1, r[i] = i + 1;
    for (int i = 0; i <= n; i ++ ) heap.push(get_data(i, i + 1));

    vector<PII> res;
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int a = t.a, b = t.b;
        if (sex[a] == sex[b]) continue;
        if (st[a] || st[b]) continue;
        if (!a || b == n + 1) break;

        heap.push(get_data(l[a], r[b]));
        remove(a), remove(b);
        st[a] = st[b] = true;
        res.push_back({a, b});
    }

    printf("%d\n", (int)res.size());
    for (auto p: res)
        printf("%d %d\n", p.x, p.y);

    return 0;
}


活动打卡代码 AcWing 5033. 最远距离

yxc
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20;

int n;
int d[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &d[i][j]);

    for (int k = 0; k < n; k ++ )
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    int res = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            res = max(res, d[i][j]);

    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 5032. 字符串操作

yxc
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n, m;
    string str;

    cin >> n >> m >> str;
    while (m -- )
    {
        int l, r;
        char a, b;
        cin >> l >> r >> a >> b;
        for (int i = l - 1; i <= r - 1; i ++ )
            if (str[i] == a)
                str[i] = b;
    }

    cout << str << endl;
    return 0;
}


活动打卡代码 AcWing 5031. 矩阵扩张

yxc
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 250;

int n, m;
char p[N][N], a[N][N], b[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%s", p[i]);

    int k = 1;
    a[0][0] = '.';

    while (m -- )
    {
        for (int i = 0; i < k; i ++ )
            for (int j = 0; j < k; j ++ )
                for (int x = 0; x < n; x ++ )
                    for (int y = 0; y < n; y ++ )
                    {
                        char c = '*';
                        if (a[i][j] == '.') c = p[x][y];
                        b[i * n + x][j * n + y] = c;
                    }

        memcpy(a, b, sizeof a);
        k *= n;
    }

    for (int i = 0; i < k; i ++ ) puts(a[i]);
    return 0;
}


活动打卡代码 AcWing 5030. 核心元素

yxc
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010;

int n;
int w[N], cnt[N], ans[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);

    for (int i = 0; i < n; i ++ )
    {
        memset(cnt, 0, sizeof cnt);
        int t = 0;
        for (int j = i; j < n; j ++ )
        {
            int x = w[j];
            cnt[x] ++ ;
            if (cnt[x] > cnt[t] || cnt[x] == cnt[t] && x < t)
                t = x;
            ans[t] ++ ;
        }
    }

    for (int i = 1; i <= n; i ++ )
        printf("%d ", ans[i]);

    return 0;
}


活动打卡代码 AcWing 5029. 极值数量

yxc
8天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int w[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &w[i]);

    int res = 0;
    for (int i = 1; i < n - 1; i ++ )
    {
        int a = w[i - 1], b = w[i], c = w[i + 1];
        if (b > a && b > c || b < a && b < c)
            res ++ ;
    }

    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 4983. 最大的数

yxc
14天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N], b[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &a[i]);

    for (int i = n - 1, t = -1; i >= 0; i -- )
    {
        if (a[i] <= t) b[i] = t - a[i] + 1;
        else t = a[i];
    }

    for (int i = 0; i < n; i ++ )
        printf("%d ", b[i]);

    return 0;
}


活动打卡代码 AcWing 4982. 进制

yxc
14天前

先计算111111…1再扣掉中间的0

#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long LL;

using namespace std;

int main()
{
    LL a, b;
    cin >> a >> b;

    int res = 0;
    for (int i = 1; i <= 60; i ++ )
        for (int j = 0; j <= i - 2; j ++ )
        {
            LL t = (1ll << i) - 1 - (1ll << j);
            if (t >= a && t <= b) res ++ ;
        }

    cout << res << endl;
    return 0;
}

分别计算0左右两边的数值再相加

#include <iostream>
#include <cstring>
#include <algorithm>

typedef long long LL;

using namespace std;

int main()
{
    LL a, b;
    cin >> a >> b;

    int res = 0;
    for (int i = 1; i <= 63; i ++ )
        for (int j = 0; j <= i - 2; j ++ )
        {
            int l = i - j - 1, r = j;
            LL left = (1ll << l) - 1, right = (1ll << r) - 1;
            LL t = (left << j + 1) + right;
            if (t >= a && t <= b) res ++ ;
        }

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 4981. 第几项

yxc
14天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int n, a;
    cin >> n >> a;

    if (a % 2)
        cout << (a - 1) / 2 + 1 << endl;
    else
        cout << (a - n) / -2 + 1 << endl;

    return 0;
}


活动打卡代码 AcWing 4980. 猜数字

yxc
22天前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);

    vector<int> res;
    for (int i = 2; i <= n; i ++ )
    {
        set<int> hash;

        int m = i;
        for (int j = 2; j * j <= m; j ++ )
            if (m % j == 0)
            {
                while (m % j == 0) m /= j;
                hash.insert(j);
            }

        if (m > 1) hash.insert(m);
        if (hash.size() == 1) res.push_back(i);
    }

    printf("%d\n", (int)res.size());
    for (auto x: res)
        printf("%d ", x);

    return 0;
}