第十五届蓝桥杯软件赛C/C++大学A组全国总决赛个人题解

先写写这场儿童节考试的感受吧，我个人是在中国矿业大学考点考的，总体上考试策略不是很理想，时间分配比较不合理，毕竟好久没操代码了。最后顺利拿到了CA组国二，复盘发现错了俩思路正确的题，感到很可惜，倒数第二题暴力的部分分也没得到，个人感觉A组国一大致70分左右吧，而自己大概50出头，倘若上面提到的失误一个都没犯才能稳稳的过国一线，不过也没啥遗憾的，个人实力也确实暂且只到国二。无论怎样，终究是给大一的蓝桥之旅画上了一个圆满的句号。

矿大的环境还是很优美的，可是电脑机子还是比较讨人厌的，样例甚至不能粘贴至编译程序里面，比较难受，考点发了瓶饮料和面包，还送了件衣服，体验上来说中规中矩吧。也许大二就不参加了，如果学校还报销的话也可能会去别的组别玩一玩（毕竟我本人学的是人工智能专业哈哈，可能去Python组康康）。

然后以下是个人题解部分：

【答案】2030

【思路】 写了一下这段代码，然后翻了下计算机自带的日历，发现没问题。

【参考代码】

inline void sol(){ int ans = 0; for(int i=2025;;i++){  if(i%4==0) ans += 366;  else ans += 365;  if(ans%7==0) return cout << i << endl, void(); }}

【答案】37044368843012180000

【思路】 假设 ，则 ，通过分解质因数，可以发现 ，然后再通过枚举因数 和 ，如果 ，那么 ，进而。考场略微检验了一下数据范围，但是就是没发现这个地方的 会超过long long数据范围，早知道用python检验一下了（，痛失5分，气死了！！

【参考代码】

