RT
突然感觉一道题写完贼容易忘
所以写一下做法粘一下题解链接
本博客第二篇与学习有关的博客
预感咕咕咕
由于懒所以没有写Latex的公式符号QAQ
已经咕咕咕了QAQ
AGC007
C
一看就很神仙QAQ人类智慧题
把它变成2*n个区间,每一次删去两个点并且在答案里累加两个点距离的期望,首项和公差可以直接往下推期望值但是不会证明QAQ
E
比上面那个看起来好点QAQ虽然我也只会看题解
首先是二分转成判定性问题,然后设dp[w][a][b]表示从w出发向子树内走花费a,回到w花费b的状态,转移显然,然而只去除无用的取值仍然状态数爆炸QAQ,这个时候发现对于一个点w,如果有两个状态[a1][b1]和[a2][b2]并且a1<b1且a2<b2,那么后一个状态就没用了QAQ,所以这样处理之后状态数就可以了虽然不会证但是好像状态数是O(n)的
F
肥肠玄妙QAQ
把字符串抄写看成二维的图,用队列保存需要拐弯的点然后求答案QAQ
因为不会言传所以这么短QAQ
AGC008
D
不难QAQ正着填一遍反着填一遍就好了QAQ
AGC009
B
首先赢了自己的向自己连一条边然后从底到上给儿子排序一遍就好了QAQ
C
一开始想了一个玄妙的线段树定义状态的做法然后没想出转移于是放弃了QAQ
首先判掉无解,设dp状态为将当前数分到分隔较大的集合的方案数,然后发现可以转移的上一个状态是一段区间QAQ,然后前缀和就可以了
D
点分树最小深度QAQ
还不会淀粉质QAQ建议看题解QAQ
那为什么来做这个题啊喂
AGC010
C
litble的题解很有意思QAQ
另外这里有一个结论:多个集合里的物品配对可以完全配对的条件是物品总数是偶数并且没有一个集合大小超过总数量的一半QAQ
D
这题总觉得哪里讲过然而忘了
考虑把情况按照奇偶数的数量的奇偶性分类,然后分几种情况讨论一下就好了QAQ
博弈论题总是很像结论题QAQ
AGC011
D
一开始找了一个贼鬼畜的规律最后wa了QAQ
实际上发现每一次如果开头是A那就弹回去,是B就去头把后面取反再在后面加个A这样就好了QAQ
然后洛谷题解里面有人就这样暴力A了这题
事实上发现2n次后这一列一定会变成...BABA这样的形式,于是k大于2n时先用上面的方法跑2n次然后如果n是奇数就特判一下就好了QAQ
AGC012
C
构造方法有好几种QAQ个人觉得上面这个最好理解了
D
O(n^2)建边连通块还是不难的QAQ
然后发现建边的时候只有每个颜色最小值之间和同颜色之间连边是必要的并且只有全局最小的那个球所在连通块有贡献,然后就可以做了QAQ
然后发现并不用实际建边
E
鬼知道会是状压dp啊QAQ
如上,发现v的取值只有大概logv种,于是先处理每个点在某个v的取值上可以达到的最左端和最右端,然后状压dp出用了哪些取值时能达到的最左最右,然后再用一开始的位置的左右边比较有没有并起来可以完全覆盖的方案就可以了QAQ
讲的好鬼畜
还是扔篇别人的题解
AGC013
C
模型转化然而原模型我都不知道QAQ
首先两个蚂蚁相遇可以直接理解成编号交换,然后发现链上的话相对顺序一定不变,环上的话比链多了一个要知道第一只蚂蚁的位置,于是在每只蚂蚁每次l-1->1或1->l-1的时候统计一下就可以知道第一只蚂蚁的位置了QAQ
统计次数的时候边界条件有点烦是真的QAQ
D
首先当然是naive的n^2想法啦QAQ
上面的n^2的问题是因为会算重,于是尝试去重,发现所有折线可以通过只计算中间到达过黑球数为零的状态得到,于是多记一维是否到达过零就可以了QAQ以及先取黑球再放球进去再拿白球也算到了零QAQ
AGC014
D
通过看题解可以发现只有树有完美匹配的时候后手才能赢否则先手就能赢QAQ
具体证明的话扔个题解
其实结论不难找QAQ然而还是没找出来QAQ
E
最近第一道有点码量的题结果调了好久QAQ
发现每次删的蓝边只能被红边覆盖一次否则不能删,于是每一次找一条满足的边删掉,然后发现树剖于是直接上就是了,记得维护覆盖的红边的编号
连线段树都打错了QAQ
好像别人还有其他的做法比较简单QAQ自己去找题解吧
AGC015
C
没有看题解居然写对了QAQ
洛谷的题解就可以了QAQ二维前缀和有点难写然后要注意边界上的情况QAQ
D
此题建议阅读英文题面QAQ
我一开始想了半天数位dp...
事实上是得到三个值区间QAQ
具体扔个题解
E
首先无穷久之后每个人的顺序是按速度排的,然后发现每个点能影响到的点是一个区间,证明的话洛谷上的题解说可以反证,不过想了一下应该也可以分类讨论一下,然后区间覆盖的dp就很经典啦QAQ
说起来不太难,代码还是比较长的QAQ
AGC016
B
感觉不难想QAQ然而还是差一点QAQ
分类讨论,具体看洛谷题解就可以了QAQ
C
wdnmd2-1e^9/(w*h)
先贪心构造,每w*h放一个大负数其余放1,然后发现不行QAQ,于是其余放k大负数变成,于是就做完了...
...个鬼QAQ
一开始用了2,然后发现会wa,然后试了各种各样的值发现不判都会wa,然后发现刚好用500不判才能过QAQ
awsl
D
后面不会做QAQzbl
可以把洛谷题解和这篇题解都看一下QAQ
E
感觉贼神仙QAQ
先算出一只鸡最后要活着要保证哪些鸡在最后时刻之前必须要活着,然后再判断两只鸡的要求有没有矛盾QAQ
说起来简单想起来难QAQ
AGC017
D
博弈论题QAQ又是我不会的经典结论
一句话:sg(i)=xor(sg(son)+1)
证明的话看这篇题解