目录
写在前面
比赛地址：https://codeforces.com/contest/1920
考试周突然发癫想打 cf 但是觉得肯定打不完所以拿小号打的。
手速慢了没上大分呃呃
A
求出上下界来，再求被限制的数有多少个在区间内即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kInf = 1e9 + 2077;
//=============================================================
//=============================================================
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() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
int minn = -kInf, maxx = kInf;
std::map <int, bool> vis;
int n = read();
while (n --) {
int opt = read();
if (opt == 1) {
minn = std::max(minn, read());
} else if (opt == 2) {
maxx = std::min(maxx, read());
} else {
vis[read()] = 1;
}
}
int num = maxx - minn + 1;
for (auto x: vis) {
num -= (minn <= x.first && x.first <= maxx);
}
printf("%d\n", minn > maxx ? 0 : num);
}
return 0;
}
B
所有数均为正数，则当 Alice 确定了保留哪些数之后 Bob 的行动就确定了，一定会把其中最大的 \(k\) 个变成负数。
另外发现 Alice 保留的数一定是一段连续的前缀。考虑反证，若 Alice 保留的数按升序排序后是 \(a_1\sim a_{i-1}, a_{i + 1}\sim a_{m}\)，若 \(k\le m - i\)，则 Alice 少删一个 \(a_i\) 可以获得更大的价值；若 \(k\ge m-i\)，则 Alice 把删 \(a_{i}\) 换成删 \(a_{m}\) 可以损失得更少。
则考虑枚举 Alice 保留的前缀长度，再减去 Bob 删的数的贡献，所有情况取最大值即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const LL kInf = 1e15 + 2077;
//=============================================================
int n, k, x, 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;
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), k = read(), x = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++ i) sum[i] = sum[i - 1] + a[i];
// for (int i = n; i >= 1; -- i) sum[i] = sum[i + 1] + 1ll * a[i];
LL ans = -kInf, s;
for (int i = n, j = 0; i >= 0 && j <= k; -- i, ++ j) {
s = sum[i];
s -= 2ll * sum[i] - 2ll * sum[std::max(0, i - x)];
ans = std::max(ans, s);
}
printf("%lld\n", ans);
}
return 0;
}
C
\(O(10^5)\) 的 \(n\) 的因子个数最多只有 128 个（https://oeis.org/A066150），于是考虑枚举每段的长度 \(k\)，先考虑如何每段的同一个位置的数 \(\{a_i, a_{k + i}, a_{2\times k + i}\cdots\}\) 变为相同的数。对某个数 \(m\) 取模之后 \(\{a_i, a_{k + i}, a_{2\times k + i}\cdots\}\) 变为相同的数，即这些数模 \(m\) 均相等，说明这些数之间的差均是 \(m\) 的倍数，则考虑将这些数升序排序并求相邻数之差，将差取 \(\gcd\) 即为 \(m\) 可能的最大值，且这个数的所有因子均可作为 \(m\)。
于是得到了使每段中同一位置变为相同的最大值 \(m_1, m_2, \cdots, m_k\)，由上述分析，再将这些数取 \(\gcd\) 即为满足题意的最大的 \(m\)，若 \(\ge 2\) 则当前枚举的 \(k\) 对答案贡献为 1，否则为 0。
实际实现上并不需要显式地把每段同一位置的数分离出来排序后作差再求 gcd，仅需枚举数列中所有距离为 \(k\) 的数对作差并对差取 gcd 即可。
总时间复杂度 \(O(n\ln n\log n)\) 级别。
下面是赛时的麻烦写法、、、
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, ans, a[kN], b[kN], c[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;
}
int gcd(int x_, int y_) {
return y_ ? gcd(y_, x_ % y_) : x_;
}
void Solve(int k_) {
if (k_ == n) {
++ ans;
return ;
}
int g = 0;
for (int i = 1; i <= k_; ++ i) {
int p = 0;
for (int j = 0; j * k_ + i <= n; ++ j) {
b[++ p] = a[j * k_ + i];
}
std::sort(b + 1, b + p + 1);
for (int j = p; j > 1; -- j) b[j] -= b[j - 1];
for (int j = 2; j <= p; ++ j) {
if (b[j] == 0) continue;
g = gcd(g, b[j]);
}
}
ans += (g != 1);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
ans = 0;
n = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1, lim = sqrt(n); i <= lim; ++ i) {
if (n % i) continue;
Solve(i);
if (i * i != n) Solve(n / i);
}
printf("%d\n", ans);
}
return 0;
}
D
挺一眼的递归分治题呃呃
在读入操作过程中计算此时数列的长度，若长度大于 \(10^{18}\) 则记为极大值。
操作 2 并不会生成新种类的权值，则所有询问实质上都可以对应到某次操作 1 上。于是考虑反向地撤销操作并减少数列的长度，设撤销后数列长度为 \(l\)，枚举所有大于 \(l\) 的询问，若这次操作为 1 则该询问的值即为此次操作 1 增加的值；若这次操作为 2 则计算该询问在撤销后的数列对应的位置，留到之后的撤销中解决即可。
在撤销过程中，对询问维护大根堆即可实现。
总时间复杂度 \(O(n + m\log m)\) 级别。
注意维护数列长度时可能爆 LL，开 __int128。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define pr std::pair
#define mp std::make_pair
#define LL __int128
// #define LL long long
const int kN = 1e5 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, q;
struct Data {
int opt, x;
LL nowl;
} a[kN];
int ans[kN];
//=============================================================
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 << 3ll) + (w << 1ll) + (ch ^ '0');
return f * w;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read(), q = read();
for (int i = 1; i <= n; ++ i) {
a[i].opt = read(), a[i].x = read();
if (a[i].opt == 2) {
a[i].nowl = a[i - 1].nowl + (LL) a[i].x * a[i - 1].nowl;
} else {
a[i].nowl = a[i - 1].nowl + 1;
}
if (a[i].nowl > kInf) a[i].nowl = kInf;
}
std::priority_queue <pr <LL, int> > query;
for (int i = 1; i <= q; ++ i) query.push(mp(read(), i));
for (int i = n; i; -- i) {
while (!query.empty() && (query.top().first) > a[i - 1].nowl) {
pr <LL, int> now = query.top(); query.pop();
if (a[i].opt == 1) {
ans[now.second] = a[i].x;
} else {
now.first = now.first % a[i - 1].nowl;
if (now.first == 0) now.first = a[i - 1].nowl;
query.push(now);
}
}
}
for (int i = 1; i <= q; ++ i) printf("%d ", ans[i]);
printf("\n");
}
return 0;
}
E
吃个饭回来补。
写在最后
学到了什么：
- C：余数相同的数作差后肯定是模数的倍数。一张非常经典的表格。