noip2016练习总结

写简要题解吧

Day1

T1

模拟水题 code

T2

。。。。传说中的天天爱跑步,这种题怎么放到Day1T2的
把题目做一个转化,就变成了查询一个点内有多少个点和他距离相等,开个桶维护点对的贡献,
在儿子处加入,在lca删除,一遍dfs就好了

code


T3

期望dp,设dp[i][j][0/1]表示枚举到i,已经申请了j次,当前这一次是否申请 分情况讨论,转移;
前面最短路用floyd求;

[code](https://www.luogu.org/record/18836444)


Day2

T1

自己做质因数分解的题做傻了
一开始想的预处理阶乘的质因子有多少个,然后n^2回答每个询问,结果没注意到T特别大
正解是n^2求%k意义下的组合数,然后做一个前缀和优化,o(1)回答询问

90分 code
100分 code


T2

一开始想用桶做,后面发现在不太好处理蚯蚓秒增长。然后直接看了正解。
要发现一个比较巧妙的性质,切蚯蚓之后肯定会变短
于是维护三个队列,Q1存还没有切过的,把一开始所有蚯蚓从大到小排序丢进去
Q2存切下来前半段的,Q3存后半段的
每次从三个队列的队首取最长的一个,切完后丢到Q2,Q3的队尾
增长很好维护

code


T3

愤怒的小鸟,记录已经有几条抛物线,有几个单独的,搜索就好了

code


原文地址:https://www.cnblogs.com/lzqlalala/p/11848272.html