写在前面

打了三年，第十六届是我最后一次参加了，终于如愿以偿国一啦。
这场的大多题目都补了，有始有终。
感谢自己前段时间的努力，基本上是把近几年的真题刷了个遍，认真的复盘补题总结，虽然这场打的还是有许多失误，但是好在有幸运女神的眷顾。
从第十四届的省二，到第十六届的国一，很符合一个普通人的发展路线了。
在这里插入图片描述

1、新型锁

dp
赛时没做出来，洛谷题解写的特别好，强推新型锁
答案：385787853
贴下代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;typedef pair<int,int> PII;
const int N=2026,mod=1e9+7;
int dp[N][2][2];
void solve(){dp[1][0][0]=8,dp[1][0][1]=4,dp[1][1][0]=2,dp[1][1][1]=1;for(int i=2;i<=2025;i++){dp[i][0][0]=dp[i-1][1][1]*8%mod;dp[i][1][0]=(dp[i-1][1][1]+dp[i-1][0][1])*2%mod;dp[i][0][1]=(dp[i-1][1][1]+dp[i-1][1][0])*4%mod;dp[i][1][1]=(dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][1][0]+dp[i-1][1][1])%mod;}int ans=(dp[2025][0][0]+dp[2025][0][1]+dp[2025][1][0]+dp[2025][1][1])%mod;cout<<ans<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;
//    cin>>T;while(T--){solve();}return 0;
}

2、互质藏卡

题目给出17600肯定是暗示着什么的，线性筛筛一下发现17600里恰好有2024个质数
那么答案肯定是1与这2024个质数的组合
对于每个质数 $p$ ，它的平方，立方等幂次 $p^2,p^3,p^3,p^4....)$ 且小于17600都是可以替换 $p$ 的
答案：174149196

#include<bits/stdc++.h>
#define int long long
using namespace std;typedef pair<int,int> PII;
const int N=17601,mod=1e9+7;
int primes[N],st[N],cnt;
int c[N];
void init(){int n=N-1;for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){st[i*primes[j]]=1;if(i%primes[j]==0) break;}}
}
void solve(){init();int ans=1;for(int i=0;i<cnt;i++){int p=primes[i];while(p<=17600){c[i]++;p*=primes[i];}ans=ans*c[i]%mod;}cout<<ans<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;
//    cin>>T;while(T--){solve();}return 0;
}

3、数字轮盘

因为每次操作都是让每个数一起按照某种规律进行变动，那么我们求一个数回到原来状态的最少次数就是求每个数回到原来状态的最少次数。这里我们就求1的最少次数。
对于第一阶段，显然循环节为n，所以先让k%n，因为目标求1的最少次数，我们要知道1在k次阶段一后的位置，不难发现，1的位置为k+1，我用变量now记录，而它的目标位置是1，我用变量tar记录。
对于阶段二，我们手玩几个样例，n为奇数和偶数都玩一玩，可以发现每次阶段二的操作，都会让最后两个数提到最前面，具体看下图
在这里插入图片描述
也就是说每次都会让当前数往后移动两个位置，规律就出来了。
我们模拟偶数以及奇数可以发现两者情况不同。
记目标位和当前位的距离为t
t为偶数时，两者都有解，就是t/2
t为奇数时，手玩样例可以n为偶数是不行的，无解，n为奇数只需要t再加n除以2就是答案，即(t+n)/2
代码：

#include <bits/stdc++.h>
#define LL long long
using namespace std;typedef pair<int,int> PII;
const int N=1e5+10;
void solve() {int n,k;cin>>n>>k;k%=n;if(!k) {cout<<0<<'\n';return ;}int tar=1;int now=k+1;int t=-1;if(now<=tar) {t=tar-now;} else {t=n-now+tar;}if(n%2==0) {if((tar&1) && (now%2==0)) {cout<<-1<<'\n';return ;}if((tar%2==0) && (now&1)) {cout<<-1<<'\n';return ;}t/=2;} else {if(t&1) t+=n;t/=2;}cout<<t<<'\n';
}int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;while(T--) solve();return 0;
}

4、斐波那契字符串

普通的递推
可以自己模拟几个后面的数量是多少就能发现规律了，式子也就推出来了。

