Day 8.2 NOIP 模拟赛总结
T1
T1赛时打表输出发现了等差数列的性质（好像不需要打表也能知道），然后我码完T2过后剩不到2个小时了，于是连T3T4暴力都没码就过来推了，但也没推出来，时间倒是耽误了不少，剩一个小时的时候去开始去码后面的暴力了。
T2
水题一道，做法，性质全给了。只不过比较玄学的是赛时手玩数据自测时间时，发现原来的实现方式对于 tp = 2 ，a或b极大时会T掉，但感觉时间复杂度很明显是对的，就是答案的长度，题面说了答案不超过1e6，所以理论上肯定不T，所以赛时很懵，卡常从6186ms 卡到了 2890多ms，但肯定会T，最后换了一种写法莫名其妙的就不T了，我怀疑我原来判断到达的方式有问题，但这是赛后的猜想，我没有找回之前的代码去调，但应该就是这个问题，换了一种dfs的写法，与先前的while 的写法有所不同，细节上的差别，导致了最终结果的不同。我为此，在考试2个小时之后才开始看T3题面，这也为我本场比赛暴力没有码完埋下了伏笔……
T3
T3必须狠狠的骂自己，由于T1和T2的原因，11：15左右我才着手码暴力，本身时间是绰绰有余的，但，由于我码的Dfs写法非常的日本，导致回溯一值出问题啊啊啊，我当时非得把字符串删去字符写成一个后一位向前一位移，开个数组存一下原值，回溯的时候还回去，但是有可能回去的时候这个数组的值是递归的倒数第二层需要的值，想到这儿之后我又对这个数组以类似的方式处理，反正最后是调崩了，实际上只需标记一下这个位置删掉了即可，我当时为了遍历字符串的那一点小小常数，非得整串的处理，这样实现的常数也不小，关键我也没码出来啊TvT。
T4
套用T3的开头，由于T1T2的缘故，T4也并未仔细思考，码了个暴力就润了。
题解里的做法有很多种，正解一共三个好像，不过一个是什么生成函数整数递推，一个是什么Ntt乱七八遭的，可写的只有第三个。
我们考虑设置一个dp：\(f[i][S]\)，表示只考虑前i种颜色，S这个集合里的格子涂上颜色了，转移方程：
\[\begin{align} f[i][S]&=\sum_{S'\in S,\mid S'\mid\nmid 2} f[i-1][S\wedge S'](i\leq a) \\ f[i][S]&=\sum_{S'\in S,\mid S'\mid\mid 2} f[i-1][S\wedge S'](i> a) \end{align} \]时间复杂度是 \(O(3^nm)\)。
考虑我们并不需要知道哪些格子被染上色了，于是我们不需要状压dp，考虑设\(f[i][j]\)表示只考虑前i种颜色，有j个格子填上的方案数。状态转移方程：
\[\begin{align} f[i][j]&=\sum_{k\leq j,k\nmid 2} f[i-1][j-k]+C_j^k(i\leq a) \\ f[i][j]&=\sum_{k\leq j,k\mid 2} f[i-1][j-k]+C_j^k(i>a) \end{align} \]时间复杂度来到了\(O(n^2m)\) 。
由于A颜色B颜色本质相同，通过二进制优化可以让复杂度来到\(O(n^2\log m)\)。
对于本题而言，最终的复杂度一定是一个与\(O(n^2)\)同阶的，我们上面的复杂度劣在了每一次得暴力往前枚举每一个位置，使得复杂度\(O(n^2)\)起步。这个时候再优秀的算法也无法做到\(O(1)\)的考虑颜色的限制，也就是说，状态的设计还得再变。
于是我们期待设计一个仅通过枚举dp数组的两个下标就能实现转移的状态。
被染上色了的设定是很伤的，因为它自带两重循环，所以上面的设定必须舍弃，我们考虑设计\(f[i][j]\)表示前i个位置，有j个格子涂了奇数次。状态转移方程：
\[\begin{align} f[i][j]&=f[i-1][j+1]*(j+1)+f[i-1][j-1]*(a+b-j+1) \end{align} \]时间复杂度来到了\(O(nm)\)，于是本题得以解决。
总结：
1.思路正确，实现却频频出错的时候，换种写法或许能够规避掉许多细节错误，7.26的dp专题赛T3便是如此。bfs就是比dfs先天具有规避递归层数带来的问题的能力，如果你是bfs，那么T3你甚至可以水到50，如果你是dfs，你会有5pts，如果你实现的优秀并且可以处理掉递归层数带来的问题，那么，你会拿到35，为什么不写bfs呢？
2.码dfs前想清楚怎么码，不同的方式往往决定码的难度，决定了码的时间，决定了你是否有更多的时间去磕后面的题。
3.赛时不要害怕写dp，不要有畏难情绪，不要一见dp就return。
标签：8.2,暴力,复杂度,mid,T3,align,NOIP2024,Day,dp From： https://www.cnblogs.com/yxans/p/18340774/2024_8_2_contest