AGC_D练习记

By acheing

新坑。。

感觉agc题质量不错啊

比TC题好懂多了

已完成[12/28]…

AGC001

考虑先自己手算几个数据，对字符一样的位置连边。

发现长度为奇数的最多只有两个，且只能在队头和队尾。

构造一下就行了。

AGC002

本蒟蒻只想出了$O(nlog^2_2n)$的可持久化并查集做法。。

说得好像你会写可持久化并查集一样

考虑整体二分

每次维护一个三元组$(l,r,S)$表示S中的ans在$[l,r]$之间

二分一个mid

如果当前并查集添加到的边大于mid，就暴力重建

否则不断添加边，直到mid为止

为什么复杂度是对的呢？。。

因为你最多分治$log(n)$层

每层从小到大更新ans的话，每层只要暴力重建一次就可以了

然后对每个询问分情况讨论一下就可以了

再继续分治下去。

注意：为了保证复杂度，这里要用bfs来分治

AGC003

假如我将每个数字分解了质因数

该怎么算答案呢？

方法是将所有指数模3，再乘起来，与补集中的数的个数取个max

该怎么分解质因数呢？

我们先预处理出$\leq \sqrt[3] {10^{10}}$的质数以及他们的平方。

对于每个数，对前面的数暴力试除即可。

AGC004

水题，首先1必须连1，别的贪心就可以了。

AGC005

神题啊！！
窝只想到了可以容斥DP，再看成个二分图。。然后就不会了
其实这个二分图很特殊，每个点度为0,1,2
这有什么用呢？
这样的话我们就可以把它看成若干条链，DP一下就行了！
注意特判每条链最后一个点的特殊情况。

AGC006

又是一道神题。。
我真是菜到不行。。。
考虑二分答案，将序列里比mid大的设为1，比mid小的设为0
然后一个格子的0/1就是这个格子下面三个格子的众数。
然后你会发现一些性质
设$a[i]$表示第i格是0/1

1. 若$a[i]=a[i+1]=1$那么a[i]上面的所有格子都是1，$a[i+1]$上面的所有格子也都是1
2. 若a中构成了一个01交替序列，则在a上面也不断反向交替。
   然后一顿操作就可以了。

AGC009

我好菜啊。。。
根本想不到。。
对每个点baoyi标一个$v[i]$
$v[i]$表示i点在点分树中以i为根的子树的深度
考虑这个东西在原树中有什么性质？
手模一下会发现，对于两个$v$相同的点，他们的路径上一定有一个$v[k]>v$
这个$v[k]$的意义就是在点分树上k是这两个点的祖先。
对每个点贪心一下就行了！
细节神烦。。

AGC021

考虑DP$f[i][j][k]$表示对于区间$[i,j]$，用了k次变换后的minans

考虑i是否与j匹配，转移即可。

AGC022

好神的题。。

去问了Anoxx才会。。

首先我们知道，Ans=X*2L。

X是这辆火车走了几个来回。

对于每个ti，我们都可以把它除以2L，并把商（向上取整）加入ans。

为什么向上取整？手模一下就知道了。

这样的ans是什么？

是每个商店无脑走一遍的时间。

注意，这时我们没加上走回来的时间.如1 10 8 5，答案是20

设$l[i]$表示一辆车从右往左走，到点i后下车，下次上车时车的方向$r[i]$同理

那么对于一个$l[i]=1$的（表示从右往左走后下次上车往右走）i，我们都可以把她跟一个$r[i]=1$的匹配。每次匹配后ans减去$2*L$

但还有一个情况，最后一个点要从右往左走，ans要加上$2*L$

具体的还是看代码吧。。

AGC026

我们可以发现一个性质，若有一行有两个相同颜色的块，那么下一行只有一种放法
否则下一行有两种方法。
考虑分治：$solve(l,r,lim)$表示l~r中的塔都比lim高的方案（分为有相同颜色和没有相同颜色两类）
算一下答案就可以了。

AGC027

对原图黑白染色，对每条黑对角线选个质数做权值，每个黑点的权值为两个对角线上的权值的积，白点的权值为周围几个黑点的lcm+1.

可以证明，这样的图的点的权值是小于题目限制的。

AGC028

设$dp[i][j]$表示i到j的点中，组成了一个连通块的方案数
容斥一下就可以了。