T1
看完题目，看到n<=9的限制，心头一紧
一个词汇浮现于心：Bruce Forces
暴力+记忆化，\(O(能过)\)
但赛时并没有这样打，而是选择了往DP方面思考
因为真的没想到能过
然后DP呢，又不清楚该如何存一列的状态
就匆匆暴力后离去
考虑状压DP
保留有用状态
关键点：\(k=\min(k,n-k)\)
可以参考\(C^k_n=C^{n-k}_n\)的理解方式（取k或舍n-k个概率相等）
但对于极限数据仍然慢了，即使只保留了有用的状态也是如此
这种题出现在比赛中时，应当多次检查自己的时间复杂度并对极限数据进行测试
因为它实在是忒卡时间了
对极限数据若没把握，可以表
对于边缘时间复杂度的程序，且输入少的题目，不失为一种方法
T2
一道构造题
要求是构一个图使得删点使得图不连通的最少数量最大
给出了点，边数
赛时有个挺好的思路，就是算出这个数量，然后构出主体，再加无关边
m有个限制：\(m≤2n-1\)
赛时根本没看数据限制，就推了所有的情况，很难
推出来了求数量的公式（可能错误）：\(s=\lfloor 2m-n\rfloor\)
但构造方式还是错了，实在是难
实际上\(2n-1\)的话，答案最大就3，很好构造，随便构一下就行
裂开，
数据限制也是很重要的一环，无论是不是正解，看它都可能会多拿分
故意弄成小标题的
T4
关于这题的思考
-
分开成两块，令人思考到区间的合并，从这点出发可以想到递归成两半做，
再进步一点就是区间DP，时间\(O(n^3)\)
-
数据范围中有一个特殊条件：\(S_i=1\)
什么作用？选票时贡献与S无关了，仅与区间长度有关
可以优化成\(O(n^2)\)的一维DP，再进一步，推式子可以用前缀和维护，优化到\(O(n)\)
-
正解是直接计数，考虑断一条边的概率，为当前段总共边中，左边右边概率相乘
记得打
标签：10,复杂度,56,能过,2023,2n,数据,DP From： https://www.cnblogs.com/tlz-place/p/17788020.html