inline void sol(){ __int128 M = 20240601000, ans = 0; for(__int128 i=2;i*i<=20240601000;i++){  //A-B = i; A+B = 20240601000/i;  if(20240601000%i || (20240601000/i + i)%2==1) continue;  __int128 A = (i + 20240601000/i)/2;  write(A*A - 10120300500), putchar('\n');  ans += A*A - 10120300500; } write(ans);}

【思路】 看到知乎上各种做法的有很多，但是实际上这题不需要多么复杂的做法。通过观察，我们就能发现最终的答案一定是两只“双向奔赴”的兔子所在位置的中点（下取整），而其他跟着目标兔同向跳跃的兔子的终点位置也就是目标兔的终点位置，因此我们开多几个数组就能通过简单的模拟来完成这个题目。

【参考代码】

#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()#define ls(x) (x<<1)#define rs(x) (x<<1|1) #define here system("pause")using namespace std;const int N = 1e5+5;const int mod = 1e9+7;const int INF = 1e15+7;const double eps = 1e-6;inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}inline int inv(int a, int p){ return pow(a,p-2,p)%p;}int n;struct node{ int pos, idx; bool operator < (const node & an) const{  return pos < an.pos; };}a[N];int pre[N], suf[N], res[N], ans[N];bool dcs[N];inline void sol(){ cin >> n; for(int i=1;i<=n;i++){  cin >> a[i].pos;  a[i].idx = i; }  sort(a+1, a+1+n); for(int i=2;i<=n;i++) pre[i] = a[i].pos - a[i-1].pos; for(int i=n;i>=1;i--) suf[i] = a[i+1].pos - a[i].pos; for(int i=2;i<n;i++) dcs[i] = (suf[i] < pre[i]); // True代表向右走  dcs[1] = 1; dcs[n] = 0;  for(int i=1;i<n;i++){  if(dcs[i] && !dcs[i+1]){   res[i] = res[i+1] = a[i].pos + a[i+1].pos >> 1;  } }  for(int i=n;i>=1;i--){  if(!res[i] && dcs[i]) res[i] = res[i+1]; } for(int i=1;i<=n;i++){  if(!res[i] && !dcs[i]) res[i] = res[i-1]; }  for(int i=1;i<=n;i++){  ans[a[i].idx] = res[i]; } for(int i=1;i<=n;i++){  cout << ans[i] << " \n"[i==n]; }}signed main(){ IOS; int tc = 1; while(tc--){  sol(); } return 0;}

【思路】 一眼BFS，直接按着旋转来写，略微有点码量，但是思路很清晰。考场上由于手生这题愣是debug了半天才看出有一处手误。而且这题是多组测试，在3s时间限制下我们可以预先跑 init() 函数，由还原好的 来逆着推初始的 ，然后用map标记一下就能实现 查询。代码就不想在这再写一遍了。

【思路】 首先改写式子：

令 ，二者均可预处理，然后我们通过枚举 来二分查找 即可，时间复杂度为 。考场上居然没注意到 可以是负数，就直接二分了（甚至有停下来怀疑过这题怎么这么简单），然后这题就基本挂了QAQ。

【参考代码】

#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()#define ls(x) (x<<1)#define rs(x) (x<<1|1) #define here system("pause")using namespace std;const int N = 3e5+5;const int mod = 1e9+7;const int INF = 1e15+7;const double eps = 1e-6;inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}inline int inv(int a, int p){ return pow(a,p-2,p)%p;}int n, a, b, c;int s[N], sum[N], L[N];pii R[N];inline void sol(){ cin >> n >> a >> b >> c; for(int i=1;i<=n;i++){  cin >> s[i];  sum[i] = sum[i-1] + s[i];  R[i].first = sum[i] - a*b*i;  R[i].second = i;  L[i] = sum[i-1] - a*c*i; } sort(R+1,R+1+n);  int ans = 0; for(int l=1;l<=n;l++){  int r = R[upper_bound(R+1, R+1+n, make_pair(L[l], 0), [&](const pii& lhs, const pii& rhs){   return lhs.first < rhs.first;  }) - R].second;  //   cerr << l << ", " << r << "  [" << L[l] << ", " << r << "]\n";  ans = max(ans, r-l+1); } cout << ans << endl;}signed main(){ IOS; int tc = 1; while(tc--){  sol(); } return 0;}

【思路】 这题和之前做过的HDU一题很像。可以去看看我先前写的题解：https://mp.weixin.qq.com/s?__biz=MzkyMDYzNDIwNA==&mid=2247484421&idx=1&sn=11d85be5ecefdb8f9be70afc94bc63c6&chksm=c18e9236f6f91b204a7289f81a44caab2bf060ce4963efbb4eeba72f2226d6af8fa0c684d3da&token=776449521&lang=zh_CN#rd。

2024杭电ACM-个人PK赛（2）https://acm.hdu.edu.cn/contest/problem?cid=1120&pid=1002

给定正整数 ，求有多少个长度为 的序列 ，满足 且 ，答案对 取模。

显然， 答案为 ，然后我们来考虑 的情况：首先，原条件此时等价于求长度为 且 的互素数列个数。那么，我们可以拆分 的因子，令 ，则对于每个 考虑贡献：数列中至少有一个数拆分为这个因子时等于 ，也至少有一个数拆分为这个因子时等于 ，剩下的元素没有限制。随后我们考虑容斥， ，（解释：每个元素都可以选择 ，答案为每个元素没有限制的方案数 - 每个元素不能选p[i]^0的方案数 - 每个元素不能选p[i]^c[i]的方案数 + 每个元素不能选p[i]^0或p[i]^c[i]的方案数）。

【参考代码】

#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()#define ls(x) (x<<1)#define rs(x) (x<<1|1) #define here system("pause")using namespace std;const int N = 3e5+5;const int mod = 998244353;const int INF = 1e15+7;const double eps = 1e-6;inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}inline int inv(int a, int p){ return pow(a,p-2,p)%p;}int n, x, y;inline void sol(){ cin >> x >> y >> n; if(y%x) return cout << "0\n", void();  y/=x; vector<pii> fc; for(int i=2;i*i<=y;i++){  if(y%i==0){   int cnt = 0;   while(y%i==0) ++cnt, y/=i;   fc.emplace_back(i, cnt);  } } if(y!=1) fc.emplace_back(y, 1);  int ans = 1; for(auto tmp : fc){  int c = tmp.second;  ans = ans * ((pow(c+1, n, mod) - 2*pow(c, n, mod) + pow(c-1, n, mod))%mod + mod) %mod; } cout << ans << endl;}signed main(){ IOS; int tc = 1; cin >> tc; while(tc--){  sol(); } return 0;}

【思路】 看起来比较的典型。和以前做过的一题有点类似的地方：

第20届纪念款-牛客周赛 Round 20 https://ac.nowcoder.com/acm/contest/69695/E

小红定义“漂亮串”为：至少包含一个"red"子串，且不能包含"der"子串。例如"redced"为漂亮串，但"reder"则不是漂亮串。

小红想知道，长度为

的、仅包含小写字母的字符串中，共有多少种不同的漂亮串？

根据数据范围，这题的正解应该就是矩阵快速幂优化DP，针对70%的数据范围，我们可以开辟数组 ，表示长度为 的串匹配了模板串的前 位 次的方案数，我们设 表示增添一个字符后由原本匹配到第 位到匹配到第 位的方案数（显然， ）。那么我们来思考转移方程： 其中 ，且 、 ，可以发现矩阵 是固定的，可以根据KMP的 数组来求解。然后如果是针对100%的数据范围，应该要用到矩阵快速幂处理（类似“GT考试”那道题的处理），具体我推导了一天也没有什么头绪，后来请教了退役的博士师兄，他换了种处理解决了这个问题（详细见100分代码注释部分）。

记 ，那么，我们有

而

而 ，且计算时应先计算 ，后计算

紧接着，令

再令

则有：

， ，

显然， ，其中

而

而

所以

而 表达式就跟复杂了，所以推不下去了，感觉上面的矩阵应该要进行一些性质发掘和简单变形。（↑↑↑自己一天的瞎推导）

// ↓↓↓ 70分代码#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()#define ls(x) (x<<1)#define rs(x) (x<<1|1) #define here system("pause")using namespace std;const int N = 1e5+5;const int mod = 998244353;const int INF = 1e15+7;const double eps = 1e-6;inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}inline int inv(int a, int p){ return pow(a,p-2,p)%p;}int n, m, nxt[35];string s;int G[35][35];int f[N][35][3]; inline void sol(){ cin >> s >> n; int m = s.size(); s = " " + s; for(int i=2, j=0;i<=m;i++){  while(j && s[i] != s[j+1]) j = nxt[j];  if(s[i] == s[j+1]) ++j;  nxt[i] = j; }  for(int i=0;i<=m;i++){  for(char c='a';c<='z';c++){   int j = i;   while(j && s[j+1]!=c) j = nxt[j];   if(s[j+1] == c) ++j;   G[i][j]++;  } }  f[0][0][0] = 1; for(int i=1;i<=n;i++){  for(int j=0;j<m;j++){   for(int k=0;k<=m;k++){    f[i][j][0] = (f[i][j][0] + f[i-1][k][0] * G[k][j]%mod) % mod;    f[i][j][1] = (f[i][j][1] + f[i-1][k][1] * G[k][j]%mod) % mod;    f[i][j][2] = (f[i][j][2] + f[i-1][k][2] * G[k][j]%mod) % mod;   }  }  for(int k=0;k<=m;k++){   f[i][m][2] = (f[i][m][2] + f[i-1][k][1] * G[k][m]%mod) % mod;   f[i][m][1] = (f[i][m][1] + f[i-1][k][0] * G[k][m]%mod) % mod;  } }  int ans = 0; for(int i=0;i<=m;i++){  ans += f[n][i][2];  ans %= mod; } cout << ans << endl;}signed main(){ IOS; int tc = 1; while(tc--){  sol(); } return 0;}// ↓↓↓ 100分代码#include<bits/stdc++.h>#define ll long longusing namespace std;const int N = 1e5+7;constexpr int P = 998244353;using i64 = long long;int norm(int x) {    if (x < 0) {        x += P;    }    if (x >= P) {        x -= P;    }    return x;}struct Z {    int x;    Z(int x = 0) : x(norm(x)) {}    int val() const {        return x;    }    Z operator-() const {        return Z(norm(P - x));    }    template<class T>    Z power(Z a, T b) {     Z res = 1;     for (; b; b >>= 1, a = a * a)         if (b & 1)             res = res * a;     return res; }    Z inv(){        assert(x != 0);        return power(*this, P - 2);    }    Z &operator*=(const Z &rhs) {        x = i64(x) * rhs.x % P;        return *this;    }    Z &operator+=(const Z &rhs) {        x = norm(x + rhs.x);        return *this;    }    Z &operator-=(const Z &rhs) {        x = norm(x - rhs.x);        return *this;    }    Z &operator/=( Z &rhs) {        return *this *= rhs.inv();    }    friend Z operator*(const Z &lhs, const Z &rhs) {        Z res = lhs;        res *= rhs;        return res;    }    friend Z operator+(const Z &lhs, const Z &rhs) {        Z res = lhs;        res += rhs;        return res;    }    friend Z operator-(const Z &lhs, const Z &rhs) {        Z res = lhs;        res -= rhs;        return res;    }    friend Z operator/(const Z &lhs,  Z &rhs) {        Z res = lhs;        res /= rhs;        return res;    }};struct Matrix{ vector<vector<Z> > mat; void init(int n){  mat.resize(n,vector<Z>(n,0)); } void init(int n,int m){  mat.resize(n,vector<Z>(m,0)); } Matrix& operator = (const Matrix& m){  for(int i=0;i<mat.size();i++)   for(int j=0;j<mat[0].size();j++)    mat[i][j] = m.mat[i][j];  return *this; } Matrix operator * (const Matrix& m){  Matrix res;  res.init(mat.size(),m.mat[0].size());  for(int i=0;i<mat.size();++i)   for(int j=0;j<m.mat[0].size();++j)    for(int k=0;k<mat[0].size();++k)     res.mat[i][j] = res.mat[i][j]+mat[i][k]*m.mat[k][j];  return res; } Matrix operator + (const Matrix& m){  Matrix res;  res.init(mat.size(),mat[0].size());  for(int i=0;i<mat.size();++i)   for(int j=0;j<mat[0].size();++j)    res.mat[i][j] = mat[i][j]+m.mat[i][j];  return res; } void single(){  for(int i=0;i<mat.size();i++){   mat[i][i] = 1;  } } Matrix qpow(ll k){  Matrix tmp; tmp.init(mat.size(),mat[0].size());  tmp = *this;  Matrix res; res.init(mat.size(),mat[0].size());  res.single();  while(k){   if(k&1){    res = res * tmp;   }   tmp = tmp*tmp;   k /= 2ll;  }  return res; } void read(){  for(int i=0;i<mat.size();i++){   for(int j=0;j<mat[0].size();j++){    cin>>mat[i][j].x;   }  } } void out(){  for(int i=0;i<mat.size();i++){   for(int j=0;j<mat[0].size();j++){    cout<<mat[i][j].val();    if(j==mat[0].size()-1) cout<<'\n';    else cout<<' ';   }  } }};string s;int n;int f[35][35];/*    f[i][j]的含义是：    如果当前已经匹配到字符串s的第i位，且接下来要匹配的字符是j + 'a'，那么f[i][j]    存储的就是在字符串s中从当前位置继续匹配时，应当跳转到的位置索引。*/int main(){ cin >> s >> n; int m = s.size(); //kmp vector<int> nxt(m); nxt[0] = -1; for(int i=1,j=-1;i<m;i++){  while(j!=-1 && s[i]!=s[j+1]) j = nxt[j];  if(s[i] == s[j+1]) j++;  nxt[i] = j; } for(int i=0;i<m;i++){  for(int j=0;j<26;j++){   int k = i-1;   while(k!=-1 && s[k+1]!=j+'a') k = nxt[k];   if(s[k+1] == j+'a') k++;   f[i][j] = k+1;  } } Matrix G; //转移矩阵 G.init(3*m+1); for(int i=0;i<m;i++){  for(int j=0;j<3;j++){   for(int k=0;k<26;k++){                  int pos;                  if(j==2 && i==m-1 && k+'a'==s[m-1]){                    pos = 3*m; //要是匹配次数超过两次就不需考虑了                  }else{                    int ni = f[i][k];                    int nj = j;                    if(ni==m) ++nj, ni = nxt[m-1]+1; //完全匹配了，转到j+1状态下的nxt失配位置                    pos = nj * m + ni;    }    G.mat[j*m+i][pos] += 1;   }  } }    G = G.qpow(n);        Matrix res;    res.init(1, 3*m+1);    res.mat[0][0] = 1; res = res*G;     Z ans = 0; for(int i=2*m;i<3*m;i++){        ans += res.mat[0][i];    } cout << ans.val() << endl;    return 0;}

【思路】 伪博弈题。考场上手推了前十几个答案，大致会发现大致流程就是先手放两个，后手毁一个 -> 先手放两个，后手毁多个。所以我们关键是找出中间的转折轮数，假设这一轮是第 轮，那么由于下一轮后手要毁 的范围，所以有 。我们的目标即是要求最大的 ，然后先手会在 轮再放两个，此时就是全局最大值了。由此，不难发现单调性，可以使用二分策略了，时间复杂度约为 ，考场上由于对自己的观察比较自信，后面直接写出了一个数列通项，现在场外冷静思考发现应该是错误的了（红温。通过OEIS，发现关于这个 的数列应该是 A190605 ：通项可表示为 后面很多项都是 ，前面几项分别是

附：

#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()#define ls(x) (x<<1)#define rs(x) (x<<1|1) #define here system("pause")using namespace std;const int N = 1e5+5;const int mod = 998244353;const int INF = 1e15+7;const double eps = 1e-6;inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}inline int inv(int a, int p){ return pow(a,p-2,p)%p;}int n;inline void sol(){ cin >> n; int lo = 1, hi = n+1; while(lo < hi){  int mid = lo + hi + 1 >> 1;  int tmp = (n / mid) + (n%mid==0 ? 0 : 1);  if(mid + 1 <= tmp*tmp) lo = mid;  else hi = mid - 1; } cout << lo+2 << endl;}signed main(){ IOS; int tc = 1; cin >> tc; while(tc--){  sol(); } return 0;}

【思路】

由于这棵根号树的性质，其深度确实不大，但是子树庞杂，但由于最后要求非 异或路径的乘积，而非和。更何况 的数据范围还可达1e9之大，实在是没什么思路，是今年A组最难的题了，赛后写了个 的打了下表，然后对着数据查OEIS也无果。

兴许只能是想办法整理出所有的异或值后进行快速的大规模的乘积运算(?)，有点超出能力范畴勒（（，考场上跳过了这题，后面剩十分钟才写暴力，没写出了，应该凡题先打个暴力再走的（（

【参考代码暴力】

#include <bits/stdc++.h>#define IOS ios::sync_with_stdio(0), cin.tie(0)#define int long long#define endl '\n'#define lowbit(x) (x)&(-x)#define pii pair<int,int>#define all(s) s.begin(), s.end()#define ls(x) (x<<1)#define rs(x) (x<<1|1) #define here system("pause")using namespace std;const int N = 1e3+5;const int mod = 998244353;const int INF = 1e15+7;const double eps = 1e-6;inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}inline int inv(int a, int p){ return pow(a,p-2,p)%p;}int n;vector<pii> g[N];int dis[N][N];inline void dfs(int u, int fa, int res, int anc){ dis[anc][u] = res; for(auto k:g[u]){  int v = k.first;  int w = k.second;  if(v==fa) continue;  dfs(v, u, res^w, anc); }}inline void sol(){ cin >> n; for(int i=1;i<=n;i++){  g[i].clear(); } for(int i=2;i<=n;i++){  int u = i, v = sqrt(i);  g[u].emplace_back(v, u-v*v);  g[v].emplace_back(u, u-v*v); } for(int i=1;i<=n;i++){  dfs(i, -1, 0, i); }  int ans = 1; for(int i=1;i<=n;i++){  for(int j=i+1;j<=n;j++){   if(dis[i][j]) ans = ans*dis[i][j] % mod;  } } cout << ans << endl;}signed main(){ IOS; int tc = 1; while(tc--){  sol(); } return 0;}

【思路】 考场上还剩20多分钟才看这题，由于深知自己这个题做不出来，脑子里不知道为啥闪过一个想法，就是开一个bitset，来表示某个数 能不能被表示为 奇数偶数奇数偶数奇数偶数 的形式，然后将奇数记为1，偶数记为0，每个数就可以用一个01字符表示，然后用 map 储存，然后遍历 map 即可，然后由于考场有点紧迫+实力确实也不是很允许，居然敲了个这个暴力上去（肯定没啥分，面对15%的数据时连空间上都有问题），还不如直接暴力枚举然后多花点时间敲完I题的暴力呢。

当然以上纯事后诸葛亮了，BTW也真是从没见过1.5e16数据量的题目，看来这题对标程卡得很死。正解应该是莫比乌斯反演+推式子。看到知乎上有大佬提到说应该有：

其中为完全平方数

经暴力检验，这个结论貌似不成立(?)。

总之，经此一役，发现不太会推导这种非入门级别的莫比乌斯反演QWQ（今年自己学校的校赛还考了一个形如 形式的莫比乌斯反演题，考场上也是没有足够的能力推导出来，暑假还得加训加训这块内容QAQ，到时看看能不能把这题补上吧......），不过总的来说这题考场上大部分人应该都没有足够的时间拿到较多的分数，而且默写杜教筛我觉得难度也不是很小，这题区分度还是差了些。