一句话题解
给出链接、标签和一句话题解。
https://codeforces.com/contest/2101/problem/B
逆序对 奇数位只会被交换到奇数位，偶数位类似。奇偶分开考虑，如果奇数列和偶数列的逆序对个数相同（模 \(2\) 意义下），则两者交换需求都可以满足，两数列必定各自有序；否则，有一个数列并非有序（其中一个序列无法排好最后两个数）。https://codeforces.com/contest/2106/problem/E
贪心 对于一个二分查找，在找到 \(k\) 之前，一定有一些数大于 \(k\)，一些数小于 \(k\)，大数、小数应当各得其所。设有 \(p\) 个大数位置错误，\(q\) 个小数位置错误，不妨设 \(p\ge q\)。\(q\) 个错误大数可以与小数交换，剩余 \(p-q\) 个只能请外援，即答案为 \(2\times\max(p,q)\)。https://codeforces.com/contest/2106/problem/F
思维题 对于 0-墙，其连通块形式为梯形；另外，只有宽度为 \(1\) 的 1-墙 可以被“穿透”，形成大连通块。计算即可。https://codeforces.com/contest/2109/problem/D
最短路 奇偶性 贪心 题目要求是否恰好走特定步数走到某点。假设到某点的最短距离为奇数，由于给的是无向图，可以来回走一条边，所以比此距离大的奇数步数都可以恰好走到。所以，求原图的奇偶最短路（奇数点更新偶数点，反之亦然），并算出题目所给集合子集和的最大奇数/最大偶数即可。https://codeforces.com/contest/2111/problem/E
毒瘤题 >表示变为。记录b>ac>ac>b的数量，并且记录合法的c>b>ab>c>a数量（对每个c>b查找后缀b>a数量，b>c>a同理）。然后直接暴力循环字符串贪心能换就换即可（注意，对于c>a，由于c>b操作会被用到，优先顺序为c>ac>b>ab>c>a）。
https://codeforces.com/contest/2117/problem/F
思维题 首先，不能有三个及以上的叶节点。一个叶节点可以随便填，\(2^n\)。两个叶节点的情况，考虑分成root->lcalca->leaf1lca->leaf2三条。第一条随便填。第二、三条，两个叶节点只能 12 或者 21，再往上只能全 2，直到一条填满（如果长的填 1，则多填一个2）然后随便填。https://codeforces.com/contest/2120/problem/D
抽屉原理 因为字典序，所以先考虑 \(n\) 最大，抽屉原理，\(n=((a-1)\times k+1)\) 个数字就能保证有一个数字出现 \(a\) 次，然后考虑竖着的，每列会给出现了 \(a\) 次的那个数字的这种排列方式的出现数量 +1，当这种排列方式出现 \(b\) 次就寄了。注意，贪心得知如果一个数字出现 \(a+1\) 次或者更多，一列会对两个或者更多的排列方式 +1，不是最优情况。所以仍然根据抽屉原理，答案为 \(C_n^a \times k \times (b - 1) + 1\)。https://codeforces.com/contest/2129/problem/B
逆序对 贪心 注意到镜像之后这个数一定大于等于所有的原数，且小数镜像成为大数。所以从数字 \(1\) 到 \(n\) 考虑是否镜像，以避免镜像后对以后的决策造成影响。只要镜像使得逆序对个数减少，就一定选择镜像。https://codeforces.com/contest/2132/problem/E
贪心 这个题非常像归并排序的归并过程。对两个人的卡牌从大到小排序，并求出前 \(i\) 张牌中分别包含有几张队员的牌。如果前 \(z\) 张牌有一个队员超出限制，只能用另一个队员的牌补足。https://codeforces.com/contest/2124/problem/D
思维题 显然前 \(k-1\) 小的数不可能被删掉，进而想到其他的数都可以被删掉，且比不删好。将数分为三类：\(<k\)，不可能被删掉；\(=k\)，部分被删掉；\(>k\)，全部删掉。第一类数组成骨架，第二类数组成表皮。骨架必须是回文；在此基础上，骨架两端表皮长度应相等，内部应对称。双指针由骨架端点向内扫，遇到一端表皮必须删，遇到两端表皮不用删。
https://codeforces.com/contest/2127/problem/D
计数题 树的直径 显然原图必须是一棵树，且除了直径上的点（不包括叶子），其他点度数必须均为 \(1\)。对于每个直径上的点（不包括叶子），其叶子都可以任意排列；另外，最终二分图可以跨河翻转，如果直径上的点（不包括叶子） \(\ge2\) 还可以不跨河翻转。