2018.08.09

t1 (已改)
一开始以为是只能改变一堆石子 这样就很简单了 然后看了看样例 发现还可以拿其他地方的石头 然后我就写了个5分代码弃了
t2(已改)
有20分的暴力和10分的特殊点可以拿 但是交的时候忘记把调试的代码删掉了 导致这题全挂
t3 (已改)
我把子序列认为是要求位置连续的序列了 然后暴力还挂了15分

2018.08.10

题号 算法
洛谷2939 [USACO09FEB]改造路 分层图最短路
洛谷1070最优贸易 tarjan缩点+dp

2018.08.11

题号 算法
bzoj3671 [Noi2014]随机数生成器 模拟+贪心

2018.08.12

题号 算法
codechef-PRIMEDST 点分治+fft快速统计
bzoj3456城市规划 生成函数+多项式求逆

2018.08.13

题号 算法
bzoj4001[TJOI2015]概率论 考虑如何由n-1个点的树生成n个点的树 还有贡献

llx的讲课结束了 首先知道了 一类递推方程的化简 普通生成函数 多项式求逆 ntt 对多项式乘法有了一个感性的理解 打代码不再靠背

还要学习的有 高等数学相关 多项式求exp ln 除法 主要是数学不然很多公式推不出来

然后今天的考试 三道题都没有什么好的想法 然后题解也是很数学的内容 复习了一下之前的内容终于能流畅的看懂题解了

t1 (已改)

莫比乌斯反演+多项式

t2 (已改)

考虑删一条或者两条树边 删一条就要删掉唯一的返祖边 两条要保证切出来的是孤链

t3 (已改)

先考虑子树大小的总和 最后除个卡特兰数就可以了
设 $g_n$ 为这个值那么
$$
g_n=nC_n+2\sum_{i=0}^{n-1}C_ig_{n-i-1}
$$

即枚举$1$的左右子树的大小对$g_n$的贡献
然后推一推就有
$$
g_n=4^n-\frac12\binom{2n+2}{n+1}
$$

2018.08.14

题号 算法
bzoj3028食物 生成函数
bzoj3771Triple 生成函数

今天继续搞之前的生成函数内容

2018.09.05

做题顺序T1->T2->T3

T1

没什么好说的 用高精度存数然后重载乘法和小于号即可

T2

用线性筛搞完​的数据之后就在找规律 不过其实​和​之间并没有什么规律 这题只要暴力搜索即可 因为​大概是​ 而且​

T3

一定是有解的 而且最多添加5个数字即可 因为将a乘100000然后在末尾配数字即可证明是一定有解的 而且数据随机 枚举a的倍数然后枚举等差数列暴力判断即可

总结

3道暴力题 没什么想法也可以想想怎么骗分 可能就对了

2018.09.06

T1

直接crt就可以有很高的分数了 但是我不会crt 赶紧学一波

T2

跑一遍spfa之后 对每一条边考虑即可

注意:在有自环和重边的时候spfa要小心用vis标记

T3

这题也是水题

注意:对环的处理要注意环头的信息

2018.09.08

今天感觉是在梦游一样

T1

就是很裸的完全背包dp 我以为是要用单调队列优化 然后想了很久用了二进制拆分??

T2

一开始想到了是一个换根dp 然后我打了一会发现好像有问题 然后看了看时限和数据觉得可以过 主要是nlogn的算法很稳 不会打挂什么的 然后我就打了 然后这个时候就用了两个小时了

T3

这题明显是要用矩阵优化dp 首先就要求出递推方程 然后一直想到考试结束

总结

最后还在编译源代码的时候把t1的代码删了 最后几分钟赶紧写出来 所以写完要存备份

做题的时候要想清楚一点 想清楚再做

2018.09.10

T1

到结束的时候想了一个暴力,没时间打了,其实暴力就是正解

T2

很容易的dp题,一下就想出来了

T3

没有考虑循环节的情况,而这是解题的关键,不然就要用矩阵快速幂,

总结:

注意各种条件,调整联赛思维

2018.09.13

T1

好眼熟,是百度之星的原题,枚举一下最大值然后容斥一下即可

T2

第一样感觉是点分治,用半个小时打了一下发现开O2都要跑3s左右,然后观察到异或的性质,就是给一个序列,求两两异或和的和,然后按位统计贡献即可

T3

容易想到N^3的dp方程,然后我观察到可以用斜率优化可以N^2调了很久,最后交了n^3的算法,爆int了

记得开long long