ARC142 A-E
A Reverse and Minimize
憨的。
B Unbalanced Squares
构造。考虑一行之内大小交错，行间则单调排列。这样可以使得每个点上下大小关系抵消，左右的又保持一样，于是就合法了。
C Tree Queries
处在 \(1,2\) 最短路径上的点一定到两个点距离和最小，于是找到这个距离。但是这个距离可能是 \(3\) 或者 \(1\)，对这样的情况进行一点分类讨论即可。
D Deterministic Placing
应该把整棵树划分成一些链，每条链带了一条白色的尾巴，这样显然可以构造方案。至于如何构造唯一方案，思考这些毛毛虫需要满足哪些条件。首先头和头不能相邻，尾巴和尾巴不能相邻。还有一个就算不能有一条虫的脑袋顶别人的身体，这样会产生歧义。相似地尾巴和身体也不能直接接触。最后就可以大力 \(f_{x,0/1/2/3/4/5/6/7}\) 来暴力转移了，分别表示是单脑袋，是有身体的脑袋，是单尾巴，是有身体的尾巴，是有前驱后继的身体，是有前驱的身体，是有后继的身体，是一截什么都没有的身体。应该是这样吧。
E Pairing Wizards
很好的一道题。大前提是每个数应该被补到一个较高的水平，该水平有两个标准。一个是不应该比原来的 \(a_i\) 低，因为补到 \(a_i\) 不劣；一个是不应该比每个关系中 \(b\) 的较小值低，因为这样就不合法了。
此时需要观察仍然不合法的数对性质。发现形式大概如此：存在 \(a_i\ge b_i,a_j<b_j\)，也就是说每个数都被划分成了两类，一类是小于的，一类是大于的，并且一个限制中恰好包含了两类数各一个。于是考虑把两类数放在两边，思考每一个限制如何满足。
从小的向大的连边，那么只需要小的满足或者大的满足即可，并且小的满足是一劳永逸的。于是每个点建立一个点，从源点向这个点连代价边，然后这个点向限制的大点连边，要求其不小于给定的数。后面需要用到一个比较经典的模型，即 \(i\) 向 \(i-1\) 连 \(\inf\) 边，\(i\) 向汇点连 \(1\) 边，这样要断只能断后缀，达到了选择一个数的目的。跑最小割即可。
ARC143 A-E
A Three Integers
选择结构。
B Counting Grids
猜想最多只有一个数满足条件，分析一下发现应该正确的。然后简单统计即可。
C Piles of Pebbles
考虑像经典 nim 游戏一样，思考后手什么时候可以跟随先手进行操作，发现这一轮操作等价于将每个数模上一个 \(a+b\)。总会有一个余数集合，思考一些比较简单的情况，即每个数都小于 \(x\)，那么后手无脑跟进是正确的。否则如果存在数大于 \(x\)，那么再次分类讨论。如果 \(x\le y\)，那么先手先把所有大余数 ban 掉之后就变成了一个后手必败的场面。最后就剩一个 \(x>y\) 的情况了，如果不存在二者之间的数那么先手必胜，因为不存在一个数减去 \(y\) 之后还比 \(x\) 大；如果存在的话那么后手必胜，容易分析得到。
D Bridges
题目中的操作很像拆点，而连边就相当于是给无向边定向。于是考虑从拆点之前的意义思考，问题变成了给定一个无向图，希望给图中每一条边定向，使得旧图中桥最少。画图发现高一棵 dfs 树出来从上到下连边是不错的。
E Reversi
一看就是从叶子开始考虑，然后逐层向上，搞出一个 DAG 后贪心搞字典序最小的操作序列即可。
ARC144 A-E
A Digit Sum of 2x
憨憨题。
B Gift Tax
二分加检查。显然是容易的。
C K Derangement
手玩发现，如果前面可以划分成一堆长度为 \(2n\) 的段那么一定划分，这样一定字典序最小。后面会有一段小于 \(4n\) 的数，考虑让其递增循环着来即可。然而 wa 了，观察题解区发现是答案 \((10,3)\) 应该是 4 5 6 1 8 9 10 2 3 7 而非 4 5 6 7 8 9 10 1 2 3。发现如果最后的长度大于 \(3n\) 的时候需要在中间进行一些循环位移，找规律就可以了，然后就没了。
D AND OR Equation
猜想合法的形式应该是存在一个大小为 \(n\) 的数列 \(p\)，满足 \(a_S=p_0+\sum\limits_{i\in S}p_i\)。然而 \(p\) 有正有负，把其按照正负性分类，而题目中的限制就变成了负的那些（可以认为是最负的那个集合）不小于零，最大的那个也不应该大于 \(k\)。然而方案似乎并没有那么好计算。
考虑切换枚举对象。思考每个 \(p\) 对应的 \(p_0\) 的取值范围，发现其就等于 \(lim-\sum|p_i|\)，而每个 \(p_i\ne 0\) 都有两个取值。于是显然想到枚举非零的个数 \(n\)，可以得到下面的柿子：
\[\text{ans}=\sum\limits_{0\le n\le m}\binom{m}{n}2^n\sum\limits_{s=n}^{k}(k-s+1)\binom{s-1}{n-1} \]右边是个上指标求和的形式。具体地：
\[\begin{aligned} &\sum\limits_{s=n}^{k}(k+1)\binom{s-1}{n-1}-\sum\limits_{s=n}^k\binom{s-1}{n-1}s\\ =&(k+1)\binom{k}{n}-\sum\limits_{s=n}^kn\binom{s}{n}\\ =&(k+1)\dfrac{n+1}{k+1}\binom{k}{n}-n\binom{k+1}{n+1}\\ =&\binom{k+1}{n+1} \end{aligned} \]然后就没啦。组合数可以递推，所以总体复杂度是线性的。
E GCD of Path Weights
哈哈哈。
首先从图中剔除那些从源点无法到达的点和无法到达汇点的点，然后拆点，忽略那些 \(-1\) 的点，最后图会形成一些连通块，一个 \(x\) 合法当且仅当对于所有连通块都是合法的。搞一个生成树出来，考虑每条非树边对答案的限制，等价于限制了答案是 \(|v-\text{dis}_{x,y}|\) 的因数，前缀和维护即可。还要注意一下什么如果存在从 \(1\) 直接到 \(n\) 的边那么需要让答案和路径的长度取一个 \(\gcd\)，其它的就没什么了。主要数组要开够。
标签：连边,limits,一个,题解,sum,arc143,arc142,即可,binom From： https://www.cnblogs.com/Feyn/p/17657143.html