AtCoder Grand Contest 001 - AtCoder.
CDEF 看了题解才会。
2025.1.17 打比赛、补题。
2025.1.18 写题解。
A
简单贪心，排序后相邻的放一起。
B
有点吓人，但是画图手玩一下就可以看出，除了开头和结尾，每一轮是在走一个平行四边形，于是递归。类似辗转相除法求 \(\gcd\) 递归算一下（不是求 \(\gcd\)）即可，注意开头结尾的特殊处理。时间复杂度和辗转相除法求 \(\gcd\) 相同（？）。
总结：画图；联想学过的东西（此题中是分析时间复杂度）。
此处原本有一张图。
更左边的是 C 的草稿。
C
树的直径，我现在很不会。
做法 \(1\)：老老实实去删，贪心。（但贪心策略我还不清楚，洛谷题解好像有，但我不懂正确性）
做法 \(2\)：考虑最终结构，[直径有性质：所有直径中点（或边）相同]（？），于是枚举直径中点（或边），DFS 去在范围内延伸到尽量多的点。是点还是边看 \(k\)（最终直径长度）的奇偶。最终直径不一定是 \(k\)，有可能小于 \(k\)（\(k\) 大于原本的直径），但没有关系（？）。（要用这个性质吗？）
总结（做法 \(2\)）：只关心进行一些操作之后最终的样子，可能可以直接从最终的样子入手。
D
总结：先抓满足限制的必要条件，从必要条件入手来构造，如果一定能构造出来，这个必要条件就也是充分条件（或者也可能在构造的过程中探索到充分条件（？）），于是可以判无解。另外也要多找性质。勤画图。把情况处理（包括想）全。关键是通过必要条件、性质来限制自己构造的方向。
神仙构造题，思路自然流畅。（个人认为；但是自己看了很多题解才懂。）
一定要自己画图，勤画图。另外有些时候画图也需要一定技巧，要尽量画得易于思考、尽可能画出各种情况（尽量富于多样性）。
首先读懂题意，发现没什么直接的思路。
注意到要求任何满足 \(a,b\) 限制的字符串所有字符都相同，那么就是说要求 \(a,b\) 的回文关系（没有其他促使所有字符相同的因素，仅仅靠回文关系）使得所有字符相同。
那么我们转化题意，变成按照回文关系在相同的字符之间连无向边，要求整个图连通。
还是没什么直接的思路，于是探索图的形态。
- 一个长度为 \(x\) 的奇回文串会连 \(\frac { x - 1 } 2\) 条边，不会给回文中心连边。
- 一个长度为 \(x\) 的偶回文串会连 \(\frac x 2\) 条边。
我们要使 \(n\) 个点连通，就至少需要 \(n - 1\) 条边。而所有回文串的长度之和为 \(2n\)，全是偶回文的话会连 \(n\) 条边，每有一个变成奇回文就会少 \(\frac 1 2\) 条边。于是所有回文段（\(a\) 中的和 \(b\) 中的）中，奇回文段的个数不能超过 \(2\)。超过 \(2\) 就判无解。
仅仅知道这一条信息还是难以构造（个人认为）。但是我们注意到 \(a\) 中回文段不相交，\(b\) 中回文段也不相交，那么一个点的度数最多是 \(2\)，即 \(a\) 中的回文段给它一条边，\(b\) 中的回文段也给它一条边；而对于奇回文段的回文中心，它们的度数是 \(1\)，因为要连通至少要给它一条边（偶回文），而奇回文不会给它边。
现在先思考有两段奇回文时的图的结构。
知道了这样的度数关系，我们发现两段奇回文的图一定是一条链，且链的开头和结尾分别是两个奇回文串的回文中心。
那考虑怎么把图串起来。看到回文的连边想到错位，我们尝试画一下：
- 偶回文段 \([x,y]\) 和偶回文段 \([x+1,y+1]\) 可以形成一段链，端头分别是 \(x\) 和 \(y + 1\)（只看这一部分的话它们的度数都是 \(1\)，也就是说它们只被 \(a\) 中的回文段或 \(b\) 中的回文段覆盖，还可以被覆盖一次）。
- 奇回文段 \([x,y]\) 和偶回文段 \([x,y+1]\) 可以形成一段链，端头分别是这个奇回文段的中心和 \(y + 1\)，但奇回文段的中心不能再被覆盖了，\(y+1\) 还能再被覆盖。
- 奇回文段 \([x,y]\) 和偶回文段 \([x+1,y]\) 可以形成一段链，端头分别是这个奇回文段的中心和 \(x\)，但奇回文段的中心不能再被覆盖了，\(x\) 还能再被覆盖。（与第二种 有点 对称）
我们在这样的过程中受到启发，把还能再被覆盖的点（一些端点；不是端点的显然度数已经满了，也就是已经被覆盖两次了）作为“插头”。那么第一种构造可以放在中间来连接，第二种构造可以放在开头，第三种构造可以放在结尾，它们通过插头互相连接（插头接插头）。
现在有了基础的想法，画一画特殊情况，再想一下扩展：
- \(a\) 只有两段时，直接第二种接第三种是否可行？可行。
- \(a\) 只有一段时怎么办？
- 如果 \(n=1\)，就直接让 \(b\) 中唯一的一个元素为 \(1\)。
- 否则让 \(b\) 中的两个元素依次是 \(1, n-1\)（相当于上面的第三种结构，\(a\) 中奇数配 \(b\) 中偶数或 \(a\) 中偶数配 \(b\) 中奇数）。
- \(a\) 中奇数不足 \(2\) 个怎么办？在 \(b\) 中构造奇数。
考虑这样拼接是否满足题目中 \(a\) 中元素加起来等于 \(n\) 且 \(b\) 中元素加起来也等于 \(n\) 的限制。
我们直接按照这种拼接构造，发现这就相当于把 \(A\) 的两个奇数丢到一头一尾得到 \(a\)，而 \(b\) 是 \(a\) 复制一遍后把开头元素 \(+1\)，结尾元素 \(-1\)（减成 \(0\) 就不要了，这个要特判，容易画图验证这样也能形成上面的第三种结构）。这样很巧妙，有两个好处：
- \(b\) 首尾和 \(a\) 首尾的奇偶性不同，而 \(a,b\) 非首尾的元素都是偶数，就保证 \(a\) 和 \(b\) 总共的奇数个数不超过 \(2\)。
- 恰好把每个部分都正确地错位了。
我们注意到这样做可以满足 \(a\) 只有两段和 \(a\) 中奇数不足 \(2\) 个的特殊情况，但满足不了 \(a\) 只有一段的特殊情况。于是 \(a\) 只有一段的特判即可。
发现这样就做完了，\(a\) 中奇数个数 \(\leq 2\) 原本是有合法构造的必要条件，但现在我们也说明了它是充分条件。
流程没想清楚的话可以看代码实现。
想清楚这种题好爽啊。
画的图（此题）：蚊香（在网上发现的比喻）。
这里的这种构造是我从这里学的：题解 AT1982 【Arrays and Palindrome】 - 洛谷专栏。%%%
#include <bits/stdc++.h>
#define gc getchar
#define pc putchar
using namespace std;
namespace FastIO{
int rd()
{
int x = 0, f = 1; char c = gc();
while(c < '0' || c > '9') { if(c == '-') f = (- 1); c = gc(); }
while(c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
return (x * f);
}
void wt(int x)
{
if(x < 0) { x = (- x); pc('-'); }
if(x > 9) wt(x / 10);
pc(x % 10 + '0');
}
}
using namespace FastIO;
const int M = 100;
int a[M + 1], na[M + 1];
vector < int > b;
void Solve()
{
int n = rd(), m = rd();
// vector < int > a(m + 1), na(m + 1);
int cnt = 0;
vector < int > od(2);
for(int i = 1; i <= m; ++ i){
a[i] = rd();
if(cnt <= 1) if(a[i] & 1) od[cnt] = a[i]; // 要写 if(cnt <= 1) // 这就不能把 cnt ++ 写在里面了 // 是 od[cnt]，不是 od[cnt + 1]
cnt += (a[i] & 1); //
}
if(cnt > 2){ // 是 > 2，不是 >= 2
// puts("Impossible"); // ?
printf("Impossible"); // ?
return ;
}
int tot = 0;
if(od[0]) na[++ tot] = od[0];
for(int i = 1; i <= m; ++ i) if((a[i] & 1) ^ 1) na[++ tot] = a[i]; // m, not n
if(od[1]) na[++ tot] = od[1];
for(int i = 1; i <= m; ++ i) a[i] = na[i];
// vector < int > b;
if(m == 1){
b.emplace_back(1);
if(a[1] - 1 > 0) b.emplace_back(a[1] - 1); // 也要特判（特判就是这里的 if）
}else{
b.emplace_back(a[1] + 1);
for(int i = 2; i <= m - 1; ++ i) b.emplace_back(a[i]); // m - 1, not m
if(a[m] - 1 > 0) b.emplace_back(a[m] - 1); // 要特判（特判就是这里的 if）
}
for(int i = 1; i <= m; ++ i) { wt(a[i]); pc(' '); }
pc('\n'); wt(((int)b.size())); pc('\n');
for(int x : b) { wt(x); pc(' '); }
// pc('\n'); // ?
}
int main()
{
Solve();
return 0;
}
// 看了大量题解才懂，感谢大佬们
// 不知道是不是 https://www.luogu.com.cn/discuss/758556
E
好题（个人认为）。
组合意义做法：列式子，显然是格路计数的组合数那个式子，发现 \(A_i,B_i\) 很小，尝试找出每个组合数的出现次数，但并不容易处理。于是将计就计用格路计数的组合意义，把 \((0,0)\to(a_i+a_j, b_i+b_j)\) 的路径转化成 \((-a_i,-b_i) \to (a_j,b_j)\) 的路径，这样就把与 \(i\) 相关的和与 \(j\) 相关的分开了，我们直接在每个起点 \((-a_i,-b_i)\) 处赋初值，跑格路计数的 DP，这样就把所有路径都一起计算了。但是还要减掉 \((-a_i,-b_i)\to(a_j,b_j)\) 的路径数（这也可 DP 求出）再除以 \(2\)。
我之前想到过从 DP 到格路计数的组合数的题，但是事实上反过来也是可以的。
总结：式子和组合意义的转化；从图像的角度思考；格路计数的平移；把与式子中两个变量有关的东西分别放到两个地方（本题中是起点和终点）；DP 可以一次性统计多种信息，比如格路计数的 DP 和子集和 DP；组合数和 DP 各自的优劣和相互转化。
还有代数推导做法，但我还不会。
组合意义和代数推导是这两个意思吧？
F
定义域和值域交换（好像叫逆排列），变成更容易思考的形式。现在是相邻交换，但要求值的差（不是绝对值）\(\geq K\)。可以发现排列字典序最小和逆排列字典序最小是对应的（？）。
要使字典序最小，直接想不太好想，于是考虑增量法，在结尾添加元素。为了使字典序最小，我们尝试交换逆序对，但是是邻项交换，没法直接换过来。一个个添加元素，使得前面的已经达到字典序最小了。那么我们直接把新加的元素尽量往左换（只要更优且满足限制的话；而此题中满足限制就显然更优（实际上如果不是应该也可以用同样的做法）），而原来的元素之间的顺序不改变。
那么就可以直接用 FHQ-Treap 维护这个不断在末尾添加再移动的过程了。
发现这个过程类似排序，可以用归并排序实现，归并排序途中记录。时间复杂度 \(O(n \log n)\)。
总结：这种定义域和值域都有限制的，可以考虑交换定义域和值域；增量来思考；抓住和排序的相似性，用归并排序处理。
标签：AtCoder,元素,Contest,int,奇数,构造,001,DP,回文 From： https://www.cnblogs.com/huangkxQwQ/p/18681889