CSP2020 联赛集训总结

发布于 22 天前  42 次阅读


各类经验总结

结论规律题

重要特征

这类题通常涉及比较高深(你都不会知道)的知识点。但是一定是可以找规律结论的

主要的明显特征就是数据范围奇大,必须O(1)回答。也许还需要预处理

比如10.14那一场的T1就是一个结论大题,考的Bell方程,打一下表就知道在一定范围内答案是一定的。

Sol

如果笃定是结论规律题,就直接上暴力打表出结论

要是是小凯的疑惑那种不一定发现的了是规律结论的,做不出来也要试试

推式子题

推式子题做的比较少,只能尽量拿分。

求并集

一般并集都不好算,想办法把并集转换成交集算。

比如说:

假设一开始里面有很多元素,每次一个操作是删掉一个区间的某个元素,这样子就是相当于询问交集了。
对每个元素分开处理,用一些方法维护出这个元素在那些区间出现过。
那么对于一个区间 [l, r],只要询问区间 [x, y][l, r]包含,那么这个元素就在交集中。

这个问题就可以动态三维数点,CDQ就好了

DP题

联赛的DP一般不会状态太复杂。只有可能是问题很难形式化地刻画。这个时候就要想办法找一种可以定量的形式化方法把问题转化。

只要不来Emiya家的饭菜那种难度的DP,应该还可以应付。

贪心

贪心靠造化,真假看缘分

但是如果只有一组数据DP写不出来,写个牛逼点的贪心应该也还行

一般DP状态很难刻画的,不妨考虑一下贪心是不是很好解决。

LIS

LIS不一定是DP

二叉树问题

算法必带O(log)

如果在一棵二叉树上还有操作,可以考虑用二进制描述操作,转化成二进制数的操作问题。

比如说:Luogu5513

题面长,故事情节丰富

这种题目,你就要不断地揣测出题人的意图

一个背景这么丰富的题目,必然是他想掩盖这道题简单。所以把题意题面搞得难懂。

给你一些分布离散的点,要你求选点的最小代价

只要分布离散,必然点数很少

比如M-sea专场那一道谜域的界外。

还有一个维护42的次幂的数据结构题,你想它的数必然只有log个,可以往这方面入手。

括号相关

必然跟线性DP和栈有关

但是我相信去年已经考了一道括号树了,今年应该不会再考了

但是谁又知道呢?去年还不是D1:数树数, 然后谢总爆奶D2绝对不会再考这些了,结果D2又是:数数树

期望概率题

除了直接把式子推出来解决问题外,有那种操作方式构造方式的题目,一定可以从这些方式入手,考虑最简单的出答案方式

几个点要在树上跑到一起

点不会太多,一定跑到几个点的lca。直接考虑贪心

DP套DP

放弃

树上问题:限制下传,贡献上传

rt

异或问题

异或问题,01trie,线性基任你挑选

树上问题序列化

转到dfn序或者欧拉序上搞吧

背包恰好选满问题

全部赋成inf就好了

低级代码错误总结

算法写挂

实名批评倍增lca, tarjin

低级错误集锦

大数不取模(算一次一定要模一次) 大数不开long long 开long longprintf("%d"); **

进subtask的条件判断错误

总数很少但是可能单个很多的时候,请选择vector

谨防MLE

Summary

csp2020 ++rp


朴实沉毅