A[CF1492A(800)]
计算离$a$，$b$，$c$的倍数最近是多少即可。
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T --) { long long p, a, b, c; cin >> p >> a >> b >> c; long long x = (a - p % a) % a; long long y = (b - p % b) % b; long long z = (c - p % c) % c; cout << min(x, min(y, z)) << ' '; } return 0; }
View Code
B[CF1486C1(1600)]
先问一次找出整个数组次大的位置，设为$p$。那么最大值肯定在$p$的某一侧，于是先问一下$[1,p]$，如果答案是$p$说明最大值在$[1,p]$，然后根据最大值的单调性二分查找即可。
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; auto query = [&] (int l, int r) -> int { cout << '?' << ' ' << l << ' ' << r << endl; int ret; cin >> ret; return ret; }; int p = query(1, n); if (p > 1 && query(1, p) == p) { int l = 0; int r = p; while (r - l > 1) { int mid = l + r >> 1; int cur = query(mid, p); if (cur == p) { l = mid; } else { r = mid; } } cout << '!' << ' ' << l << endl; } else { int l = p; int r = n + 1; while (r - l > 1){ int mid = l + r >> 1; int cur = query(p, mid); if (cur == p) { r = mid; } else { l = mid; } } cout << '!' << ' ' << r << endl; } return 0; }
View Code
C[CF1418C(1500)]
设$dp[i][0/1]$表示当前在第$i$个位置，轮到谁打怪兽，最小的花费。转移则枚举这次打几个怪兽即可。
#include <bits/stdc++.h> using namespace std; const int inf = 1000000000; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while(T--) { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; ++i) { cin >> a[i]; } vector<vector<int> > dp(n + 1, vector<int> (2, inf)); dp[0][0] = 0; for(int i = 0; i < n; ++i) { dp[i + 1][0] = min(dp[i + 1][0], dp[i][1]); if(i + 2 <= n) { dp[i + 2][0] = min(dp[i + 2][0], dp[i][1]); } dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + (a[i] == 1)); if(i + 2 <= n) { dp[i + 2][1] = min(dp[i + 2][1], dp[i][0] + (a[i] == 1) + (a[i + 1] == 1)); } } cout << min(dp[n][0], dp[n][1]) << ' '; } return 0; }
View Code
D[CF1557C(1700)]
考虑常见的套路，从高位到低位枚举。假设当前在第$i$位，且前面几位两个数都对应相等，那么这一位可以选择大于或者继续等于。如果大于的话，那么第一个数这位为$1$，第二个数这位为$0$，说明所有的$a_i$这位必须是$1$，那么$n$为偶数的时候第二个数这位为$0$。这样大小关系已经分出，之后的位随便选即可。如果继续相等，那么可以两个数这位都为$1$或$0$。为$1$的情况上面已经讨论，为$0$的情况需要所有$a_i$这位不全为$1$，同时有偶数个$a_i$这位为$0$，这里利用组合数的恒等式计算即可，即$sum_{i=0,i%2==0}^{n}{inom{n}{i}}=2^{n-1}$。然后最后加上两个数相等的情况。
#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; long long modpow(long long x, long long y) { long long ret = 1; for (; y; y >>= 1, x = x * x % mod) { if (y & 1) { ret = ret * x % mod; } } return ret; } int main() { int t; cin >> t; while (t--) { int n, k; cin >> n >> k; long long s = 1; long long ans = 0; for (int i = k - 1; i >= 0; --i) { if (n % 2 == 0) { ans += s * modpow(2, 1ll * n * i); ans %= mod; s *= modpow(2, n - 1) - 1; s %= mod; } else { s *= (modpow(2, n - 1) + 1); s %= mod; } } ans += s; ans %= mod; cout << ans << ' '; } }
View Code