【算法竞赛】Codeforces Round #841 (Div. 2) C, E

Livinfly

发布于 2022-12-29 15:23:08

3610

发布于 2022-12-29 15:23:08

文章被收录于专栏：Livinfly

闲言

赛时ABD，C题没做出，赛时其实想到过前缀和，然后就是没太想清楚怎么高效的利用前缀信息。

Problem - C - Codeforces

容易发现，当一个数是另一个数的平方时，有奇数个因数。

而区间得到的结果，最多是2*n-1，联系数据范围，对答案有贡献（减少）的数较少。

所以，利用异或运算的可逆性，从对答案有贡献的值倒推。

而为了实现区间的倒推，可以尝试记录下前缀和s的当前值，每个前缀和出现过的次数（其实也就是s[p-1]出现的次数， p为让[p, i] 的区间异或和符合题目的区间起点）

void solve() {
    LL n;
    cin >> n;
    vector<int> cnt(2*n);
    int s = 0;
    LL sum = 0;
    cnt[s] ++;
    for(int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        s ^= x;
        for(LL j = 0; j*j < 2*n; j ++) {
            LL t = ((j*j)^s);
            if(t < 2*n)
                sum += cnt[t];
        }
        cnt[s] ++;
    }
    cout << n*(n+1)/2-sum << '\n';
}

Problem - E - Codeforces

因为发现题目中的总花费肯定是选的组数+边的条数，那么就让选的组数尽可能小，就需要选的组尽可能大，所以考虑从大往小贪心枚举，严谨证明我这里可能给不太出（（

然后，思考如何高效找出gcd = k的组合。

由于点的编号是1~n连续的（是不是[L, R]连续区间也是这样做挺好？），找出k的倍数的个数，理论上组数就是{n/k \choose 2}，但是由于是k倍数的组合有可能gcd = tk \space\space\space (t \in Z \bigcap \space t \geq 2)，所以，令a[x]为gcd=x的组合的数量，

a[x] = {n/k \choose 2} - a[tk] \space\space\space (t \in Z \bigcap \space t \geq 2)

void solve() {
    LL n, m;
    cin >> n >> m;
    vector<LL> a(n); // can't use a[n]
    LL res = 0;
    for(LL i = n-1; i >= 2; i --) { // i -> gcd & cost
        LL k = i-1; // edge can choose in one group
        a[i] = (n/i)*(n/i-1)/2;
        for(LL j = i*2; j < n; j += i)
            a[i] -= a[j];
        LL edges = a[i]/k*k;
        if(edges > m) 
            edges = m/k*k;
        m -= edges;
        res += edges/k*i;
    }
    if(m > 0) res = -1;
    cout << res << '\n';
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年12月28日，如有侵权请联系 cloudcommunity@tencent.com 删除

海外加速

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

海外加速

登录后参与评论

0 条评论

热度