写在前面
比赛地址：https://codeforces.com/contest/1916
是了，你被骗了，其实根本没有 2023 总结哈哈
当时是第二天没课不想复习了就打打玩玩，本来想把题解拖到考完试再写，但是元旦假期经过三天的牛逼熬夜最终今天失眠到三点，还有早八怕起不来直接不睡了起来学习算了呃呃，于是把这场补了。
赛时 D 一看不会以为是什么超强搜索剪枝就跑去看 E 想到线段树维护颜色了但是做法歪了没搞出来又溜去看 D 打了个表发现是沙比提笑烂了写完还剩十分钟就下班了没看 H 没想到是傻逼中的傻逼 oeis 呃呃。要是这把能搞掉 H 就纯纯上大分，可惜搞不得。这场 G 还是错题哈哈，喜提几千个踩，虽然我感觉 E 还挺有意思的。
一周二十节课的生活结束之后完全没心思期末复习，潜意识里就想着累麻了该歇歇了天天颓废。
唉，飞舞一个没有活着的价值。
A
签到，判断 \(\prod b_i\) 是否是 2023 的因数，若是则有解，直接输出 \(\frac{2023}{\prod b_i}\) 和 \(k-1\) 个 1 即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
int n, k, b[10];
//=============================================================
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();
for (int i = 1; i <= n; ++ i) b[i] = read();
int x = 2023, flag = 0;
for (int i = 1; i <= n; ++ i) {
if (x % b[i]) flag = 1;
x /= b[i];
}
if (flag) {
printf("NO\n");
continue;
}
printf("YES\n");
for (int i = 1; i < k; ++ i) printf("1 ");
printf("%d\n", x);
}
return 0;
}
B
基础数论。
由算数基本定理有 \(x = \prod_i p_i^{c_i}, (p_i\in \mathbf{Prime}, 0\le c_i)\)，设 \(x\) 的最小和次小质因子分别为 \(p_1, p_2(p_1\not= p_2)\)，则 \(a,b\) 的取值仅可能是下列两种情况之一：
- \(b = \frac{x}{p_1}\)，\(a = \frac{x}{p_1^2}\)，则此时有 \(\gcd(a, b)= a\)，则 \(x = \frac{b}{a}\times b\)。
- \(b = \frac{x}{p_1}\)，\(a = \frac{x}{p_2}\)，由算数基本定理有 \(\gcd(a, b)= \frac{x}{p_1p_2} = \frac{b}{p_2} = \frac{a}{p_1}\)，则 \(x = \frac{a}{\gcd(a, b)}\times b\)。
//
/*
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;
}
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 --) {
LL a = read(), b = read();
LL d = gcd(a, b);
if (a == d) {
printf("%lld\n", b / d * b);
} else {
printf("%lld\n", a / d * b);
}
}
return 0;
}
C
发现当且仅当某轮中选中的两个操作数奇偶性不同时才会使最终的结果减少 1，且每次操作后的结果必定为偶数，奇数的个数是不增的，且 Masha 先手第一次操作之后偶数将永远存在。贪心地考虑，显然 Masha 应当每轮尽可能地在不影响和情况下减少奇数的数量，即最优策略是每次操作都选择两个奇数；而 Olya 应当每次都选择两个奇偶性不同的数进行操作。
最终答案即为所有数的和减去 Olya 执行最优策略的次数（加上特判 Masha 可能至多执行一次的不得不选两个奇偶性不同的数）。发现该过程的结果仅与初始时数列中奇数偶数的个数有关。将两人分别进行一次最优策略最终减少了 3 个奇数的连续两轮看做整体，即将奇数个数对 3 取模即得进行的次数，再特判余数即可。
//
/*
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(), sum[2] = {0, 0};
LL ans = 0;
for (int i = 1; i <= n; ++ i) {
int x = read();
++ sum[x % 2];
ans += x;
int k = sum[1] / 3, r = sum[1] % 3;
if (i == 1) printf("%lld ", ans);
else printf("%lld ", ans - k - (r == 1));
}
printf("\n");
}
return 0;
}
D
呃呃打表题。
直接大力枚举数字集合+爆搜出 3 5 7 的结果发现存在如下构造：
感觉规律很显然了呃呃，用 python 写个高精：
T = int(input())
for time in range(0, T):
n = int(input())
if n == 1:
print(1)
continue
l = (n + 1) // 2
for i in range(0, l - 1):
s = int("1" + (l - i - 2) * "0" + "3" + i * "0")
print(s * s)
t = int("14" + (l - 2) * "0")
print(t * t)
for i in range(0, l - 1):
s = int("3" + (l - i - 2) * "0" + "1" + i * "0")
print(s * s)
E
好玩题。
有一种树上 HH 的项链的感觉？
首先特判答案 \(f(a, b)\) 满足 \(\operatorname{lca} = a\) 的情况，显然此时令 \(a=1\) 是最优的，简单 dfs 求所有节点到 1 路径上颜色种类数即可。
然后考虑 \(\operatorname{lca} \not= a\) 的情况。一个典中典的思考方向是考虑枚举答案式子中的 \(\operatorname{lca}=u\)，即考虑维护 \(\operatorname{subtree}(u)\) 到 \(u\) 路径上的颜色种类数，找到位于不同子树中颜色种类数最大和次大的节点，则它们的颜色种类数的乘积即为 \(\operatorname{lca}=u\) 时所有路径中对答案贡献的最大值。
主要难点在于如何维护。发现要查询的是子树中的最值，另一个典中典想法是考虑先将树按 dfs 序转化为序列，子树变成了一段连续的区间，令序列中每个位置为对应节点到当前枚举的 \(\operatorname{lca}\) 路径中颜色种类数，维护和查询区间最大值即可。考虑用 dfs 枚举 \(\operatorname{lca}\)，并同时用线段树维护上述区间最值，则对于节点 \(u\) 枚举所有儿子 \(s\) 并查询 \(\operatorname{subtree}(s)\) 对应的区间的最值，取最大值和次大值即为 \(\operatorname{lca}=u\) 时贡献的最大值。
然后考虑具体如何在 dfs 过程中维护线段树。\(\operatorname{lca}=1\) 对应的线段树可以在预处理后直接建出来，仅需考虑在父节点 \(u\) 向下转移到子节点时如何削除 \(u\) 的影响来维护路径的颜色种类数，即令子树中某些位置对应的值 \(-1\)。手玩下发现，设点集 \(\{ x \}_u\) 满足：
- \(x\) 在 \(u\) 的子树中。
- \(x\) 与 \(u\) 同色。
- 路径 \(u\rightarrow x\) 上没有其他同色节点。
则在转移后会影响的节点集合即为：\(\operatorname{subtree}(u) - \sum_{v\in \{x\}_u} \operatorname{subtree}(v)\)。
显然 \(\{x\}\) 中节点的子树均不相交，则 \(\operatorname{subtree}(v)\) 在序列中对应 \(|\{x\}_u|\) 个不相交的连续区间，被影响的节点集合即这些区间的补集，显然为不多于 \(|\{x\}_u|+1\) 个不相交的连续区间。考虑点集 \(\{x\}_u\) 的实际意义显然有 \(\sum_u |\{x\}_u|< n\)，则转移时影响到的区间数量之和为 \(O(n)\) 级别，直接枚举区间进行线段树区间加维护即可。在回溯时进行反向操作还原 \(u\) 的影响即可。
上述点集 \(\{x\}_u\) 同样可以预处理，仅需在 dfs 预处理过程中顺带维护当前节点的祖先中距离最近的每种颜色的节点，将当前枚举到的节点加入到距离最近的同色祖先的 \(\{x\}\) 的集合中即可。
总时空复杂度 \(O(n\log n)\) 级别。
思路理顺了代码也挺好写（迫真
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, a[kN];
int datanum, data[kN];
int edgenum, head[kN], v[kN], ne[kN];
int bnum, L[kN], R[kN], b[kN];
int cnt[kN], num[kN], last[kN];
std::vector <int> next[kN];
int sonnum, son[kN];
LL ans;
//=============================================================
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;
}
namespace Seg {
#define ls (now_<<1)
#define rs (now_<<1|1)
#define mid ((L_+R_)>>1)
const int kNode = kN << 2;
int v[kNode], tag[kNode];
void Pushup(int now_) {
v[now_] = std::max(v[ls], v[rs]);
}
void Pushdown(int now_) {
v[ls] += tag[now_], v[rs] += tag[now_];
tag[ls] += tag[now_], tag[rs] += tag[now_];
tag[now_] = 0;
}
void Build(int now_, int L_, int R_) {
v[now_] = tag[now_] = 0;
if (L_ == R_) {
v[now_] = num[b[L_]];
return ;
}
Build(ls, L_, mid), Build(rs, mid + 1, R_);
Pushup(now_);
}
void Modify(int now_, int L_, int R_, int l_, int r_, int val_) {
if (l_ <= L_ && R_ <= r_) {
v[now_] += val_;
tag[now_] += val_;
return ;
}
if (tag[now_]) Pushdown(now_);
if (l_ <= mid) Modify(ls, L_, mid, l_, r_, val_);
if (r_ > mid) Modify(rs, mid + 1, R_, l_, r_, val_);
Pushup(now_);
}
int Query(int now_, int L_, int R_, int l_, int r_) {
if (l_ <= L_ && R_ <= r_) return v[now_];
if (tag[now_]) Pushdown(now_);
int ret = 0;
if (l_ <= mid) ret = std::max(ret, Query(ls, L_, mid, l_, r_));
if (r_ > mid) ret = std::max(ret, Query(rs, mid + 1, R_, l_, r_));
return ret;
}
#undef ls
#undef rs
#undef mid
}
void Clear() {
bnum = edgenum = datanum = 0;
ans = 0;
for (int i = 1; i <= n; ++ i) {
head[i] = 0;
L[i] = R[i] = 0;
num[i] = cnt[i] = 0;
next[i].clear();
}
}
void Add(int u_, int v_) {
v[++ edgenum] = v_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Init() {
n = read();
Clear();
for (int i = 2; i <= n; ++ i) {
int fa = read();
Add(fa, i);
}
for (int i = 1; i <= n; ++ i) a[i] = data[i] = read();
std::sort(data + 1, data + n + 1);
datanum = std::unique(data + 1, data + n + 1) - data - 1;
for (int i = 1; i <= n; ++ i) {
a[i] = std::lower_bound(data + 1, data + datanum + 1, a[i]) - data;
}
}
void Dfs1(int u_) {
if ((++ cnt[a[u_]]) == 1) ++ num[u_];
ans = std::max(ans, 1ll * num[u_]);
L[u_] = ++ bnum;
b[bnum] = u_;
int temp = last[a[u_]];
if (temp) next[temp].push_back(u_);
last[a[u_]] = u_;
for (int i = head[u_]; i; i = ne[i]) {
num[v[i]] = num[u_];
Dfs1(v[i]);
}
-- cnt[a[u_]];
R[u_] = bnum;
last[a[u_]] = temp;
}
void Dfs2(int u_) {
sonnum = 0;
for (int i = head[u_]; i; i = ne[i]) {
son[++ sonnum] = Seg::Query(1, 1, n, L[v[i]], R[v[i]]);
}
std::sort(son + 1, son + sonnum + 1);
ans = std::max(ans, 1ll * son[sonnum] * son[sonnum - 1]);
int l_ = L[u_];
for (auto x: next[u_]) {
if (l_ <= L[x] - 1) Seg::Modify(1, 1, n, l_, L[x] - 1, -1);
l_ = R[x] + 1;
}
if (l_ <= n) Seg::Modify(1, 1, n, l_, n, -1);
for (int i = head[u_]; i; i = ne[i]) Dfs2(v[i]);
l_ = L[u_];
for (auto x: next[u_]) {
if (l_ <= L[x] - 1) Seg::Modify(1, 1, n, l_, L[x] - 1, 1);
l_ = R[x] + 1;
}
if (l_ <= n) Seg::Modify(1, 1, n, l_, n, 1);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
Dfs1(1);
Seg::Build(1, 1, n);
Dfs2(1);
printf("%lld\n", ans);
}
return 0;
}
写在最后
学到了什么：
- D：敢打就是赢。
- E：dfs 回溯 + 线段树维护树上节点到子树中节点路径颜色数。
哈哈期末考试我草，现在开始学习量子物理！！！！！