#include <bits/stdc++.h>
#define int long long
using namespace std;typedef pair<int,int> PII;
const int N=1e5+10,mod=1e9+7;
int cnt0[N],cnt1[N],f[N];
void init() {cnt0[1]=1;cnt0[2]=0;cnt1[1]=0;cnt1[2]=1;f[1]=f[2]=0;int n=1e5;for(int i=3; i<=n; i++) {cnt0[i]=(cnt0[i-1]+cnt0[i-2])%mod;cnt1[i]=(cnt1[i-1]+cnt1[i-2])%mod;int res=cnt1[i-2]*cnt0[i-1]%mod;f[i]=(((f[i-1]+f[i-2])%mod)+res)%mod;}
}
void solve() {int n;cin>>n;cout<<f[n]<<'\n';
}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;cin>>T;init();while(T--) solve();return 0;
}

5、项链排列

贪心分类讨论即可，注意c为0的情况。

#include <bits/stdc++.h>
#define LL long long
using namespace std;typedef pair<int,int> PII;void solve(){int a,b,c;cin>>a>>b>>c;if(!c){if(a && b){cout<<-1<<'\n';}else{while(a--) cout<<'L';while(b--) cout<<'Q';cout<<'\n';}return ;}string ans;if(c&1){if(a<(c+1)/2 || b<(c+1)/2){cout<<-1<<'\n';return ;}int r=a-((c+1)/2);for(int i=1;i<=r;i++) ans+='L';for(int i=1;i<=(c+1)/2;i++){ans+='L';ans+='Q';}r=b-((c+1)/2);for(int i=1;i<=r;i++) ans+='Q';}else{if(a>=c/2+1 && b>=c/2){int r=a-(c/2+1);for(int i=1;i<=r;i++) ans+='L';for(int i=1;i<=c/2;i++){ans+='L';ans+='Q';}r=b-c/2;for(int i=1;i<=r;i++) ans+='Q';ans+='L';}else if(a>=c/2 && b>=c/2+1){ans+='Q';int r=a-c/2;for(int i=1;i<=r;i++) ans+='L';for(int i=1;i<=c/2;i++){ans+='L';ans+='Q';}r=b-(c/2+1);for(int i=1;i<=r;i++) ans+='Q';}else{cout<<-1<<'\n';return ;}}cout<<ans<<'\n';
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;while(T--) solve();return 0;
}

6、蓝桥星数字

不会做，比较暴力的做法可以考虑二分+数位dp，应该能过
赛时写的纯暴力
贴一下纯暴力的代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;typedef pair<int,int> PII;
bool check(int x){int r=-1;while(x){int now=x%10;if(r==-1) r=now;else{if((r%2==0) && (now%2==0)) return false;if((r&1) && (now&1)) return false;}r=now;x/=10;}return true;
}
void solve(){int n;cin>>n;int cnt=1;int ans=10;while(cnt<n){int now=ans+1;while(!check(now)) now++;ans=now;cnt++;}cout<<ans<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;while(T--) solve();return 0;
}

7、翻倍

赛时一眼cf原题，秒了
不需要暴力的*2，对于当前数，用一个变量记录前一个数翻了多少遍就行了
cf原题链接：E. Look Back
注意比赛题目是没有多组的，且范围是2e5

#include <bits/stdc++.h>
#define int long long
using namespace std;typedef pair<int,int> PII;
const int N=2e5+10;
int n,a[N],c[N];
void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int ans=0;for(int i=2;i<=n;i++){if(a[i]==a[i-1]){c[i]=c[i-1];}else if(a[i]>a[i-1]){int t=0,x=a[i-1],y=a[i];while(x<=y){t++;x*=2;}c[i]=max(c[i-1]-t+1,0ll);}else{int t=0,x=a[i],y=a[i-1];while(x<y){t++;x*=2;}c[i]=c[i-1]+t;}ans+=c[i];}cout<<ans<<'\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;while(T--) solve();return 0;
}

8、近似回文字符串

不会做
暴力分n<=6就考虑判断输出了
贴一下暴力代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;typedef pair<int,int> PII;
int ans=0;
int n;
bool f(string s){int sz=s.size();s='#'+s;for(int i=1;i<=sz;i++){if(s[i]!=s[sz-i+1]) return false;}return true;
}
bool check(string s){if(f(s)) return false;int sz=s.size();for(int i=0;i<sz;i++){string t;for(int j=0;j<i;j++) t+=s[j];for(int j=i+1;j<sz;j++) t+=s[j];if(f(t)) return true;}return false;
}
void dfs(int id,string s){if(id==n+1){if(check(s)) ans++;return ;}for(int j=0;j<26;j++){char c='a'+j;dfs(id+1,s+c);}
}
void solve(){cin>>n;if(n<=6){if(n==3){cout<<1300<<'\n';return ;}if(n==4){cout<<50050<<'\n';return ;}if(n==5){cout<<67600<<'\n';return ;}string s;dfs(1,s);cout<<ans<<'\n';}else{ans=1e9+7-1;cout<<ans<<'\n';}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;while(T--) solve();return 0;
}

