鸽子的题解太多了。只好直接写。

GYM
雅礼集训
Codeforces
洛谷
Atcoder
- AtCoder Grand Contest 048
- ACL Beginner Contest
  - F - Heights and Pairs
牛客
- ICPC小米邀请赛2
  - A.2020
  - I.Subsequence Pair

GYM

2019-CCPC-哈尔滨

B. Binary Numbers

$f(a,b)$即$a,b$的最长公共前缀长度，然后暴力打表，可以知道$a,b$越相近，$f(a,b)越大$，从每个区间里选出一个代表数字$A i$，如果对于所有区间$i$，满足$f ( A_i , k ) ≥ f ( A_j , k )$,$L_i≤k≤R_i$。

显然根据单调性

$f ( A_{i-1} , R_{i-1} ) ≥ f ( A_{i} , R_{i-1})$

$f ( A_i , L_i ) ≥ f ( A_{i-1} , L_i )$

$f ( A_{i-1} , L_i ),f ( A_{i-1} , R_{i-1} )$当作$dp[i-1][][]$的状态去转移，根据两个条件看是否转移，以及更新状态即可。

E. Exchanging Gifts

请先搞清楚，基本最大快乐值如何求。

两个操作可以想成一颗树，然后根据最后需要的向下类似$dp$,最后得到某些数的数量。

就是比较最大值和总和之间大小的分类讨论。

I. Interesting Permutation

考虑每次就相当于一个区间长度，$tmp=$可插空位

$h_{i+1}=h_i$,$ans=ans\times tmp,tmp-1$
$h_{i+1}>h_i$,$ans=2\times ans,tmp=tmp+h_{i+1}-h_i-1$,表示新的数可以插前面和后面。并且更新可插空位。

L. LRU Algorithm

找到规律发现，内存其实无所谓，假设内存无限大，那么对于有内存去前面$k$个即可，轻松可以预处理$hash[n][k]$，然后每次暴力查找即可。注意$0$。

300iq Contest 1

B.Best Subsequence

逆向思维取删出相邻最大的一定最优。用$set$模拟即可。

C.Cool Pairs

转化成$a_i< -b_j=z_j$，这类构造先考虑$k=0$,直接$z_j=-n$，再将$a_i$按照顺序变$[-n,-1]$。然后慢慢调整$z_j$大小。

如果不够，直接设$z_j=1$,就可以覆盖$j-1$个$a_i$。
如果够了，将$i<j$的$a_i$，排个序找到第$k$小的$a$,$z_j$直接等于就好了，并且结束，由于$a_i$是负的，保证$z_j$单调递减。

D. Dates

每个妹子匹配一个时间区间，每个时间最多选择𝑎𝑖个妹子，每个妹子有一个快乐值，最大化总快乐值。

由于一个妹子最多只会占用其他妹子的约会时间，所以贪心的选择快乐值总没错。

那么题意就变成选择妹子是否可以保证能成功过匹配。

对于任意区间$[i,j]$，区间$[i,j]$中选中妹子的数量需要小于等于这个区间和。

此时相当于判断是否所有子集的邻域（即与其相邻的点构成的集合）大小都比子集本身大。由于$L_i\leq L_{i+1},R_i\leq R_{i+1}$，左侧的区间的情况只有$n^2$种。

$c[j]-c[i-1]\leq s[r_j]-s[l_i-1]$

$c[j]-s[r_j]\leq c[i-1]-s[l_i-1]$

考虑我加入一个选中一个妹子的时候左侧$[j,n]$会发生变化。右侧$[j+1,n]$会发生变化。判断变化的那端是否发生左侧最大值$[j,n]$是否大于右侧最小值$[1,j]$了。

不然撤回操作。

F. Free Edges

问至少删掉多少条边后图中不存在环。并茶几瞎几把找一找就好了

K. Knowledge

每次可以删加掉$aa$,$bb$,$ababab$。

发现任何字符串都可以变成一个最短无法变短字符串
找到关键的几个变化

$aa\rightarrow$
$bbb\rightarrow$
$abba \rightarrow bab$
$ababa\rightarrow bb$
$abba\rightarrow bab$
$baba\rightarrow abb$

多写一点就好了，然后发现就$12$个为基底的字符串。

