我能在毫无思维题基础的可能下 AK 思维题竞赛吗？这真的是可能的吗？
好吧真不能
T1
题目提示我们需要「深度思考」，所以我们开始「深度思考」。
好的，我现在得仔细看看这个问题。题目是说，给定一个字符串，其中包含一个竖线，我们需要输出竖线之后的内容。首先，我得想想怎么处理输入。因为字符串只包含 | 和小写字母，所以我们可以使用 cin 来输入。然后我们要找到 | 的位置，在 C++ 中，我们可以用 string 自带的 find 来找到 | 的位置。因为输出不能包含 |，所以答案部分就是 s.substr(idx+1)。比如说 hi|acgo，| 所在位置为 2，然后输出从 3 开始的位置的字符串 acgo。
所以我们直接按照深度思考的内容编写代码即可。
时间复杂度：O(∣s∣)O(|s|)O(∣s∣)。
本题解为整活，比赛时请不要使用 deepseek 等 AI 帮助解题。
T2
这题全靠感觉去做。
显然一个对角线就能形成一个正方形，如图所示。
所以对于没有干扰的情况下，我们可以直接染对角线。可以证明没有更优的染色方法。
接下来考虑干扰。
偶数的情况不需要管，肯定有一条对角线没有被干扰。
奇数的情况有可能两条对角线都被干扰，所以我们可以按如下方法染色。
上面的可以变成一个 (n−1)×(n−1)(n-1)\times (n-1)(n−1)×(n−1) 的方格。
然后我们可以发现右下角的点可以一直往左蔓延。
所以当 m≥nm\ge nm≥n 且 n≠1n\not= 1n=1 时，可以把所有格点染成黑色。
T3
分类讨论。
如果上一次不是平局，那么就拿这次的最小值减去上一次的最大值。
如果上一次是平局，为避免平局必须得将答案-1。
最后需要加上 (0,0)(0,0)(0,0) 的情况。
时间复杂度：O(n)O(n)O(n)。
T4,T6
这两题不是同一道吗（
看不出来性质，考虑打表。
我们将第 iii 个数，即 2×i−12\times i-12×i−1 进行 k(k为奇数)k(k为奇数)k(k为奇数) 次方操作，然后以二进制排列。
我这里选的 k=3k=3k=3。该情况如下：
没看懂？纵向排列一下：
注意到每一位都有一个循环节，第 iii 位的循环节长度为 2i−12^{i-1}2i−1，并且任意间隔 2i−22^{i-2}2i−2 的数都不相同。
为啥？我不到啊！
反正我们可以知道想要两个数的后 iii 位相同，两个数必须得差 2i−12^{i-1}2i−1 的倍数。比如 20,420,420,4 相差 161616，会发现它们的后 555 位相同。
所以我们只需要找到：
∑i=1n∑j=1n∑k=1n(i≠j≠k)×(ctz(∣j−i∣)+1)\sum_{i=1}^n \sum_{j=1}^n\sum _{k=1}^n (i\not= j\not= k)\times (\text{ctz}(|j-i|)+1) i=1∑n j=1∑n k=1∑n (i=j=k)×(ctz(∣j−i∣)+1)
，其中 ctz(i)\text{ctz}(i)ctz(i) 表示 iii 以二进制表示后最后面的连续的 000 的个数。
注意到 kkk 是无效状态，所以可以简化成
(n−2)×(∑i=1n∑j=1n(i≠j)×(ctz(∣j−i∣)+1))(n-2)\times (\sum_{i=1}^n \sum_{j=1}^n (i\not= j)\times (\text{ctz}(|j-i|)+1)) (n−2)×(i=1∑n j=1∑n (i=j)×(ctz(∣j−i∣)+1))
code：
时间复杂度：O(T×n2)O(T\times n^2)O(T×n2)。
当然，你可以预处理优化成 O(Tlogn+n2)O(T\log n+n^2)O(Tlogn+n2)，但因为实现难度巨大我就不讲了。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
接下来，我将把这个代码优化成可以通过的代码。
显然，
∑i=1n∑j=1n(i≠j)×(ctz(∣j−i∣)+1)=2∑i=1n∑j=1i−1(ctz(i−j)+1)\sum_{i=1}^n \sum_{j=1}^n (i\not= j)\times (\text{ctz}(|j-i|)+1)\\ =2\sum_{i=1}^n \sum_{j=1}^{i-1}(\text{ctz}(i-j)+1)\\ i=1∑n j=1∑n (i=j)×(ctz(∣j−i∣)+1)=2i=1∑n j=1∑i−1 (ctz(i−j)+1)
现在问题就转化成如何快速求出 ∑j=1i−1(ctz(i−j)+1)\sum_{j=1}^{i-1}(\text{ctz}(i-j)+1)∑j=1i−1 (ctz(i−j)+1) 的问题。
我们可以把数位拆开，分别统计每个数位产生的贡献。
举个例子：164=(10100100)2164=(10100100)_2164=(10100100)2 。
减去 0,2,4,6,8,10,...0,2,4,6,8,10,...0,2,4,6,8,10,... 共 828282 个数都会使后 111 位为 000。
减去 0,4,8,12,16,20,...0,4,8,12,16,20,...0,4,8,12,16,20,... 共 414141 个数都会使后 222 位为 000。
减去 4,12,20,28,36,...4,12,20,28,36,...4,12,20,28,36,... 共 202020 个数都会使后 333 位为 000。
减去 4,20,36,52,68,...4,20,36,52,68,...4,20,36,52,68,... 共 101010 个数都会使后 444 位为 000。
减去 4,36,68,100,1324,36,68,100,1324,36,68,100,132 共 555 个数都会使后 555 位为 000。
减去 36,10036,10036,100 共 222 个数都会使后 666 位为 000。
减去 363636 会使后 777 位为 000。
最后去掉 000 的贡献 222，所以 ∑j=1163(ctz(164−j)+1)=82+41+20+10+5+2+1−2=159\sum_{j=1}^{163}(\text{ctz}(164-j)+1)=82+41+20+10+5+2+1-2=159∑j=1163 (ctz(164−j)+1)=82+41+20+10+5+2+1−2=159 。
按照这个办法计算即可。
code：
时间复杂度 O(Tlogn+nlogn)O(T\log n+n\log n)O(Tlogn+nlogn)。
当然，这还可以优化成 O(Tlogn)O(T\log n)O(Tlogn)，敬请期待。
