写在前面
比赛地址：https://codeforces.com/contest/1882。
你知道我要在这里放一首由日本女歌手演唱的歌曲：
一个队友去医院一个队友军训，堂堂单刷！
感觉开场 5h 太浪费了于是找了场 div2，然后 C 不会做卡了 1h，妈的。
看完题解立马会了，我果然是没脑子选手。
A
显然直接从从 1 开始构造即可，记 \(b_0 = 0\)，则：
\[b_i = \begin{cases}
b_{i - 1} + 1 & (a_{i} \not= b_{i - 1} + 1)\\
b_{i - 1} + 2 & \text{otherwise}
\end{cases}\]
//
/*
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(), a, b = 1;
for (int i = 1; i <= n; ++ i, ++ b) {
a = read();
if (a == b) ++ b;
}
printf("%d\n", b - 1);
}
return 0;
}
B
\(S\not= \cup_{i} S_i\) 这个限制挺有趣的，又发现数据范围挺小，于是考虑枚举不在 \(S\) 中的数，将不含有该数的所有 \(S_i\) 并起来求的势的最大值即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 60;
//=============================================================
int n, sz[kN], s[kN][kN];
std::vector <int> val;
bool have[kN], 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() {
n = read();
for (int i = 1; i < kN; ++ i) have[i] = 0;
val.clear();
for (int i = 1; i <= n; ++ i) {
sz[i] = read();
for (int j = 1; j <= sz[i]; ++ j) {
int v = s[i][j] = read();
if (!have[v]) val.push_back(v);
have[v] = true;
}
}
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
int ans = 0;
for (auto v: val) {
int sum = 0;
for (int i = 1; i < kN; ++ i) vis[i] = 0;
for (int i = 1; i <= n; ++ i) {
int flag = 1;
for (int j = 1; j <= sz[i]; ++ j) {
if (s[i][j] == v) {
flag = 0;
break;
}
}
if (!flag) continue;
for (int j = 1; j <= sz[i]; ++ j) vis[s[i][j]] = 1;
}
for (int i = 1; i < kN; ++ i) sum += vis[i];
ans = std::max(ans, sum);
}
printf("%d\n", ans);
}
return 0;
}
C
呃呃呃，我是傻逼。
显然最理想的情况是数列中所有正数位于奇数位置，直接倒着取数即可；再考虑一个没那么理想但是也挺理想的情况，数列中所有正数均位于偶数位置，这样只需要拿掉他们之前的某个数，就转化成了最理想情况。
然后经过大力手玩加猜想发现固定了取的数中最靠前的位置后，总存在一种取数方案使得可以把它之后的所有正数全部取走。正确性可以感性理解，可以先对后面进行一顿操作，再把这个最靠前的位置取走，相当于改变了后面的奇偶性，再进行一顿操作，使得所有正数均可以位于奇位置上。
于是维护后缀正数和，再枚举取的数中最靠前的位置即可。对后面的位置进行操作不会影响最靠前的位置的奇偶性，该位置对答案的贡献是固定的。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN];
LL suf[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();
for (int i = 1; i <= n; ++ i) a[i] = read();
suf[n + 1] = 0;
for (int i = n; i; -- i) suf[i] = suf[i + 1] + std::max(a[i], 0);
LL ans = 0;
for (int i = 1; i <= n; ++ i) {
ans = std::max(ans, suf[i + 1] + ((i & 1) ? a[i] : 0));
}
printf("%lld\n", ans);
}
return 0;
}
D
典中典之拆位，再加典中典之换根 DP。
发现进行操作的贡献是 \(\operatorname{size}\times c\)，影响是子树中所有点 \(\oplus c\)，于是考虑拆位，考虑 \(c = 2^k\) 的互不影响的若干次操作，再将所有位的答案累计即可。
拆位后每个结点的权值 \(b_i\) 只有 0/1 两种情况这太典中典之树形 DP 了。先考虑以 1 为根的情况，于是设 \(f_{i, 0/1}\) 表示将以 \(u\) 为根的子树全部置为 0/1 的最小代价，若当前拆出的是第 \(k\) 位则有：
\[\begin{aligned}
f_{u, b_u} &= \sum_{v \in \operatorname{son}(u)} f_{v, b_u}\\
f_{u, \overline{b_u}} &= f_{u, b_u} + \operatorname{size}_u\times 2^k
\end{aligned}\]
发现恒有 \(f_{u, b_u} < f_{u, \overline{b_u}}\)，则对于第 \(k\) 位以 1 为根的答案即 \(f_{1, b_u}\)。
再考虑换根，考虑从父亲 \(u\) 移向儿子 \(v\) 对所有节点的 \(f\) 影响，发现对于此题仅会影响 \(u, v\) 的 \(f\)。记 \(g_{u, 0/1}\) 表示以 \(u\) 为根时，将整棵树全部置为 0/1 的最小代价，则有：
\[\begin{aligned}
f'_{u, b_{u}} &= g_{u, b_u} - f_{v, b_u}\\
f'_{u, \overline{b_u}} &= f'_{u, b_{u}} + (n - \operatorname{size}_v)\times 2^k\\
g_{v, b_v} &= f'_{u, b_v} + f_{v, b_v}\\
g_{v, \overline{b_v}} &= g_{v, b_v} + n\times 2^k
\end{aligned}\]
注意换根的写法，\(f'_u\) 仅在计算 \(g_v\) 时有效，并不会真正修改 \(f\) 数组的值。则对于第 \(k\) 位，对答案 \(m_u\) 的贡献即为 \(g_{u, b_u}\)，求和即可。
总时间复杂度 \(O(n\log w)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kM = kN << 1;
//=============================================================
int n, edgenum, head[kN], v[kM], ne[kM];
int sz[kN];
LL a[kN], b[kN], f[kN][2], g[kN][2], ans[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;
}
void Init() {
n = read();
edgenum = 0;
for (int i = 1; i <= n; ++ i) {
head[i] = sz[i] = 0;
ans[i] = 0;
}
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i < n; ++ i) {
int u_ = read(), v_ = read();
Add(u_, v_), Add(v_, u_);
}
}
void Dfs1(int u_, int fa_, LL val_) {
sz[u_] = 1;
f[u_][0] = f[u_][1] = g[u_][0] = g[u_][1] = 0;
int type = (b[u_] > 0);
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
Dfs1(v_, u_, val_);
f[u_][type] += f[v_][type];
f[u_][!type] += f[v_][type];
sz[u_] += sz[v_];
}
f[u_][!type] += 1ll * sz[u_] * val_;
}
void Dfs2(int u_, int fa_, LL val_) {
ans[u_] += g[u_][b[u_] > 0];
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i];
if (v_ == fa_) continue;
int tu = (b[u_] > 0), tv = (b[v_] > 0);
LL fu[2] = {};
fu[tu] = g[u_][tu] - f[v_][tu];
fu[!tu] = fu[tu] + 1ll * (n - sz[v_]) * val_;
g[v_][tv] = f[v_][tv] + fu[tv];
g[v_][!tv] = g[v_][tv] + 1ll * n * val_;
Dfs2(v_, u_, val_);
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
for (int i = 0; i < 20; ++ i) {
for (int j = 1; j <= n; ++ j) b[j] = a[j] & (1 << i);
Dfs1(1, 0, (1ll << i));
g[1][0] = f[1][0], g[1][1] = f[1][1];
Dfs2(1, 0, (1ll << i));
}
for (int i = 1; i <= n; ++ i) printf("%lld ", ans[i]);
printf("\n");
}
return 0;
}
E1
暴力的构造。
发现先对 1 再对 \(n\) 操作可以维持形态。于是显然的想法是先分别求出复原 \(p, q\) 的方案，猜测方案步数奇偶性相同则有解，用上述操作补全步数之差即可。
又发现对于已复原的且 \(n\) 为奇数的排列，进行 \(n\) 次位置 1 的操作后可以维持形态并改变复原方案的奇偶性，于是修正上面的判无解条件，大胆猜测当且仅当 \(n,m\) 均为偶数且步数奇偶性不同时无解。
然后考虑如何复原 \(p\)，一个想法是考虑每次将 \(i+1\) 接到 \(i\) 后面，并使 \(1\sim i\) 为一个连续的子序列。手玩一下发现可以先对 \(\operatorname{pos}_{i}+1\) 操作使得保持 \(1\sim i\) 为连续子序列下将 \(i\) 移动到末尾，再对 \(\operatorname{pos}_{i+1}\) 操作即可将 \(i+1\) 接到 \(i\) 后面。
按照上述方案进行操作至多进行 \(O(2\times n)\) 步，数据范围不大可以直接暴力进行。再加上改变奇偶性的 \(n\) 步，则至多进行 \(O(3\times n)=7500\le 10000\) 步。
总复杂度 \(O(n^2 + m^2)\) 级别。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2510;
//=============================================================
int n, m, a[kN], b[kN], temp[kN];
std::vector <int> ans1, ans2;
//=============================================================
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 Modifya(int pos_) {
int len = 0;
for (int i = pos_ + 1; i <= n; ++ i) temp[++ len] = a[i];
temp[++ len] = a[pos_];
for (int i = 1; i < pos_; ++ i) temp[++ len] = a[i];
for (int i = 1; i <= n; ++ i) a[i] = temp[i];
}
void Modifyb(int pos_) {
int len = 0;
for (int i = pos_ + 1; i <= m; ++ i) temp[++ len] = b[i];
temp[++ len] = b[pos_];
for (int i = 1; i < pos_; ++ i) temp[++ len] = b[i];
for (int i = 1; i <= m; ++ i) b[i] = temp[i];
}
void Calc() {
int p;
for (int i = 1; i < n; ++ i) {
for (p = 1; a[p] != i; ++ p);
if (p != n) ans1.push_back(p + 1), Modifya(p + 1);
for (p = 1; a[p] != i + 1; ++ p);
ans1.push_back(p), Modifya(p);
}
for (int i = 1; i < m; ++ i) {
for (p = 1; b[p] != i; ++ p);
if (p != m) ans2.push_back(p + 1), Modifyb(p + 1);
for (p = 1; b[p] != i + 1; ++ p);
ans2.push_back(p), Modifyb(p);
}
}
void Print() {
printf("%d\n", std::max(ans1.size(), ans2.size()));
if (ans1.size() <= ans2.size()) {
int i = 0;
for (int sz = ans1.size(); i < sz; ++ i) {
printf("%d %d\n", ans1[i], ans2[i]);
}
for (int j = 0, sz = ans2.size(); i < sz; ++ i, ++ j) {
printf("%d %d\n", (j & 1) ? n : 1, ans2[i]);
}
} else {
int i = 0;
for (int sz = ans2.size(); i < sz; ++ i) {
printf("%d %d\n", ans1[i], ans2[i]);
}
for (int j = 0, sz = ans1.size(); i < sz; ++ i, ++ j) {
printf("%d %d\n", ans1[i], (j & 1) ? m : 1);
}
}
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
n = read(), m = read();
for (int i = 1; i <= n; ++ i) a[i] = read();
for (int i = 1; i <= m; ++ i) b[i] = read();
Calc();
// printf("--%d %d\n", ans1.size(), ans2.size());
if (ans1.size() % 2 == ans2.size() % 2) {
Print();
return 0;
}
if (n % 2 == 1) {
for (int i = 1; i <= n; ++ i) ans1.push_back(1);
Print();
return 0;
}
if (m % 2 == 1) {
for (int i = 1; i <= m; ++ i) ans2.push_back(1);
Print();
return 0;
}
printf("-1\n");
return 0;
}
E2
牛逼构造，懒了，跑路！
写在最后
学到了什么：
- B：考虑什么不在集合中。
- C：尝试通过理想情况进行拓展（？
- D：复习了换根 DP。