写在前面
比赛地址：https://codeforces.com/contest/1878。
前天晚上他妈睡不着觉又不想看漫画打游戏于是到阳台上开把 div3 放松心情。
40min 过了 5 题把剩下两题都口了感觉没意思了于是睡觉。
太菜了还是，现在是 div3 随便 AK 但是 div2 过不了 E 的憋屈水平。
这场全是典中典，随便写写。
A
检查 \(k\) 是否出现即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
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 n = read(), k = read(), flag = 0;
for (int i = 1; i <= n; ++ i) {
int a = read();
if (a == k) flag = 1;
}
printf("%s\n", flag ? "YES" : "NO");
}
return 0;
}
B
一个暴力的想法是令 \(a_1 = 2, a_2 = 3\)，对于 \(a_i\) 依次检查令 \(a_i=a_{i-1}+1, 2,\dots\) 是否合法即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
LL a[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);
a[1] = 2, a[2] = 3;
for (int i = 3; i < kN; ++ i) {
a[i] = a[i - 1] + 1;
while (3 * a[i] % (a[i - 1] + a[i - 2]) == 0) ++ a[i];
}
int T = read();
while (T --) {
int n = read();
for (int i = 1; i <= n; ++ i) printf("%lld ", a[i]);
printf("\n");
}
return 0;
}
/*
2 3 4 5 7 8 9 10
*/
C
从 \([1, n]\) 中选 \(k\) 个数之和的范围为 \([\sum_{1\le i\le k} i, \sum_{0\le i< k} n - i]\)，判断 \(x\) 是否在区间内即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
LL sum[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);
for (int i = 1; i < kN; ++ i) sum[i] = sum[i - 1] + i;
int T = read();
while (T --) {
int n = read(), k = read(); LL x = read();
LL minx = sum[k], maxx = sum[n] - sum[n - k];
printf("%s\n", minx <= x && x <= maxx ? "YES" : "NO");
}
return 0;
}
/*
1 2 3 4 5
*/
D
题面很长但是全是屁话。
发现区间 \([l_i, r_i]\) 互不重合且恰好覆盖整个字符串，操作 \(x\) 实际上是选择了 \(x\) 所在的区间 \([l_i, r_i] (l_i\le x\le r_i)\)，并将其中一个关于区间中心 \(\frac{l_i + r_i}{2}\) 对称的字符串进行了翻转。手玩下发现操作顺序和最终的字符串形态无关，且最终形态中某个位置 \(k\) 的字符，要么是原字符 \(s_k\)，要么是与 \(s_k\) 所在区间 \([l, r]\) 中心 \(\frac{l+r}{2}\) 对称的字符 \(s_{l+r - k}\)。
然后很容易发现某字符的取值，取决于这个位置被区间翻转操作覆盖次数的奇偶性，差分维护区间修改次数即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, k, q, l[kN], r[kN];
char s[kN], t[kN], map[kN];
int d[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;
}
void Init() {
n = read(), k = read();
for (int i = 1; i <= n; ++ i) d[i] = 0;
scanf("%s", s + 1);
for (int i = 1; i <= k; ++ i) l[i] = read();
for (int i = 1; i <= k; ++ i) r[i] = read();
for (int i = 1; i <= k; ++ i) {
for (int j = l[i]; j <= r[i]; ++ j) {
map[j] = s[l[i] + r[i] - j];
}
}
q = read();
while (q --) {
int x = read(), i = std::lower_bound(r + 1, r + k + 1, x) - r;
int pl = std::min(x, l[i] + r[i] - x), pr = std::max(x, l[i] + r[i] - x);
d[pl] ++, d[pr + 1] --;
}
}
void Solve() {
t[n + 1] = '\0';
for (int i = 1; i <= n; ++ i) {
d[i] += d[i - 1];
t[i] = d[i] % 2 ? map[i] : s[i];
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
Solve();
printf("%s\n", t + 1);
}
return 0;
}
/*
abcdef
fedcba
fbcdea
*/
E
典中典之拆位。
维护数组 \(f_{i, j}\) 表示数列前缀 \(1\sim i\) 中满足第 \(j\) 位上为 1 的数的个数，区间的与和即可 \(O(\log w)\) 地求得。
回答询问时二分即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a, cnt[kN][31];
//=============================================================
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;
}
void Init() {
n = read();
for (int i = 1; i <= n; ++ i) {
int a = read();
for (int j = 0, k = 1; j < 31; ++ j, k <<= 1) {
cnt[i][j] = cnt[i - 1][j];
if (a & k) ++ cnt[i][j];
}
}
}
int Calc(int l_, int r_) {
int ret = 0, len = r_ - l_ + 1;
for (int i = 0, j = 1; i < 31; ++ i, j <<= 1) {
if (cnt[r_][i] - cnt[l_ - 1][i] == len) {
ret |= j;
}
}
return ret;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
int q = read();
while (q --) {
int L = read(), k = read(), ans = -1;
for (int l = L, r = n; l <= r; ) {
int mid = (l + r) >> 1;
if (Calc(L, mid) >= k) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
printf("%d ", ans);
}
printf("\n");
}
return 0;
}
F
典中典之维护质因子。
对于操作 1 的询问：
- 若有 \(d(n) = n\) 令 \(a=1\) 即可。
- 否则 \(d(n)<n\)。条件 \(\gcd(a, n)\) 容易满足，随便找一个 \(n\) 中不存在的质数的幂 \(p^c\) 即可；在此基础上对于条件 \(d(n\cdot a) = n\)，有：\(d(n\cdot a) = d(n)\times (c+1)(c\in \mathbf{N}^+)\)。则当且仅当 \(d(n) \mid n\) 时存在合法的 \(a\)。
两种情况可以合并，则对于操作 1 仅需检查修改后的 \(n\) 是否满足 \(d(n)\mid n\) 即可。
发现要在操作 1 中动态维护 \(d(n)\)。又发现有典中典之条件 \(n\le 10^6\)，\(x\le 10^6\)，即 \(n\) 的质因子不会超过 \(10^6\)，于是考虑预处理 \(1\sim 10^6\) 中所有数的质因子，维护当前的 \(n\) 的质因子及其次数即可轻松维护 \(d(n)\)。
对于操作 1 的询问，先对 \(d(n)\) 做质因数分解，再与 \(n\) 的质因子进行比较即可。而对于操作 2，每次暴力地枚举把所有质因子出现次数重置显然不可取，套路地记时间戳懒惰删除即可。
质数数量不是很大，总复杂度非常优秀。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e6 + 10;
//=============================================================
int n, q, nowt, num, tag[kN], cnt[kN];
std::vector <int> p, d[kN];
bool vis[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;
}
void Init() {
for (int i = 2; i < kN; ++ i) {
if (!vis[i]) p.push_back(i), d[i].push_back(i);
for (int j = 2; i * j < kN; ++ j) {
vis[i * j] = true;
if (!vis[i]) d[i * j].push_back(i);
}
}
}
void Reset() {
++ nowt;
num = 1;
for (int i = 0, sz = d[n].size(), temp = n; i < sz; ++ i) {
int x = d[n][i];
if (tag[x] < nowt) cnt[x] = 0, tag[x] = nowt;
while (temp % x == 0) ++ cnt[x], temp /= x;
num *= cnt[x] + 1;
}
}
bool Modify(int x_) {
for (int i = 0, sz = d[x_].size(), temp = x_; i < sz; ++ i) {
int x = d[x_][i];
if (tag[x] < nowt) cnt[x] = 0, tag[x] = nowt;
num /= cnt[x] + 1;
while (temp % x == 0) ++ cnt[x], temp /= x;
num *= cnt[x] + 1;
}
for (int i = 0, sz = p.size(), temp = num; i < sz; ++ i) {
int x = p[i], c = 0;
if (temp % x != 0) continue;
if (temp < x) break;
while (temp % x == 0) ++ c, temp /= x;
if (tag[x] < nowt) cnt[x] = 0, tag[x] = nowt;
if (c > cnt[x]) return 0;
}
return 1;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
Init();
int T = read();
while (T --) {
n = read(), q = read();
Reset();
while (q --) {
int opt = read();
if (opt == 1) printf("%s\n", Modify(read()) ? "YES" : "NO");
else Reset();
}
printf("\n");
}
return 0;
}
/*
1
20 4
1 3
2
1 7
1 12
1 2 4 5 10 20
*/
G
不太典但是很恼弹的题。
记 \(h(u, v)\) 表示链 \((u,v)\) 上所有数的或和中 1 的数量。对于一次询问 \((x, y)\)，考虑取答案的位置 \(z\) 在链上移动的影响。显然 \(z\) 越靠近 \(x\) 时 \(h(x, z)\) 越小，\(h(y, z)\) 越大，反之亦然，存在单调性。于是有一个显然的想法是枚举 \(h(x, z)\) 的所有取值，对于每种取值找到令 \(z\) 最靠近 \(x\) 的位置最大化 \(h(y, z)\)，对所有情况取最大值即可。
又发现 \(h(x, z)\) 至多只有 31 种取值，考虑在链 \((x, \operatorname{lca}(x, y))\) 上从 \(x\) 开始倍增地上跳 \(z\) 即可得到当 \(z\) 在链 \((x, \operatorname{lca}(x, y))\) 上时 \(h(x, z)\) 的所有取值，以及取到该值时最靠近 \(x\) 的位置。
那 \(z\) 在链 \((y, \operatorname{lca}(x, y))\) 上的时候怎么办？考虑换成枚举 \(h(y, z)\) 的取值，找到令 \(z\) 最靠近 \(y\) 的位置最大化 \(h(x, z)\) 即可。
倍增预处理一下链的或和即可。
对于每次询问要进行枚举取值、倍增、统计 1 的个数，总时间复杂度上界理论上是 \(O(n\log n + q\log n\log^2 w)\) 级别的，但是跑不满，给了 5S 跑了 1372 ms 。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&(-x))
const int kN = 2e5 + 10;
//=============================================================
int n, q, a[kN], c[kN];
int edgenum, head[kN], v[kN << 1], ne[kN << 1];
int fa[kN][21], g[kN][21], cnt[kN][21], dep[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;
}
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
int Calc(int val_) {
int ret = 0;
for (int i = val_; i; i -= lowbit(i)) ++ ret;
return ret;
}
void Dfs(int u_, int fa_) {
dep[u_] = dep[fa_] + 1;
fa[u_][0] = fa_;
g[u_][0] = a[u_] | a[fa_];
for (int i = 1; i <= 20; ++ i) {
fa[u_][i] = fa[fa[u_][i - 1]][i - 1];
g[u_][i] = g[u_][i - 1] | g[fa[u_][i - 1]][i - 1];
}
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
Dfs(v_, u_);
}
}
int Lca(int u_, int v_) {
if (dep[u_] < dep[v_]) std::swap(u_, v_);
for (int i = 20; i >= 0; -- i) {
if (dep[fa[u_][i]] >= dep[v_]) {
u_ = fa[u_][i];
}
}
if (u_ == v_) return u_;
for (int i = 20; i >= 0; -- i) {
if (fa[u_][i] != fa[v_][i]) {
u_ = fa[u_][i];
v_ = fa[v_][i];
}
}
return fa[u_][0];
}
void Init() {
n = read();
edgenum = 0;
for (int i = 1; i <= n; ++ i) head[i] = 0;
for (int i = 1; i <= n; ++ i) a[i] = read(), c[i] = Calc(a[i]);
for (int i = 1; i < n; ++ i) {
int u_ = read(), v_ = read();
Add(u_, v_), Add(v_, u_);
}
Dfs(1, 0);
}
int Sum(int u_, int d_) {
if (!d_) return a[u_];
int ret = 0;
for (int i = 20; i >= 0; -- i) {
int step = (1 << i);
if (step <= d_) {
d_ -= step;
ret |= g[u_][i];
u_ = fa[u_][i];
}
}
return ret;
}
int Query(int x_, int y_) {
int lca = Lca(x_, y_), ans = 0;
int vx = Sum(x_, dep[x_] - dep[lca]), vy = Sum(y_, dep[y_] - dep[lca]);
int s1 = a[x_], s2 = vx | vy, c1 = Calc(s1), c2 = Calc(s2);
for (int now_ = x_; ; ) {
ans = std::max(ans, c1 + c2);
for (int i = 20; i >= 0; -- i) {
if (dep[fa[now_][i]] >= dep[lca] && Calc(s1 | g[now_][i]) == c1) {
s1 |= g[now_][i];
now_ = fa[now_][i];
}
}
if (now_ == lca) break;
s1 |= g[now_][0], c1 = Calc(s1);
now_ = fa[now_][0];
s2 = Sum(now_, dep[now_] - dep[lca]) | vy, c2 = Calc(s2);
}
s1 = vx | vy, s2 = a[y_], c1 = Calc(s1), c2 = Calc(s2);
for (int now_ = y_; ; ) {
ans = std::max(ans, c1 + c2);
for (int i = 20; i >= 0; -- i) {
if (dep[fa[now_][i]] >= dep[lca] && Calc(s2 | g[now_][i]) == c2) {
s2 |= g[now_][i];
now_ = fa[now_][i];
}
}
if (now_ == lca) break;
s2 |= g[now_][0], c2 = Calc(s2);
now_ = fa[now_][0];
s1 = Sum(now_, dep[now_] - dep[lca]) | vx, c1 = Calc(s1);
}
return ans;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
q = read();
while (q --) {
int x_ = read(), y_ = read();
printf("%d ", Query(x_, y_));
}
printf("\n");
}
return 0;
}
/*
1
7
4 7 7 4 10 8 10
6 1
3 1
2 1
7 4
1 5
4 2
4
7 5
2 3
4 5
2 5
6
9 5 6 2 4 6
5 1
2 1
1 6
4 3
1 3
4
6 1
1 4
4 3
3 5
7
5 1 3 7 5 1 6
2 1
5 4
2 3
3 4
7 6
6 3
2
4 2
7 7
*/
写在最后
学到了什么：
- 典中典中典中典。
- 呃呃好像什么都没学到。
- 放松了心情。
- 学到了打 div3 就是玩刷子游戏，以后摸鱼也打 div2 了。