平凡无奇的思维笔记：寻找创意的灵感

一个笨脑瓜仰慕并很努力地追上平常人的能力

如何做思维题&＃xff1f;

思维过程

以CF1151B Dima and a Bad XOR 为例

1. 自顶向下

1.分析问题的元素&＃xff1a;最突出的元素为异或&＃xff0c;其次为结果大于零&＃xff0c;其次为每行取一个&＃xff0c;其次为一个二维数组

2.分析每个元素的特点&＃xff1a;

异或&＃xff1a;相同取0&＃xff0c;不同取1

结果大于零&＃xff1a;为什么是零&＃xff0c;不是某个数字&＃xff0c;如果是零会是什么情况

每行取一个&＃xff1a;每行的数字在求解问题中是独立的&＃xff0c;在列中是存在关系的&＃xff08;异或关系&＃xff09;

等等……

2. 自底向上

1.分析元素的结论&＃xff1a;

异或&＃xff1a;

相同的数字异或为零&＃xff0c;反之大于零&＃xff08;对应大于零这个元素&＃xff09;
多个数字异或为零不代表所有数字一定相同&＃xff0c;但根据上面的结论将一个数字换成一个不同的数&＃xff0c;异或结果必大于零

每行取一个&＃xff1a;

作用就是换数字&＃xff0c;但是有可能所有的数字都是相同的
等等……

3. 总结结论&＃xff0c;解决问题

随便找一个选数方案如果结果大于零就可以直接解决问题。但找到了一个为零的选数方案&＃xff0c;尝试用其中一个数字同一行的不同的数替换该数字&＃xff0c;如果所有数字都找不到对应不同数字&＃xff08;同一行全相同&＃xff09;&＃xff0c;就解决了问题。

|x1-x2|&＃43;|y1-y2|

1. 二维问题的其中一种思维是x&＃xff0c;y相互独立&＃xff0c;想到就好做&＃xff08;CF1499C Minimum Grid Path、B Eastern Exhibition&＃xff09;

贪心

1. 选择i和j且i!&＃61;j&＃xff0c;a[i]–,b[j]–&＃xff0c;求最多操作数
   使a[i]尽可能不为0以便配对有多种选择&＃xff0c;每次选择最大和次大&＃xff08;维护优先队列&＃xff0c;2e5&＃xff09;

双指针

1.勿默认左指针为主指针&＃xff0c;请考虑题意确定主指针。主指针的特点&＃xff1a;

1. 维护较复杂的问题
2. 变化幅度较小
3. 次指针维护最值

2.处理答案贡献连续的问题&＃xff0c;通常要确定连续边界&＃xff0c;第一次满足条件和不满足条件的情况&＃xff08;Unstable String&＃xff09;

二分答案

最大的最小 最小的最大

博弈

玄学奇思妙想就行了
1.递推性&＃xff1a;总结出递推过程的特点。

Vasya and Chess
我找到了间隔1列的时候可以“逼”对方过不来&＃xff0c;什么特点&＃xff1f;
对方所在地棋子无时&＃xff0c;对方输了。

2.对称性&＃xff1a;图形问题&＃xff0c;特别是题目给定开始移动位置对称时。&＃xff08;包括对角对称&＃xff09;

只要和先手对称&＃xff0c;就能将当前状态递推到最终状态。