Overall, this set of problems is much simpler than last year’s national competition problems. Last year’s problems included several advanced algorithm questions, while this year’s problems have been reduced to a more general difficulty level.The problems have been updated on Luogu, and everyone can try submitting solutions there!Problem 1: StringProblem 2: EnumerationProblem 3: FactorizationProblem 4: Greedy – Interval ProblemProblem 5: BFS SearchProblem 6: Dynamic Programming, Rolling Array
Problem 1: Simple string processing, basic syntax content
#include<bits/stdc++.h>using namespace std;bool check(string a,string b){ for(int i=0;i<a.size();i++) { int t=a[i]-b[i]; if(b[i]=='?'||abs(t)==32)continue; return false; } return true;}int main(){ string s,t; cin>>s>>t; int n=s.size(),m=t.size(); int cnt=0; for(int i=0;i+m<=n;i++) { string str=s.substr(i,m); if(check(str,t))cnt++; } cout<<cnt<<endl; return 0;}
Problem 2: Simulation Enumeration. Set the variables according to the input order as a, b, c, d, e, f, g, h, and the answers as abs1, ans2, ans3, ans4;ans2 can be calculated directly, then enumerate ans3 to calculate ans1 and ans4, excluding invalid content to get the answer.
#include<bits/stdc++.h>using namespace std;int a,b,c,d,e,f,g,h,s;int main(){ cin>>s>>a>>b>>c>>d>>e>>f>>g>>h; set<int> st={a,b,c,d,e,f,g,h}; int ans2=s-a-b-d-h; st.insert(ans2); int x=s-f-g-h,y=s-a-c-e; for(int ans3=1;ans3<=12;ans3++) { if(st.count(ans3))continue; int ans1=y-ans3,ans4=x-ans3; if(st.count(ans1)||st.count(ans4))continue; if(ans1==ans3||ans4==ans3||ans1==ans4)continue; if(ans1>12||ans4>12)continue; cout<<ans1<<' '<<ans2<<' '<<ans3<<' '<<ans4<<endl; break; } return 0;}
Problem 3: FactorizationThe idea is that to form perfect squares in pairs, we can factor out the perfect square factors from each number. The remaining values that are the same form a group, and any two numbers within the group can form a perfect square. Finally, we seek the largest group.
#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int a[N],cnt,n;map<int,int> mp;int main(){ for(int i=2;i*i<=10000000;i++)a[++cnt]=i*i; cin>>n; for(int i=1;i<=n;i++) { int x; cin>>x; for(int j=1;j<=cnt&&a[j]<=x;j++) { while(x%a[j]==0)x/=a[j]; } mp[x]++; } int ans=0; for(auto x:mp)ans=max(ans,x.second); cout<<ans<<endl; return 0;}
Problem 4: Greedy – Interval ProblemThis problem is essentially an interval selection problem. Unlike the typical interval selection, we sort by the left endpoint in descending order and solve it in reverse. If you are not familiar with interval selection problems, you can search for them online. There are five basic types of interval problems that you can learn about.
#include<bits/stdc++.h>using namespace std;const int N=1e5+10;struct node{ int l,r; bool operator<(const node& a)const { return l>a.l; }}nd[N];int n;int main(){ cin>>n; for(int i=1;i<=n;i++) { cin>>nd[i].l>>nd[i].r; } sort(nd+1,nd+n+1); long long ans=nd[1].l,ed=nd[1].l; for(int i=2;i<=n;i++) { if(ed<=nd[i].r)continue; ans+=nd[i].l; ed=nd[i].l; } cout<<ans<<endl; return 0;}
Problem 5: BFS. The original problem, just be careful not to write the wrong variable during BFS expansion.
#include<bits/stdc++.h>using namespace std;const int N=210;bool vis[N][N][N];int v,x,y;struct node{ int a,b,c,step;};int main(){ cin>>v>>x>>y; if(v%2) { cout<<-1<<endl; return 0; } vis[v][0][0]=1; queue<node> q; q.push({v,0,0,0}); while(q.size()) { int a=q.front().a,b=q.front().b,c=q.front().c,step=q.front().step; q.pop(); if(a==v/2||b==v/2||c==v/2) { cout<<step<<endl; return 0; } int aa,bb,cc; if(a>=x-b)aa=a-x+b,bb=x,cc=c;//a pours into b else aa=0,bb=a+b,cc=c; if(!vis[aa][bb][cc]) { q.push({aa,bb,cc,step+1}); vis[aa][bb][cc]=1; } if(a>=y-c)aa=a-y+c,bb=b,cc=y;//a pours into c else aa=0,bb=b,cc=a+c; if(!vis[aa][bb][cc]) { q.push({aa,bb,cc,step+1}); vis[aa][bb][cc]=1; } if(b>=v-a)aa=v,bb=b-v+a,cc=c;//b pours into a else aa=a+b,bb=0,cc=c; if(!vis[aa][bb][cc]) { q.push({aa,bb,cc,step+1}); vis[aa][bb][cc]=1; } if(b>=y-c)aa=a,bb=b-y+c,cc=y;//b pours into c else aa=a,bb=0,cc=b+c; if(!vis[aa][bb][cc]) { q.push({aa,bb,cc,step+1}); vis[aa][bb][cc]=1; } if(c>=v-a)aa=v,bb=b,cc=c-v+a;//c pours into a else aa=a+c,bb=b,cc=0; if(!vis[aa][bb][cc]) { q.push({aa,bb,cc,step+1}); vis[aa][bb][cc]=1; } if(c>=x-b)aa=a,bb=x,cc=c-x+b;//c pours into b else aa=a,bb=b+c,cc=0; if(!vis[aa][bb][cc]) { q.push({aa,bb,cc,step+1}); vis[aa][bb][cc]=1; } } cout<<-1<<endl; return 0;}
Problem 6: Dynamic Programming, Idea:The state dp[i][j][k]: the number of ways to reach row i, column j, with the product modulo 11 equal to k.State initialization: dp[1][1][a[1][1]%11]=1State transition: dp[i][j][k*a[i][j]%11]=(dp[i][j][k*a[i][j]%11]+dp[i][j-1][k]+dp[i-1][j][k])%mod;I personally think that if this can be done during the competition, it would be a medium difficulty problem. If submitted like this on Luogu, it would result in MLE.To optimize memory size, we can use a rolling array. Since the current state depends on the previous row and column, we can initialize it as a 2-row array to ensure memory limits are not exceeded. I initially wanted to use a vector array, but it still exceeded limits, so I defined it as an array within the program.
#include<bits/stdc++.h>using namespace std;const int mod=1e9+7;int main(){ int n,m; scanf("%d%d",&n,&m); int dp[min(2,n)][m+1][11]; memset(dp,0,sizeof dp); for(int i=0;i<n;i++) for(int j=1;j<=m;j++) { int x; scanf("%d",&x); x%=11; if(i==0&&j==1) { dp[0][1][x]=1; continue; } for(int k=0;k<11;k++)dp[i%2][j][k]=0; for(int k=0;k<11;k++) { int t=k*x%11; dp[i%2][j][t]=(dp[i%2][j][t]+dp[i%2][j-1][k])%mod; if(i>0)dp[i%2][j][t]=(dp[i%2][j][t]+dp[1-i%2][j][k])%mod; } } printf("%d\n",dp[(n-1)%2][m][0]); return 0;}