codeforces round976 div2

A find minimum operations

思路：将所给的n变成k进制数，答案就是n的k进制形式下的位数之和

代码：
 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n, k;

void solve() {
    cin >> n >> k;
    ll cnt = 0;
    if(k == 1) cout << n << "\n";
    else {
    while(n) {
        cnt += n % k;
        n /= k;
    }
    cout << cnt << "\n";}
}

int main() {
    int t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}

B brightness begins

问题：

思路：
不难得到结论，只有当一个数的约数个数为偶数时，才可以保证灯处于on状态

模拟一组数据后发现，只有当该数为平方数时，约数个数才为偶数个

现在对于此结论给出证明：
将数x分解质因数可以得到以下形式：

由加法原理，乘法原理(其实就是排列组合)可知，x的约数个数与b有关

即约数个数

不难发现，只有当b全部为偶数时，n才为偶数，因为在乘法中只要有一个乘数为偶数，结果就是偶数

现在得到结论，b均为偶数

那么有

即可证明x为平方数

并且数n以内的平方数有个，因此就可以用二分求解答案

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    ll k;
    cin >> k;

    auto find = [&](ll x) {
        ll l = 0, r = 1e9;
        while(l < r) {
            ll mid = l + r + 1 >> 1;
            if(mid * mid <= x) l = mid;
            else r = mid - 1;
        }
        return l;
    };
    //cout << find(3) << " ";
    ll l = 0, r = 2e18;
    while(l < r) {
        ll mid = l + r >> 1;
        if(mid - find(mid) >= k) r = mid;
        else l = mid + 1;
    }
    cout << l << "\n";
}

int main() {
    int t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}

C bitwise balenced

问题：

思路：首先观察式子，是否存在进位借位关系

注意到a | b >= a   a & c <= a因此不存在借位关系，又因为是减法运算，所以也不会存在进位关系，那么这道题就是位独立的一道题，直接拆位讨论即可

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void solve() {
    ll b, c, d;
    ull a = 0;
    cin >> b >> c >> d;
    for(int i = 0; i <= 60; i ++ ) {
        int u = d >> i & 1;
        if(u == 1) {
            if((b >> i & 1) == 1 && (c >> i & 1) == 1) {
                a += 0;
            } else if((b >> i & 1) == 1 && (c >> i & 1) == 0) {
                a += 0;
            } else if((b >> i & 1) == 0 && (c >> i & 1) == 1) {
                cout << "-1\n";
                return;
            } else if((b >> i & 1) == 0 && (c >> i & 1) == 0) {
                a += ((ull)1 << i);
            }
        } else {
            if((b >> i & 1) == 1 && (c >> i & 1) == 1) {
                a += ((ull)1 << i);
            } else if((b >> i & 1) == 1 && (c >> i & 1) == 0) {
                cout << "-1\n";
                return;
            } else if((b >> i & 1) == 0 && (c >> i & 1) == 1) {
                a += 0;
            } else if((b >> i & 1) == 0 && (c >> i & 1) == 0) {
                a += 0;
            }
        }
    }
    cout << a << "\n";
}

int main() {
    int t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}

D connected dots

问题：

思路：首先注意到是联通块问题，因此可以考虑图论，并查集之类的做法，这里是并查集。

如果一个一个枚举判断是否在一个集合中，最差情况下要比较次，显然超时，这时候注意到我们的d很小，公差很小，就意味着每一个点最多与前面的d个点联通。我们可以用差分对一段线段打上标记，并强制点向前连边，那么我们就可以在d * n的时间复杂度内完成并查集的合并

代码：
 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 10;

int p[N], _size[N];

void init(int n) {
    for(int i = 1; i <= n; i ++ ) {
        p[i] = i;
        _size[i] = 1;
    }
}

int find(int x) {
    if(x != p[x]) {
        p[x] = find(p[x]);
    }
    return p[x];
}

void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if(pa == pb) return;
    if(_size[pa] < _size[pb]) swap(pa, pb);
    _size[pa] += _size[pb];
    p[pb] = pa;
}

void solve() {
    int n, m;
    cin >> n >> m;
    init(n);
    vector<vector<int>> diff((n + 11), vector<int>(11));
    while(m -- ) {
        int a, d, k;
        cin >> a >> d >> k;
        diff[a + d][d] ++;
        diff[a + d * k + d][d] --; 
    }

    for(int i = 1; i <= 10; i ++ ) {
        for(int j = 1; j <= n; j ++ ) {
            diff[j][i] += diff[max(0, j - i)][i];
        }
    }
    
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 1; j <= 10; j ++ ) {
            if(i - j >= 1) {
                if(diff[i][j]) {
                    merge(i, i - j);
                }
            }
        }
    }
    
    set<int> se;
    for(int i = 1; i <= n; i ++ ) se.insert(find(i));
    cout << se.size() << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}

E expected power

思路：注意到值域最大是1023，并且恰好二进制表示时各个位数都为1，由异或性质得知，最后S的值域也是不大于1023，可以枚举值域，然后用dp计算概率

时间复杂度1e8理论可以过，但是这里tle thinking....

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

ll qmi(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) (res *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}

void solve() {
    ll n;
    cin >> n;
    vector<ll> a(n + 1), p(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    for(int i = 1; i <= n; i ++ ) {
        cin >> p[i];
        p[i] = (p[i] * qmi(10000ll, mod - 2)) % mod;
    }

    vector<vector<ll>> dp((n + 1), vector<ll>(1025));
    dp[0][0] = 1;
    for(int i = 1; i <= n; i ++ ) {
        for(ll val = 0; val <= 1023; val ++ ) {
            (dp[i][val ^ a[i]] += dp[i - 1][val] * p[i]) %= mod;
            (dp[i][val] += dp[i - 1][val] * (mod + 1 - p[i])) %= mod;       
        }
    }

    ll ans = 0;
    for(int i = 0; i <= 1023; i ++ ) {
        (ans += dp[n][i] * i * i) %= mod;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cout.tie(0),  cin.tie(0);
    int t;
    cin >> t;
    while(t -- ) solve();
    return 0;
}