巅峰赛#20除T5外全题解（未完成
2025-05-01 14:41:05
发布于：广东
我能在毫无思维题基础的可能下 AK 思维题竞赛吗？这真的是可能的吗？
好吧真不能
T1
题目提示我们需要「深度思考」，所以我们开始「深度思考」。
好的，我现在得仔细看看这个问题。题目是说，给定一个字符串，其中包含一个竖线，我们需要输出竖线之后的内容。首先，我得想想怎么处理输入。因为字符串只包含 | 和小写字母，所以我们可以使用 cin 来输入。然后我们要找到 | 的位置，在 C++ 中，我们可以用 string 自带的 find 来找到 | 的位置。因为输出不能包含 |，所以答案部分就是 s.substr(idx+1)。比如说 hi|acgo，| 所在位置为 2，然后输出从 3 开始的位置的字符串 acgo。
所以我们直接按照深度思考的内容编写代码即可。
#include <iostream>
#include <cstdio>
std::string FindTheStringAfterSeperator(std::string S){//寻找分隔符之后的字符串
return S.substr(S.find('|') + 1);//注意加1
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
std::string InputString;
std::cin >> InputString;//cin 输入
std::cout << FindTheStringAfterSeperator(InputString);
return 0;
}
时间复杂度：。
本题解为整活，比赛时请不要使用 deepseek 等 AI 帮助解题。
T2
这题全靠感觉去做。
显然一个对角线就能形成一个正方形，如图所示。
所以对于没有干扰的情况下，我们可以直接染对角线。可以证明没有更优的染色方法。
接下来考虑干扰。
偶数的情况不需要管，肯定有一条对角线没有被干扰。
奇数的情况有可能两条对角线都被干扰，所以我们可以按如下方法染色。
上面的可以变成一个 的方格。
然后我们可以发现右下角的点可以一直往左蔓延。
所以当 且 时，可以把所有格点染成黑色。
T3
分类讨论。
如果上一次不是平局，那么就拿这次的最小值减去上一次的最大值。
如果上一次是平局，为避免平局必须得将答案-1。
最后需要加上 的情况。
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, ans = 0;
int lstx = 0, lsty = 0;
cin >> n;
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
if(lstx == lsty) ans += min(x, y) - lstx;
else if(lstx < lsty){
if(x >= lsty) ans += min(y - lsty + 1, x - lsty + 1);
}else{
if(y >= lstx) ans += min(x - lstx + 1, y - lstx + 1);
}
lstx = x, lsty = y;
}
cout << ans + 1;
return 0;
}
时间复杂度：。
T4,T6
这两题不是同一道吗（
看不出来性质，考虑打表。
我们将第 个数，即 进行 次方操作，然后以二进制排列。
我这里选的 。该情况如下：
1 000000000000000000001
2 000000000000000011011
3 000000000000001111101
4 000000000000101010111
5 000000000001011011001
6 000000000010100110011
7 000000000100010010101
8 000000000110100101111
9 000000001001100110001
10 000000001101011001011
11 000000010010000101101
12 000000010111110000111
13 000000011110100001001
14 000000100110011100011
15 000000101111101000101
16 000000111010001011111
17 000001000110001100001
18 000001010011101111011
19 000001100010111011101
20 000001110011110110111
...
没看懂？纵向排列一下：
11111111111111111111111111111111111111111111111111...
01010101010101010101010101010101010101010101010101...
00110011001100110011001100110011001100110011001100...
01101001011010010110100101101001011010010110100101...
01111110100000010111111010000001011111101000000101...
00100101101001001101101001011011001001011010010011...
00111000010001111110001000011100110001111011100000...
00001010010101000011011110110011110011011110110000...
00010101100110100111101110111000001011111100110110...
00001000110100100101011011001110011111101010011001...
00000101001111111111110101100010010111110011011111...
00000011010111101000100010010000000011001111010011...
00000000110010110000010100001011110100101110010100...
00000000001110010101011000000110100111100100010010...
00000000000001110011001010101011000111100010111011...
00000000000000001111000110011001010010110100100011...
00000000000000000000111110000111001110010010010110...
00000000000000000000000001111111000001110001110001...
00000000000000000000000000000000111111110000001111...
00000000000000000000000000000000000000001111111111...
...
注意到每一位都有一个循环节，第 位的循环节长度为 ，并且任意间隔 的数都不相同。
为啥？我不到啊！
反正我们可以知道想要两个数的后 位相同，两个数必须得差 的倍数。比如 相差 ，会发现它们的后 位相同。
所以我们只需要找到：
，其中 表示 以二进制表示后最后面的连续的 的个数。
注意到 是无效状态，所以可以简化成
code：
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
struct modInt{
int val;
modInt(int n){val = n % mod;}
void operator ++(signed){
val++;
if(val >= mod) val -= mod;
}
void operator += (modInt b){
val += b.val;
if(val >= mod) val -= mod;
}
void operator *= (modInt b){
val = val * b.val % mod;
}
modInt operator + (modInt b){
return val + b.val;
}
modInt operator * (modInt b){
return val * b.val;
}
};
modInt pow(modInt n, int t){
modInt ans = 1;
while(t){
if(t & 1) ans *= n;
n *= n, t >>= 1;
}
return ans;
}
void solve(){
int n;
cin >> n;
modInt ans = 0;
for(int i = 1; i <= n; i++){
int cur = 0;
for(int j = 1; j <= n; j++){//计算
if(i == j) continue;
ans += (__builtin_ctz(__builtin_labs(i - j))) + 1;
}
}
cout << (ans * pow(n * (n - 1), mod - 2)).val << '\n';//计算分数，n-2直接约掉。
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度：。
当然，你可以预处理优化成 ，但因为实现难度巨大我就不讲了。
接下来，我将把这个代码优化成可以通过的代码。
显然，
现在问题就转化成如何快速求出 的问题。
我们可以把数位拆开，分别统计每个数位产生的贡献。
举个例子：。
减去 共 个数都会使后 位为 。
减去 共 个数都会使后 位为 。
减去 共 个数都会使后 位为 。
减去 共 个数都会使后 位为 。
减去 共 个数都会使后 位为 。
减去 共 个数都会使后 位为 。
减去 会使后 位为 。
最后去掉 的贡献 ，所以 。
按照这个办法计算即可。
code：
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
//modInt
modInt ans[1000005];
void solve(){
int n;
cin >> n;
cout << (ans[n] * pow(n * (n - 1), mod - 2) + 1).val << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for(int i = 1; i <= 1000000; i++){
ans[i] = ans[i - 1];
int cur = 0;
for(int j = 0; (1 << j) < i; j++){//一位一位计算贡献
cur += (i >> j + 1);
}
cur -= __builtin_ctz(i);//减去0的贡献
cur *= 2;//注意因为重复的两遍只算了一遍，答案需要乘2
ans[i] += cur;
//dfs(i, 1);
}
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度 。
当然，这还可以优化成 ，敬请期待。
有帮助，赞一个