\(\downarrow 2023.09.04\)
CF1952,CF1954
有一个集合，初始状态里面有数字 \(1\)、\(2\)、\(3\)、\(4\)、\(5\)、......、\(10^{1000}\)。
现在给你一个长度为 \(n\) 数组 \(a (1\leq a_i \leq 10^9 )\)，要进行 \(k\) 次操作，每次操作将当前集合中第 \(a_1\) 小、第 \(a_2\) 小、......、第 \(a_n\) 小的数同时移除。
请问 \(k\) 次操作之后，最小的数是多少。
顺难则逆。
考虑如果已知删除后在集合中的位置，可以很简单的找到删除前的位置。
所以已知初始的位置，也可以很简单的找到删除后的位置，\(O(n + k)\) 即可。
void work() {
int n, k; cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
lint i = 1, cur = 1, pre = 0;
while (k--) {
cur += pre;
while (i <= n && a[i] <= cur)
++cur, ++i, ++pre;
}
cout << cur << '\n';
}
对于一个给定的长度为 \(n\) 的数组 \(A\)，定义一个长度为 \(n\) 的数组 \(B\) 是不平衡的当且仅当以下全部条件满足：
\(-n \leq B_{i} \leq n\) 且 \(B_{i} \ne 0\)。即每个数在 \([-n,n]\) 内且不为 \(0\)。
\(\forall i,j \in [1,n], B_{i} + B_{j} \neq 0\)。即数组内不存在一对相反数。
\(\forall i \in [1,n], \sum_{j = 1}^{n} [ \left (B_{i} + B_{j} \right) > 0] = A_{i}\)。即对于任意的 \(i\)，数组中与 \(B_{i}\) 和大于 \(0\) 的数的个数恰好为 \(A_{i}\)。注意：这里需要计算本身。也即 \(i\) 与 \(j\) 可以相等。
请构造长度为 \(n\) 的不平衡序列。
两种方法，其一可以参见 hfjh。
考虑递归的构造序列，如果当前存在 \(A_i = 0\) 或者 \(A_i = n\)，那么其对应所填的数必定为 \(-n\) 或者 \(n\)。
由于相反数不可能同时出现，所以两个不能同时存在，否则无解。
递归的构造即可。
代码链接：https://codeforces.com/contest/1852/problem/B
给定一个长度为 \(n\) 的序列 \(a\) 和正整数 \(k\)。
每次可以选择一个区间 \([l,r]\)，\(\forall i \in [l,r],a_{i} = a_{i} -1\)。
如果 \(a_{i} = 0\)，则将 \(a_{i}\) 变为 \(k\)。
求让序列全部为 \(k\) 的最小操作次数。
多组测试数据，\(1 \leq n \leq 2 \times 10^{5}\)。
先不考虑 \(\bmod k\) 的情况，则构造差分序列 \(d\)，答案即为：
那么考虑每次 \(0 \to k\) 的变换，相当于在原序列上加了 \(k\)，然后求上式。
考虑变成差分序列上加减。也就是有地方 \(+k\)，有地方 \(-k\)，使得上式最小。
所以考虑正负平衡一下即可。
代码链接：https://codeforces.com/contest/1852/submission/221761642
能考场切自是极好。
你有一个 \(2\times n\) 的矩阵，第一行给定（字符串 \(s\)），你需要在第二行的位置填上 \(A\) 或 \(B\)。
你需要构造矩阵的第二行，使得该矩阵相邻的格子不同的个数恰好为 \(k\)。
考虑很 naive 的 DP \(f_{i, 0/1, k}\) 表示填完前 \(i\) 个数，恰好为 \(k\) 是否可行。
打表可以发现，\(k\) 可行的集合至多为两个区间。
证明：每一次转移可以是 \(+1\) 或者 \(+2\)，同时又是前面的两个区间并过来的，所以空缺只会是 \(0/1\) 个。
所以可以压成 \(f_{i, 0/1}\) 即可 /kel
所以可以用
bitset对吧。
最后贪心的构造即可。
Ntarsis 有一个长为 \(n\) 的数组 \(a\)。
定义一个子数组 \(a_l \cdots a_r\) 的权重为：
称数组 \(b\) 与 \(a\) 数组匹配，当且仅当满足：
最大化 \(b\) 的权值和。
\(1 \le n,t \le 10^5\)
考虑几个 hints
对于每一个值，只有最左边和最右边的两个之外的区间可以做出贡献。
将最左和最右记成二元组，如果存在 \(a_i \gt a_j\) 并且 \(i\) 完全被 \(j\) 覆盖，那么 \(j\) 将无法做出任何贡献。
为了不改变权重，我们只可能增加上面所说的 \(j\) 区间。
并且至多会有一个区间会加上某一个数。
有 \(t\)（\(1\le t\le 500\)）组数据，对于每组数据给出一个长度为 \(n\)（\(1\le n\le 20\)）的序列 \(a\)（\(-20\le a_i\le 20\)）。
可以进行 \(k\)（\(0\le k\le 31\)）次操作，每次操作任选一组 \(i,j\)（\(1\le i,j\le n\)），把 \(a_i\leftarrow a_i+a_j\)，最后使得整个序列单调不减。
对于每组数据，第一行输出 \(k\)，之后 \(k\) 行输出执行操作的 \(i,j\)。
超级分讨。
考虑到全部变成正的，或者全部变成负的，然后前缀/后缀和即可，这需要 \(19\) 次。
首先找到绝对值最大的那个数。
如果异号的个数 \(\le 12\)，那么直接加上即可。
反之，则同好的个数 \(\le 7\)，那么找到最大的正数，做 \(5\) 次自加操作，然后加上去即可。
代码链接：Submission #221821611 - Codeforces
有一长度为 \(n\) 的一副牌，每张牌上都有一个数字，设第 \(i\) 张牌上的数字为 \(a_i\)。初始时，你手里只有第一张牌。对于每一张牌，你有两种选择：
如果剩余的牌数量 \(< a_i\)，则将牌摸完，否则继续往下摸 \(a_i\) 张牌。摸牌完成后，这张牌会被丢弃。
获得 \(a_i\) 的分数，并丢弃这张牌。
求你能获得的最大分数。
对于所有数据，保证 \(1 \le n \le 10 ^ 5\)，\(0 \le a_i \le n\)。
考虑如果可以摸完 \(k\) 张牌，由于摸一张牌的代价为 \(1\)，所以得分为：
所以判断哪些地方可以摸到即可。
考虑一个 naive 的 \(O(n^2)\) DP。
有：
于是可以考虑用 bitset 优化。
所以总的复杂度为 \(O(\frac {n^2} w)\)。
代码：https://codeforces.com/contest/1854/submission/221792387
给定大小为 \(n\) 的正整数集合 \(S\)，\(S\) 中的每个数在 \(1\sim m\) 之间。
每一秒进行如下操作：
求 \(S\) 变成空集的期望时间，对 \(10 ^ 9 + 7\) 取模。
\(1\leq n\leq m \leq 500\)，\(1\leq S_1 < S_2 < \cdots < S_n \leq m\)。
\(\downarrow 2023.09.06\)
多组数据。
每组数据给你一个 \(n\) 和两个序列 \(a,b\)。
求有多少个数对 \((i,j)\) 满足 \(1 \le i < j \le n\) 且 \(a_i \times a_j = b_i + b_j\)
对于每一个 \(i\) 看作用 \(a_i \times x - b_i = y\) 这条线来切所有的点。
注意到当 \(a_i\) 很大的时候的简单的，我们只需要用一个桶记录一下 \((x, y)\) 的个数即可，然后可以 \(O(\frac n {a_i})\) 求出。
此时设一个阈值 \(B\)，当 \(a_i \gt B\) 的时候认为是很大的，所以上面的复杂度可以看作 \(O(\frac n B)\)。
问题在于当 \(a_i\) 很小的时候，注意到其实可以 \(O(B)\) 预处理出 \(\forall k \in [1, B]\) \(k \times a_i - b_i\) 的值。
这样就可以 \(O(1)\) 查询了。
两者稍微平衡一下，令 \(B = \sqrt {2n}\) 于是可以 \(O(n \sqrt {n})\) 解决本题。
代码链接： https://codeforces.com/contest/1830/submission/222008847
给定一个数 \(n\) 和 \(k\) 个区间 \(\left[l_i,r_i\right]\in [1,n]\)。
我们定义，对于一个长度为 \(n\) 的，仅由 ( 和 ) 组成的合法括号序列，如果它的每一个区间 \(\left[l_i,r_i\right]\) 内的子串都是合法括号序列，那么这个括号序列是好的。
求好的括号序列的数量，答案对 \(998244353\) 取模。
相交和包含的情况很 naive，重点在于如何处理。
类比 \(2023.09.05\) izumi，采用一个随机化异或的做法。
每一个区间附上一个神秘的权值，差分前缀一次。
如果异或权值相同，意味着需要形成一个合法括号，这预处理卡特兰数即可。
rapper 的讲解见：hfjh
代码链接：https://codeforces.com/contest/1830/submission/222007540
给定一棵 \(n\) 个结点的树，点有点权，点权为 0 或 1。你需要给一种指定点权的方案，使得每一条路径的点权 \(\operatorname{mex}\) 之和最大。
\(n\le 2\times 10^5\)，多组数据。
如果考虑跨越多种数的正贡献，发现很难。于是考虑块内的负贡献。
正难则反！！！！！！！！！！！！！！！！！！！！！！！哦
对于每一个连通块，考虑树形背包。
关键结论是连通块的大小一定不会很大，否则减少的贡献太多了。
有证明在 \(n \le 2e5\) 小不会超过 \(258\)。
代码：https://codeforces.com/contest/1830/submission/222027041
对于一个非升序的排列 \(\{p_i\}\)，定义一次操作为按顺序执行以下步骤：
令 \(p_i\) 为排列中最大的满足 \(p_i\neq i\) 的数。
令 \(p_j\) 为排列中最小的满足 \(i<j\) 的数。
交换 \(p_i\) 和 \(p_j\)
可以证明在排列非升序的前提下总能找到满足条件的 \(i\) 和 \(j\)。
定义一个排列的权值为将其升序排序所需的操作次数，可以证明总能在有限次操作内将其升序排序，注意如果排列本身就是升序的那么其权值为零。
现在给定一个排列和若干次修改操作，求出每次修改后排列的权值，每个修改操作为交换排列中指定的两个数。
注意修改是永久的。
发现排序方式和冒泡排序很像，于是考虑与逆序对之间的关系。
发现每次交换 \((i, j)\) 使得逆序对的个数减少 \(2(j - i) - 1\)。
发现 \(2(j - i)\) 这个东西很好，考虑交换会影响什么改变 \(2(j - i)\)。
发现 \(\sum_{i = 1}^n |p_i - i|\) 符合要求。
发现两者最后都为 \(0\)。
发现操作次数等于 \(\sum_{i = 1}^n |p_i - i|\) 与逆序对个数之差。
于是动态维护逆序对即可。
发现分块很优秀，\(O(n \sqrt{n \log n})\)，虽然是正常的 \(O(n \log^2 n)\) 的树套树的四倍时间……
代码：https://codeforces.com/contest/1830/submission/222012835
给定一个长度为 \(n\) 的序列 \(v\)，其值域为 \([0,m]\)。
现在你需要选择一个 \(x \in [0,m]\)，使其权值最大。定义一个数 \(x\) 的权值为：
请你找到权值最大的数 \(x\)，若有多个，输出最小的那个。
考虑 \(k = 1\) 的特殊情况，发现两个人内部的所有点都造成了 \(\frac 12\) 的贡献。所以告诉我们不需要枚举太多的点，在一些点的周围枚举一下即可。
这可以很合理的外推到所有的 \(k\) 的情况。
给定 \(2^{k+1}\) 个 \([0,4^k)\) 内的整数，请求出任意两个不交非空区间使得其异或和相等，若无解则输出 -1。
抽屉原理抽象题。-1 是不可能的，这一定有解。
于是考虑生日悖论，随机化一些区间即可（逃。
考虑正解，将 \(4^k\) 分成前 \(k\) 位和后 \(k\) 位。
前缀异或和有 \(2^{k + 1} + 1\) 个，而前 \(k\) 位最多有 \(2^k\) 种取值。所以至少会有 \(2^k + 1\) 对前 \(k\) 位相等的前缀。
考虑把这些对找出来，其后 \(k\) 位却也只有 \(2^k\) 种取值，所以至少有两对的后 \(k\) 位的异或值相等。所以就完了。
代码：https://codeforces.com/contest/1835/submission/222050899
给定一张 \(n\) 个点 \(m\) 条边的简单有向图和常数 \(k\)，请求出有多少组 \((x,y)\) 满足 \(1\le x\le y\le n\) 且存在一条 \(x\) 到 \(y\) 和一条 \(y\) 到 \(x\) 的长为 \(k\) 的路径，\(k\ge n^3\)。
发现 \(n^3\)，所以发现可以随便走环凑最小公约数。
于是先缩点，在连通块内考虑。
找出生成树，考虑一个非树边，有结论，\(d | \mathrm{abs}(dep_y - dep_x - 1)\)。
所以可以找出 \(d\)，而合法当 \(k \equiv 0 \pmod d\) 或者 \(d \equiv 0 \pmod 2 \text{ and } k \equiv \frac d2 \pmod d\)。
用桶记录一下即可。
代码：Submission #222076413 - Codeforces
\(\downarrow 2023.09.11\)
给定整数 \(n\) 和一个非负整数序列 \(a\)。
你需要选择整数 \(l,r,k(1\leq l\leq r\leq n;0\leq k)\)，然后将 \(a_l,a_{l+1},\cdots,a_r\) 的值均变为 \(k\)。
判断能否通过恰好一次上述操作使操作后的 \(\mathrm{mex}(a)\) 增加 \(1\)。
如果没有 \(\mathrm{mex}(a) + 1\) 的存在，并且 \(\mathrm{mex}(a) \lt n\)，那么一定存在方案。
否则，需要变换所有的 \(\mathrm{mex}(a) + 1\)，而为了使影响最小，只是恰好包含所有的区间变成 \(\mathrm{mex}(a)\)，重新求一次 \(\mathrm{mex}\) 即可。
代码：https://codeforces.com/contest/1819/submission/222839488
有一张 \(h\times w\) 的纸片，但你并不知道 \(h\) 与 \(w\) 的具体数值。现在对这张纸片进行 \(n-1\) 次裁剪。每次裁剪后会将其中一半收归（即这一半不会再被裁剪），保证纸片不会被旋转。
告诉你最终裁剪后的 \(n\) 张纸片长宽，问初始有多少 \(h\times w\) 的纸片可以裁剪成这 \(n\) 张纸片，输出所有可行的 \((h,w)\)。
发现一张一定是 \(h\) 或者 \(w\)，那么找到 \(\max h\) 和 \(\max w\) 作为两种可能即可。
由于每次减下 \(w, h\) 递减，所以考虑双指针扫一遍即可。
代码：https://codeforces.com/contest/1819/submission/222845297
给定整数 \(n\) 和一棵包含 \(n\) 个节点的树。
记 \(\text{Dist}(x,y)\) 表示树上节点 \(x,y\) 之间最短路径的边数。
你需要判断是否存在一个 \(1\sim n\) 的排列 \(p\)，满足：
存在则输出 Yes 然后输出任意一个满足要求的 \(p\)，不存在则输出 No。
有两种方法，一种是我考场想出来的，分讨比较严重：
先考虑状态 \(f_{x, 0/1}\) 表示走完其子树后是否可以在其子节点或者本身上。
发现叶子节点对于其可行性没有影响，考虑非叶节点的影响。
不难分类讨论，设当且节点为 \(x\)：
所以我们可以愉快的 DP 了，但是考虑父节点为根且根没有其他子树的情况不太好判断，所以任意找一个度数 \(\ge 2\) 的点作为根，那么自然这个条件就无法满足，如果没有找到……这还是能一颗树？
int rt = 1;
void dfs(int x, int p) {
dep[x] = dep[p] + 1;
int son = 0;
vector<int> nonleaf;
for (int y : G[x]) {
if (y == p) continue;
++son;
dfs(y, x);
if (!leaf[y]) nonleaf.push_back(y);
}
if (son == 0)
leaf[x] = 1, f[x][1] = 1;
else if (nonleaf.size() == 0)
f[x][0] = f[x][1] = 1;
else if (nonleaf.size() == 1) {
int y = nonleaf[0];
f[x][0] = f[y][1], f[x][1] = f[y][0];
} else if (x == rt && nonleaf.size() == 2) {
int y = nonleaf[0], z = nonleaf[1];
if ((f[y][0] && f[z][1]) || (f[y][1] && f[z][0])) f[x][1] = true;
}
}
这样，从根开始，依据 DP 转移的过程构造即可。
vector<int> v;
void construct(int x, int t, int p) {
vector<int> nonleaf;
for (int y : G[x]) {
if (y != p && !leaf[y]) nonleaf.push_back(y);
}
#define pushLeaf() { for (int u : G[x]) if (u != p && leaf[u]) v.push_back(u); }
if (nonleaf.size() == 0) {
if (t == 0) v.push_back(x);
for (int y : G[x]) {
if (y != p) v.push_back(y);
} if (t == 1) v.push_back(x);
} else if (nonleaf.size() == 1) {
int y = nonleaf[0];
if (t == 0) {
v.push_back(x);
construct(y, 1, x);
pushLeaf();
} else {
pushLeaf();
construct(y, 0, x);
v.push_back(x);
}
} else if (nonleaf.size() == 2) {
int y = nonleaf[0], z = nonleaf[1];
v.push_back(x);
if (f[y][1] && f[z][0]) {
construct(y, 1, x);
pushLeaf();
construct(z, 0, x);
} else if (f[y][0] && f[z][1]) {
construct(z, 1, x);
pushLeaf();
construct(y, 0, x);
} else assert(nonleaf.size() == 2);
}
}
虽然是说稍微复杂了一点，但是分讨很简单，代码依据分讨就可以直接模拟出来，十分的 naive，这比正解要更 brute force 一点（CF优良传统）。
而对于正解，先找出最长链，那么支链的深度不能超过 \(1\)，否则一定不合法，\(O(n)\) 做即可，只是要扫很多遍而已。
给定 \(n\) 个集合 \(S_i\)，第 \(i\) 个集合的大小为 \(k_i\)，集合元素为 \(1\sim m\) 的正整数。特别地，若 \(k_i = 0\)，则 \(S_i\) 可以是正整数 \(1\sim m\) 的任意可空子集，由你确定。
设 可重集 \(S\)，初始为空。按编号从小到大依次遍历每个集合，往 \(S\) 中加入 \(S_i\) 所有元素。每次加入当前集合的所有元素后，若 \(S\) 包含重复元素，则清空 \(S\)。注意，一个集合内的元素 同时 被加入 \(S\)。
你需要确定 \(k_i = 0\) 的 \(S_i\) 具体包含哪些数，使得最终的 \(|S|\) 最大。求出这个最大值。
\(1\leq T, \sum n, m\leq 2\times 10 ^ 5\)，\(0\leq \sum k_i\leq 2\times 10 ^ 5\)，\(S_i\) 的元素互不相同。
考虑找到可以清空的位置 \(can_i\)，以及每一个 \(i\) 往前最多可以保留到的位置 \(late\)。
每次找到最后一个冲突的位置 \(max\_conflict\) 记为 \(mc\)，于是如果 \(mc \le late\) 那么对于 \(late\) 没有影响，而 \(can_i\) 可行当且仅当 \((late, i]\) 之间存在一个 \(k = 0\)。
否则 \(can_i\) 一定可行，而 \(late\) 需要更新到 \(mc\) 之后第一个 \(can_i\) 为 \(1\) 的点。
于是，就搞定了。
这是一道交互题。
给定一张 \(n\) 个点 \(m\) 条边的无向连通图，无自环，但可能有重边。
图上有一些特殊边，保证任意两个结点通过特殊边连通，你希望求出所有特殊边。
初始所有边都没有被堵住。你可以进行以下三种操作：
你最多进行 \(100m\) 次操作。
\(2\leq n\leq 2000\)，\(n - 1\leq m\leq 2000\)，\(1\leq t\leq 1000\)，\(\sum n, \sum m\leq 2000\)。保证图无自环且连通。
利用其随机化，以及联通的性质。
找到一个特殊的生成树，然后考虑非树边即可。
问题在于如何判断树边，断开，然后两边跑 \(k\) 次，那么错误率为 \((\frac x n \frac {n - x} n)^k\)，在 \(k \to 20\) 的时候就趋近于 \(0\) 了，可以认为完全正确。
于是就做完了。
有 \(n\) 个人观看一场与 VOCALOID 有关的演出，场地里有一行座位，从左到右标号 \(1\) 到 \(m\)，接下来观众将按顺序以如下三种方式中的一种选择座位：
现在知道每个人选择座位的方式，你可以让人们按照任意顺序入场，求最多找到座位的人数。
安排方式只有三种，1/2/3 分别先，依次向左/向右/向两边扩展即可。
给定一棵 \(n\) 个结点的树，现在有 \(k(k\le n)\) 个结点上有人。
一个结点是好的当且仅当这个点到所有人的距离之和最小。
求在这 \(n\) 个点中随机取 \(k\) 个点时，好的结点的期望个数，对 \(10^9+7\) 取模。
发现用点来算很难算，于是考虑用边来算贡献。由于每种情况边会比点数少 \(1\)，所以期望点数等于期望边数 \(+1\)，于是考虑边如何做贡献，两边的点数相等即可。
于是就搞定了：https://codeforces.com/contest/1824/submission/222881710
给定一棵 \(n\) 个节点的树，根节点为 \(1\) ，每个点有一个点权 \(a_i\) ，每次操作可以选择一个点任意修改点权，求最少的操作次数，使得每一条根结点到叶子结点的路径上的异或和都为 \(0\) 。
如果要相等，那么只需要子树所有相等，那么改变只需要改变自己即可。
所以找到子树中最多的那个值，保留即可。
并且启发式合并即可……
代码：https://codeforces.com/contest/1824/submission/222885893
注意 if (maxcnt > 1) 的优化，否则会 TLE。
Feyn 给了你一个长度为 \(n\) 的整数数组 \(a\)，下标由 \(1\) 开始。
用以下方式定义函数 \(g(i,j)\)：
\(q\) 次询问，每次给定 \(l,r,x,y\)，请求出 \(\sum\limits_{i=l}^r\sum\limits_{j=x}^y g(i,j)\) 的值。
需要个可以区间赋值和历史版本求和线段树……不会额。
\(\downarrow 2023.09.18\)
给定长度为 \(n\) 一个序列 \(a\) 以及 \(q\) 次询问，每次询问给出 \(l\) 和 \(r\)，找出序列 \(a\) 在 \([l,r]\) 内最长的几乎递增子序列。
对于几乎递增的定义：如果一个序列中不存在连续的三个数 \(x\)，\(y\)，\(z\)，使得 \(x \ge y \ge \ z\)，则这个序列是几乎递增的。
也就是说每一段递减的都至多取两个。转换一下，减去连续的三个的个数，差分一下即可。
代码：https://codeforces.com/problemset/submission/1817/223787996
定义“鱼图”为满足以下条件的无向图：
现在给定一个简单无向图，问该图中是否有一个子图为“鱼图”。一个无向图的子图即为原图中删去若干个点和若干条边所形成的图。如果存在，还需要构造出其中任意一个满足要求的子图。
合法的点当且仅当 \(D_x \ge 4\) 并且 \(SCC_x \ge 3\)，于是可以 \(O(n)\) 求了。
注意我的写法中，需要回退，防止 \(<><>\) 的这种图找不到环。
代码：https://codeforces.com/problemset/submission/1817/223785932
给定两个次数为 \(d\) 的多项式 \(A, B\) 在 \(0, 1, 2, \dots, d\) 处的点值对 \(10^9+7\) 取模，保证 \(B(x) \equiv A(x+s) \pmod {10^9+7}\)。求 \(s \bmod 10^9+7\)。
考虑差分：
于是可以求出 \(s\) 了。
还有拉格朗日插值求出系数然后求的方法，差不多。
代码：https://codeforces.com/problemset/submission/1817/223798973
有一个长 \(n\) 宽 \(2\) 的矩形游戏机。保证 \(n\) 是奇数。
游戏开始之前，有 \(n - 2\) 个玩具放在第一排中间的 \(n - 2\) 个位置中（两个角除外）。编号从左到右依次为 \(1\) 到 \(n - 2\)。第二行为空，其最左、最右和中心位置是障碍物。你可以控制玩具机向左、向右、向上、向下，分别用字母 \(\texttt L\)、\(\texttt R\)、\(\texttt U\) 和 \(\texttt D\) 表示。
操控时，所有玩具将同时沿相应方向移动，碰到另一个玩具、墙壁或障碍物停止。您的目标是将第 \(k\) 个玩具移动到第一行最左边。给定 \(n\) 和 \(k\)，构造一个最多使用 \(1000000\) 次操作的方案。
认为代码展示了一切：https://codeforces.com/problemset/submission/1817/223803543
有一个非负整数序列 \(\{a_1,a_2,\dots,a_n\}\)。
你可以从序列中取任意两个数，并将它们的平均数放回序列。
序列最后会剩两个数，请求出这两个数的差的绝对值的最大值。
因为答案将会是一个小数，所以请输出答案对 \(10^9+7\) 取模的结果。
呃，推一点点式子，发现如果从断点 \(x\) 到断点 \(y\) 的差距为：
于是可以 \(O(y - x + 1)\) 求解，于是发现可以分治求解。
问题在于如何维护这些加加减减的值。
有一个 trick：Trygub Number，适用于此。
于是可以 \(O(n \log n)\) 求解了。
注意可能需要较快的读入：Submission #223847308 - Codeforces
然而正解，考虑 \(2^i\) 在 \(i \ge 30\) 时便很大了，使得 \(\frac {a_i}{2^i}\) 趋近于 \(0\)，于是可以发现断点只会出现在前/后 \(\log n\) 个不同的数上，于是常数为 \(64\) 的 \(O(n)\) 做法新鲜出炉！
没什么好说的，模拟即可。
代码：https://codeforces.com/problemset/submission/1863/225013381
给定一个 \(1 \sim n\) 的排列 \(q\)，你可以多次进行以下操作：
你需要找到使 \(\forall i \in [1,n]\)，\(p_{i} = i\) 的最小操作次数。
本题有多组测试数据，\(1 \leq T \leq 10^{3}\)，\(1 \leq n,\sum n \leq 10^{5}\)。
记 \(i\) 出现的位置为 \(p_i\)，则答案为 \(\sum_{i = 2}^n [p_i < p_{i - 1}]\)
代码：Submission #225039544 - Codeforces
给定值域在 \([0, n]\) 的一个序列，\(p_i\) 互不相同，定义一次操作为 \(i = 1 \to n, p_i = \mathrm{mex}(P)\)，求 \(k \le 10^9\) 后的序列是什么样子的。
将初始的 \(\mathrm{mex}\) 放在序列开头，则一次操作相当于 \(i = 1 \to n, \mathrm{swap}(p_0, p_i)\)，结果是加入了 \(\mathrm{mex}\) 的序列向右循环了一次。
所以最后就是循环 \(k\) 次，去掉第一个数即可。
代码：https://codeforces.com/problemset/submission/1863/225014759
有一个 \(n \times m\) 的棋盘，上面铺着一些 \(1 \times 2\) 的多米诺骨牌（横竖均有可能），骨牌之间没有重叠。
你需要找到一种染色方案满足以下条件：
请输出任意一种染色方案，如果无解，输出 \(-1\)。
本题有多组测试数据，\(1 \leq T \leq 10^{4}\)，\(2 \leq n,m \leq 500\)，\(\sum (n \times m) \leq 2.5 \times 10^{5}\)。
发现横竖之间没有影响，所以分开考虑。
考虑只有竖着，那么横向黑白染色，这无法影响道下一行，所以忽略。
纵向类似即可。
代码：https://codeforces.com/problemset/submission/1863/225041894
你在玩一个游戏，要完成 \(n\) 个任务。其中对于每个任务 \(i\)，它只能在某一天的第 \(h_i\) 时刻完成。游戏每天有 \(k\) 个小时，分别编号为 \(0,1,...k-1\)。
给出 \(m\) 对任务间的依赖关系，\((a_i,b_i)\) 表示 \(a_i\) 必须比 \(b_i\) 先完成。保证依赖关系不形成环。
完成任务不需要时间，也就是说可以在同一天的同一时刻先后完成多个任务。
求完成所有任务所需的最短时间。这里的时间定义为：完成最后一个任务的时刻 与 开始第一个任务的时刻 之差。
多组数据，\(T\le 10^5\)，\(\sum n,m\le 2\times 10^5\)，\(k\le 10^9\)。
最优的情况是延迟了一部分拓扑序第一的点，而且这一部分一定是前缀。
所以扫一次前缀，一一延迟更新当前答案，然后更新总答案。
每一个点至多更新一次，所以这部分 \(O(n)\)。
代码：https://codeforces.com/problemset/submission/1863/225021336
有一个长为 \(n\) 的数组 \(a_1, a_2, \cdots, a_n\)。
在每次操作中，你可以把数组分成两段，留下一段，扔掉另一段，要求前者的异或和不小于后者的。重复操作，直到只剩下一个数为止。
对于每个 \(i\)，问最后剩下来的可不可能是第 \(i\) 个数。
有 \(t\) 组数据。\(1 \le t \le 10\ 000\)，\(1 \le n \le 10\ 000\)，\(1 \le a_i \le 2^{60}\)，\(\sum n \le 10\ 000\)。
有一个显然的 \(O(n^3)\) 做法。
考虑一个区间 \([l, r]\) 什么时候可以被转移过来，由于异或，从二进制入手。
假定从 \([l, k]\) 转移过来，其区间异或和为 \(x\)，\([l, r]\) 区间异或和为 \(y\)。
如果 \(x\) 的第 \(k\) 位为 \(0\)，那么显然两边这一位都是相等的。如果为 \(1\)，那么有一边会大一点，下面的位随意了。
所以可以有条件 \(y \& \mathrm{highbit}(x) \ne 0\) 则可以转移。
于是一个一个长度递减做下去即可。
代码：https://codeforces.com/problemset/submission/1863/225050040
给定长度为 \(n\) 的序列 \(a\)，每次操作可以选定一个 \(i\)，并 \(\operatorname{swap}(a_i,a_{a_i})\)。求能通过某种操作顺序得到的不同序列数。
\(n\le 10^6\)。
简洁的题面，深邃的思想。
首先，一个经典的套路是：
对于序列中涉及到对于 \(a_i\) 和 \(a_{a_i}\) 进行操作的问题，一般可以考虑建立 \((i,a_i)\) 的内向基环树或者 \((a_i,i)\) 的外向基环树转化为图论问题。
-- from weakpyt
一次交换相当于使得一个点自环，儿子连向父亲。
于是转换为对于一个点，儿子可以断一条边，并且至多段一条边的模型。
所以如果只是一棵树的话，答案就是 \(\prod (d_x + 1)\)。
然而有环，发现环上所有边的断掉的情况不存在。
再发现环上留一条边不断，但是每一个点都断了一条边/或者不变的情况都是一样的，这部分显然是 \(\sum (d_x - 1 + 1)\) 的。
所以减去重复的，只保留一个，答案为：
化简一下：
这样就好求了。
代码：https://codeforces.com/problemset/submission/1863/225037149
给定一棵树，每个节点要么没有儿子，要么有两个儿子，每个叶子节点有一个权值。
多次修改某个叶子节点的权值，维护递推式子：\(f_x = 2 \max(f_y, f_z) - (f_y \ne f_z)\)。
令 \(t_x = f_x - 1\)，则递推式子转换为 \(t_x = 2 \max(t_y, t_z) + [t_y = y_z]\)。
记 \(x\) 的深度为 \(dep_x\)，则可以令叶子 \(g_x = 2^{dep_x} f_x\)，则递推式子为 \(g_x = \max(g_y, g_z) + 2^{dep_x}[g_y = g_z]\)。
有一个结论是 \(g_x\) 的二进制中 \(1\) 的个数是 \(\log A + \log n\) 级别的。
考虑暴力合并。
假定 \(x, y\) 的 \(g\) 相等，则可以在 \(z = \mathrm{LCA}(x, y)\) 处贡献 \(2^{dep_z}\)。
于是可以利用 vector 字典序暴力找相同的，然后合并即可。
最后会得到很多个答案，取最大的即可。
为什么取最大的正确性没问题？考虑如果 \(x\) 在和 \(y\) 之前与某一个 \(u\) 合并了，那么合并的位置一定在 \(z\) 下面，也就是贡献 \(2^{dep}\) 一定大于 \(2^{dep_x}\)，使得最终的答案大于错误的答案，所以如此是没有问题的。
由于当日晚上呕吐，身体不适，所以没有写本题。然而代码实际上是好写的，不过多赘述。