目录agc001agc002agc003agc004agc005agc006agc007

agc001

A：排序后取相邻的

B：先折一次，发现等于在一个平行四边形的钝角处射出光线，直到碰到另一个钝角为止，实际就是辗转相减，取模加速

C：枚举最终直径终点，暴力

D：显然就是通过回文的方式把n个点连通，必要条件是n-1条边，所以当n为奇数时没有多余奇数块，n为偶数时ab加起来最多两块

讨论，若m=1就1,a-1，m>1分奇偶，奇数就 奇-1,偶…,1，这样两个块错位交替可以只剩一个点

偶数若没有奇数块则 1,偶…,偶m -1，有奇数块就 奇1 -1,2,偶…,奇2 -1，原理同上

E：等于(sum_i sum_{i<j}inom{Ai+Aj+Bi+Bj}{Ai+Aj})，考虑组合意义，把点丢到(A,B)和(-A,-B)上，从左下往右上走O(V^2)dp，最后减掉自己/2

F：把排列反过来变成每次满足相邻绝对差<=K交换相邻的，要依次使1~n的出现位置最前

大胆猜想，每次新加一个数然后贪心往前移，这样感觉很河里因为如果存在abc满足a>b>c，则到b时换a后c也可以换a，如果不换不可能更优

所以直接按位置分治，每次把左边建权值线段树，右边算出最前能放的位置，最后把两边归并，这样可以log^2爆过去

题解做法：

注意到要求的是原序列字典序最小（比如翻转后312大于231，1更前），但是经过观察后发现就是使新序列字典序最小，感性证明：

如果存在当前最小的a，使得a往前移动后字典序变大，则必然存在移动完后的a前面有个b，b和后面的某个c交换（b a'(不存在) c a => c a’ b a(不存在)，a’是a移动后的位置）

由于字典序变大了，所以有a<b<c，而b和ac都交换过，所以ac也可以交换，即a可以在c离开a’时把c换掉，这样可以多进一位

那么可以给绝对差<K的连边，然后从前往后按位确定，用堆+拓扑解决

问题是边数很多，实际只用在位置在后面，小于/大于的值域的最近的那个连边即可，因为值域内的会互相连，现在连x没连y到x时就会连上y，时间一个log，没写

agc002

F比E简单

A：算一下负数个数，特判0

B：维护每个位置的个数以及可能性，移球把可能性一起移过去，如果盒子空了就必不可能

C：反过来变成合并，队列维护

D：建Kruskal重构树，询问倍增log^2，应该可以主席树+线段树二分做到一个log

E：看错题了，以为每次只能减一堆

把a从大往小排序，发现每次全体-1相当于移下边界，删最大相当于移左边界，则等于从(0,0)往上/右走直到碰到折线为止

讨论01发现(i,j)等于(i+1,j+1)，因此可以先从(0,0)走到(i,i)，然后讨论一下上/右的奇偶即可

可以先走到碰到折线为止然后往回退一格，这样结果不变且不用讨论边界情况

F：假设每种颜色x只保留一个0和一个x，则会构成一个2n的序列，其中每个0和往后的第一个颜色匹配，剩下K-2个后面的任意

从后往前dp序列，设f[i,j]表示放了i种颜色剩j个颜色未放0，每次讨论放颜色或放0，放颜色就把剩下K-2个组合进去，放0就匹配最后一种颜色，方案唯一

agc003

E写不完

A：判一下EW,SN是否共存

B：先贪心把奇数往后移，最后Σa/2

C：如果只有2操作等于把奇偶分开排序，问题是一开始奇偶的集合可能不对，有些跑到另一个集合里，则可以把两个集合中不对的通过2操作换到相邻，然后1操作归位，所以ans=集合不对的数/2

D：把每个数的平方因子去掉，剩下的和互补的分成若干对，每对取较大的，再判掉=1的即可

问题是怎么分解因式，之前牛客里有类似的但是忘了，可以硬上pollardrho?

枚举除掉<=n^(1/3)的因子，则剩下最多2个，判一下平方数讨论即可得到互补的(a^2=>a,ab=>(ab)^2)，写双哈希

E：显然先单调栈一下，然后每次操作等于把一段*K+前缀，考虑反推算次数，维护堆表示当前长度下每个前缀被计算的次数，从后往前枚举qi，每次把>qi的分一下