9、子串去重

这应该是送分题了
用pos[i][j]数组记录从j位置开始往后找，字母i第一次出现的位置
对于每次询问，找出26个字母在区间范围内最早出现的位置，放进vector后排序然后暴力匹配就行了

#include <bits/stdc++.h>
#define LL long long
using namespace std;typedef pair<int,int> PII;
const int N=1e5+10;
int pos[30][N];
void solve(){string s;int m;cin>>s>>m;int n=s.size();s='#'+s;for(int j=0;j<26;j++) pos[j][n+1]=n+1;for(int i=n;i>=1;i--){for(int j=0;j<26;j++) pos[j][i]=pos[j][i+1];pos[s[i]-'a'][i]=i;}while(m--){int la,ra,lb,rb;cin>>la>>ra>>lb>>rb;vector<PII> va,vb;for(int i=0;i<26;i++){int p=pos[i][la];if(p<=ra){va.push_back({pos[i][la],i});}p=pos[i][lb];if(p<=rb){vb.push_back({pos[i][lb],i});}}sort(va.begin(),va.end());sort(vb.begin(),vb.end());int sa=va.size(),sb=vb.size();int ans=0;for(int i=0;i<min(sa,sb);i++){if(va[i].second!=vb[i].second) ans++;}ans+=abs(sa-sb);cout<<ans<<'\n';}
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;while(T--) solve();return 0;
}

10、涂格子

暴力可以拿20%的分
对于k=0的情况，暴力打表发现就是 $2^{n*m}+1$
格子可能重复出现，且染成不同的颜色，这种情况答案为0
贴下暴力代码

#include <bits/stdc++.h>
#define int long long
using namespace std;typedef pair<int,int> PII;
int n,m,k;
const int N=25,mod=998244353;
int a[N][N],b[N][N],vis[N][N];
const int dir[][2]= {{-1,0},{1,0},{0,-1},{0,1}};
int qmi(int a,int b) {int res=1;while(b) {if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
bool bfs(int sx,int sy) {int lx=sx,rx=sx,ly=sy,ry=sy;vis[sx][sy]=1;queue<PII> q;q.push({sx,sy});while(!q.empty()) {auto it=q.front();q.pop();int x=it.first,y=it.second;for(int z=0; z<4; z++) {int xx=x+dir[z][0];int yy=y+dir[z][1];if(xx>=1 && xx<=n && yy>=1 && yy<=m && !vis[xx][yy] && b[xx][yy]==b[sx][sy]) {lx=min(lx,xx);rx=max(rx,xx);ly=min(ly,yy);ry=max(ry,yy);q.push({xx,yy});vis[xx][yy]=1;}}}for(int i=lx; i<=rx; i++) {for(int j=ly; j<=ry; j++) {if(b[i][j]!=b[sx][sy]) return true;}}return false;
}
bool check() {for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {vis[i][j]=0;}}for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {if(!vis[i][j]) {if(bfs(i,j)) return false;}}}return true;
}
void solve() {cin>>n>>m>>k;if(n*m<=20) {for(int i=1; i<=n; i++) {for(int j=1; j<=m; j++) {a[i][j]=-1;}}bool ok=0;for(int i=1; i<=k; i++) {int x,y,c;cin>>x>>y>>c;if(a[x][y]!=-1 && a[x][y]!=c) {ok=1;}a[x][y]=c;}int ans=0;if(ok) {cout<<0<<'\n';return ;}for(int i=0; i<=(1<<(n*m)); i++) {for(int p=1; p<=n; p++) {for(int q=1; q<=m; q++) {b[p][q]=a[p][q];}}int x=1,y=1;bool f=0;for(int j=0; j<n*m; j++) {if((i>>j)&1) {if(b[x][y]!=-1 && b[x][y]!=1) {f=1;break;}b[x][y]=1;} else {if(b[x][y]!=-1 && b[x][y]!=0) {f=1;break;}b[x][y]=0;}if(f) break;y++;if(y==m+1) {x++;y=1;}}if(f) continue;if(check()) ans++;}cout<<ans<<'\n';} else {if(!k) {int x=n*m;int ans=(qmi(2,x)+1ll)%mod;cout<<ans<<'\n';}else{map<PII,int> mp;bool ok=0;for(int i=1;i<=k;i++){int x,y,c;cin>>x>>y>>c;if(!mp.count({x,y})) mp[{x,y}]=c;else if(mp[{x,y}]!=c) ok=1;}if(ok){cout<<0<<'\n';return ;}}}}signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T=1;while(T--) solve();return 0;
}