Bronze
T1 Cow College
暴力扫一遍，更新最大值。
提交记录：Submission - Luogu
T2 Feeding the Cows
贪心放，维护一个能分别被 \(\texttt{G}\) 和 \(\texttt{H}\) 覆盖到的最远位置，如果当前位置 \(i\) 覆盖不到就在 \(i+k\) 放一个新的。由于 \(i\) 各不相同，这样放置除了可能在 \(n\) 位置重合其余都不会。同时除 \(k=0\) 外其余方案一定不会两个相邻为放相同元素，所以在 \(n\) 重复就 \(n-1,n\) 各放一个即可。
提交记录：Submission - Luogu
T3 Reverse Engineering
其实是有 \(2n\) 个关键字（把 \(01\) 拆开），按照某顺序依次判断该信息是否具有这个关键字并返回值，问是否存在合法顺序。
注意到当前可以判断某个关键字当且仅当剩下的所有具有这一关键字的信息返回值都相同，且如果现在同时有多个关键字可以删去，删去顺序不影响，就可以一起删。于是判断能不能删完所有信息即可。
提交记录：Submission - Luogu
Silver
T1 Barn Tree
考虑先求出每棵子树应得的总数和现有的数量，那么可以得到到父亲的边是什么操作，输出顺序可以先走向父亲输入的边再走从父亲输入的边。
提交记录：Submission - Luogu
T2 Circular Barn
不是很难的博弈论题。
每个 \(a_i\) 分别考虑，我们需要判断出胜败双方，并求出在最优策略下结束的轮次 \(f_i\)。
根据定义 \(a_i=1\) 或 \(a_i\in \mathbf{P}\) 时先手必胜，轮次 \(f_i=1\)。
尝试找到一个显然的必败态 \(k\ge 4\)，要求 \(k\) 被减去 \(1\) 或质数后一定是 \(1\) 或质数。
\(k\) 一定不是奇数，这样减去 \(1\) 是偶数，\(k\) 一定不是大于 \(4\) 的偶数，这样减去 \(2\) 是偶数。
因此必败态 \(k=4\)。考虑对这个结论关于所有非质数归纳，假设 \(a_i=4n\) 均必败，其余均必胜。对于 \(a_i=4(n+1)\)，一定只能移动到 \(4\nmid a_i\) 的位置，那么必败，对于 \(4(n+1)<a_i<4(n+2)\)，可以移动到 \(4(n+1)\)，那么必胜。
之后考虑如何求 \(f_i\)，实际上这是关于 \(a_i\) 的，不妨设 \(g_k\) 表示 \(a_i=k\) 时操作次数（不是轮次），暴力计算复杂度 \(O(w^2)\)。
可以归纳发现一些性质，假设目前所有 \(g_{4n}\) 单调增加，发现 \(g_{4n+k}\) 一定由某个 \(g_{4m}+1\) 转移而来，因此所有 \(g_{4n+k}\) 都是不会大于 \(g_{4n}+1\) 的；对于所有 \(g_{4n+2}\)，必胜方能且只能操作到 \(g_{4n}+1\)；而对于所有 \(g_{4n}\) 必败方希望操作次数尽量多，因此会选择一定不劣的 \(g_{4n-2}+1=g_{4(n-1)}+2\)（此时 \(g_{4(n-1)}+1\) 一定是所有 \(g_{4m+k}\) 中的最大值），换言之有：
\[g_{4n}=2n,g_{4n+2}=2n+1 \]这样可以归纳得到 \(g_{4n}\) 是递增的，那么 \(g_{4n+1}\) 和 \(g_{4n+3}\) 就会选最大的与 \(1\) 或 \(3\) 同余的质数或 \(1\) 转移，因此 \(g_k\) 可以预处理出来，而 \(f_i\) 关于 \(g_{a_i}\) 求出即可。
时间复杂度 \(O(n+w)\)。
提交记录：Submission - Luogu
T3 Range Reconstruction
简单构造。
设 \(f(l,r)\) 为区间 \([l,r]\) 中最大值减最小值。
考虑维护差分数组 \(a\)，对于每个 \(f(l,r)=0\) 的极大 \([l,r]\) 看作一体，那么现在相邻的位置一定不相等。
考虑比较 \(f(i-2,i-1)+f(i-1,i)\) 与 \(f(i-2,i)\)，如果相等说明单调，反之说明单调性改变。这样容易根据 \(a_{i-1}\) 的正负得到 \(a_i\) 的正负，绝对值就是 \(f(i-1,i)\)。
求出原数组后，如果有超出边界的，统一加或减即可。
提交记录：Submission - Luogu
标签：Submission,关键字,乱写,Luogu,质数,4n,必败,DEC,杂题 From： https://www.cnblogs.com/SoyTony/p/Problems_in_USACO_2022_DEC.html