时间复杂度考虑每次模x后新增一个x共Q个，每个数膜一次时间+1(?)，一共会膜logA次，加上堆总时间O(QlogQlogA)

F：打表观察，设xy表示行/列首尾都有的个数，cnt=黑色格子个数，若x=y=0显然每次扩展不会合并，ans=cnt^(K-1)

否则若x,y>0或K=0则ans=1，因为可以发现每个块在下一层都能走到相邻的块，而下一层块之间又连通，所以整体还是连通，且下一层的x’,y’>0

那么有x>0,y=0，记A=(a[i,j]=a[i,j+1]=黑)的方案，可以发现此时每行都是独立的，因为块之间不能上下走，所以连通块合并只用考虑相邻的

记(当前连通块数s1,当前行首尾相接连通块数s2)，发现每次扩展后当前的s2会乘上x，同时s1=>s1*cnt-s2*A，因为K+1层等于把K层放到1层上，1层有A对相邻的，每对会有s2个块合并，而1层有x对首尾相接的，放进去就是x*s2

矩乘优化

agc004

A：如果有偶就是0，否则min(AB,AC,BC)

B：n^2求出合并至多i次的答案bi，求min(i*x+bi)，加入顺序可以安排

C：第1列全红第m列全蓝，中间行交替红蓝，这样红蓝无交且加上紫色后仍连通

D：如果fa[1]!=1则一定不行，因为环>1，任意找环上一个K步后走到1的，往前一步就不合法

所以把fa[1]变成1，然后变成一棵树，树形dp，每次把深度=K-1且当前点不为1的儿子的出边接到1

E：设f[i,j,k,l]表示已经走的路径的四边界，由于爆炸与否只和边界有关，所以往一边扩时贪心把多的走完，因为扩时该爆的已经爆完了，把i滚动即可O((nm)^2)，注意枚举顺序

F：神必题，考虑树的部分分，把树黑白染色黑色放1白色-1，则每次操作会把颜色不同的边的两个颜色交换，最终要把黑白互换，即把1移动到-1上消成0，求(sum_i |sum_i|)

然后考虑环，当为奇环时任意找一条边(x,y)拆开，对改变操作等于在两端同+1/-1，算出加减次数后同树

偶环操作等于一边+x一边-x，最后贡献等于(|x|+sum_i |k_ix+sum_i|)，k=-1/0/1，排序取中位数

构造的证明：主要是两个1不能重合，那么只需要把1移到-1时如果碰到了其他的1，就用当前的1推着往前走

然后可以做到把任意一个1移到-1上了，树随便移，环就不断把(x,y)上的+1/-1移走/移入，然后继续操作

agc005

A：维护1~i操作后剩下的S和T的个数，按顺序加，因为如果 前面操作了的 加后面的 后 也不会改变

B：枚举min，并查集

C：max即为直径长度，先放中间的，放完后大于直径/2都可以无限，分奇偶讨论

D：容斥，硬点|ai-i|=K，发现对于两个ij会冲突当且仅当i=j (mod 2K)，相当于一排数和空交替的序列，i可以把ai放在左/右边，且两个a不能冲突

按%2K分组dp，设f[i,j,0/1]表示当前到i，容斥了j个，当前位置的左边是否放过，转移枚举左右，注意a在[1,n]内

E：如果A能走到一条红边，满足蓝树上dis>2，则A可以在上面反复横跳，此时为-1

否则当A没走到时，红边两端的dis蓝<=2，此时A在以B为根的蓝树的子树内，且B的最优策略一定是往A的方向走

先假设是这样，则A要走到一个终止边，或者走到dis蓝最大的点然后等死，能走到该点的条件是路上的dis红<dis蓝

先假设也是这样，观察到A走相当于在蓝树上跳，且每次跳最多两步，如果A走到某个点满足dis红>=dis蓝，且B没能走到该点，则A一定迫使B往回走了，而A每次最多走两步，无法走出B的子树，所以一定不可能

因此条件是dis红<dis蓝，且B往A走一定是B的最优策略，那么建树求dis然后dfs就好了

F：容斥，算出每个点为根的儿子大小，直接卷（原根5）

这不比A水

agc006

突然自闭

A：枚举，哈希

B：发现如果第二层有两个相同的，则这两个会一直往上直到碰顶，所以在n-1~n+2放<x,x,>x,<x，x=1,2,2n-1特判

