题意
给 \(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{1\leq 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,j\in[L,R]\) 。
题解
知识点：整除分块。
设 \(\gcd(i,j) = d\) 我们考虑讨论 \(d\) 的大小：
- 当 \(\left\lfloor \dfrac{R}{2} \right\rfloor + 1 \leq d\) ，那么对于最小的倍数 \(2d\) ，也一定有 \(2d > R\) ， 所以不存在 \([L,R]\) 的数满足这个范围的 \(d\) 。
- 当 \(L \leq d \leq \left\lfloor \dfrac{R}{2} \right\rfloor\) ，我们一定可以构造 \(\gcd(d,2d) = d\) ，其中 \(L \leq d < 2d \leq R\) 。
- 当 \(d \leq L - 1\) ，我们尝试构造大于等于 \(L\) 的最小的一组数 \(L \leq d \cdot \left\lceil \dfrac{L}{d} \right\rceil < d \cdot \left( \left\lceil \dfrac{L}{d} \right\rceil +1\right)\) ，这两个数满足 \(d \cdot \left\lceil \dfrac{L}{d} \right\rceil < d \cdot \left( \left\lceil \dfrac{L}{d} \right\rceil +1\right) \leq R\) ，则 \(d\) 是合法的，否则一定不合法。
对于前两类我们可以轻易求出个数，但第三类，显然我们不可能一个一个枚举 \(d\in[1,L-1]\) 。
实际上，我们发现会存在许多连续区间的 \(d\) ，其 \(\left\lceil \dfrac{L}{d} \right\rceil\) 的值是一样的，大约有 \(\sqrt L\) 个。假设 \([l,r]\) 区间的 \(d\) 满足 \(\left\lceil \dfrac{L}{d} \right\rceil = \left\lceil \dfrac{L}{l} \right\rceil\) ，那么若 \(d\) 满足 \(l \leq d \leq \min \left(r,\left\lfloor \dfrac{R}{\left\lceil \dfrac{L}{d} \right\rceil + 1} \right\rfloor \right)\) 则构造的数不会超 \(R\) ，是合法的。
那么这个问题现在就变成一个整除分块问题，为了方便，我们把取上整都转化为取下整，即 \(\left\lceil \dfrac{L}{d} \right\rceil = \left\lfloor \dfrac{L-1}{d} \right\rfloor + 1\) 。已知左端点 \(l\) 和 \(\left\lfloor \dfrac{L-1}{l} \right\rceil = k\) ，求最大的右端点 \(r\) 满足 \(\left\lfloor \dfrac{L-1}{i} \right\rfloor = k,i \in [l,r]\) 。为了在 \(l\) 的基础上将 \(i\) 向上逼近，我们将整除等式转化一个不等式 \(i \cdot k \leq L-1\) ， \(r\) 即为 \(i\) 的最大值 \(\left\lfloor \dfrac{L-1}{k} \right\rfloor\) 。
现在我们就可以从 \(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;
}