然后即从$k$长度的字符串变成$s$,考虑$12$个的互相变换关系，相当与走路径一样，查看从$x$走到$y$有几种走法，这里就是从空字符串走$k$步，有多少种变成$s$的路径种类，矩阵快速幂即可。

ICPC Asia-East Continent Final

H.King

找到$qa_i \equiv a_{i+1} \pmod p$,$\geq n/2$的最长子序列。
$q\equiv a_{i+1}a^{-1}_i \pmod p$

$\geq n/2$的最长子序列。必定存在相邻的$a_i$。

随机化枚举即可。

雅礼集训

LOJ6029. 「雅礼集训 2017 Day1」市场

当线段树上的点$max[pos]-min[pos]< d$就会变成减法，而$\sum a_i+d$，只会改变两个$max-min$。即我最多需要除$qlog(q\times 10^4)$。
需要一个支持最大值，最小值，区间和的线段树即可。

LOJ6030. 「雅礼集训 2017 Day1」矩阵

先构造一行都是#,然后填充竖即可。（注意需要注意已经$ok$的竖，以及填充此行只需要有这行的竖，或者花费一次构造这个竖

LOJ6031. 「雅礼集训 2017 Day1」字符串

$qk\leq 10^5$

$k\leq 300$，暴力跳所有子串，然后暴力二分询问$mp[l][r]，在[a,b]$中有几个,可以离线做到$O(qk^2)$，在线就是$O(qk^2\log n)$
$q\leq300$,从$1$走子串保证后缀那种，每走到$r$，需有所有的$l$,这个时候倍增往上跳寻找$siz$最大。$O(qm\log n)$

LOJ6032. 「雅礼集训 2017 Day2」水箱

按照高度排序，（注意这里需要先合并再处理那些条件),$ans[x]$表示$x$个块的答案，$f[x]$表示目前为止有水需求的数量。

考虑合并，合并答案即可。
考虑有水，则$f[find(x)]$++,更新答案$ans[x]$
考虑无水，则直接更新$ans[x]$

LOJ6033. 「雅礼集训 2017 Day2」棋盘游戏

二分图博弈，即找到那些点是非必须点。即删除了之后对最大匹配没影响。考虑一个非匹配点𝑥，假如它连向了一个匹配点𝑦，那么它就能替换掉当前当前和这个匹配点匹配的点𝑧，而这时𝑧也可以进行同样的操作。

首先根据时间戳的匈牙利算法可以找到所有可能的匹配点，然后找非匹配点。

于是我们从每个非匹配𝑥出发进行𝑑𝑓𝑠，途经的和𝑥同一集合的点都满足要求。

LOJ6034. 「雅礼集训 2017 Day2」线段游戏

李超线段树模版题。

LOJ6035. 「雅礼集训 2017 Day4」洗衣服

考虑只洗衣服，则用优先队列维护当前最小洗衣时间。就可以得到洗$k$间衣服需要的最短时间。同样处理烘干衣服的时间。

考虑到所有衣服都被烘干后烘干机全部是空的，可以把这个过程倒过来，这样子就和洗衣服一样。即当$i$衣服洗完后，选如果当第$p_i$烘干的则时间

$\max(a_1+b_{p_1},a_2+b_{p_2}....a_n+b_{p_n})$

顺序和大于等于乱序和大于等于逆序和,求个逆序和即可。

LOJ6036. 「雅礼集训 2017 Day4」编码

可以得到一个$O(n^2)$的2-SAT。
考虑如何优化

首先按照长度排序，就可以减少不必要的分类讨论。

如果有遍历到前缀，那么连接两个点表示不能同时成立。

在最后不能把这个情况直接压入终止节点，会导致某个节点太多点。考虑每次新建点，$new$不能与$old$同时成立，但需要和$tmp$同时成立。

LOJ6038. 「雅礼集训 2017 Day5」远行

只可能是直径上的点，用LCT和并查集动态维护直径即可。

LOJ6039. 「雅礼集训 2017 Day5」珠宝

对于$C$一样的物品，我们要选肯定是要先选价值大的，所以$sum$数组是一个上凸的

$i<j$且$i$的决策点为$p$，即有任意$s<p$满足 $dp[s]+sum[s,i]<dp[p]+sum[p,i]$,然后决策单调性即可。

