没有见到山东的朋友们。由于lcez认为的疫情原因，以及noi22需要提前七天到昆山，所以原定在noi22之前举行的sdptt r3改为线上进行。
但是双感觉我已经不再年轻了。
D1
爆力100+100+100=300。
A. adventure
求所有\(n\)个点的竞赛图中，\(1\)能到达的点数之和。\(n\leq 10^5\)，2s。
考虑竞赛图缩scc之后变成链，把点分成和\(1\)同一个scc/属于\(1\)前面/后面的scc的，第一/三种每个点贡献\(1\)。所以设\(A(z)\)是任意竞赛图的egf，强连通竞赛图就是\(1-\frac{1}{A}\)，那么枚举\(1\)所在的scc大小\(k\)，目标是求\(\sum_ii[z^{n-k}w^i]A(z)A(zw)\)，这里\(w\)表示\(1\)的贡献。
发现这个就是\(\displaystyle\sum_{i+j=n-k}ia_ia_j\)，于是卷\(a_i\)和\(ia_i\)即可。复杂度\(O(n\log n)\)。
B. war
原题cf1137F。
树，点权，一开始是排列，支持把一个点点权改成当前最大的点权\(+1\)，查询如果不停剥掉点权最小的叶子，一个点会是第几个被剥掉的。没有一个部分分是只查询两个点答案的大小关系(但是确实有这个查询)。\(n,q\leq 10^5\)，4s。
发现点权最大的点可以看成一个根，然后对于任意两个点，必然是子树\(\max\)较小的点先被剥掉，如果相同，说明它们一定是祖先-后代关系，则后代先被剥掉。所以我们会做不存在的部分分了。
直接做不是很可做。考虑一个性质，子树\(\max\)相同的点是一条链。考虑我们维护这些链，那么换根的时候，旧根到新根的链被翻转，此时链上的点的子树\(\max\)必然变成旧根，而别的点必然不变，所以这个就是链推平，lct维护链，全局开一个BiT即可。这里lct是一个\(\log\)，但是很遗憾每推一段链都要进行一次BiT操作，所以复杂度是俩\(\log\)。
由于只有\(n\)次查询，可以换成\(\log\log\)叉线段树做到\(\log^2/\log\log\)。
C. cookie
原题cf799G。
凸多边形，每次给一个点，过这个点画一条直线把多边形分成两部分，使得两部分面积相等，求直线的极角。\(n,q\leq 10^5\)，3s。
二分。考虑这玩意肯定是连续的，并且我画一条线算两边的面积差，它正着(左边减右边)和反着(右边减左边这样的)必然异号，所以我们在从正着转到反着的过程中必然经过一个两边相等的点，二分然后胡乱算算面积即可。这个面积算起来就二分这条线经过了哪两条边，然后面积是叉积的和，就把经过的一段加起来，可以用前缀和维护，两边处理一下即可。复杂度是俩\(\log\)。
我感受了一下能不能线段树上二分啊，但是好像会非常复杂。
cf1119 F. Niyaz and Small Degrees/apio2021 A. 封闭道路
考虑dp，发现好像需要记录子树根选了多少，但是又发现不需要，只需要钦点子树根的父边选没选，也就是设\(dp(u,i,0/1)\)表示\(u\)子树每个点度数不超过\(i\)，\(u\)的父边没选/选了的答案，转移的时候我们先都按不选父边算，然后按改为选父边的代价排序选取最小的若干个。使用nth_element，复杂度\(O(n^2)\)。
考虑一个牛逼想法，当我们处理\(k\)的时候，选的边必然和某个度数\(>k\)的点相连，所以每个点会作为度数\(>k\)的点出现度数次，总出现次数就是\(O(n)\)。dp的时候，只考虑度数\(>k\)的点，对于每个这样的点，枚举选了多少个度数\(>k\)的儿子，用数据结构维护度数\(\leq k\)的点。这个数据结构需要支持查询从所有数开始，长度递减\(1\)的若干个值域前缀的和，使用堆，开始处理这个点的时候当堆大小超过我们需要的最大可能大小(\(\mathrm{deg}(u)-k\))就弹max，然后我们需要处理一些前缀，维护总和并不停弹max把它减去，最后再加回去即可。复杂度\(O(n\log n)\)。
cf1103 D. Professional Layer
要让\(\gcd\)变成\(1\)，那么如果除了一个素因数，肯定要一口气把一个素因数除完，否则不如不除。
把\(\gcd\)分解掉，然后考虑每个素因数被哪个数除了。如果有一个素因数幂\(>k\)了，那么必然无解。发现素因数个数\(c\leq\omega(10^{12})=11\)，并且只有这些素因数有用，忽略剩下的素因数后，据说剩下最多\(L\approx 12000\)个数。对于每个数，我们只会用到最多\(c\)次。
简单想法是直接在已经干掉的集合上面状压dp，但是我们需要枚举补集的子集来转移，所以失败了。考虑对于所有\(2^c\)种集合，算出干掉这个集合的前\(c\)小代价，复杂度是\(O(2^ccL)\)，而此时只剩下\(2^cc\)个数了，爆力dp复杂度就是\(O(3^cc^2)\)，就结束了。
cf1097 G. Vladislva and a Great Legend
考虑dp选\(k\)条可重的边，计算所有点集的斯坦呐树中，这么选的方案数之和。根据二项式定理，这里如果一条边重数是\(c\)，则要带\(\frac{1}{c!}\)的系数。
当然dp，直接设\(dp(u,i)\)表示\(u\)子树(不包括\(u\)的父边)选了\(i\)条边的贡献，而\(g(u,i)\)包括父边。
考虑转移，一条边在斯坦呐树上，当且仅当它两边都有点集中的点。但是现在我们是选边，选了一条边之后，需要保证它两边确实有点集中的点。考虑首先每条边较深的点子树里必然要选一个点，这个是容易处理的。然后考虑所有选了的边的lca，如果lca的至少两棵子树有选了的边，那么所有边都满足要求，子树外的点可以随便选；否则，必然是lca的一条邻边和它所在的子树中若干边被选了，剩下的部分至少要选一个点，这也是好计算的。
考虑\(dp\)到\(g\)的转移，枚举选了多少次，容易做到\(O(nk^2)\)。考虑\(g\)到父亲的\(dp\)的转移，就是背包一下，总复杂度\(O(nk^2)\)。只要算出这俩，按照上面的东西统计答案就比较简单了。
考虑砍一个\(k\)。发现如果每个点状态数变成\(\min(\mathrm{size}(u),k)\)，就可以砍掉这个\(k\)了，分析请见 如果我不知道把一些东西放在哪里，那就放在这里吧/树卷积。考虑不拆普通幂，而是拆下降幂，那么相当于每条边选一次，于是结束了。
cf1085 G. Beautiful Matrix
也就是每行是一个排列，并且是上一行的一个错排。计算字典序比一个序列小的序列个数，我们考虑枚举从哪里开始小了，则前面的全部相等，这一位更小，后面的随意。发现我们要从某个格子往后计算半个矩阵的方案数，只需要把这一行剩下的排完，然后下面每一行都是上一行的错排，主要问题是在排这一行剩下的哪个后缀的时候，我们还需要它是一个错排。
如果一个数在上一行的这个后缀中没有出现过，那么它可以随便放，否则它有一个不能放的位置。第一个位置只能放一个足够小的数。所以放完我们枚举到的位置之后只有两种数，也就是可以随便放的和有一个位置不能放的。考虑我们枚举放在当前位置这个数是哪一种，问题变成，有\(n\)个数，其中\(k\)个有互不相同的不能放的位置，求重排的方案数。那么不妨转化成前\(k\)个数分别不能放在前\(k\)个位置。
考虑dp，设\(f(n,k)\)表示答案，那么考虑\(1\)，如果放在前\(k\)位中，有\(k-1\)种方案，并且有一个数不能放的位置就消失了，它就变成了一个可以随便放的数；如果放在后面，有\(n-k\)种方案。于是\(f(n,k)=(n-k)f(n-1,k-1)+(k-1)f(n-1,k-2)\)。于是结束了。
cf1082 F. Speed Dial
考虑建立trie，问题是我们要标记\(k\)个点，然后拨打一个号码的时候，会先按它到根路径上最近的点。
考虑dp，发现我们没法自底向上确定，因为一个点子树里可能有很多点被选了，但是如果自顶向下，一个点的贡献只和选了的最近的祖先有关。设\(dp(u,i,j)\)表示\(u\)子树用了\(i\)个点，上面选的第一个点深度是\(j\)的答案，复杂度\(O(n^2k^2)\)。
cf1067 E. Random Forest Rank
考虑这个rank是啥。
考虑什么时候一组点会线性相关。考虑邻接矩阵的行列式我们在哪里见过，发现在图图矩阵中我们见过这种东西，但是它不太一样，那里我们是给了每条边一个变量，但是这里我们给的都是\(1\)；发现在矩阵树定理中我们也见过这种东西，但是它也不太一样，我只好发怒。
考虑什么时候rank是\(n\)，也就是矩阵是满秩的。类似矩阵树定理的直接组合证明，我们考虑行列式是枚举一个排列，我们把排列拆成若干个环，发现由于排列是在矩阵上每行每列选恰好一个数，如果出现不是一条边的环，那么要么不是排列，要么贡献是\(0\)，所以这个相当于选若干边。并且如果一个点被选两次，那么它也不是排列，所以相当于选一个边独立集，或者说匹配。如果要有贡献，每个点必须都在匹配中，所以完美匹配才有贡献。所以我们知道如果树不存在完美匹配，则必然不满秩。然后可以发现树的完美匹配是唯一的，因为叶子必然和父亲匹配这样的，所以如果存在完美匹配，则行列式必然是\(\pm 1\)。
秩就是最大满秩子矩阵的大小，也就是最大匹配中的点数，所以我们dp一下，设\(dp(u,0/1)\)表示\(u\)没有/有和儿子匹配，\(u\)子树答案的期望。转移显然。
cf1060F Shrinking Tree
考虑这个相当于给每条边标了一个时间，时间是一个排列，然后每次把一条边加入，把新连通块的颜色置为原来两个连通块的颜色中随机的一个，这样树的形态就不会变了。
考虑无标号无根树个数，或者一棵树上的本质不同连通块个数，看起来都很大啊。
考虑我们枚举一个点，不妨设为\(1\)，那么颜色就变成01了，然后我们当然直接把它作为根，这就非常阳间。考虑如果我们合并了两个0，那么啥事都没发生，而我们合并01的时候，1留下来的概率会乘一个\(\frac{1}{2}\)，我们将这样的合并称为惊悚的。
考虑什么时候一条边贡献了一次惊悚的合并。发现如果它到根路径上的边都在它之前触发，那么它贡献了一次惊悚的合并。dp，设\(dp(u,i,j)\)表示\(u\)子树贡献了\(i\)次惊悚的合并，其中最早的那个在子树中的时间排名是\(j\)的方案数，转移要求父边插在前\(j\)个之间，然后子树之间用一个组合数插起来。复杂度\(O(n^4)\)。
cf1038F Wrap Around
问题是怎么把首尾接起来，考虑枚举开头最长匹配的后缀，跑序列的自动机上dp，到最后就可以得到最后最长匹配的前缀，看看能不能拼出\(s\)即可。
但是这个假了，因为我们没法保证这个后缀真的是最长的。考虑如果它是一个自动机，我们边dp边算真正的最长匹配的后缀就好了，所以我们建立sam，然后在上面跑，如果跑到了sam之外，则立即计算最长匹配的后缀，状态数是\(O(n^3)\)。
D2
由于时间紧迫，按计划今天没有模拟赛，而是lyh讲一天。时间紧迫指的是从通知到办三轮省集时间很短。
cf1063 F. String Journey
作为sdptt21 D8 B. fade被搬过。
考虑答案不超过根号。
考虑如果前面的串长度比后面的串大了超过\(1\)，那么我们完全可以把前面的串长度砍\(1\)，并且最后一个串必然是单字符。所以我们知道每个串长度也不超过根号。
dp，设\(dp(l,len)\)表示现在选到\(s_l,...,s_{l+len-1}\)的答案，那么\(len=O(\sqrt{n})\)。转移的话，找到这个串的两个最长真子串在后面第一次出现，转移过去即可。可以找到所有\(O(n\sqrt{n})\)个可能有用的串，然后同时扫所有串的所有出现，复杂度\(O(n\sqrt{n})\)。
考虑如何优化。注意到在这个dp中\(len\)就是答案，所以实际上值是\(0/1\)，并且一定是一个前缀可行，所以考虑设\(dp(i)\)表示已经处理了\(i\)右边的部分，\(i\)作为第一个串左端点的情况下，最大的\(len\)能是多少。
可以注意到\(dp(i)\)不超过\(dp(i+1)+1\)，于是我们可以令\(dp(i)=dp(i+1)\)然后判断是否可行，如果不可行就\(dp(i):=dp(i)-1\)，这样总共需要判断\(O(n)\)次。
考虑判断这个相当于找到\(dp(j)=dp(i)-1\)满足\([j,j+dp(j)-1]\)是\([i,i+dp(i)-1]\)的子串。考虑建立st，那么两种可能的转移分别是st上的父亲和suffix link，直接维护即可，使用hash table，复杂度\(O(n)\)。
但是有个小问题，就是这里我们需要计算\([i,i+dp(i)-1]\)对应哪个点，发现问题是往左加字符，往右删字符，这个是某个经典题，改为建立前缀树，删字符的时候跳suffix link就好了。
我感觉这个对，但是我并不想写。如果有老哥发现它错了，请务必D我/se
cf995 F. Cowmpany Cowmpensation
1e9/jy
考虑权值很小怎么做。dp，设\(dp(u,i)\)表示\(u\)子树每个点权值不超过\(i\)的方案数，那么转移考虑\(u\)的权值是不是\(i\)，如果不是方案数就是\(dp(u,i-1)\)，否则把儿子们的\(dp(v,i)\)乘起来。
猜测\(dp(u,i)\)是关于\(i\)的\(\mathrm{size}(u)\)次多项式，插即可。复杂度\(O(n^2)\)。
cf930 E. Coins Exhibition
考虑这个限制，记一下上一个0/1出现在哪里即可。也就是设\(dp(i,0/1,j)\)表示考虑前\(i\)个，\(i\)是\(0/1\)，上一个\(1/0\)是\(j\)的方案数。这里长度很大，所以离散化一下，一次处理一段即可，也就是设\(dp(i,0/1/2,j)\)表示考虑前\(i\)段，\(i\)包含\(0,1\)/只包含\(0\)/只包含\(1\)，\(i\)不包含的数上一次出现在\(j\)段的方案数。
考虑转移，\(dp(i,0)\)只有一个状态，\(dp(i,1),dp(i,2)\)看起来是一样的，需要把\(j\)过大的状态杀了。注意到由于我们是从上一段转移，\(j\)每走一步最多增加\(1\)，用栈维护(是不是直接前缀和也行啊?)，dp部分的复杂度\(O(n)\)，但是要排序所以还是\(O(n\log n)\)。
另一个做法是直接不设\(j\)，而是枚举上一个这个在哪，不过我不懂这个为啥是对的啊。
cf724 E. Goods Transportation
恐怖题。显然考虑网络流，建图是显然的，但是边数很大没法跑。考虑改为最小割，那么问题就是把点分配到\(s\)的一边或者\(t\)的一边，每个点划分到两边各有一个代价，并且如果\(i<j\)且\(i\)连\(s\)，\(j\)连\(t\)，则要付出\(c\)的代价。
现在可以dp了，设\(dp(i,j)\)表示前\(i\)个有\(j\)个连\(s\)的答案，复杂度\(O(n^2)\)。
存在一个牛逼贪心。考虑如果没有这个\(i<j\)，我们直接先全选\(s\)，然后枚举\(t\)一边选了多少，让改的代价最小的若干个改为连\(t\)，这里改的代价是不计\(c\)的，因为我们枚举了\(c\)的系数。但是现在有\(i<j\)，我们不是很好枚举\(c\)的系数了。可以考虑一个牛逼想法，发现如果让每个连\(t\)的点\(j\)付出\((j-1)c\)的代价，也就是假设前面全连了\(s\)，那么如果其实前面有\(k\)个连了\(t\)，就多算了\(kc\)。发现所有多算的东西，如果一共连了\(k\)个\(t\)，就多算了\(\binom{k}{2}\)，所以还是结束了。
下面就不是dp题了。
cf1407 E. Egor in the Republic of Dagestan
按最终的距离从小到大贪心。为什么这会是对的?
因为在最短路dag上跑是无后效性的。
cf1379 F. Chess Strikes Back
画一画可以发现，简单策略是放\(1,3,5,7\)行这样的。如果某个奇数行的第\(i\)个格子被ban了并且它应该放，那么下一行的第\(i\)个格子就要放，并且后面所有偶数行的后\(i\)个都要放。所以可行当且仅当可以画出一条从左下到右上的单调的分界线，把每个\(2\times 2\)的格子划分到一边，其中左上部分的放左上，右下部分的放右下。我们考虑左上被ban了的位置，在它们中任何一个右下方的位置就必须放右下，如果存在一个右下被ban了的位置在这里面，那么就不可能放了，所以如果有一个左上被ban了的位置在一个右下被ban了的位置的左上方，那么就死掉了。用线段树维护即可。
cf1370 F. The Hidden Pair
考虑我们如果计算每个点的\(\mathrm{dist}(u,w)+\mathrm{dist}(v,w)\)，那么将会得到一个以\(u\rightsquigarrow v\)为底的谷。所以这个问的就是以\(u\rightsquigarrow v\)为根，点集中最浅的点以及它的深度。
先问一次所有点得到\(\mathrm{dist}(u,v)\)，以及\(u\rightsquigarrow v\)上的一个点\(w\)。以\(w\)为根把树拎起来，然后我们二分\(u,v\)中深度更大的那个，也就是把深度为\(mid\)的点一起问一次，如果得到的还是\(\mathrm{dist}(u,v)\)就说明\(mid\)不够大。这样我们就得到了深度更大的那个，然后查询距它\(\mathrm{dist}(u,v)\)的点即可。查询次数是\(2+\lg n\)。
注意到深度更大的那个，深度在\([\frac{\mathrm{dist}(u,v)}{2},\mathrm{dist}(u,v)]\)中，所以我们就少了一次二分，查询次数是\(1+\lg n\)。
cf1364 E. X-OR
当然考虑找\(0\)。不自适应的话，直接shuffle king。然后所有做法shuffle了都是对的（
cf1361 D. Johnny and James
称在原点同一方向上的点是一组，那么每个点的贡献就是组内的贡献，加上组外的点数乘它到原点的距离，所以每一组是独立的。猜测这玩意是上凸的，所以闵和即可。
那么问题是怎么算每一组内的答案。如果组内选了\(c\)个点，那么选了的点中距离的排名为\(i\)的点，设它到原点的距离是\(d\)，组内的贡献就是\((i-1-(c-i))d\)，组间是\((k-c)d\)，总共是\((k-2(c-i)-1)\)。所以我们知道，一定是先选最大的若干个，再选最小的若干个。
cf1344 D. Resume Review
考虑当\(b_i\)增加时，\(b_i(a_i-b_i^2)\)的增量递减，可以直接求导。所以闵和即可。
但是\(k\)很大，所以wqs二分即可。
cf1344 F. Piet’s Palette
考虑这个操作，打一个表可以发现合并两个元素的操作和\(0,1,2,3\)上的xor同构，而变色不是很好处理。猜测它是xor上一个数，如果是我们就可以直接bitset解方程，但是实际上不是。
构造发现变色是对两位的线性变换，所以就可以bitset了。
cf1340 F. Nastya and CBS
牛逼题。
但是可以分块，所以就简单题了。
cf1336 E. Chiori and Doll Picking
离奇题。收录于 线性代数。
cf1329 D. Dreamoon Likes Strings
考虑这个只和所有相邻相同的间隔有关。每个间隔可以用一个字符表示，然后比如现在有aa aa，把中间那一段(a a)删掉还剩下aa，如果有aa bb，则把中间那一段删掉就啥也不剩了，不过最后总要操作一次。
考虑我们几乎每次都能找到相邻的不同间隔，但是如果出现次数最多的那一种超过了一半，到最后我们就可能找不到了。把这种设为1而剩下的都设为0，则每次找到一个1和0相邻的间隔干掉，就可以让出现次数最多的尽可能少。set维护间隔的序列和每种间隔剩下的出现位置即可。
cf1307 F. Cow and Vacation
考虑爆力，直接从每个关键点连到它为中心半径\(k\)的邻域，点分之后拆一拆，看起来复杂度直接就是\(O(n\log n)\)。
考虑一个简单做法。先考虑如果查询的都是关键点怎么做。我们只需要处理关键点之间的可达性。
爆力就直接从每个关键点出发bfs。
考虑我们bfs \(\frac{k}{2}\)的距离，搜到一个已经搜过的点就合并，这样每个点被标记之后，关键点的虚树上每条边最多再产生一次代价，所以总复杂度是\(O(n)\)。如果\(k\)是奇数，可以往每条边中间塞一个点，并\(k:=2k\)。
考虑如果不是关键点怎么做。相当于临时钦点这两个点是关键点，因为我们再次到达起点显然是不优的。考虑我们从一个点出发，走到的第一个关键点必然在另一个点的方向上，所以往那边走\(\frac{k}{2}\)，然后看之前bfs的时候这个点属于哪个连通块，这个连通块中的关键点就是可以走到并且可能用到的。从另一个点做同样的事情，然后判断两个连通块是否相同即可。考虑如何走若干步，使用四毛子la即可，复杂度线性。
cf1307 G. Cow and Exercise
收录于 线性规划对偶定理。
cf1305 G. Kuroni and Antihype
注意到边是不对称的。但是可以发现，每个人只被拉了一次，所以我们钦点边权是\(a_i+a_j\)，则一共多算了\(\sum a_i\)。所以问题变成mst了。
考虑边数只有\(n^{\lg 3}\)，所以爆力即可。复杂度\(O(n^{\lg 3}\alpha(n))\)。
考虑别乳卡，每轮要寻找一个点补集的所有子集中，两个在不同连通块的点，跑一个法嘛塔即可，复杂度\(O(n\log^2 n)\)。
cf1292 D. Chaotic V.
也就是建虚树。先把每个阶乘都分解了，然后在上面扫一扫，就可以\(O(\frac{k}{\log k})\)求lca，于是结束了。
cf1290 D. Coffee Varieties
离奇题。
显然可以每次问两个是否相同。
考虑我们让一个数最左的出现贡献\(1\)。
考虑如果从左往右问，我们可以得到\([i-k,i-1]\)中是否有和\(i\)相同的。所以考虑把\([1,i-1]\)每\(k\)个一块，也就是分成\([i-k,i-1],[i-2k,i-k-1],...\)这样的，一共有大约\(\frac{n^2}{2k}\)块，然后好像不太对啊，因为我们塞出一块之后，问一次就又要清了。
考虑直接全局每\(k\)个一块，然后对于任意两块，我们先把第一块加进去，然后把第二块加进去，这样加入第二块的第\(i\)个元素的时候，就知道它跟第一块的\(i,...,k\)个元素是否有相同的。然后清空，把第一块倒着加进去，然后把第二块倒着加进去，这样居然就拼出来了。啊还有块内的，发现加一块的时候就知道块内的了，所以没有什么问题。看起来这个大概是\(\frac{2n^2}{k}\)的。
发现这个相当于每个块是正反两个点，每个点连向前面所有同类点，也就是一张后面连到前面的完全图。考虑一张图，我们可以用\(\frac{n^2}{16k^2}\)条路径把这些块串起来，方法是枚举一个步长\(k\)，然后从右往左枚举起点，步长为\(k\)的路径数是\(\min(k,n-k)\)，因为前\(k\)个点不能作为起点，然后加起来就得到这个。边数是\(\frac{n^2}{2k^2}-\frac{n}{2k}\)，每条边和每条路径的起点都要花费\(k\)的代价，然后一共有两张图，所以加起来好像还是\(\frac{2n^2}{k}\)级别的。
考虑 让一个数最左的出现贡献\(1\) 导致这个东西性质不是很好。我们直接考虑，如果加入一个数的时候里面有相同的，就把它删掉，此后要加它的时候直接跳过去。注意到我们只要保证每两个数都被check过一次(一个数加进去的时候，另一个数在队列里，则认为它俩check了一次)，于是可以得到另一个\(\frac{2n^2}{k}\)，也就是枚举两个块，正着做一遍反着做一遍，感觉一下这个看起来很对。
考虑还是串起来，这是一张完全图，每条边需要经过两次。问题在于可能出现一个环，环上每一个干掉后一个，那么最后一个都不剩了，就完蛋了。注意到，只要我们在一串连续的加入(也就是截止于一次清空)之中，一个数不会被加入两次，那么就不可能出现干出一个环的情况，所以还是划分成若干路径就好了。这里做法非常牛逼，我们把块排成一个环，然后进行一个之字形的划分，枚举起点\(s\)，走\(s,s+1,s-1,s+2,s-2,...\)，这样一条边\(i\leftrightarrow j\)会在\(i,j\)的两个中点被正反走到恰好两次。边数是\(\frac{n^2}{k^2}-\frac{n}{k}\)，一共有\(\frac{n}{k}\)条路径，这就赢麻了。
cf1288 F. Red-Blue Graph
考虑这个相当于红边流量-1，蓝边流量1，考虑怎么处理\(-1\)，我们连\(s\)表示正的超额流，连\(t\)表示负的超额流之类的，然后设下界\(1\)即可，反正这里是对称的。核心思想是源汇是提供正/负超额流的。
cf1286 D. LCC
考虑答案只有\(O(n)\)种，也就是每个间隔有两种可能的贡献。我们从小到大枚举，那么使答案更小的情况都不能出现，也就是我们要ban一些某个间隔的可能情况求概率。如果只算一次这个概率，可以直接dp，但是现在ban的集合要加东西，发现这个dp是每个间隔的线性变换的复合，而每次ban一个间隔相当于修改矩阵，线段树维护即可。
cf1285 F. Classical?
考虑枚举gcd，然后要求剩下的部分互素，也就是多次给一个序列，求两个互素的数使得乘积最大，序列总长\(n\log n\)。
我们枚举一个数。考虑爆力怎么做，我们需要ban它的素因数，然后在剩下的数里面找最大的，那么求出每个素因数被ban了之后的最大值即可。
考虑把所有互素的对画到平面上，那么相当于拿\(xy=k\)去切这个东西，那么我们知道答案必然在右上单调栈上。从大往小扫\(i\)，我们知道如果\((i,j>i)\)合法，那么\(<j\)的都没用了，于是考虑对\(j\)维护一个栈，问题是计算栈中有没有数和\(i\)互素。
考虑转而计算有多少，莫反即可。结束了，跑一次的复杂度是\(O(n\log n)\)，然后枚举\(\gcd\)就是跑总长\(n\log n\)的，所以总复杂度\(O(n\log^2 n)\)。
考虑一个牛逼想法，我们把每个数的因数也都放进序列里，然后直接对序列跑一次上面这个东西，注意到加入因数们显然不会让答案变大，而此时必然存在两个数互素且它们的乘积就是答案，所以就一个\(\log\)了。这个还是比较的妙。
cf1280 E. Kirchhoff’s Current Loss
考虑我们不可能选两个电阻使得它们的阻值都非\(0\)，并且一条电流同时经过它们两个，否则把阻值都调整到其中某一个上必然不劣。
所以所有的电阻都是并联的。容易知道如果最后选了\(k\)个，那么答案就是\(k^2R\)，所以问题就是最小的\(k\)。显然对于一个串联的点，答案是各部分的\(\min\)，而并联的点是各部分的和。
cf1267 G. Game Relics
显然先随若干次，然后全买。如果随的期望收益\(<0\)，也就是不如直接全买了，那么我们就会开始全买。
随的期望收益，如果已经出了\(k\)个，并且令一开始的收益是负的总和，算起来就是\(\displaystyle-x+\sum_{i\text{已经获得}}\frac{x}{2}+\frac{n}{c}\sum_{i\text{还未获得}}c_i\)。所以是否继续随只和出了多少和没出的的和有关。每个出了\(k\)个的情况，概率都是一样的，所以枚举出了的个数和没出的总和，背包跑出这个方案数，然后把收益更大的一边计入答案即可。但是如果直接买某一个的话，就不能保证”每个出了\(k\)个的情况，概率都是一样的”，所以我们需要随机买一个，不过算起来没有什么区别。
D3
爆力100+100+100=300。
A. combination
对于一个排列，定义一个区间是好的，当且仅当它的值域区间等于序列区间。求长\(n\)的排列中，有多少不存在一个非平凡好区间划分。
考虑一个序列必然存在一个极大好区间划分，那么设答案是\(F\)，排列总数是\(A\)，我们知道\(F=A-\frac{F^2}{1-F}\)，恐怖故事是这是一个一次方程\(F=A-AF\)，它的意义就是枚举第一段，剩下的部分还是好的但不一定极小，一次求逆即可。
B. algebra
我感觉这个题在去年省集出现过?
给\(a,m,n\)，求每次把\(a\)加上\(a\)十进制下最大的数位再膜\(m\)，\(n\)次操作后得到的数。\(10^4\)组询问，\(n,m\leq 10^{18}\)。
发现这个取膜相当于没有，因为每次膜完了必然在\(0,...,8\)之中，我们只要处理\(0,...,8\)到再下一次取膜会经过多少次，以及会变成什么，然后就得到一个内向基环树，在上面走即可。
考虑怎么快速求不取膜操作\(n\)次之后会变成啥。
考虑最大的位会变化多少次，打表发现很多。
考虑一个牛逼想法，我们可以每次处理一次进位到最高位的发生。发生一次到\(i\)位的进位之后，\(i-1,...,1\)位就都是\(0\)了，只有\(0\)位是\(1\)，于是设\(f(i,j,k)\)表示\(i,...,1\)位是\(0\)，\(0\)位是\(j\)，\(>i\)的位上最大值是\(k\)，再向\(i+1\)位进位一次，需要多少次操作，以及操作之后得到的\(0\)位是多少。那么我们可以考虑\(i\)位的变化来转移，设进制\(t=10\)，这部分总复杂度\(O(t^3\log_t n)\)。要用这个算不取膜操作\(n\)次之后会变成啥，每次找到最高的可以进的位，这个可以维护一个指针均摊\(O(1)\)，然后我们就可以\(O(t\log_t n)\)求一次。
C. geometry
原题洛谷P5600。
尺规作图的提答。发怒。
古代字节营杂题选讲。
Disk Troubles
bsgs。问题是如何求逆，容易想到直接多项式exgcd。
最后一个样例看起来很奇怪。
可以发现那个答案恰好是\(2^{32}-2\)，所以再看一眼我们知道\(x^{2^{32}-1}\bmod{P}=1\)，所以\(x^k,x^{2^{32}-1-k}\)就是一对逆元。
Embeddings
考虑pam。发现我们从一个串走到它套的一个串的过程可以唯一地表示成先走若干次父亲，然后走若干次fail。
于是可以dp，设\(dp(u,0/1,0/1)\)表示走到\(u\)，上一步走了父亲/fail，这个点没选/选了的方案数。
Joy with Cookies
也就是算出这些矩形的sg值，然后考虑改就是给总sg值xor上一个数，线性基即可。是不是\(\frac{n^2}{w}\)也冲了。
注意到这个图是一个可比图，所以我们知道它上面的\(\mathrm{mex}\)就是\(\max\)，扫描线BiT维护左下方的\(\mathrm{mex}\)即可。
Knights of Round Table
cf741C。
Lands of Infinistan
\(v-e+f=1\)，\(v\)好算，\(e\)也好算。结束了。
需要讨论圆锥曲线是椭圆，双曲线还是抛物线。如果是双曲线还要特判它的两部分是否相交。
Binary Trees
考虑一个子树合法，当且仅当它的中序遍历中，所有的间隔都满足左边\(\leq\)右边。我们跑出整棵树的中序遍历，然后每次修改相当于改两个间隔。注意到一共会产生\(O(n)\)个合法间隔的极长连续段，数点即可。
Deep Red
考虑得到每个数的过程，发现这些误差虽然不是独立的，但是误差的上下界总是有可能达到的，所以可以对每个数分别dp。设\(dp(l,r)\)表示能否得到一个必然在\([l,r]\)之中的数，发现对于每个\(l\)只有最小的\(r\)有用，然后爆力转移就\(n^2\)了。
Jury Troubles
网络流。
但是跟学生们没有啥关系。考虑裁判之间的冲突是一个二分图，跑最大独立集即可。
Minimize the Similarity
先进行一个trie的建。
考虑让相邻的\(\mathrm{lca}\)深度之和最小，改成让距离之和最小，但是这里是序列，加一个空串变成一环，就是一个经典问题，求出重心，然后如果有一棵子树要超过一半了就选它，否则选最小的就好了。
jAG Strikes Back
考虑一条链，发现两端各两个点是重要的。大家都不会选这些点，直到我们不得不面对它们。如果是偶数，那么先手会选一个近的，后手会选同一侧，然后先手选另一个近的，这样答案是\(n-3\)；如果是奇数，那么后手会选一个近的，先手会选另一侧，后手选同一侧，答案是\(n-2\)。
考虑如果是根上挂了若干条等长的链，那么先手的目标是不选到两个最远的点，但是发现这个很困难，因为这要求先手必须选所有最近的点。
考虑如果是任意树，那么先手的目标是不选到两个在同一棵子树的最远的点。
考虑如果\(n\)是奇数，那么最后一步是先手选，所以先手必须选一个最远点。如果存在两条直径，则至少有三个最远点，先手至少要选俩，而后手必然可以留先手选的那个对着的那个；否则先手可以只选一个。
如果\(n\)是偶数，那么最后一步是后手选。发现我们需要不超过四条直径，但是这个看起来比较困难，直接枚举所有本质不同的情况爆搜即可。也可以手动讨论。
Knocking Down
居然被我猜中了。可以发现答案必然在两条中线上，因为如果它不在，把它平移过去必然不劣，所以就结束了。我们只需要求出每个点在两条线的哪个区间是有贡献的。
Rats
考虑这个等价于\(s\)是\(a\)的最小整周期的重复。发现每个串的效果是把\(s\)从某个长度往后接到另一个长度，长度可以膜\(\vert a\vert\)，所以爆力算出这个效果，然后问题是\(\vert a\vert\)个点的图求\(0\)开始的最小环，floyd即可。
Marbles
qyc
每个物品可以在O(1)个时刻到达每个位置
qyc
就是对于物品i和位置j，i有O(1)个时刻可以到达j
qyc
所以我全跑出来
qyc
枚举一个时间看看有没有完美匹配。
注意到这个图每个点度数最多是\(2\)，所以可以直接模拟得到有没有完美匹配。
NoteBook
这个问题在省选计划出现过。考虑把这个看成多项式，它能拼出来的就是多项式的\(\gcd\)，然后合并就好了。复杂度\(O(n\log n\log v)\)。
Aunts
二分。考虑如果对于任意两个点，都满足它们之间的曼哈顿距离\(\geq\)高度差，那么就合法。所以分四个方向扫描线BiT即可。
Davy Jones Tentacles
请注意每一时刻每根手指都可以移动。发现如果上一次用一根手指在\(\max(h,w)-1\)时间之前，那么这一次它可以在任何地方了，所以考虑前九个键被哪根手指按了，看起来这个是bell数。第九个bell数是\(21147\)，于是看起来几乎结束了，实际上状态数更小。
注意到一个时刻的手指属于哪个等价类不重要，只有它是不是所在等价类的最后一个时刻重要，所以状态数就是\(3^9\)。结束了。
Exploring the Space
也就是求哪些元素必然在线性基里。
删掉线性基里的每一个元素，然后再求线性基看rank是否减少了。复杂度\(O(n^2m)\)，看起来困难。
考虑点牛逼想法。如果线性基中的元素\(x\)参与表示了线性基外的元素\(y\)，那么把\(x\)扔掉，插入\(y\)也没有问题，所以一个元素必然在线性基里，当且仅当(在它被插入之后)它不参与表示任何一个其它元素。在插入一遍的时候就可以处理出来，复杂度\(O(nm)\)。
Funny Graphs
强的。
猜测必然有解，那么这个问题等价于如何判断能不能把度数都在\(d,d+1\)中变成都在\(d-1,d\)中。
首先把连接两个\(d+1\)的边都删了。不停重复这个过程，现在所有点度数是\(d,d+1\)，并且没有两个\(d+1\)相连。
考虑接下来我们还要给每个\(d+1\)删一条邻边。跑一个\(d,d+1\)之间的完美匹配。注意到每个\(d+1\)邻接\(d+1\)个\(d\)，所以根据hall定理，任何一个\(d+1\)的集合，邻接至少\(d+1\)个\(d\)，所以必然存在完美匹配。总复杂度\(O(n^{3.5})\)，但是众所周知dinic不满。
How to Pack String
问题是 编码长度不能超过\(L\)。
这是一个经典问题，可行当且仅当，如果一个串长度是\(k\)则贡献\(\frac{1}{2^k}\)，总贡献不超过\(1\)。
显然权值大的串编码长度不会更长，所以从大到小排序，设\(dp(i,j,k)\)表示考虑前\(i\)个，第\(i\)个长\(j\)，总和为\(\frac{k}{2^j}\)，那么如果\(k>n\)则直接全填在这一层即可，转移是\(O(L)\)，复杂度\(O(n^2L^2)\)。
King of Renovations
考虑给每个点建入度出度两个点，边是无向边，问题变成二分图，选一些边使每个点度数\(>0\)。
上下界。结束了。
Balanced Binary String
考虑平衡说的是啥。对于所有\(i\leq j,k\leq l,j-i=l-k\)，有\(\vert s_j-s_i-s_l+s_k\vert\leq 1\)。
D5
cf1707 E. Replace
注意到\(\min,\max\)是结合的，所以我们知道一个区间的\(f\)就等价于找到若干个区间，相邻两个有交，并且它们并起来得到这个区间，然后求它们\(f\)的并。
然后可以发现，一个区间的\(f(f)\)，居然等价于找到若干个区间，相邻两个有交，并且它们并起来得到这个区间，然后求它们\(f(f)\)的并。发现这个也是显然的。所以我们可以考虑搞出所有\([i,i+1]\)的\(f,f(f),f(f(f)),...\)。
D6
今天有模拟赛了。
A. divide
给一个\(n\times m\)的棋盘，有一些边已经被剪开，你要再剪开若干边，使得得到的每一块都是\(1\times k\)或者\(k\times 1\)的矩形。\(n,m\leq 50\)。
考虑网络流。发现我们的问题就是，给每个点分配一个横竖，然后横点和上下的必须割，竖点和左右的必须割。然后这个好像不是很好做。
考虑换个想法，考虑最后每个格子要么
B. perm
给一个\(1,...,n(n+1)\)的排列，选出\(2n\)个数，使得删掉剩下的数，新序列中第\(2i-1\)小和第\(2i\)小是相邻的。可以证明必然有解。\(n\leq 1000\)。
考虑dp，可以做到\(O(n^4)\)。需要一个至少是几乎线性的做法。
考虑构造一个解。我们把值域分成\(n\)块，尝试每一块里面选一个出来。每一块里有\(n+1\)个数，那么我们把序列也分成\(n\)块，则必有两个数在同一块。
然后发现这个好像有点假，因为可能有两个值域块里面，那个同一块是同一块，这时候我们就比较见鬼。考虑我们把用过的块删掉，但是这样可能删掉别的数，注意到如果我们取了一个长\(a\)的值域块，把序列分成若干长\(b\)的块，则要求\(a>\frac{n}{b}\)，然后最坏情况下两块都不能用了，所以我们删掉了\(a\)个值和\(b\)个位置，其中至少两个是重合的，所以我们删掉了\(a+b-2\)个数。
考虑第一次取前\(n+1\)个值，把序列每\(n+1\)个数一块，分成\(n\)块，然后找到出现相同的那一块把它加进答案并删掉，此时有\(2n\)个数没了。等比数列求和一下，我们得到\(n(n+1)\)，也就是最坏情况下刚好用完所有数，于是结束了。
C. hypercube
给一个\(n\)维超立方体，每个点有一个点权，每次钦点若干维的值，求对于剩下维度的所有可能，对应点点权的和。\(n\leq 20,m\leq 10^6\)。
joi 2018 final E. 毒蛇越狱。
大概做法是，考虑我们显然有一个关于未确定位个数的做法，然后容斥之后法嘛塔可以得到关于确定的0/1位个数的做法，选择三种中最少的一个做就好了。
结束了。
一年又过去了呢。