感谢XZY提供这个页面

日期 题号 第一次提交 结果 做法
20180807 bzoj 1568 WA AC 李超线段树
20180808 bzoj 3938 WA AC 李超线段树
bzoj 3165 WA AC 李超线段树
20180810 bzoj 3160 TLE AC FFT + manacher
20180811 bzoj 4259 WA AC FFT
luogu 3803 AC AC 练习NTT
20180812 luogu 4245 WA AC 3模数NTT
20180816 luogu 4238 WA AC 倍增多项式求逆
20180817 luogu 4245 WA AC MTT(拆系数NTT)
20180818 luogu 4239 WA AC 多项式求逆(MTT合并)
luogu 4512 AC AC 多项式除法
20180819 luogu 4717 AC AC 快速沃尔什变换
bzoj 2875 AC AC 矩阵乘法
hdu 5239 WA AC 线段树+规律
20180820 bzoj 4589 WA AC FWT+快速幂
20180821 bzoj 2229 TLE AC 最小割树(分治+最小割)
20180822 bzoj 5290 WA AC 树形dp
bzoj 1226 AC AC 状压dp
bzoj 2595 AC AC 斯坦纳树(状压dp+spfa)
20180823 bzoj 1190 TLE AC 分层dp
bzoj 3594 TLE AC dp+二维树状数组
20180824 bzoj 3673 WA AC 可持久化并查集
AGC 014E TLE AC set+并查集
20180825 poj 2752 TLE AC kmp
20180828 51nod 1526 AC AC trie+贪心
20180829 zoj 3545 WA AC AC自动机+状压DP
bzoj 2809 WA AC 左偏树
20180830 bzoj 2212 WA AC 线段树合并+可持久化
hdu 6109 WA AC 并查集+set
bzoj 1227 WA AC 离散化+卡常+组合数
bzoj 4552 WA AC 线段树+二分
bzoj 4568 WA & RE AC 树链剖分+线性基
20180831 bzoj 4810 AC AC 莫队+bitset
bzoj 1468 AC AC 点分治
bzoj 1367 WA AC 左偏树
ural 1519 AC AC 插头DP
20180902 bzoj 4881 AC AC 树状数组+set
bzoj 3133 WA & TLE AC 优先队列+倍增
20180904 yzoj 10003 WA AC 拉格朗日乘数法+二分
luogu 4755 TLE AC 分治+树状数组+莫队
poj 3613 RE AC floyd+矩阵快速幂
20180905 yzoj 10005 WA & MLE AC dp+剖分+空间回收
20180906 yzoj 10009 RE AC 分块+可持久化trie

考试总结:

test 2018.08.09

T1:第一眼看上去觉得好简单,但是仔细想了一会后发现根本没有思路,于是硬肝了1h,结果5分暴力滚粗。
T2:维护一个凸包,计算交点位置,根据时间在树上跑倍增。
(想到了正解,结果没时间实现,只打了感觉较简单的60分部分分,结果20分。。)
T3:考场上看到根本没思路,后来看了tj,结果是两个LIS,详情见tj。

test 2018.08.13

T1:最难题(结果还一直硬肝,导致放弃T2的80分做法),打了个暴力有40,还没改,
T2:想到做法并不难,难就难在覆盖的表示方法,可以用异或来表示,再记录一下覆盖的非树边的数量就能求解。
考场上想到了80分做法,但是肝T1去了,只打了个暴力,结果30分。
T3:生成函数题,但是被我找规律过了,可以说运气比较好,留坑,要找时间打打正解。

test 2018.08.14

T1:感觉很有意思,考场上硬肝两小时,想到了70分的$n^2$解方程的办法,然后选择了打T2、T3的暴力,结果没时间打T1的$n^2$了,然后手动模拟输入情况,打了人生中最长的一份代码20分滚粗。

正解:思考dp的解法,$f[i][j]$表示当前甲赢$i$场,乙赢$j$场甲获得最终胜利的概率,易知$\forall i=n,f[i][j]=1$并且$\forall j=n,f[i][j]=0$,因为甲乙水平相当,那么有$$
f[i][j]=\frac{1}{2}(f[i+1][j]+f[i][j+1])
$$
根据此状态转移方程可知,下一场比赛不管是甲赢还是输,其最终胜率的变化量是相同的,这样如果胜率增加就赢钱,胜率减少就输钱,则我们需要构造一种下注方法使得达到最终结果的得或失的钱数为$2^{2n-1}$ ,大胆猜测,当胜率为$\frac{1}{2}$时剩余的钱数为$0$,这样就会简化问题,又据题意,当胜率为$1$时,钱数为$2^{2n-1}$,胜率为$0$时,钱数为$-2^{2n-1}$,因此大胆猜测,当胜率为$\frac{1}{2}+q$时,钱数为$2q*2^{2n-1}$。这样就有了70分正解。

(话说我的70分做法是用之前的结果计算当前应下注的钱占总数的百分比,有点像一个递归函数)

关注这个问题的核心,就是,当前甲赢了i场,乙赢了j场,甲的胜率是多少。假设没有提前结束的情况,剩下的$t=2n-1-i-j$场比赛一定打完。如果甲在其中赢了n-i场或更多,甲就获得最终胜利,所以甲的胜率为$\frac {\Sigma _ {k=n-i} ^{t} ( _{k} ^{t})}{2^{t}}$,考虑其胜率在下一场比完后的胜率,如果赢了,胜率变为$\frac {\Sigma _ {k=n-i-1} ^{t-1} ( _ {k} ^{t-1})}{2^{t-1}}$,如果输了,胜率变为$\frac {\Sigma _ {k=n-i} ^{t-1} ( _ {k} ^{t-1})}{2^{t-1}}$,两者作差,得$(^{t-1} _ {n-i-1})=(^{2n-2-i-j} _ {n-i-1})$,带入dp的结论,可知答案即为$2^{i+j+1}(^{2n-2-i-j} _ {n-i-1})$,统计前缀中甲乙分别赢的次数i,j,然后直接计算即可。

