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;
}
