目录
写在前面
比赛地址：https://codeforces.com/contest/1780。
执念就像是记错的二级结论一样可怕的东西。冥冥之中有一种结论错了的感觉，但总是觉得自己曾经亲手推导的东西不可能出错，一边不断纠结着要不要重新推一遍，一边还是犹豫地把求出来的答案写到了试卷上。
一点随想。
还有就是这场打着打着 unrated 了。本来手感挺好，写完 C 看了看 D 也会写，本想直接飞升，突然整这么一出也劲了，我直接开摆。
A
三个奇数或两个奇数一个奇数。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
//=============================================================
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
int T = read();
while (T --) {
int n = read();
std::vector <int> odd, even;
for (int i = 1; i <= n; ++ i) {
int a = read();
if (a % 2) odd.push_back(i);
else even.push_back(i);
}
if (odd.size() >= 3) {
printf("YES\n");
for (int i = 0; i < 3; ++ i) printf("%d ", odd[i]);
printf("\n");
} else if (odd.size() >= 1 && even.size() >= 2) {
printf("YES\n");
printf("%d ", odd[0]);
for (int i = 0; i < 2; ++ i) printf("%d ", even[i]);
printf("\n");
} else {
printf("NO\n");
}
}
return 0;
}
B
考虑枚举第一段 \(b_1 = \sum_{i=1}^{r_1}a_{i}\)。显然如果一个数 \(d\) 可以成为 \(\gcd(b_1, b_2\dots,b_k)\)，那么一定有 \(b_1\bmod d=0, b_2\bmod d=0, \dots, b_k\bmod d=0\)。换言之，在保证 \(k>1\) 的情况下，\(d\) 对答案有贡献的充要条件是 \(b_1\bmod d=0\) 且 \(\sum_{i=2}^{k} b_{i} \bmod d=0\)，此时一定可以至少将 \(\{a_i\}\) 分为满足条件的 2 段。
那么我们仅需考虑 \(\{a_i\}\) 的所有前缀 \(b_1 = \sum_{i=1}^{r_1}a_{i}\) 和剩余部分 \(\sum_{i=r_1+1}^{n} a_i\)，它们两者的所有约数均对答案有贡献，取最大公约数即可。
复杂度 \(O(n\log A)\) 级别，\(A = \sum{a_i}\)。
//By:Luckyblock
/*
*/
#include <cstdio>
#include <cctype>
#include <algorithm>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN];
LL sum[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
LL gcd(LL x_, LL y_) {
return y_ ? gcd(y_, x_ % y_) : x_;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read();
sum[i] = sum[i - 1] + 1ll * a[i];
}
LL ans = 1;
for (int i = 1; i < n; ++ i) {
LL d = gcd(sum[i], sum[n] - sum[i]);
ans = std::max(ans, d);
}
printf("%lld\n", ans);
}
return 0;
}
C
贪心假咯。
虽然题都没了，但还是在这里放一组 hack 数据：
1
11 3
1 1 1 1 1 1 2 2 2 2 2
5 4 2
D
交互。
好像不难。
还是先溜了。
E
这里有一张 \(n=10^{18}\) 的完全图，点有点权，边有边权。第 \(i\) 个节点的点权值为 \(i\)，边 \((u,v)\) 的边权值为 \(\gcd(u,v)\)。
\(t\) 组数据，每组数据给定整数 \(l,r\)，求由节点 \(l\sim r\) 构成的完全子图中边权的种类数。
\(1\le t\le 100\)，\(1\le l\le r\le 10^{18}\)，\(l\le 10^9\)。
2S，256MB。
纪念第一个在赛时想到正解的 div2 E……虽然赛时没写完。
前置知识：整除分块。
问题实质是求 \([l, r]\) 中的数两两 \(\gcd\) 的种类数。考虑枚举 \(d = \gcd(i, j) (l\le i<j\le r)\)：
对于 \(d\ge l\) 时，显然当 \(2\times d \le r\) 时，\(d\) 对答案有贡献，则有贡献的 \(d\) 满足的条件为：\(d\in \left[l, \left\lfloor\frac{r}{2}\right\rfloor\right]\)。
对于 \(d< l\)，考虑 \([l,r]\) 中 \(d\) 的倍数的位置。显然其中最小的 \(d\) 的倍数为 \(\left\lceil \frac{l}{d} \right\rceil \times d\)，最大的倍数为 \(\left\lfloor \frac{r}{d} \right\rfloor \times d\)。当满足 \(\left\lceil \frac{l}{d} \right\rceil < \left\lfloor \frac{r}{d} \right\rfloor\) 时 \(d\) 对答案有贡献。由整除分块可知 \(\left\lceil \frac{l}{d} \right\rceil\) 和 \(\left\lfloor \frac{r}{d} \right\rfloor\) 分别只有 \(\sqrt{l}\) 和 \(\sqrt{r}\) 种取值，但仅有 \(r\) 过大，我们考虑通过整除分块枚举所有 \(\left\lceil \frac{l}{d} \right\rceil\) 相等的区间 \([i,j]\)。
对于 \(d\in [i,j]\)，也有 \(\left\lfloor \frac{r}{d} \right\rfloor\) 单调递减成立，则可以考虑在区间 \([i,j]\) 上二分得到最大的满足 \(\left\lceil \frac{l}{d} \right\rceil < \left\lfloor \frac{r}{d} \right\rfloor\) 的 \(d\)，区间 \([i,j]\) 对答案有贡献的数的取值范围即 \([i, d]\)。\(O(\sqrt{l})\) 地枚举所有区间后再 \(O(\log l)\) 地累计贡献即可，总复杂度 \(O(\sqrt{l}\log l)\) 级别，可以通过本题。
或者更进一步地，对于 \(d\in [i,j]\)，满足上述条件实质上等价于 \(\left(\left\lceil \frac{l}{d} \right\rceil + 1\right)\times d \le r\)。枚举区间后 \(\left\lceil \frac{l}{d} \right\rceil\) 的值固定，则最大的 \(d = \min\left(\frac{r}{\left(\left\lceil \frac{l}{d} \right\rceil + 1\right)}, j\right)\)。注意这样计算出的 \(d\) 可能小于 \(i\)，需要特判一下。此时总复杂度变为 \(O(\sqrt{l})\) 级别。
//By:Luckyblock
/*
*/
#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define LL long long
//=============================================================
//=============================================================
inline LL read() {
LL f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
LL l = read(), r = read(), ans = 0, p = 0;
if (r / 2 >= l) ans += r / 2 - l + 1;
for (LL j = l - 1, i; j; j = i - 1) {
i = ceil(1.0 * l / ceil(1.0 * l / j));
LL k = ceil(1.0 * l / j);
ans += std::max(0ll, std::min(r / (k + 1), j) - i + 1);
}
printf("%lld\n", ans);
}
return 0;
}
F
先咕。
写在最后
- \(\gcd\) 问题可以考虑枚举 \(\gcd\)。
- 有相同的约数问题可以放在模意义下考虑。
2023.1.26 是一个值得铭记的日子。今晚久违的能睡个好觉了。
就这样。
标签：846,ch,frac,Codeforces,le,right,include,Round,left From： https://www.cnblogs.com/luckyblock/p/17068373.html