T2:只打了70分暴力,考试中感觉可能最终答案只可能和位置有关,后来看tj中推式子,结果真是。最终答案为$\Sigma _ {j=0} ^ {k} ( _ {j} ^ {x}) ( \Sigma _ {i=1} ^ {x} ( _ {k-j} ^ {k-i})a[0][i] )$,注意到后面括号里是一个前缀和,注意到k很小,而$k-j$只有k个取值,所以用k+1个树状数组维护即可。

T3:只会60分的矩阵树定理,留坑

test 2018.08.15

T1:考场上只写了60分暴力,没想到怎么状压转移。后来看了tj,发现还是自己姿势水平不够,学到了
正解:$f[t][i][j]$表示$t$为叶子节点到根的距离,$i$为树上非叶子节点的集合,$j$为树上叶子节点的集合,枚举$k$,$k$为非树上结点的集合,预处理$j$到$k$的方案数和权值和,然后转移就很容易了。

T2:文件名写错,导致掉了30分暴力,推锅给zsh的自动补全,(逃
正解:首先考虑没有异或和为0的限制条件,考虑一维的情况,如果没有Burnside的限制,那么答案很显然为$2^{n}$,然后考虑到每个情况都能旋转n次,那么就将答案除以n,但是这样我们少算了旋转k次后与自身相同的情况,所以要加回来,于是答案即为$\frac {\Sigma _ {d|n} \phi(n/d) * 2 ^{d}} {n}$,扩展到二维的情况,一个$nm$的矩阵中填0或1考虑循环同构的方案数为$\frac {\Sigma _ {a|n} \Sigma _ {b|n} \phi(a) \phi(b) 2 ^ {nm/lcm(a,b)}} {nm}$,其中a、b为横纵坐标变换的循环节。

如果有异或限制的情况下,2的指数应该发生一点变化,令$l=lcm(a,b)$。如果$l/a$为奇数,指数应减去$n/a$,如果$l/b$为奇数,指数应减去$m/b$,如果$l/a$和$l/b$同为奇,那么指数应该加上1,如果同为偶,则程序有bug。

T3:四位偏序,考场上只打了30分暴力。还没改,留坑

test 2018.09.01

T1:打了个暴力+随机,50分。
正解:按$k$排序,枚举去掉绝对值后括号前的正负情况。

T2:想到了正解,打的也是正解,只有40分,T只因多写了一层循环,那一层循环用$minx$代替就行,动态更新。
正解:$f[i][j]$表示目标串到$i$,文本串到$j$的情况。
转移:
1.$f[i][j]=min(f[i][j],f[i-k][j-k]+c1)$
2.$f[i][j]=min(f[i][j],f[i][j-k]+c2)$
3.$f[i][j]=min(f[i][j],f[i-1][j]+c3)$

T3:A了,裸的费用流

test 2018.09.03

T1:题目描述出锅,不然很多人能拿更高分,没改

T2:将图画出来发现是很多棵环套树。对于树,贪心即可。对于环上的点,已经有一些点被覆盖了,对剩下的没有被覆盖的点,我们只要找一个点从那个点出发,覆盖这个点,然后找下一个没有被覆盖的点,再覆盖……直到没有点不被覆盖,枚举所有这样的点就可以找到最小的添边条数。这里可以用倍增找。

T3;:不会,没改

test 2018.09.05 暴力大赛

T1:scanf读入字符串,再转成long double类,暴力算即可。

T2:预处理一点,然后再dfs。我预处理的1e7,太大,结果TLE

T3:枚举几倍a,判断能否到达S即可。犯了个傻逼错误,每次判断嫌对vis数组memset麻烦,改用cnt标记vis,结果每次判断前初始化了cnt,结果GG

test 2018.09.06

T1:用孙子定理,将$x$表示成$num _ 1+num _ 2+…+num _ n$的形式,其中$num _ i$为$ \prod _ { j = 1 ,j \ne i } ^ {n} p _ j * inv * a _ i$,$inv$表示$ \prod$那一坨在模$a _ i$意义下的逆元。$x$还能表示成$k * M+r$的形式,其中$M = \prod _ {i=1} ^{n} p _ i$,最终答案为$r\% b _ i$,根据前面已经求出的$num$可以算出$x \% b _ i$的值,还可以算出$M\% b _ i$的值,然后对于每个$num$除以一个$M$,此时的$num _ i = \frac{inv _ i * a _ i}{p _ i}$,用$double$将其记录下来,对所有的$num _ i$求和,得到的实数的整数部分即为$k$。

T2:先对所有的自来水厂投放$inf$浓度的魔法物质,跑一遍$spfa$,$dis _ i$表示流到$i$号点的魔法物质的浓度最大值,然后枚举每一条边,找到可以修改的最小量,对于单向边可以修改的量为出水点的$dis$减去边权,双向边则是两端的$dis$减去边权。

T3:对于树,求$lca$就行。对于多一条边的树,先求出一条可以使树中成环的边,考虑三个点走不走这条边的情况,暴力讨论。最后的代码对于一次查询要跑33次lca

test 2018.09.08

T1:裸的完全背包。

T2:想复杂了,打了个带$log$的做法,结果$TLE$。
正解:$dfs$一遍求出以当前节点为根的子树内的最大深度,再跑一遍$dfs$,记录深度最大次大即可。

T3:状态转移错了,$GG$。
正解:构造出转移矩阵,再根据数据高斯消元(雾),得到递推式。
找规律也可,最快的是OEIS,只可惜考试时不能用