昨天刚结束的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;}

第三题：

图片

{jz:field.toptypename/}

难度：普及/提高-

知识点解析：思维，贪心。

首先，同样根数的数字，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。

建站客服QQ：88888888

部分分二，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题难度就上升了。而且，与去年相比，今年的题目都变得比较长，这也在一定程度上考察了同学们的耐心😂

预祝所有信奥选手都能取得自己理想的成绩！

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。