准备复健 没敢打比赛怕掉分 先做做题练练手.
突然就想通了. 异或是不进位加法 虽然这导致其无法与加法结合 但是 如果只看二进制下的最低位 那么加法虽然进位了 但是我们不看 于是就等同于异或. 所以他们对最低位的贡献是完全一样的 表现在整个结果上 就是奇偶性相同. 而 $x + 3$ 正好与 $x$ 奇偶性相反.
发现两行能够填连续的 $2k$ 个数字. 而且只有这种情况能够让填入的数字"密度"最大(从不超过 $nk$ 的角度去考虑填的数字).
想了想貌似没其他做法了. 就写了发交了.
这样很容易发现 最大值和最小值是对等的. 所以我们回答的 其实是"最长的线段".
那么问题就来了 如果第一次选取的 $i j$ 存在最大值或者最小值 该怎么办. 不过也很好分析 只需要模拟一遍情况即可.
直觉告诉我 只要没有奇数 就都能做.
直觉告诉我是图论 因为我想到了二分图黑白染色上去. 但是我并不能构造出 选了一个就不能选另一个的图. 这个数据范围也不可能是网络流.
偷看题解.
题解直接说一堆偶数 然后就欧拉回路也是偶数. 这也太难了吧. 应该不是这么一个思考逻辑. 可能有些题是这样的吧 发现了性质 然后看到某些图有这样的性质.
如果找不到这样的图 可以先尝试乱连边建图 看看能得到什么.
建图的方法其实要总结也是有的 二分图黑白染色是 "互斥型" 建图 而我们这里要用到的是 "支配型" 建图. 建图方法之前网络流总结过 可以拿来借鉴 用在其他图论问题中.
提示里是说把区间加斐波那契换成区间加常数 能不能不用数据结构做.
首先把他变成维护一个序列 判断序列是否全为 $0$.
然后怎么搞斐波那契呢? 我还是傻傻的对斐波那契差分 想找他有啥性质.
这里就能够体现我多菜了. 不会思考.
我们为什么区间加的时候要差分呢? 因为这样需要维护的数就变少了. 应该从这个角度去考虑 如何对序列操作 使得区间加斐波那契 需要维护的数变少.
妙啊 果然我学习不懂原理 只会抓表面 变一下就用不来了. 我太菜了.