LOJ6040. 「雅礼集训 2017 Day5」矩阵

咕咕

LOJ6041. 「雅礼集训 2017 Day7」事情的相似度

建好link树之后。

给定一棵树，每个点有一个权值$(𝑚𝑥𝑙𝑒𝑛)$，询问编号在一段区间内的点两两之间$𝑙𝑐𝑎$权值的最大值。

离线来看，对于一个点他到根节点的都要打上标记，如果下次访问到则表示存在$lca$.其实就是动态维护所有的$lca$出现的时机。

若遇到了以前打的标记，则该节点为旧标记与新标记的$lca$ 。贪心可得应把标记尽量覆盖为较大的值，已经只会维护$[i,r]$之间区间。

LOJ6045. 「雅礼集训 2017 Day8」价

Codeforces

翻转$a$数列
将$a$数列变成他的前缀和

前缀和不断增大得很快。$n\geq 3$模拟即可，你问我咋模拟，$std$,满足单调增就差分，不满足就倒置，否则就$-1$。

$n=2$,就特别麻烦。

根据上题，我们需要把本来差分的部分快速差分，
如果快速差分过程中出现$a$数组，两两特判。
以上情况都没有并且被差分到某个数$=0$,$-1$

之后就是看清题意写整齐

CF1367F2 Flying Sort (Hard Version)

我们可以发现，中间的数字是不能插进去的，所以这组数是在排序后仍相邻的数，则要找到最长的子序列。

对于相同数字的考究。

如果一个数当第一位以及最后一位，数量是可以任意。
否则必须全部数字加进去。

先离散化一下。
我们可以这样$dp$,$dp[i]$，表示$[1,i]$最长的不严格增序列

