A
题意
给 (n) 个正整数，找到三个数，使得他们的和为奇数，输出他们的下标。
题解
知识点：贪心。
找到三个奇数或者一个奇数两个偶数即可，其他情况无解。
时间复杂度 (O(n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; bool solve() { int n; cin >> n; vector<int> v1, v2; for (int i = 1;i <= n;i++) { int x; cin >> x; if (x & 1) v1.push_back(i); else v2.push_back(i); } if (v1.size() >= 3) { cout << "YES" << 'n'; cout << v1[0] << ' ' << v1[1] << ' ' << v1[2] << 'n'; } else if (v1.size() >= 1 && v2.size() >= 2) { cout << "YES" << 'n'; cout << v1[0] << ' ' << v2[0] << ' ' << v2[1] << 'n'; } else return false; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << "NO" << 'n'; } return 0; } B
题意
给 (n) 个正整数 (a_i) 。选择一个 (k>1) ，随后将 (a_i) 分成 (k) 个连续非空段，使得每段的和 (b_i) 的最大公约数 (gcd(b_1,cdots,b_k)) 最大。
题解
知识点：数论，贪心。
对于任意 (k) 的任意划分有答案 (gcd(b_1,cdots,b_k)) ，根据 (gcd(a,b) = gcd(a+b,b)) ，即 (a) 和 (b) 的最大公因数一定也是 (a+b) 的因子，那么 (gcd(b_1+b_2,b_3,cdots,b_k) geq gcd(b_1,cdots,b_k)) ，所以任意两段合并代替合并前的两段不会让答案变差，因此最好的情况一定出现在只分为两段的情况。
因此，我们只要求出 (max_limits{1leq i leq n-1}gcd(a[1,i],a[i+1,n])) 即可。
时间复杂度 (O(n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; ll a[200007]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i], a[i] += a[i - 1]; ll ans = 1; for (int i = 1;i <= n - 1;i++) { ans = max(ans, gcd(a[i], a[n] - a[i])); } cout << ans << 'n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << 'n'; } return 0; } C
题有问题。
D
题意
有一个数字 (n in[1,10^9]) ，告诉你 (n) 的二进制位 (1) 的个数 (cnt)。
随后可以执行不超过 (30) 次操作：选择一个 (x) ，使得 (n) 减去 (x) ，得到新的 (n) 的二进制位 (1) 的个数 (cnt) 。
最后，你需要猜出 (n) 是多少。
题解
知识点：位运算，枚举。
由于 (n) 最多会有 (30) 个 (1) ，我们可以探测每一位是否为 (1) 。
具体的说，我们探测第 (i) 位是否为 (1) ，可以减去 (2^{i-1}) 。如果这位是 (1) ，那么新的个数 (cnt' = cnt-1<cnt) ，否则一定有 (cnt'geq cnt) 。但是，这个结论的前提是，我们是对原本的 (n) 做减法。考虑到操作会改变 (n) ，因此我们第 (i-1) 位探测完后，第 (i) 位的探测减去的应该是 (2^{i-1} - 2^{i-2}) ，这样可以抵消上一次操作，等效于对原来的 (n) 减去 (2^{i-1}) 。
要注意的是，如果减的数超过 (n) 那么也会错，即我们不能探测超过 (n) 最高位二进制的数。为了防止超出，我们可以记录探测为 (1) 的位数 (tot) ，如果 (tot = cnt) 那么可以立刻停止，因为此时答案已经满足要求了。
时间复杂度 (O(1))
空间复杂度 (O(1))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; int query(int x) { int cnt; cout << "- " << x << endl; cin >> cnt; return cnt; } void answer(int n) { cout << "! " << n << endl; } bool solve() { int cnt; cin >> cnt; int ans = 0, tot = 0; if (query(1) < cnt) ans += 1, tot++; for (int i = 1;i < 30 && tot < cnt;i++) { if (query((1 << i) - (1 << (i - 1))) < cnt) ans += 1 << i, tot++; } answer(ans); return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << 'n'; } return 0; } E
题意
给定一个区间 ([L,R]) ，求 (gcd(i,j)) 的种类，其中 (i,jin[L,R]) 。
题解
知识点：整除分块。
设 (gcd(i,j) = d) 我们考虑讨论 (d) 的大小：
- 当 (leftlfloor dfrac{R}{2} rightrfloor + 1 leq d) ，那么对于最小的倍数 (2d) ，也一定有 (2d > R) ， 所以不存在 ([L,R]) 的数满足这个范围的 (d) 。
- 当 (L leq d leq leftlfloor dfrac{R}{2} rightrfloor) ，我们一定可以构造 (gcd(d,2d) = d) ，其中 (L leq d < 2d leq R) 。
- 当 (d leq L - 1) ，我们尝试构造大于等于 (L) 的最小的一组数 (L leq d cdot leftlceil dfrac{L}{d} rightrceil < d cdot left( leftlceil dfrac{L}{d} rightrceil +1right)) ，这两个数满足 (d cdot leftlceil dfrac{L}{d} rightrceil < d cdot left( leftlceil dfrac{L}{d} rightrceil +1right) leq R) ，则 (d) 是合法的，否则一定不合法。
对于前两类我们可以轻易求出个数，但第三类，显然我们不可能一个一个枚举 (din[1,L-1]) 。
实际上，我们发现会存在许多连续区间的 (d) ，其 (leftlceil dfrac{L}{d} rightrceil) 的值是一样的，大约有 (sqrt L) 个。假设 ([l,r]) 区间的 (d) 满足 (leftlceil dfrac{L}{d} rightrceil = leftlceil dfrac{L}{l} rightrceil) ，那么若 (d) 满足 (l leq d leq min left(r,leftlfloor dfrac{R}{leftlceil dfrac{L}{d} rightrceil + 1} rightrfloor right)) 则构造的数不会超 (R) ，是合法的。
那么这个问题现在就变成一个整除分块问题，为了方便，我们把取上整都转化为取下整，即 (leftlceil dfrac{L}{d} rightrceil = leftlfloor dfrac{L-1}{d} rightrfloor + 1) 。已知左端点 (l) 和 (leftlfloor dfrac{L-1}{l} rightrceil = k) ，求最大的右端点 (r) 满足 (leftlfloor dfrac{L-1}{i} rightrfloor = k,i in [l,r]) 。为了在 (l) 的基础上将 (i) 向上逼近，我们将整除等式转化一个不等式 (i cdot k leq L-1) ， (r) 即为 (i) 的最大值 (leftlfloor dfrac{L-1}{k} rightrfloor) 。
现在我们就可以从 (d = 1) 开始枚举，每次可以枚举一个区间。
时间复杂度 (O(sqrt{L}))
空间复杂度 (O(1))
代码
#include <bits/stdc++.h> using namespace std; using ll = long long; bool solve() { ll L, R; cin >> L >> R; ll ans = max(0LL, R / 2 - L + 1); for (int l = 1, r;l < L;l = r + 1) { int k = (L - 1) / l; r = (L - 1) / k; ans += max(0LL, min((ll)r, R / (k + 2)) - l + 1); } cout << ans << 'n'; return true; } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << 'n'; } return 0; } 
