AGC001

D (1000)

被干了
将一个回文串看做回文串两边的点互相连边,要求最后形成一个联通块

如果奇数块的个数超过两个,就达不到题目要求了。

证明:假设a有X个奇数元素,字符串长度为N,那么连接两点的边的个数为(N-X)/2, b有Y个奇数元素,连接两点边的个数为(N-Y)/2,然后因为要互相都等于,所以边数至少要N-1个,就有(N-X)/2 + (N-Y)/2 >= N-1推出X+Y<=2,可知a最多有两个奇数元素,才能符合题目要求,否则直接输出。
http://2997ms.com/2016/07/20/AtCoder-Grand-Contest-001/

对于合法的情况,我们可以直接构造

E (1400)

求 $\sum_{i=1}^{n}\sum_{j=1}^{n}C_{A_{i}+A_{j}+B_{i}+B_{j}}^{A_{i}+A_{j}}$
被干了
我们可以发现这个东西的本质是求所有点对$(-A_{i},-B_{i})到 (A_{j},B_{j})$的方案数,然后我就一直想怎么求
$$
\left\{\begin{matrix}
a_{i}+a_{j}=x \\
b_{i}+b_{j}=y
\end{matrix}\right.
$$
的对数,然后不会,然后发现,这个东西用第三象限的坐标初始化,在第一象限统计答案,直接dp就完了,

F (1400)

被干了
对于每个点,与他距离小于k的点,在任何时候,与他的大小关系是固定的,同时对于每一个合法的顺序,我们一定能够通过初始状态到达。所以直接拓扑排序即可


AGC002

D (1000)

一开始想的是,先建kruskal生成树,然后二分+倍增来做到两个log,然后有没有更优的做法呢?然后我发现可以整体二分再加并查集维护就好。

E (1400)

将a排序,将这个图形看成柱状图,第i个柱子高度为$a_{i}$,从$(1,1)$出发,那么每次要么向上走,要么向右走。假设0为必败,1为必胜,我们可以考虑到:如果$(i+1,j+1)$为0,那么$(i,j)$也为0,显然$w(i,A_{i})=0$,如果$(i+1,j+1)$为1,那么$(i,j+1)$和$(i+1,j)$不可能都为1,也就是说$(i,j)$为1,所以我们从$(1,1)$开始尽量向右上方扩张就好。

F (1600)

这道题还是属于转化充要条件的高端dp:对于每一个最终序列,你只需要保证每个空白的球后面一定存在一个颜色,使得这个颜色在空白的球后出现过k-1次,那么这个序列就是ok的,那么就是个简单dp了


AGC003

D (1100)

很容易想到将每个数分解过后,将所有的幂模3,这样的话,最终每组相互纠缠的数就一定是两个。取这一组中个数最多的那一个就行,

E (1400)

如果一次询问比之前的询问小,明显之前的询问没有用,所以所有的询问一定是单调递增的
一开始想的是每个状态把每个点用的次数记一下,是$O(n^2log^2n)$的后面发现,由于一开始每个数的顺序是固定的,所以我们只需要记每个数在最后出现的次数即可,复杂度就变成了$O(nlog^2n)$

F (1700)

设a为level-1中黑格子数量

显然只需要考虑上下,左右是否联通,
对于这两个联通情况,分三种讨论:

  • 都不联通:那么答案为$a^{k-1}$
  • 都联通: 那么答案为$1$
  • 只有一个联通: 我们把level-1看做单位格子,答案=最后的黑格子数-最后左右联通个数,最后的黑格子数就是$a^{k-1}$,然后左右联通个数求法如下:
    • 设$f_{i}$表示level i+1的格子左右联通个数,$s$表示level 1的格子内部左右联通的个数,t表示level 1与level 1的格子左右/上下相连的格子数。
      $$f_{i}=a^{i-1} \cdot s+f_{i-1} \cdot t$$
      矩阵乘法即可.

AGC004

C (700)

第一张图将所有奇列和第一行染色,第二张图将所有偶列和最后一行染色就完了。

D (800)

很显然最后$a_{1}=1$,对于所有深度大于k的,他一定是要被修改的。所以我们从下到上

E (1400)

这道题很显然是考虑相对位置,然后我们发现,我们判定一个机器人能不能被拯救时,只需要看,他的位置与我们当前走过的最小/最大的x,y坐标,所以$dp[l][r][u][d]$表示一下当前走过的边界就可以转移了

F (2200/1500)

先考虑1500分段,这是一棵树,想要满足条件的话,每个点难免与他父亲进行操作,所以我们记一下进行操作的个数就ok了,我们设每条边的值来表示这条边两边的点一起操作的个数
再考虑一下2200分段(环的情况),当我们确定一条边的值后,其他值也一定能求出,考虑表示成函数,那就是若干个abs,取中位数即可


AGC005

C (700)

考虑将树的重心作为根就完了

D (900)

考虑一下最后的这张二分图,很明显,这个二分图可以分成2*k条完全独立的链,所以我们只需要考虑在链上dp一下就好了。
f[i]j表示链的前i个节点组合了j对,最后一个点被没被组合的方案数,
f[i][j][0] = f[i]j + f[i][j][0]
f[i]j = f[i][j - 1][0].

再搞一次背包?
f[i][j]前i条链总共组合j次的方案数,每加入一条链,就跑一下背包,注意,所有链的总长为n,所以复杂度还是n方的。

然后就ok了。

$$ ans = \sum_{i = 0}^{n} M_{i} \cdot (-1)^{i} \cdot (n - i)! $$

E (1400)

这道题666.
首先如果对于一个点,存在与他连的一条红边,使得这个点和另一个点在蓝树上的距离大于2的话,并且走到他不会被抓,答案肯定是-1,所以我们就只用考虑长度为1和2的点,就有这样一个结论,Sigma不会走出Sugim的子树,然后完了。

F (1900)

考虑一下对于一个k点i的贡献:
每条边的权值w等于他指向的那个集合的大小
$$ w_{i}= C_{n}^{k}-\sum_{(u,v) \in E} C_{w(u,v)}^{k} $$
$$\sum_{i=1}^{n}w_{i}=n C_{n}^{k} - \sum_{(u,v)\in E} C_{w(u,v)}^{k}$$
考虑$a_{i}表示\sum_{(u,v)\in E}[w(u,v)==i]$
$$ = S- \frac{1}{k!}\sum_{i=k}^{n} \frac{a_{i}i!}{(i-k)!}$$
$$A_{i}=a_{i}i!, B_{i}=\frac{1}{i!}$$
所以只需要计算 $$ ans_{k}=\sum_{i=k}^{n}A_{i}B_{i-k}$$
倒一下B $$ ans_{k}=\sum_{i=k}^{n}A_{i}B_{n+k-i}$$
$$C_{n+k}=\sum_{i=1}^{n+k}A_{i}B_{n+k-i}$$
直接fft即可


AGC006

C (800)

考虑差分,那么问题就变为置换了。

D (1300)

一个套路:二分后转化为0/1判定问题,在这道题中就是二分出一个x,看最后的数是不是小于等于x的,第一个小于等于x的就是答案。

E (1500)

首先将奇偶分别看为一个集合,使用手模拟一下,会发现每次你能够进行两种操作,第一个是使集合中相邻的两个元素翻转,第二个是交换集合中两个相邻的元素,并且使另一个集合中的元素翻转,统计逆序队即可。
这种题一般是看交换的一般结果,然后继续找。

F (1700)

把(x,y)想象成一条边,那么考虑一下这张图,将这张图染成三色图,如果能够成功染,说明点与点之间都有边,否则说明,不同颜色的点之间有边


AGC007

C (1000)

坑逼题+神题啊,I good vegetable a.
这道题大概的思想是,由于期望的线性性,我们可以每次可以用第i段的期望长度来组成新的序列。然后新的序列仍然等差

考虑第$i$个球,他左边是第$2i-1$条边,右边是第$2i$条边
如果他向左滚动,
那么$t \in [1,2i-3]$的边长度不变,仍然是$d-x+tx$
$2i-2$这条边变成$3d+(6i-6)x$
$t \in [2i-1,2n-2]$的边加上$2x$,变成$d+x+tx$
如果他向右移动,
那么$t \in [1,2i-2]$的边长度不变,仍然是$d-x+tx$
$2i-1$这条边变成$3d+(6i-3)x$
$t \in [2i,2n-2]$的边加上$2x$,变成$d+x+tx$

考虑第$i$条边
在$2n$种情况中有$2n-i-1$种会使$d-x+ix \rightarrow d-x+ix$
在$2n$种情况中有$1$种会使$d-x+ix \rightarrow 3d+3ix$
在$2n$种情况中有$i$种会使$d-x+ix \rightarrow d+x+ix$
即第$i$条边长度的期望为$$\frac{2n-i-1}{2n} (d-x+ix)+\frac{1}{2n}(3d+3ix)+\frac{i}{2n}(d+x+ix)$$
$$= \frac{n+1}{n}d + \frac{2ni-2n+1+4i}{2n}x$$
$$= \frac{n+1}{n}d + \frac{-2n+1}{2n}x+ \frac{n+2}{n}xi$$

D (1200)

$$f[i]=min(max(T + a[i] - a[j], 3(a[i] - a[j]))+f[j - 1]+a[j]-a[j-1])$$
将中间的Max拆开,分别讨论。

  • $2(a[i] - a[j]) > T$
    $$f[i]=min(3a[i]-2a[j]-a[j-1]+f[j-1])$$这个维护个前缀就行。

  • $2(a[i] - a[j]) < T$
    $$f[i]=min(T+a[i]-a[j-1]+f[j-1])$$这个维护个单调队列就好了

E (1400)

首先二分答案,然后对于每个子树,维护子树每个被访问的第一个点,最后一次访问的深度最小的点是哪个,用点队$(x,y)$表示。对于两个子树,可以考虑归并来合并,每个点合并后集合的大小$|S|=2min(|S_{L}|,|S_{R}|)$
拆开后,这个式子的意义可以理解为$|S|=2^{子树内叶子的最小深度}$,考虑每次拿掉最小叶子,那么$T(n)=\sum_{t=1}{T(\frac{n}{2^t})}+O(n)$,暴力拆几层,然后归纳归纳,就能得出复杂度是$O(nlogn)$的,再加上二分那么总复杂度就是$O(nlognlogANS)$的,然后我懒,没有打归并排序,所以就又加了一个log

F (1500)

这道题很显然就可以把整个过程可以看成一个折线图:
折线图(感谢ccz)
所以我们直接开个队列维护即可。


AGC008

D (800)

很简单的构造。

E (1400)

考虑一下a,那么a一定是一个环套树森林,在a中的每个联通块中的点在p中一定同属一个环。
考虑每个环套树,他一定不能与其他的东西合并,并且每条支链一定为直链,然后对于环上每个有支链的点,讨论一下相邻支链之间的距离,就可能有0,1,2这三种情况,乘法原理即可。然后对于环的话,我们可以将相同大小的合并,也可以直接就$a_{i}=p_{i}$这个就是个组合数,然后我们还可以将大于1的奇环”开方”,

F (1900)

先考虑所有点都为关键点时的情况
$F(x,d)$表示x延伸d得到的点集,我们不考虑全集,设对于集合S,所有的$F(x,d)=S$的最小d为d’,那么满足$F(x,d’)=S$的$x$唯一,所以统计关于一个点x的所有方案时,我们需要确保他的“d”一定是最小的,然后随便在纸上画画,设他的次大高度的儿子的高度为$h_{x}$,那么很显然,他能够取的d为$[0,h_{x}+1]$,
当一个点不为关键点时,我们需要找到这个点所有的儿子代表的包含关键点的子树中最小的高度$p_{x}$,答案减去$p_{x}$即可。


AGC009

B (800)

树形贪心

C (1100)

随便dp

D (1400)

考虑将最后每个点的标号写下来,那么问题就可以转化为,任意两个相同的标号间一定有一个更大的标号,求最小的标号

E (1600)

(枚举用了多少个K)本质是将m个球装进t=(n+m-1)/(k-1)个盒子,每个盒子的数量大于等于0,小于k-1,每个盒子本质相同,球本质不同的方案数直接dp就完了.
$ f[i][j]=\sum_{p=1}^{k}{f[i-1][j-p+1]}=\sum_{p=0}^{k-1}{f[i-1][j-p]} $


AGC010

C (700)

先取一个叶子的父亲u,那么他脚下的儿子两两之间组成点对的的方案数为$\sum_{i\in son[u]}w_{i} - w_{u}$一直计算就完了。

D (1000)

博弈题Orz
http://blog.csdn.net/werkeytom_ftd/article/details/78233136
https://szy.fun/2017/09/29/agc010d/

E (1600)

想了一部分。。。
很显然两个不互质的点的相对位置不变,所以我们不妨连一条边,然后对于同一个联通块,我们肯定要尽量取最小的点,所以我们将边按指向的点的大小从小到大排序,一直dfs下去。这样的话每个联通块都是一个有向无环图,然后我们再跑拓扑排序,每次拿最大的点即可。

F (1600)

看这道题的第一眼我的想法是考虑所有度为1的点,如果与他相连的点比他大,那么先手必赢,从这个,我们很容易推广到,对于一个点,如果所有与他相邻的点都是大于等于他的,那么这个点必败。否则这个点只能向比他小的点走,所以我们直接按权值从小到大扫一扫每一个点就好了。


AGC011

C (800)

考虑一下原图的每个联通块,不考虑大小为1的,如果一个联通块无奇环,设他权值为2,否则权值为1,考虑不同联通块之间的答案,很显然贡献为1,相同联通块的答案就等于他的权值。
也就是说如果权值为1的联通块个数为a,权值为2的联通块个数为b,他们之间的答案为
$a^2+2b^2+2ab$
然后如果大小为1的联通块的个数为c,那么答案还要加上$c(n-c)2+c*c$

D (900)

稍微模拟一下就会发现,其实操作是这样的:如果第一个元素为’A’,那么将它变成’B’,否则将整个序列左移并在末尾添上’A’,很容易看出不超过2n次,这个序列就一定是’BABABA…’这样的形状了,直接暴力模拟即可

E (1300)

我的内心毫无想法。
一个数位单调递增的数是可以拆成若干个数位全为1的数的,如果最后的答案为k,那么
$\sum_{i=1}^{9k}\frac{10^{a_{i}}-1}{9}=N$
$\sum_{i=1}^{9k}10^{a_{i}}=9N+9K$
这个K可以二分。很显然直接把a表示成9N+9K的各位就好了。(其实这个K好像直接暴力就OK了,因为进位是均摊O(1)的


AGC012

C (1000)

构造题,考虑一下我们先输出一个1~n的排列,再依次输出1,2,3,4…n,很显然最后的方案数等于前面的排列的上升子序列数,考虑从小到大加数,加在首的贡献会让原来的答案加一,加在尾的贡献会让原来的答案乘二,直接递归就完了。

D (1000)

考虑将能够互相交换的点连边,很显然每个联通块的点都能相互交换,相互独立,所以最后组合数计算即可,考虑怎么连边。
根据限制条件,我们发现,对于相同的颜色,我们只需要取这个颜色重量最小的那个和其他点连边就行了,对于不同的颜色,我们只需要取所有颜色中重量最小的点i,和i颜色不同的重量最小的点j和别的点连边就好。

E (1000)

很显然这个就是跳来跳去,每次将一个联通块覆盖。(强迫必须第一次跳某个联通块)
很显然v的所有可能的权值只有log个,所以我们可以先预处理对于v的所有权值,每个点所在的联通块,然后状压,就可以判断了。


AGC013

C (700)

考虑每个点,很显然我们只关心其他点的位置,而不关心具体编号,所以说”两个点相遇后交换方向”是没有任何影响的。这类经典的蚂蚁碰撞问题主要依赖于下面这两个定理
定理1:如果忽略个体之间的差异, 那么每个物体的运动可以看作是独立的。
定理2:如果不忽略个体之间的差异, 那么物体之间的相对顺序不会发生改变。
也就是说我们考虑在直线上移动的话,对于第i个点,我们直接求最后从左到右第i个点的坐标。
那么放到环上的话,唯一需要注意的就是,当有点经过参考点时,所有点的坐标都会移动。

D (900)

(任意时刻,球的数量都为n)考虑每一种方案中,黑球的数量的变化,一定是一条直线,由于初始时,黑球的数量自定,也就是说我们是可以平移这条折线的,我们考虑将这条折线平移到最下面,然后对于每种方案,只统计他在最下面的那条折现即可。

E (1600)

好神的模型转换Orz

将原问题的模型稍微修改一下
现在有n个连续的空格,其中左边界和右边界必须放置隔板
可以在两个相邻空格摆放隔板,可以在空格内放红球和蓝球
需要统计,有多少种不同的方案,满足:
每相邻的两块隔板之间都恰好有一个红球和一个蓝球
隔板不能摆放在有标号的地方
两种方案不同,当隔板的摆放不同或隔板间红蓝球分布不同
隔板的摆放对应正方形的划分,红蓝球的摆放对应正方形的面积
因此总方案数对应着美丽度之和
那么定义$f[i][j]$为考虑前$i$个空格,
从最后一块隔板到现在已经摆放了$j$个球的方案数
不同的空格只有三类,每类可以写出固定的转移方程
第二维状态只有3种,因此可以使用矩阵乘法优化转移
$O(3^3Mlog2N)$


AGC014

D (900)

当且仅当二分图存在完美匹配时后手必胜,充分性显然,必要性的话,你每次找一个度为1的点,将他的父亲染白,很显然要让后手胜的话他的父亲只能有这一个儿子,那么就必须将这个儿子染黑,然后很显然是可以将这两个点砍掉的,一直下去…将每次砍掉的两个点匹配,很显然这就是一个完美匹配。

E (1400)

任意一个时刻,当前的红边与蓝边组成的都是一颗树,倒起考虑,我们可以发现每次取的红边一定满足,两个端点之间的蓝边只剩一条,考虑维护红边联通的集合,也就是说,我们每次只需要考虑同时有红边和蓝边相连的集合。
所以这个问题就转化为:每次找一对集合,使得他们之间有一条红边和一条蓝边相连,考虑合并A,B两个集合的时候,会产生新的一对的情况:与A集合有红边相连,且与B集合有蓝边相连。与A集合有蓝边相连,且与B集合有红边相连


AGC015

C (700)

由于这是树,所以很显然只考虑每个矩形的边数和点数就行了,直接二维前缀和。

D (900)

从高到低找到一个A,B不相同的二进制位,设为第r位
那么所有大于该二进制位的位都是没有用处的.可以直接删除.
这时我们把所有的数分成两个集合:
$X:[A,2^r),Y:[2^r,B]$
如果设k为B中第一个小于r的为1的二进制位.那么有:

只用X集合的数可以组合出 : $[A,2^{r})$
只用Y集合的数可以组合出 : $[2^{r},2^{r}+2^{k+1}−1]$
必须同时使用$X,Y$集合的数可以组合出 : $[2^r+A,2^{r+1}−1]$
所以直接加上$[A,2^{r+1}−1]$再判一下和$(2^r+2^{k+1}−1)$和$(2^r+A)$的关系减一下就好了
参考自Sky_miner

E (1200)

对于一个点x,考虑一下哪些点变成Aoki后,X也能变。很显然是”数轴上在X左边,速度比X大的坐标最小的点”到”数轴上在X右边,速度比X小的坐标最大的点”.因此每个点对应一段区间。现在的问题就变成了“有若干个区间,要求每个区间至少有一个点被覆盖,求覆盖点的方案数”,然后不可做
我们再换一个角度,考虑一下x变了后,哪些点也会变,我们会发现这些点在速度上是形成一个区间的,即在x的左边速度最大的和在x右边速度最小的。这样就变成了区间覆盖的方案数。就很好搞了


AGC016

B (700)

简单题,不解释。。

C (700)

这个大矩形可以看做小矩形的不断复制,平移。。我们将小矩形的左上角设为1e9-1,右下角设为-1e9就好了。

D (1000)

a和b再加一个位置存放a和b的亦或和,每次操作的本质是交换。所以对于a[i]!=b[i]将他们连起来就好,最后答案就等于联通块个数和a[i]!=b[i]的数量。

E (1400)

没做出。。我们定义一个点i在j时刻的存活集合表示只要这个集合中的所有点在j时刻存活的话,在最后i这个点也能够存活的最小的集合。很显然这个集合是可以倒推的,然后我们可以推出每个点在最开始的时候的存活集合,那么如果两个点的存活集合是没有交集的,说明这两个点在最后可以同时存在。


AGC017

D (1100)

真是玄学的博弈啊,我也不知道自己懂没懂,看了看《组合游戏略述——浅谈SG游戏的若干拓展及变形》,发现我们是定义$sg(g)=sg(g’)+1$.也就是说,对于g’能到达的每个状态,我们在g中的对应的那个状态中加上1,然后(g,g’)这条边对应0,然后这样的话,我们很显然是可以把每个儿子代表的子树拆成子游戏的,所以亦或一下就好了


AGC018

B (700)

简单题

C (800)

简单题

D (1100)

考虑每条边最多被用”他两边的联通块的较小块的大小”那么多次,然后令重心为根就可以构造方案


AGC019

C (900)

一开始没看到所有喷泉的x,y都各不相同,然后gg。知道了这个过后显然LIS就行了

D (1000)

简单题

E (1400)

考虑一下最后交换的情况:(a,b)表示在a,b中这个位置是否为1
$(1,0),(1,1)$ 这个肯定凉了
$(1,0),(0,1)$ 这个没有问题,并且以后不会出现与这个相关的
$(1,1),(1,1)$ 这个没有问题,完全可以忽略
$(1,1),(0,1)$ 这个没有问题,只是第一个位置变为0了,会不会GG看后面的
所以我们考虑一下什么时候不会GG,最后只要是形成的$(0,1)(1,1)(1,1)…(1,1)(1,0)$的这条链
我们可以进一步发现,最后一定是被划分成若干条$(0,1)(1,1)(1,1)…(1,1)(1,0)$这样的链,然后我们可以dp,f[j][i]表示用了i对(1,1)(1,1),j对(0,1)(1,0)
$$f[i][j]=f[i-1][j] \cdot i \cdot i+f[i][j-1] \cdot i \cdot j$$
$$ANS=\sum_{i=1}^{x}f[y][i] \cdot g(x-i)$$
$$g(i)=C_{x}^{i}C_{x+y}^{i}(i!)^2$$
$g(i)$就是$i$个自由的$(1,1)$组合的方案数,$C_{x}^{i}$表示选i个出来,$C_{x+y}^{i}$表示选i个位置
$$ANS=\sum_{i=1}^{x}f[y][i] \cdot C_{x}^{x-i}C_{x+y}^{x-i}((x-i)!)^2$$
让$f[i][j]=(i!)^2 \cdot (j!) \cdot h[i][j]$
$h[i][j]=h[i-1][j]+h[i][j-1] \cdot i$
$$ANS=\sum_{i=1}^{x}(y!)^2 \cdot (i!) \cdot h[y][i] \cdot C_{x}^{x-i}C_{x+y}^{x-i}((x-i)!)^2$$
$$=(x!) \cdot (y!)^2 \cdot (x+y)!\sum_{i=1}^{x}\frac{h[y][i]}{(y+i)!}$$

(h也可以ntt计算

F (2000)
挺有趣的一道题,看wxh的题解吧。


ARC058

D (400)

$ANS=\sum_{i=B+1}^{W}C_{H-A+i-2}^{i-1}C_{w-i+a-1}^{w-i}$


ARC062

E (900)

枚举相对的面就完了

F (1300)

把所有的桥删掉,答案可以直接乘法原理算.
简单环,根据$Polya$,$ANS=\frac{1}{n}\sum_{i=0}^{n-1}k^{gcd(i,n)}$
复杂环,画一画,不难发现是可以任意交换的,这个问题就相当于把n个相同颜色的球放在k个盒子里,盒子可以为空,求方案数,那就是$C_{n+k-1}^{k-1}了$
所以这道题求求点双就完了


ARC063

E (800)

维护一下每个点的范围就完了

F (1600)

这个矩形一定是由四个点来定住的
N^3 做法:枚举上下边界,考虑y坐标在其中的点,找到相离最远的两点。
N^2logn做法:枚举上界,依次枚举下界,每次更新相距最远的两点
N^2做法:枚举左边界的那个点,然后依次枚举他右边的所有点,算出上下界。
然后不会了。
看题解的第一眼:答案至少为Max{W,H}+2,说明矩形至少与x=H/2或y=W/2相交,这说明如果我们考虑过分治算法的话实际上分治的那个log可以省掉(然而我还没有想到成熟的分治做法。
我们直接时候分治做法吧, 考虑每个点,我们处理他作为上端点后,将他作为下边界来维护,那么这样的话,一定是一个单调的东西,考虑修改,一定是某一端完全被削平,这个时候,我们只需要保留栈中最后一个点即可,然后为了单调性,开两个栈就好(这就是分治的意义吧。
总结一下,这道题非常的好,打破了我原来做过所有题的对分治思想的固化,这个思想应该和字符串分治相关的差不多,利用中间多了一个分界线,来优化复杂度!


ARC064

F(1000)

f(n)表示长度为n的不能被表示成两个回文串的回文串个数。
考虑一下这个回文串的最小拆分那么
$$ ans=\sum_{d|n}f(d)*d $$
$$ f(n)=k^{ \left \lfloor \frac{n+1}{2} \right \rfloor }-\sum_{d|n,d<n}f(d) $$
然后我们可以发现统计答案时如果d为偶数,那么是被算了两次的。所以偶数时要除以2


ARC065

E(900)

就是统计每个点的度数,然后维护一下联通块就完了,STL大法好。

F(900)

f[i][j]表示前i个,用了j个1的方案数,有的dp,转移是需要记一下额外的信息的。


ARC066

E (900)

一个很重要的性质就是括号不超过两层,所以直接dp

F (1400)

分治,是我老了,还是不够熟练?
我们考虑先直接斜率优化dp。
然后考虑分治求出每个点必选时的最小值。
$f[i]=max(\frac{max(2f[j]+j^2+j-2ij+2T[j])-2t[i]-i+i^2}{2}, f[i-1])$
$x[i]=i,y[i]=2f[i]+i^2+i+2T[i]$
$f[i]=max(\frac{max(y[j]-2ij)-2t[i]-i+i^2}{2}, f[i-1]), \frac{y[j]-y[j’]}{j-j’}>2i$

$f[i]=max(\frac{max(2f[j]+j^2-j-2ij-2T[j])+2t[i]+i+i^2}{2}, f[i-1])$
$x[i]=i,y[i]=2f[i]+i^2-i-2T[i]$
$f[i]=max(\frac{max(y[j]-2ij)+2t[i]+i+i^2}{2}, f[i-1])$


ARC067

F (1000)

走过的餐馆一定形成一段区间,考虑枚举区间的左端点即可。


ARC068

E (700)

简单题

F (1200)

$f[i][j]$表示,填了i个数,最小数为j的方案数



ARC069

F (1200)

我也太sb了,二分后很显然是个2-SAT问题,然后一看就是线段树优化建边.

ARC071

F(1000)

直接dp用个前缀和优化就好


ARC072

E(900)

没有独立想出
很好的思维题,首先这个东西是有对称性的,所以我们直接考虑当前与终点的距离,然后很明显要算出经历了1~i-1的操作后到达的状态,再算出使得i~n的这些操作结束后仍不能到达终点的最小值,这个东西可以发现很好转移,它有两种转移,第一种是(x->x+d),第二种是(x->d-x),第三种是(x->x)很明显第二,三种要求x< d/2,然后这个很显然最小的永远是最优的。

F(900)

没有独立想出
考虑一下对于每个i结尾用的水,这个东西一定是一个单调的

这个东西很值得反思

这道题会了后感觉挺简单的,但我为啥就想不出来呢。
这种看起来有单调性的东西,同时为了满足某个东西不得不将一些较小的东西保留下来,是可以考虑一下单调队列的


ARC073

E(700)

假设S集合的最大值为最大的那个数,枚举T集合的最小值即可。

F(900)

线段树维护两种状态


ARC074

E(800)

没有独立想出
f[a][b][c],这类颜色相关问题,一般可以考虑每种颜色最后(前)的出现位置。

F(800)

很显然的最小割模型


ARC075

F(800)

爆搜


ARC076

E(700)

很显然,只有在边框上的点对才有用
一开始想的扫描线,有个更简单的办法, 将所有点逆时针排序,然后栈维护就好

F(1000)

没有独立想出
Hall定理来进行二分图最大匹配:
$ 设最小匹配不了的点个数设为p,那么最大匹配的个数就是|X| - p, p等于max (|x| − Γ(x)) $ , $ 其中x是X部的任意子集,Γ(x) 是和x相连的Y部的点的个数. $


ARC077

E(700)

简单题,扫一遍就完了

F(1100)

没有独立想出
考虑 $ f(S) $ , $ T $ 为 $ S $ 的一个前缀,且 $ |T| $ 为 $ S $ 的最小周期,那么 $ f(SS)=STST $ , $ 10^{100} $ 暗示我们最后是很长的,只需要注意前缀即可,那么我们直接考虑 $ g(S)=ST $
继续考虑 $ g(ST) $ 当 $ |T| | |S| $ 时, $ g(ST)=STT $ ,否则 $ g(ST)=STS $
即 $ |T| | |S| $ 时 $ ans=TTTTTTTTTTTTTT… $
否则 $ S的变化为(S,ST,STS,STSST,STSSTSTS…) $ 可以发现每次添加的数为 $ T,S,ST,STS,STSST $ 明显的fib形式,所以直接暴力计算即可


ARC078

E(800)
交互题,二分就好。
F(900)
没有独立想出
不难的dp,f[S][t],表示S集合,1~t只有一条路径的最小花费,考虑当前联通块的形状,一定是1~t为主路径,然后分出去很多东西,然后我们每次考虑枚举与t联通的点就好,当然有可能t是孤零零的一个点,这就是另一种转移了


ARC079

F(800)
环上每个点只有两个取值,枚举其中一个点的取值就完了


ARC080

E(800)
线段树+堆维护就完了
F(1200)
没有独立想出
Orz….考虑将序列差分,那么就是每次改两个点的问题了,对每个点对单独讨论:
若|i-j|是一个奇素数,操作次数为1。

若|i-j|是一个偶数,操作次数为2。

若|i-j|是一个奇合数(或1),操作次数为3。
所以我们要让第一种点对尽量的多,这就是一个二分图最大匹配的问题了
写得详细的见
http://www.cnblogs.com/onioncyc/p/7352408.html


ARC081

F (700)

我特么怎么就看不出结论:很显然任意一个2*2的矩形,里面黑色格子为奇数。


ARC082

E (700)

一开始想了个维护三角剖分的dp,后面发现了一个更简单的方法,就是答案就相当于统计每个凸包内的子集数,这些”子集和凸包上的点的并”一定是互不相交的,也就是说最后的答案,就相当于有面积的点集的数量,所以我们统计直线就完了。

F (700)

维护沙漏,简单的线段树


ARC083

E (700)

一开始想的是f[i][j]表示以i为根的子树中,与i不同颜色的点的权值和能否为j,后面发现其实这只是简单的判定性问题,于是只需要f[i]表示以i为根的子树中,与i不同颜色的点的权值和至少为多少就好了

F(1200)

很妙的计数(包括实现)
考虑x->y连边,那么每个联通分量为一个环套树,只有环上的点有两种情况,dp一下就完了。