Codeforces Round #757 (Div. 2)

problem: (C ) Divan and bitwise operations

刚开始在写拆位，然后对于每一位有若干区间不存在，再把这些区间合并，算一个总长度，剩下的就是含有这位的数，再套个组合数

写一半边上妹妹说乱猜就过了然后回过头来模样例，112除以16怎么是7啊可恶，就猜了下就过了

先说结论：把读入的每个数或起来然后乘上2的n-1次

关于证明：还是拆位考虑，对于第i位如果存在一个位置是1，不考虑这个位置，剩下长度为n - 1的数的subsequence是$2^{n-1}$，并且对于每个subsequence再加上这个位置都可以唯一确定一个xor贡献为(1 << i)的方案：当其余位置xor和为0时，取这位的1；xor为(1 << i) 时，不取这位的1 。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll N = 1e6 + 10;
const ll M = 40;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;

struct node {
    ll l, r;
};
vector<node> vec[M];

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    ll T;
    cin >> T;
    while (T--) {

        ll n, m;
        cin >> n >> m;
        ll ans = 0;
        for (ll i = 0; i < m; ++i) {
            ll l, r, x;
            cin >> l >> r >> x;
            ans = ans | x;
        }

        ans = ans % mod;
        ans = ans * qpow(2, n - 1) % mod;
        cout << ans << endl;
    }
    return 0;
}

problem: (D1) Divan and Kostomuksha (easy version)

考虑直接构造一个gcd序列

满足每个数是前一个数的约数，考虑dp转移，先对于每个数分解（将它的每个约数的num++，反过来也就是对于每个数将它本身的贡献加到它的每个倍数上面）

构造的gcd序列是有点像阶梯那样的（什么破比喻）d1d1…d1d2d2…d2d3d3…d3…，
记num[i] := i 的倍数有多少个

dp[i] := 以 i 开头的数列的最大值

从后往前dp， d p [ i ] = m a x j ∣ i { d p [ i ] , n u m [ i ] ∗ ( i − j ) + d p [ j ] } dp[i] = max _{j| i} {dp[i], num[i] * (i - j) + dp[j]} dp[i]=maxj∣i​{dp[i],num[i]∗(i−j)+dp[j]} // 大概想的是按层算贡献

时间复杂度：计算num这里 $O(MlogM)$ dp这里 $O(MlogM)$ ， 所以一共也是$O(MlogM)$

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll N = 5e6 + 10;
ll a[N], dp[N], num[N];

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    ll n;
    cin >> n;
    for (ll i = 1; i <= n; ++i) {
        cin >> a[i];
        ++num[a[i]];
    }

    for (ll i = 1; i < N; ++i) {
        for (ll j = i << 1; j < N; j += i) {
            num[i] += num[j];
        }
    }

    dp[1] = num[1];
    for (ll i = 1; i < N; ++i) {
        for (ll j = 2; j * i < N; ++j) {
            dp[i * j] = max(dp[i * j], dp[i] + (j * i - i) * num[i * j]);
        }
    }

    ll ans = 0;
    for (ll i = 1; i < N; ++i) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;

    return 0;
}

problem: (D2) Divan and Kostomuksha (hard version)

进行一个优化，可以使得gcd数列里面每一项都是前一项刚好除掉一个素数，将合数拆开中间以实际不存在的素数作为跳板（因为没出现算贡献的时候是0）

即将gcd 6666111表示成 6(4) 3(0) 1(3) 括号内为数的个数

想法参考埃氏筛，于是这部分的复杂度就变成了$O(MloglogM)$ 几乎$O(M)$

先将素数都筛出来然后对于每个数枚举他的因子的时候 枚举中间的倍数 并且这个倍数是素数

前面num的部分可以用类似的方法参考狄利克雷前缀和，高位前缀和之类的做也是$O(MloglogM)$， 或者对于每个数分解把他每个数位置的因子加上去

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll N = 2e7 + 10;
ll a[N], dp[N], num[N];

ll primes[N], cnt = 0;
bool st[N];

void sieve() {
    cnt = 0;
    for (ll i = 2; i < N; ++i) {
        if (!st[i]) primes[++cnt] = i;
        for (ll j = 1; primes[j] * i < N; ++j) {
            st[primes[j] * i] = 1;
            if (i % primes[j] == 0) break;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    sieve();

    ll n;
    cin >> n;
    for (ll i = 1; i <= n; ++i) {
        cin >> a[i];
        ++num[a[i]];
    }

    for (ll i = 1; i <= cnt; ++i) {
        for (ll x = N / primes[i]; x; --x) {
            num[x] += num[x * primes[i]];
        }
    }

//    for (ll i = 1; i < N; ++i) {
//        for (ll j = i << 1; j < N; j += i) {
//            num[i] += num[j];
//        }
//    }

    dp[1] = num[1];
    for (ll i = 1; i < N; ++i) {
//        for (ll j = 2; j * i < N; ++j) {
//            dp[i * j] = max(dp[i * j], dp[i] + (j * i - i) * num[i * j]);
//        }
        for (int k = 1; i * primes[k] < N; ++k) {
            dp[i * primes[k]] = max(dp[i * primes[k]], dp[i] + (i * primes[k] - i) * num[i * primes[k]]);
        }
    }

    ll ans = 0;
    for (ll i = 1; i < N; ++i) {
        ans = max(ans, dp[i]);
    }
    cout << ans << endl;

    return 0;
}

最后

以上就是顺心猎豹为你收集整理的Codeforces Round #757 (Div. 2)Codeforces Round #757 (Div. 2)的全部内容，希望文章能够帮你解决Codeforces Round #757 (Div. 2)Codeforces Round #757 (Div. 2)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。