布吉老司机修车群
发布日期：2025-12-17 14:42 点击次数：129昨天刚限定的CSP复赛，改日号教研团队就火速对题目作念了解读，以下是CSP-J每说念题的具体分析
第一题：
图片
难度：普及-
常识点剖析：模拟，不错简化为去重计数，有好多种短处。比较简便的是用字符串数组+sort+unique函数，疏漏字符串数组+sort+成列。也不错像底下的代码用map来回重。
#include <bits/stdc++.h>using namespace std;int n;string s;map<string,int> mp;int main(){ cin>>n; for(int i=1;i<=n;i++) { cin>>s; mp[s]=1; } cout<<52-mp.size(); return 0;}第二题：
图片
难度：普及-
常识点剖析：模拟，用二维数组保存舆图，记载是否到过某个点，模拟操作进程即可。题目还很“贴心”的把右转怎样用代码暗示王人教唆了。多组数据，铭记重置数组。
#include <bits/stdc++.h>using namespace std;int T,n,m,k,x,y,d,ans;char a[1010][1010];int vis[1010][1010];int dx[4]={0,1,0,-1};int dy[4]={1,0,-1,0};int main(){ cin>>T; while(T--) { cin>>n>>m>>k; cin>>x>>y>>d; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; memset(vis,0,sizeof(vis)); vis[x][y]=1; ans=1; for(int i=1;i<=k;i++) { int nx=x+dx[d]; int ny=y+dy[d]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]=='.') { x=nx; y=ny; if(vis[x][y]==0) { vis[x][y]=1; ans++; } } else d=(d+1)%4; } cout<<ans<<endl; } return 0;}第三题：
图片
难度：普及/进步-
常识点剖析：想维，无餍。
最初，不异根数的数字，6根（0，6，9），5根（2，3，5），2根（1），4根（4），3根（7），7根（8）。
先从n比较小驱动谈判，尽量用最少的数字位数：
n=1，莫得有规划；n=2，1；n=3，7；n=4，4；n=5，2；n=6，6；n=7，8，到这里咱们发现，能用一个数字处罚就不必两个数字。
n=8，10；n=9，18；n=10，22；n=11，20；n=12，28；n=13，68；n=14，88；两个数字不错处罚。
n=15，108；n=16，188；n=17，200；n=18，208，n=19，288；n=20，688；n=21，888；三个数字不错处罚，良好这里的数字是高涨的。
n=22，1088，从这里驱动，咱们不错说发现了限定，末尾用8是最优采纳，因为不必8剩下的根数多，而剩下的根数多，意味着数字大（由上一行得出的限定）。
这一题可能比较容易猜测动态缱绻，从想维短处上也很直不雅，泰国按摩群然而因为对应的整数很大，会卡在大整数怎样处理上。
打表部仳离算可能出错，不错暴力成列考证一下。
#include <bits/stdc++.h>using namespace std;int T,n;int a[22]={0,-1,1,7,4,2,6,8,10,18,22,20,28,68,88,108,188,200,208,288,688,888};int main(){ cin>>T; while(T--) { cin>>n; if(n<=21) cout<<a[n]<<endl; else { int l=n%7; if(l==0) l=7; cout<<a[14+l]; for(int i=1;i<=(n-15)/7;i++) cout<<8; cout<<endl; } } return 0;}第四题：
图片
难度：进步
常识点剖析：动态缱绻。
部分分一，r=1，循序判断每个东说念主，序列中从1驱动的第2到K个中是否包含C。
部分分二，n<=10，r<=5，DFS，成列每种可能性。
咱们暂时不谈判复杂度，先把想路理清：dp[i][j][k]暗示第i轮到第j个东说念主的数字k是否可行。
要是可行，则不错走到 dp[i+1][j1][k1]，其中j1!=j，k1是在j1中从k不错到达的数字。
咱们不错先瞻望算每个东说念主的序列相关，配置a->b是否可走的相关图。
这个朴素的动规，用图论的想维来想考每个数字的跳转相关，然而景况的复杂度是r*n*S，搬动的复杂度是n*S。复杂渡过高。
想考一下该怎样优化景况和搬动？
dp[i][j]暗示第i轮的终结是第j个数字是否可行
这里把n个东说念主的序列拼接起来，j是拼接后的序列的位置。因为n个序列的长度和不进步2*10^5，景况的复杂度缩短到了可罗致的进程。
假定拼接后的序列是a，要是第j个数字属于第x个东说念主，第x个东说念主的第一个数排在第y个，那么dp[i][j]取决于[max(j-K+1,y),j-1]这个区间的某个数能否与第i-1轮的其他东说念主的不错达到的数字接上
用f[j]暗示a[j]能否与上一轮的其他东说念主的不错达到的数字接上。咱们不错用前缀和在O(1)的复杂度臆度这个区间内是否存在可接。
接下来想考f[j]怎样得到，分情况野心a[j]：
①要是a[j]只出现了一次，彰着不成；
②要是a[j]出现了屡次，但王人是并吞个东说念主的序列内，也不成；
③要是a[j]出现了屡次，且在上一轮可行的位置不是第x个东说念主的区间，不错。
也即是说，咱们每一轮，要爱戴每一个数字可行的位置。这里又有一个小手段优化，其实咱们不需要知说念扫数的位置，要是唯有一个东说念主可行，则记载该东说念主，要是两个东说念主王人可行，则扫数的东说念主王人可行。
到这里为止，咱们把搬动优化到了O(1)，举座复杂度是T*n*L， 5*100*2*10^5 = 10^8，爱戴多个数组的常数比较大，是以题目给了2s的时限。
#include <bits/stdc++.h>using namespace std;int T,n,k,q,l,r,c;int a[200010]; //拼接后的数组int dp[110][200010]; //第i轮，以第j个数字终结是否可行int f[110][200010]; //第i轮第j个数a[j]是否能与上一轮的其他东说念主的疏浚数字的可行有规划接上int sum[200010]; //f数组的前缀和int p[110][200010]; //第i轮第j个数a[j]在上一轮的情况，0暗示不可行，n以内的数x暗示唯有被编号x的东说念主可行，1e6暗示至少两个东说念主王人可行int b[200010]; //i属于哪个东说念主int st[100010]; //第i个东说念主的早先int ans[110][200010]; //第i轮到数字j是否可行int main(){ cin>>T; while(T--) { cin>>n>>k>>q; int len=0; for(int i=1;i<=n;i++) { cin>>l; st[i]=len+1; for(int j=1;j<=l;j++) //1到len { cin>>a[++len]; b[len]=i; } } memset(dp,0,sizeof(dp)); memset(p,0,sizeof(p)); memset(f,0,sizeof(f)); memset(ans,0,sizeof(ans)); p[0][1]=1e6; //第0轮，1岂论几个王人可行 for(int i=1;i<=100;i++) { for(int j=1;j<=len;j++) { if(p[i-1][a[j]] && p[i-1][a[j]]!=b[j]) //上一轮a[j]的情况不是0，且不是我方 f[i][j]=1; sum[j]=sum[j-1]+f[i][j]; dp[i][j]=(sum[j-1]-sum[max(st[b[j]],j-k+1)-1]>0)? 1:0; if(dp[i][j]>0) { ans[i][a[j]]=1; if(p[i][a[j]]==0) p[i][a[j]]=b[j]; else if(p[i][a[j]]!=b[j]) p[i][a[j]]=1e6; } } } for(int i=1;i<=q;i++) { cin>>r>>c; cout<<ans[r][c]<<endl; } } return 0;}图片
综上，J组的前边2说念题目难度还行，第3题难度就高涨了。何况，与旧年比较，本年的题目王人变得比较长，这也在一定进程上老到了同学们的耐性😂
预祝扫数信奥选手王人能赢得我方瞎想的收成！布吉老司机修车群
本站仅提供存储做事，扫数践诺均由用户发布，如发现存害或侵权践诺，请点击举报。