C：假设对ai操作，则ai会变为a[i-1]+a[i+1]-a[i]，对a差分发现就是把差分数组交换（几何意义是对a[i-1],a[i+1]的中点对称，结果一样）

维护一轮后每个值到哪里的排列，把环找出来填数，或者直接倍增

D：二分答案，设<=ans为0>ans为1，中位数操作不变，发现如果有两个0/1并列就会在上一层左右扩一格，如果有两块01相碰就不会扩

找到距离n最近的连续0/1即可判断，再判一下01交替的情况，不可能有两个0011距离相同，否则中间01交替后一定有一边更近

E：类似agc003C，把矩阵转化成n个数，每个数有正负，一次交换i和i+2同时把i,i+1,i+2取反

首先先忽略正负，找任意一种方案把数移到对应位上，则剩下部分合法的充要条件是奇偶位的负数个数为偶数

必要性：显然0是偶数，交换奇数位会改变奇数(位)的逆序对个数和偶数的负数个数，最后二者都要为0，即为偶数，而交换偶数为对二者奇偶没有影响，所以当奇数逆序对=0时偶数负数个数至少要为偶数，否则无论怎样交换都有一个>0的奇数

充分性：构造，对i,i+1操作两轮可以把i-1,i,i+1,i+2取反，对i,i+2操作三轮可以把i,i+2（2<=i<=n-3）取反，综合得到可以对i,i+2（1<=i<=n-2）取反，所以可以分奇偶移到头消掉

求逆序对判断

F：把原图中弱连通块三染色（A->B->C->A三个集合），讨论一下：

①染色失败：连通块可以变成完全图

②3<染色成功：是一个点或一个二分图，无法加边

③染色成功：AB,BC,CA间都有边

先证明③，显然操作顺序与结果无关，所以每次加入一个与当前连通块有边的点，发现每次操作后都是一个完全三分图，归纳即可

那么如果染色失败了，就把失败的边先去掉最后加上，则加上后一定直接/间接产生了反向边/自环，当某个点有自环时可以把相连的所有点都搞出反向边，然后搞出自环，最后搞成完全图

agc007

自闭+1

A：dfs找一条路，去掉后判是否还有

B：ai=50000i，bi=50000(n-i+1)，然后对a[pi]减n-i

C：大胆猜想操作一次后的期望距离还是等差数列，列式子得新的第k个的位置：

(large frac{1}{2n}(k(d+(k+1)x)+(2n-k-1)(d+(k-1)x)+(3d+3kx)))

代入k=1，化简得到(large d’=frac{1}{2n}((2n+2)d+5x),x’=frac{2n+4}{2n}x)，期望求和算

D：显然是走一段折返再走，如果对一个位置折返超过一次那不如在原地等

设f[i]表示做完[1,i]的答案，转移i-1->i，或者枚举上次折返的位置j，然后j->j+1->i->j+1->i

可以发现j+1和i之间走了一个环，即第二次j+1->i时每个熊x距产币的时间（第二次-第一次）相等，x->i->j+1->x，所以只用在第二次走熊j+1时等，后面直接走即可收币

转移写出来拆开线段树优化

E：等于从下往上做，每次找到左右子树中两个点连x-t-y的路

二分答案，设f[i,x,y]表示子树i中分别剩深度x,y的两个点，f是否可达，发现如果xy偏序了显然没用，所以改一下维护合法的(x,y)对，维护x增y减，双指针即可

显然归并后由于一个在左一个在右，所以对数不超过2min(sz左,sz右)，总和显然nlogn

乘2是因为可以把对反过来，所以反过来后还要归并，注意此时归并只能保证x单调，y可能偏序，所以要特判弹掉

F：发现可以看作把S中字符往后移，移的过程中留下轨迹，最后得到T

由于移越多越劣，所以对T[i]求出i->1中最大的j满足S[j]=T[i]，贪心找到移过来的S[j]，最后把同一S[j]移到的不同位置合并，即可得到移动方案

问题变成把A[i]移到B[i]位置上，满足每轮移动要从左往右移，即一个数移完后不能超过下个数移动前的位置，发现等于把两个数中间的空往左移，一轮整体移一格，显然超了B[i]无所谓，所以i=n->1，双指针维护，时间O(n)