- 搬题人：
- 就这：Y25t
- 保序回归问题：Y25t
- 恰钱：skip2004
- 排序：Wu_Ren
- 图同构：hehezhou
- 找零：p_b_p_b
- 组题人：p_b_p_b
- 题解：p_b_p_b, Wu_Ren, Y25t, nantf
就这 (Div. 2 Only)
来源：
- 2021-2022 ICPC Northern Eurasia - Belarus Regional Contest. Problem A. Constructiveforces
- Кубок Трёх Четвертьфиналов 2021. Problem A. Constructiveforces
Tutorial by Y25t
其实只用保证每个长为 $m$ 的子串中恰好有 $k$ 个 1 就合法了，一种简单的构造是：
for(int i=0;i<n;i++) std::cout<<(i%m<k);保序回归问题 (Div. 2 Only)
来源：
- 2021-2022 ICPC Northern Eurasia - Belarus Regional Contest. Problem E. Positive Thinking
- Кубок Трёх Четвертьфиналов 2021. Problem E. Positive Thinking
Tutorial by Y25t
当 $\prod y_i> 0$ 时，取 $x_i=y_i$，答案为 $0$。
当 $\prod y_i= 0$ 时，设 $\{y_i\}$ 中 $0$ 的个数为 $c$，那么至少要 $c$ 的代价才能使乘积非 $0$。而先把 $c-1$ 个 $0$ 变成 $1$，然后剩下那个 $0$ 根据情况变为 $1$ 或 $-1$ 即可取到这个下界。
当 $\prod y_i< 0$ 时，考虑 $\{y_i\}$ 中绝对值最小的位置，不妨设为 $j$。当 $y_j> 0$ 时将其变为 $-1$，否则将其变为 $1$，这样能使 $\prod y_i$ 反号，花费代价为 $|y_j|+1$，容易证明这是下界。
这些情况均可线性判断。
恰钱：(Div. 1 + Div. 2)
来源：
- The 2022 ICPC Asia Regionals Online Contest (I)
Tutorial by p_b_p_b
如果你会数位 dp 那么可以直接往里套，显然是能做的。
否则，你也可以毛估估一下：
- 当 $\text{ctz}(x)\le 5$ 时 $\text{ppc}(x)$ 也很小，这样只会有 $O((\log r)^4)$ 个合法的 $x$ 。
- 否则这样的 $x$ 只有 $r/2^5$ 个，也不会太多，把合法的留下就更少了。
所以可以写个爆搜得到所有合法的 $x$ ，然后每次询问时二分。爆搜只需要 dfs+剪枝 即可。
最后，你也可以每次询问时枚举 $\text{ctz}(x)$ ，然后进行一些神秘贪心或调整，也可以通过此题。
排序：(Div. 1 + Div. 2)
来源：
- Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest. Problem C. StalinSort Algorithm
链接：https://qoj.ac/problem/1456
tutorial by Wu_Ren
考虑 dp，设 $f_i$ 为当前子序列结尾为 $a_i$ 并且保证最终子序列包含 $a_i$ 的情况下，当前子序列长度的最大值。
那么考虑 $f_i+1$ 贡献到 $f_j$ 的条件，设 $nx_i$ 为 $\min\{j\mid j>i\land a_j>a_i\}$，那么就是 $j\in[nx_i,nx_{nx_i})\land a_j>a_i$。
为了干掉 $a_j>a_i$ 这个条件，我们可以按 $a_i$ 从小到大枚举 $i$ 进行转移，这样就可以忽略这个条件。具体的，按 $a_i$ 从小到大枚举 $i$，用 $f_i$ 更新答案，然后用 $f_i+1$ 更新在 $[nx_i,nx_{nx_i})$ 中的 $f_j$。
注意，假如 $a_0=0$，那么 $f_i$ 的初值是 $[i\in[nx_0,nx_{nx_0})]$。
用线段树辅助转移，复杂度 $O(n\log n)$。
图同构：(Div. 1 Only)
来源：
- 2021“MINIEYE杯”中国大学生算法设计超级联赛（6）. Problem 1007. Power Station of Art
- Petrozavodsk Summer 2021. Day 6. Xi'an JTU Contest 1, Grand Prix of Xi'an. Problem G. Power Station of Art
- XXII Open Cup named after E.V. Pankratiev, Grand Prix of Xi'an. Problem G. Power Station of Art
链接：https://qoj.ac/problem/1869
Tutorial by nantf
对相邻两个点 $u,v$ 操作时，相当于将两点同时反色，然后交换颜色。于是可以看成每个点的颜色跟着点权形成的二元组在移动，从起点到终点如果经过了偶数条边（经过多次算多次）则最终颜色不变，否则最终颜色需要反色。
每个连通块独立，以下分别考虑每个连通块，有两种情况。
1. 该连通块为二分图
则无论如何移动，只要确定了每个二元组的起点和终点，则颜色是否被反色只与起点与终点是否在二分图的同一部有关。
分别考虑每种点权，则要求 $A$ 图和 $B$ 图的 左部黑点+右部红点 数量相等、右部黑点+左部红点 数量相等。这是一个必要条件。构造说明这也是充分条件。
任取这个连通块的一棵生成树，任取一个叶子，不妨设其在 $B$ 图中为左部黑点或右部红点，则任取 $A$ 图中一个点权相同的左部黑点或右部红点（由和相等一定存在），将其一路交换过来，以后的过程就可以在两张图中都忽略这个叶子。最后所有点都可以归位。
2. 该连通块不为二分图
也即该连通块一定存在奇环。
此时在确定每个二元组的起点和终点后，颜色是否被反色还不好确定。
再注意到，所有二元组经过的边数之和为偶数。则要求两图黑点奇偶性相同，红点奇偶性相同，且对于每种点权，两图的总点数相等。这是一个必要条件。构造说明这也是充分条件。
首先若整个连通块就是一个奇环，可以用下述的方法使得点权不变的前提下，相邻两个点 $x,y$ 的颜色反转。
- 将 $x$ 上的二元组沿反方向交换一圈到 $y$ 点，然后将原本 $y$ 上的二元组沿反方向交换一圈到 $x$ 点。
那么先任意交换至点权对应，由黑点红点奇偶性不变，容易用该操作使得颜色也对应。
然后对于任意一个连通块，固定一个奇环，任取这个连通块的一棵生成树（要求奇环上至多一条边不属于该生成树），任取一个不在奇环上的叶子。任取 $A$ 图中一个点权相同的点一路交换过来，若仅沿树边交换会导致颜色不对，则交换到该叶子后再一路交换到奇环，绕奇环交换一圈，再原路返回，颜色就是正确的。最后只会剩下这个奇环的点没有归位，用上一种情况的做法即可。
直接按上述过程判断即可，时间复杂度 $O(n+m)$。
找零：(Div. 1 Only)
来源：
- 京都大学プログラミングProgrammingコンテストContest 2021. Problem F. One Yen Coin
- Petrozavodsk Winter 2022. Day 1. Kyoto U Contest 2. Problem F. Flatland Currency.
- XXII Open Cup named after E.V. Pankratiev, Grand Prix of Kyoto. Flatland Currency.
链接：https://qoj.ac/problem/2544
Tutorial by p_b_p_b
可以发现，虽然纸币有不同面额，但我们其实只关心面额为 $1$ 的纸币数。剩余的钱具体是用哪些纸币表示出来，对后续操作没有影响。
因此也不难发现每次只会购买一个物品，不会出现打包购买的情况。
所以一个价格为 $a_i$ 的物品的价值就是 $5\lceil a_i/5\rceil-a_i$ ，我们需要做一个背包问题。但是价格实在是太高了。
注意到价值很小，所以可以把价值放进状态里。设 $dp_{i,j}$ 表示考虑了前 $i$ 个物品，获得的价值为 $j$ ，所需的最小代价，这样就可以把复杂度优化到 $O(n^2)$ 。
然后有多种继续优化的方法：
- 注意到如果价值相同，那么一定是按价格从小到大选。所以可以设 $dp_{i,j}$ 表示考虑了所有价值 $\le i$ 的物品，获得的价值为 $j$ ，所需的最小代价，然后利用决策单调性在 $O(n\log n)$ 的时间内从 $dp_i$ 转移到 $dp_{i+1}$ 。
- 注意到价值的 $\text{lcm}$ 是 $12$ ，所以可以把每种价值的物品分别先打包成价值为 $12$ 的包裹，然后按照价格从小到大选包裹。这样的一个问题是最优解的价值并不一定是 $12$ 的倍数，但是可以枚举价值为 $1,2,3,4$ 的物品选的个数模 $12,6,4,3$ 的值，然后先把这些物品选掉之后再贪心即可。
- 放弃分析，直接先按照性价比排序贪心选，然后在每种价值物品的边界附近进行小背包。大概和前一种是等价的。