把$a[i]-1$当中间的数字，则$dp[i]=dp[l[a[i]-1]+cnt[a[i]-1]$
把$a[i]-1$当第一的数字，则$dp[i]=cnt[a[i]-1]+1$
把$a[i]$当最后一位的数字，则$dp[i]=dp[pre[a[i]]]+1$

CF1368E Ski Accidents

有 $n$ 个顶点，以及 $m$条有向边，所有有向边$(u,v)$ 均满足 $u<v$ ，且所有顶点的出度都不超过 $2$ ，要求从中删去不超过 $\frac{4}{7}$个顶点，使得图中不存在长度超过$1$ 的路径。

如果是完全二叉树显然可以的$4/7$。考虑反向建边，如果找到长度为 $2$的路径的顶点时，将顶点 $i$ 删掉即可,并且由于题目所给$u<v$，就不会有后效性了。

CF1374E2 Reading Books (hard version)

思路很明显，先离散化离线，后面做权值线段树第$k$大。别把线段树写错了。

CF1380G Circular Dungeon

自己做出来的，按照宝箱大小去分配遇到$k$个之前的价值。这里可以提前预处理，前缀和即可。注意下无法$(n-i)\mod i \not = 0$即可。

CF1384D. GameGame

对于每位来说如果异或位$0$,则这位没影响。

考虑最高位异或不为$0$,必定在此有决战，且必定有奇数个$1$。观察下可得如果都是$1$,则$cnt\mod 4=1$。或者$cnt\mod 4=2,(n-cnt)\mod 2=1$，拿到奇数个$1$之后有$0$拿。

CF1387B1 Village (Minimum)

简单的树形$dp$。

CF1387B2 Village (Maximum)

答案显而易见$\sum min(n - siz[i], siz[i])$。

看怎么合理分配。$min(n - siz[i], siz[i])\leq n/2$，也就是路径必须经过重心

则答案一定产生在重心的子树里，$siz[i]\leq n/2$,也一定是重心的每个子树里的点互相匹配。

这个序列的第$i$项和第$i+\lfloor\frac{n}{2}\rfloor$，匹配，注意$n\&1$，有个点会保持不变，其实此时交换不会发生变化，随便找个点互换即可。

CF1399E2 Weights Division (hard version)

分类花费硬币的价值每个边权计算$/2$给予的价值。可以提前$n\log$处理，反正除我之前一定要除我之前的。

就变成花费硬币$1$，所以直接枚举一个的种类使用的数量，再二分或者单调队列另一个。

CF1354C2. Not So Simple Polygon Embedding

求$n$为奇数，$n$为偶数

可以变成扩大变成偶数，偶数就是非常简单。
选择$\frac{pi}{2n}$，不要被六边形迷惑计算。

CF1354F. Summoning Minions

解释一下为啥是一定是前$k-1$张放下，然后$n-k$张放了就拿走，最后一张再放下。

首先无论怎么放终究是$\sum a_i+(k-1)\sum b_i+\sum (j-1)b_j$。

这样肯定是最优的，然后其实就是枚举所有最后留在桌子上的$C_n^k$张权值就定了。一定不会错过最优解，然后知道了就简单的二维$dp$。

CF1354G. Find a Gift

注意$k\leq \frac{n}{2}$，就可以随机化确定$1$是否为礼物了。只要出现小的一定是礼物。显然随机化$k$,如果是礼物一定会出现$2$。否则是石头是不会出现$2$的。

然后就可以通过一次次倍增确定$[1,2^k]$是否为石子，也可以发现$(2^k,
2^{k+1}]$，然后既然我知道有可以对比的任何小于区间的石头,就可以轻松用二分找到最左端的礼物在哪了。

CF1421E. Swedish Heroes

找到规律一定是正负交替，并且发现只需要$(n+\sum [p_i=-1])\mod 3=1$。并且不能为$+-+-+$这样显然不可能。设$m=\sum [p_i=-1]$,$dp[n][m][last][flag]$,$last=$最后一个$a_i$的正负，是否当前为$+-+-$

CF1353F. Decreasing Heights

一定有元素不变，直接枚举不变的$O(n^4)dp$

CF1353E. K-periodic Garland

看错题意+失误，类似于求子段最大和一样即可。注意$dp$可以重头开始，也可以接后面的。

CF1427E . Xum

通过给定的$a$,$a$为奇数，操作$\oplus, +$构造出一个$1$,显然$ax-by=1$即可。构造一个互质的$y$即可，暴力枚举$(a\times(2k+1)\oplus a)$，然后注意范围$ax\leq 10^{12}$，$x\times t$这个好构造。注意控制大小。

CF1344D.Résumé Review

暴力很好想，把$a_i-3x^2+3x-1$，放到优先队列里面一个一个取。

而这里巧妙枚举了最后结束的$\Delta f(i,x)$，可以判断每个最多可以取多少。（这里再用二分）。

然后细节就需要，因为可能有好几个相同的值，所以二分时候往大的方向取答案，即找到满足条件的尽可能小的值，然后由于可能多了使用次数，找到$=ans$,—。

CF1344C Quantifier Question

题意很恶心，注意$x$成立是有顺序的，显然有环不可能。然后所有存在一定可能，然后发现如果出现一个任意，递推到我的和我递推的都要变成存在，又因为$a<b,b<c,a<c$,具有传递性，就是说跑这个有向图跑到的点都要变成存在（别忘记跑反图。然后我们发现只要被任意一个图跑到的节点，他的值也确定了，我的反图和正图那些也不能任意了，要做一样的操作。

CF1363F Rotating Substrings

给定两个长度为 $n$ 的字符串 $s$，$t$。定义一次操作为选择 $s$ 的一个子串 $s_{l, l +1, \dots, r}$

，然后将之修改为 $s_{r, l, l + 1, l + 2, \dots, r - 1 }$s
请求助使 $s$ 与 $t$ 相等的最小操作次数。无解输出 $-1$。

$S$的前$i$个字符和$T$的前$j$个字符匹配的最小花费

每一个操作可以让一个字符提到前面的任何位置，并不能提到到后面，最少的操作次数是$n$ - 两个字符串的最长公共子序列。

但是对于$acbd,adbc$。匹配到第三个字符的时候，显然不能把$c$放到后面去。这个时候在做最长公共子序列。我们需要加上一个条件，$s$的每个字母后缀数量必须比$t$多即可。

CF1408E Avoid Rainbow Cycles

如果我保留某个元素，那么这个集合就会和所有有这个元素的点连边。我们把集合当成一个点，那么当两个集合同时选择一个$x$，$x$连集合$A$,集合$B$连$x$,$A-B$，即最后要搞一个最大生成树即可。

CF1408F Two Different

模拟时，显然$2^n$的长度暴力模拟，就会全部变成一个。然后对剩下的贪心分配。

但是直接正做一遍，反做一遍就好了。(我是傻逼)

CF1422F Boring Queries

在线区间$lcm$

解1

对于小于等$\sqrt{2\cdot 10^5}$的质因子，直接各开一个线段树暴力维护，需要动态以及常数优化
对于大于 $\sqrt{2\cdot 10^5}$
的质因子，每个元素至多有一个。这有点像维护区间不同颜色个数，$\sum [last_x<l]$只不过每个颜色还带了权值（强制在线）
版本$r$这个线段树维护的是点$x$，维护的是$last[t]=x$,的$t$的所有乘积。

解2

根据解$1$去做预处理第 $i$版本的线段树时，将 $i$ 位置的权值乘上 $a_i$的大质因子，为了防止二次计算，并将$a_i$上次出现的位置除掉该质因子。

版本$r$这个线段树维护的是位置$x$,在$[1,r]$上的乘积。

CF1437G - Death DBMS

$AC$自动机上树链剖分最大值，或者标记永久化线段树维护子树点的最大值。

CF1436F. Sum Over Subsets

用$jiangly$的话说看到$\gcd=1$,一定想到莫比乌斯容斥这种东西。

然后想想没有限制咋做。

$a_i\times a_i$产生贡献。选择一个$(k-1)$是被踢掉的，然后随便选$2^{k-2}$
$a_i\times a_j$产生贡献。（是有顺序的那种），$2^{k-3}(k-2)[a_i,a_j\in A]+^{k-3}(k-2)[a_j\in A,a_i\in B]$。

维护一下两个乘积的$\sum$即可。

CF1443F - Identify the Operations

先考虑如何处理不合法的情况。每次删观察是否两边都是不需要的数。

正解其实很简单，观察拿出某个数之后，此时这个数就成了不必要的数。如果下次想拿被移走的数，其实间接在拿$pos_{b_i}$，并且一定拿的到，然后模拟一下就没了。

CF1443E - Long Permutation

大水题，逆康托展开得维护后$14$个数就好了。

提醒我要准备他两板子了。两者都可以做到$n\log n$。

CF19D

这题告诉我们线段树上区间二分时间复杂度不大。

CF204E Little Elephant and Strings

锁定字符串的每个$r$,就可以知道这个后缀是否存在$k$个重复。

然后标记下，某个结点可以贡献的就是结点到根最大有标记的$len$，瞎几把维护即可。

CF793C Mice problem

阴间题。

我们只要把每一个老鼠在矩形里的时间段算出来然后取交集，若交集非空则输出交集中的任意点即可。
但是有很多恶心的点。

出现与边的线段一样的直线，永远不能交在矩阵内。
如果最后交集在一个时间点，也永远不能在矩阵内。
如果有不动点要特殊判断。

CF1285E Delete a Segment

你要求出正好删去一条线段后，并集最多包括多少条线段。

如果不删，就把所有线段排个序加入，然后判如果加入的左端点小于当前最大右端点则，出现了一个新的线段。考虑$dp[i][r][2]$显然空间不够，但是发现删一条边，对枚举到一个点的$r$产生$2$个状态。直接暴力$map$保持即可。
考虑计算去掉每条线段的贡献，显然如果出现$[[\ ],[\ ]]$这种情况这条线段的贡献是+2的，推广到一般形式，如果在括号匹配中遇到$set$里只有一个括号$[$显然去掉我是可以让之后的括号与之前括号分离。但是要记住加入一个括号他自己这个并集也会消失，然后用$set$维护即可（主要$set$好删除）

CF1451E Bitwise Queries

其实就是探究如何在$4$次询问找到$a,b,c$

首先记住$a+b=a\oplus b+2(a\&b)$

观察题目都是$[0,2^n)$。

假设有重复那就很简单。

如果没有重复

可以白票一个询问，一定存在$a_i \oplus a_j=2^n$,并且此时$a_i \& a_j=2^n$
或者直接确定根据异或1的和异或2的推导出即可。

CF1452E Two Editorials

二维差分细节题，只是场上摸鱼了。这里只是告诉自己别摸鱼

CF1158B The minimal unique substring

打表得到的，循环$(n-k)/2$个$1$+$0$,即可。

考虑$110110110$此时每加循环$k=k+1$,设$x$个1

$n-2(x+1)+2=k,x=(n+k)/2$

CF1158C Permutation recovery

考虑最简单$val_{nxt[i]}>i,i>j， j\in[i+1,nxt[i]-1]$

连好边，有线段树优化一下边，就可以拓扑排序，就做完了。

CF1251E2 Voting (Hard Version)

很巧妙的贪心，从跟随大贪心去考虑，如果发现我就算把后面全部选完，还不能免费跟随，就需要从剩下里选最小的，保证后面都选完就可以免费跟随了。

CF1283F DIY Garland

可以知道叶子结点，根结点，以及每个点的出度。从小的选，一定选叶子结点里面最小的那个结点，这里注意当点的出度为$0$，才能放入堆里，。仔细思考想想即可。

CF1461F Mathematical Expression

大力分类讨论。

只需要处理$*+$

用$0$分开每一段。

此时就有个$n^2$的$dp$。首先去头尾$1$，一定是$+$,如果我一段之间的乘积是$K$，如果用$1$分开，最坏就是$2+K/2+n>K$,$K>2n$用$1$分开就没有意义了。考虑到此时非$1$的有$\log n$个。

对于$dp$

$a[i]=1$,一定选择$+$。
$a[i]\not ={1}$,需要选择乘法区间转移即可$dp[i]=\max{dp[j]+\prod_{t=j+1}^ia[t]}$。

拿个数组记录过程即可复杂度$O(n\log n)$

CF1462F The Treasure of The Segments

求的是删除最少的线段使存在一条线段能够和其他所有线段均重合

对于每条线段求一遍即可，统计一下跟他不重合的就行了。

CF1463E Plan of Lectures

一直在想咋判不正确。显然需要输出方案，直接缩点拓扑排序，为了防止缩点里面又不合法的，我们直接在原图上再连边去拓扑排序，看是否可以实现。

CF1464B Grime Zoo

如果$1$,$0$的数量定了，$01+10$已经定了。
那我要让$10$更多，坑定是把$1$往前放，获得更多$10$，反之也是。
所以只需要瞎几把预处理即可。枚举前缀都是$0$，后缀都是$1$的情况。

CF1464C Poman Numbers

打表，贪心。

洛谷

P4103 [HEOI2014]大工程

记录下最长边，最小边，次小边，次大边即可,虚树模版题。

P5504 [JSOI2011]柠檬

一番证明就可以发现最优的两端一定是相同数，如果左右端点贝壳大小不相等的话，必然有一个端点对答案没有贡献。干嘛不直接分开呢？

上凸包维护对于每个$a_i$。然后斜率优化即可单调栈（PS:好像没啥麻烦的，甚至直接二分上凸包也可以）。

P2542 [AHOI2005] 航线规划

LCT维护边权，简单多了。如果连接成环，就把这些全部变成$0$.这些就不会是关键路径。

Atcoder

AtCoder Grand Contest 048

ACL Beginner Contest

F - Heights and Pairs

容斥是显然的。$f(i)$表示保证$i$对相同的答案。$g(i)$表示随便选$i$人成对的数量。$z(i)$表示选$i$对情侣的方法。

对于每种$h_i$我们可以计算出选出$i$对的方法,变成多项式就是$(k_0x^0+k_1x_1+k_2x^2…)$，启发式$NTT$即可。

$g(i)=g(i-2)\times C_{i-2}^2/(i/2)$

$f(i)=g(2n-2i)z(i)$

$ans=f(0)-f(1)+f(2)-f(3)…$

当然想要想的更快，二项式反演就不用思考了。（显然我要复习下）

牛客

ICPC小米邀请赛2

A.2020

赛时没做，考虑二分，先安排前$k$个再安排后$k$个，就没了。

I.Subsequence Pair

脑子进水题，想到$lcs$然后，问马老师：说不需要$LCS$。

其实就是$lcs$裸题。

$\max(dp_{i,j}+m-j)$,公共一样直接贪心染$t$取最长。
$\max(dp_{i-1,j-1}+m-j-1+n-j-1)$，如果发现$s_i<t_j$,发现取完之后就随便取了。

GYM