赛时T4梳理

似水流年

2026-10-02 17:02:11

发布于：山东

6阅读

0回复

0点赞

1.十分的动态规划基础部分分
完全应该想到的部分，但是没有想到。解决方法：完成相似的动态规划一题。

最长上升子序列
这两中做法应该是相似的吧。

同样是以xxx为结尾，满足xxx条件的xxx
而这边由于我们的数字就是在1~10^6的范围之内的，所以我们可以直接将数值作为下标。

那么我们就可以得出一个定义：设g[a][b]为最后两项是a<b的合法序列数。
先用长度为2的序列初始化g[a][b]=1，再按b从小到大转移，枚举c>b且需要满足条件a^bc!=0（这里^是异或）。

哦。补充一下为什么是这样设计状态的：最长上升子序列中，约束条件其实是两两之间的（即，要求a[i]<a[j]）
而那时，我们只需要一个维度。
而现在约束状态存在于三者之间，所以最简单的，我们会想到要使用二维动态规划。

刚刚在完成这部分代码的时候稍微调试了一下：注意注意注意一定要注意！异或的优先级特别特别低！一定要在异或运算时加括号！！！

2.正难则反
这是一个非常经典的解题技巧，在很多方面都能用到：包括但不限于：绿题核心思路，绿题难度以上题目的部分分优化方案。
这是在题目方面的，那什么情形能够用到它？
1.求合法方案数
当直接求取合法方案数太过困难，我们可以反向求取不合法方案数（这种方案似乎一般叫做容斥）
2.两者相互制约
当题目给出两种东西：比如拿串子串烤肉，用脚踩草地，吃草
这种一方答案与另一方息息相关的情况下，我们需要学会转变思路。

与其想串子串了哪串烤肉，不如想哪串烤肉被串起。

那么这道题目也是相同的。我们与其计算枚举符合要求的数列，不如去计算不符合要求的数列。

设f[x]为以x结尾的合法序列数，s[x]=f[1]+f[2]+f[3]+...+f[x]
那么此时我们有：f[x]=s[x-1]+1-接上之后不符合要求的数
（那个1是x本身）

那么，我们如何去计算接上之后不符合要求的数？
我们已经完成了一个类似于最长上升子序列的问题，那么现在的约束条件就是异或。

原先是合法的序列，连接上x之后变得不合法，那么只有可能是最后三项不合法，不合法的条件：
a^bx=0，b=a^x
（我们一般选特殊项都选中间的，应为它左右两边都有数值）
现在x已经定下来，我们去枚举a，可以看出当x和b都已经确定，a是唯一的。

这里需要一个证明：任意以a结尾的合法序列，连接上b之后都是合法的。
那么我们可以得知，最后包含a,b的不合法最后三项一定是(a,b,x)
但是由于大小关系的约束，它们的顺序能且只能是a,b,x。

那么最后，a的范围就是1<=a<(a^x)<x

补充一个想到一维动态规划的思路：
我们可以发现，在最长上升子序列的基础上，这道题目还给出了额外的约束条件。
那么我们就可以先做一个普通的最长上升子序列，而后再搞出不满足另一个约束条件的序列数量，将它们相减。