【题解】Codeforces Round #770 (Div. 2)
rk1000，半小时ABC，D 先是想了半天，然后想歪了一个做法，写出来发现一处特判有问题，改不动，寄了
这种题不太会做啊
B
考虑奇偶性/最后一位，注意到两种操作对于最后一位的影响是相同的，而 x 和 x+3 的奇偶性不同
D
题意：
有 \(n (n\geq 4)\) 个非负整数 \(a_n\)，其中有且仅有一个 \(0\)；给 \(2n-2\) 次询问机会，每次询问三个 互不相同 的下标 \((i, j, k)\)，返回 \(\max \lbrace a_i, a_j, a_k\rbrace - \min \lbrace a_i, a_j, a_k\rbrace\)。询问结束后，回答两个下标 \((x, y)\)，需要满足 \(a_x=0\) 或 \(a_y=0\)。
考虑最小的数据规模—— n=4 时怎么做
不妨假设大小关系：\(0=a
\(a:d-b\)
\(b:d\)
\(c:d\)
\(d:c\)
找特征
你可以试试排除法
显然返回值最大的两个是不可能为 0 的，这对于不含 0 的四个数字当然也适用
所以可以通过对 4 个位置的 4 次询问排除掉 2 个数字
就做完了
btw，当时的想法：
如果我找到了最大的数字的位置 p，那么 ?(p, x, y) 最小的 (x, y) 就是答案
怎么找到这个位置？固定位置 1, 2，询问 ?(1, 2, i)，由单调性注意到此时最大的那个位置 p，a[p] 要么是 0，要么是最大数字
假设 a[p] 是最大的数字，接下来我们升序询问 ?(p, i, i-1)，找到第一次出现最小数字的位置 q，a[p] 和 a[q] 肯定有一个是 0，好像恰好 2n-2 次！
有问题吗？
有。特殊情况是，恰好 a[1] 和 a[2] 就是 0 和最大的数字，此时任意的询问 ?(1, 2, i) 都会得到相同的数字，上述讨论无效
但是是可以做的，在评论区看到类似的做法
E
这种选择问题，能考虑图论吗？（用边来刻画选择）
网络流呢？
我们可以很容易想到一个二分图最大流模型：左边是 1 到 m 表示每个数组，右边是数字，对于一个数组 i 里的一个数字 a，连一条 i 到 a 容量 1 的边，令流过表示选择到 L；从源点到 i 连一条容量 n[i]/2 的边，从 a 到汇点连一条容量为 count[a]/2 的边，然后跑最大流
但是它TLE了。我们找一个更优的做法
回到刚刚建的模型，我们保留二分图部分，我们定义从左边走到右边意味着把这个数选为 L，那么我们还需要为选的那个 数 选一个 数组 使之设为 R，同样我们又需要为选的这个 数组 选一个 数 使之设为 L...
我们设定从右边走到左边表示把这个数选为 R
那么答案就是一个有向的欧拉回路
存在欧拉回路的等价条件是，所有数组的长度都为偶数，所有数字的出现次数都为偶数，这是显然需要的
求欧拉回路的代码很简单，见代码，注意几个点：
- 边是无向的，但是又需要存正反边，可以用 x 和 x^1 来表示正反边，防止重复走
- 走过的边不再走，可以用 cur[x] 代替 fst[x]，不过和当前弧优化的那个写法不一样，看代码
- 对于所有的点，都要作为 dfs 的起点来一遍！
- 如果需要输出欧拉回路，倒过来存边即可
#include
#include
#include
#include
using namespace std;
const int MAXN = 2000006;
const int MAXE = 2000006;
int M, N[MAXN], fst[MAXN], cur[MAXN], tote, tot; bool vise[MAXN];
int deg[MAXN];
struct edge {
int v, pre;
} e[MAXE];
void adde(int a, int b, int k)
{
// printf("%d -> %d (%d)\n", a, b, k);
e[k].v = b, e[k].pre = fst[a], fst[a] = k;
}
struct node {
int id, p, a, ide; bool ch;
} P[MAXN];
int cmp(node x, node y) { return x.a < y.a; }
int cmp1(node x, node y) { return x.id==y.id ? x.p< y.p : x.id< y.id; }
void dfs(int x)
{
// printf("[%d]\n", x);
for (int o=cur[x]; o!=-1; o=cur[x]) {
// printf("ide = %d\n", o);
cur[x] = e[o].pre;
if (!vise[o] && !vise[o^1]) vise[o] = 1, dfs(e[o].v);
}
}
int main()
{
memset(fst, -1, sizeof(fst));
scanf("%d", &M), tot = 0;
for (int i=1; i<=M; i++) {
scanf("%d", &N[i]);
for (int j=1; j<=N[i]; j++) {
++tot, P[tot].id = i, P[tot].p = j;
scanf("%d", &P[tot].a);
}
}
sort(P+1, P+tot+1, cmp);
int l = 1, r = 0, col = 0;
while (l<=tot) {
col++;
while (r< tot && P[r+1].a==P[l].a) r++;
for (int i=l; i<=r; i++) {
P[i].ide = tote; // choose to L
adde(P[i].id, M+col, tote++);
adde(M+col, P[i].id, tote++);
deg[P[i].id]++, deg[M+col]++;
}
l = r+1;
}
int ok = 1;
for (int i=1; i<=M+col; i++) if (deg[i]&1) ok = 0;
if (!ok) { puts("NO"); return 0; }
for (int i=1; i<=M+col; i++) cur[i] = fst[i];
for (int i=1; i<=M+col; i++) dfs(i);
for (int i=1; i<=tot; i++) P[i].ch = vise[P[i].ide];
sort(P+1, P+tot+1, cmp1);
puts("YES");
for (int i=1; i<=tot; i++) {
printf("%c", P[i].ch ? 'L' : 'R');
if (i< tot && P[i].id!=P[i+1].id) printf("\n");
}
}
F
感觉是个假的 F 题...这题应该放在 D 或 E...
我们希望能简化这个“增加斐波那契数列”操作，就像对付区间加用差分数组一样，所以需要构造一个新数列
目的是当进行一次区间加法时，在新数列上只有少数几个点被修改，大多不变，即加 0
很自然的想到对于数组 a，定义数组 b：b[1] = a[1], b[2] = a[2], b[i] = a[i]-a[i-1]-a[i-2]
就做完了
注意对于 1e9+7 这种模数，最好还是开 longlong，不然比如 a = (a+M-b+M-c)%M 这种写法括号里直接爆 int 有点蠢...