您的位置: 首页  >  IT文章  >  2019CCPC秦皇岛自我反省&部分题解

2019CCPC秦皇岛自我反省&部分题解

分类: IT文章 • 2024-09-22 15:36:19

练了一年半了，第一次打CCPC，险些把队友坑了打铁，最后也是3题危险捡了块铜。

非常水的点双连通，我居然不相信自己去相信板子，唉，结果整来整去，本来半个小时能出的题，整到了3个小时，大失误呀，不然就可以去弄其他题了，对自己的表现太失望了，给自己记一大过。然后导致了策略失误，稀里糊涂的时间久过去了，不然感觉我们队还是能再出3题的。

可惜可惜，自己的这些大赛的经验还是不足，但相信这不会成为拖累自己队伍的后腿，发现问题就要及时调整，在赛场上还是要坚信自己所想到的，不用太苛求于模板形式。

有些急躁，但心态还是挺好，下次多喝点水，急的时候就去尿尿冷静一下。

之前思维题都由鲲鲲和+1很快就想出来了，想不出来就没得法子，自己在思维上明显退步了，接下来除了算法的学习，更重要的思维也不能忘了，自己去补一补。

之后几场不知道会怎么样，未来不可想，现在犹可抓，好好把握接下来不多的时间。

Stand by,Stand by.

1004 就看是不是只包含2和5

 1 #include<cstdio>
 2 bool judge(int n){
 3     while(n>1){
 4         if(n%5==0) n/=5;
 5         else if(n%2==0) n/=2;
 6         else return false;
 7     }
 8     return true;
 9 }
10 int main(){
11     int t,n;
12     scanf("%d",&t);
13     while(t--){
14         scanf("%d",&n);
15         if(judge(n)) printf("No
");
16         else printf("Yes
");
17     }
18     return 0;
19 }
签到

1006 就看每个环的贡献，就这个sb了，套了个点双的板子，发现错误没及时改。后来重现时是单组测试，所以把多组去了

 1 #include<cstdio>
 2 #include<stack>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int N=5e5+11,M=5e5+11;
 7 const ll md=998244353;
 8 struct Side{
 9     int v,ne;
10     Side(){}
11     Side(int v,int ne):v(v),ne(ne){}
12 }S[M<<1];
13 Side sta[M];
14 int n,sn,dn,bn,tn,head[N],dfn[N],low[N],bin[N],bsi[N];
15 ll cf2[M];
16 void init(){
17     sn=dn=bn=tn=0;
18     for(int i=0;i<=n;i++){
19         head[i]=-1;
20         dfn[i]=bin[i]=0;
21     }
22 }
23 void add(int u,int v){
24     S[sn].v=v;
25     S[sn].ne=head[u];
26     head[u]=sn++;
27 }
28 void pdc(int u,int fa){
29     dfn[u]=low[u]=++dn;
30     for(int i=head[u],v;~i;i=S[i].ne){
31         v=S[i].v;
32         if(!dfn[v]){
33             sta[++tn]=Side(u,v);
34             pdc(v,u);
35             low[u]=min(low[u],low[v]);
36             if(low[v]>=dfn[u]){
37                 int su,sv;
38                 bsi[++bn]=0;
39                 while(tn){
40                     su=sta[tn].v;sv=sta[tn].ne;
41                     tn--;
42                     if(su==u&&sv==v) break;
43                     if(bin[su]!=bn){
44                         bin[su]=bn;
45                         bsi[bn]++;
46                     }
47                     if(bin[sv]!=bn){
48                         bin[sv]=bn;
49                         bsi[bn]++;
50                     }
51                 }
52             }
53         }else if(v!=fa){
54             low[u]=min(low[u],dfn[v]);
55             if(dfn[u]>dfn[v]) sta[++tn]=Side(u,v);
56         }
57     }
58 }
59 int main(){
60     cf2[0]=1;
61     for(int i=1;i<M;i++){
62         cf2[i]=cf2[i-1]<<1;
63         if(cf2[i]>=md) cf2[i]%=md; 
64     }
65     int t,m,u,v;
66     //scanf("%d",&t);
67     //while(t--){
68         scanf("%d%d",&n,&m);
69         init();
70         for(int i=0;i<m;i++){
71             scanf("%d%d",&u,&v);
72             add(u,v);
73             add(v,u);
74         }
75         ll ans=1;
76         for(int i=1;i<=n;i++) if(!dfn[i]) pdc(i,i);
77         for(int i=1;i<=bn;i++){
78             if(!bsi[i]) continue;
79             ans*=((cf2[bsi[i]]-1)%md+md)%md;
80             if(ans>=md) ans%=md;
81             m-=bsi[i];
82         }
83         ans*=cf2[m];
84         if(ans>=md) ans%=md;
85         printf("%lld
",ans);
86 //    }
87     return 0;
88 }
点双

其实直接dfs找环就行了。

 1 #include<cstdio>
 2 #include<stack>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int N=5e5+11,M=5e5+11;
 7 const ll md=998244353;
 8 struct Side{
 9     int v,ne;
10     Side(){}
11     Side(int v,int ne):v(v),ne(ne){}
12 }S[M<<1];
13 Side sta[M];
14 int n,m,sn,dn,bn,tn,head[N],vis[N],dep[N];
15 ll ans,cf2[M];
16 void init(){
17     sn=dn=bn=tn=0;
18     for(int i=0;i<=n;i++){
19         head[i]=-1;
20         vis[i]=0;
21     }
22 }
23 void add(int u,int v){
24     S[sn].v=v;
25     S[sn].ne=head[u];
26     head[u]=sn++;
27 }
28 void dfs(int u,int fa,int d){
29     dep[u]=d;
30     vis[u]=1;
31     for(int i=head[u],v;~i;i=S[i].ne){
32         v=S[i].v;
33         if(v==fa||vis[v]==2) continue;
34         if(vis[v]){
35             m-=d-dep[v]+1;
36             ans*=(cf2[d-dep[v]+1]-1+md)%md;
37             if(ans>=md) ans%=md; 
38         }else dfs(v,u,d+1);
39     }
40     vis[u]=2;
41 }
42 int main(){
43     cf2[0]=1;
44     for(int i=1;i<M;i++){
45         cf2[i]=cf2[i-1]<<1;
46         if(cf2[i]>=md) cf2[i]%=md; 
47     }
48     int t,u,v;
49     scanf("%d%d",&n,&m);
50     init();
51     for(int i=0;i<m;i++){
52         scanf("%d%d",&u,&v);
53         add(u,v);
54         add(v,u);
55     }
56     ans=1;
57     for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,i,0);
58     ans*=cf2[m];
59     if(ans>=md) ans%=md;
60     printf("%lld
",ans);
61     return 0;
62 }
dfs判环

1009 一道dp题，当时是+1做的，自己补了下。就每个技能最多有6种组合，dp[i][j]就是第i个技能，是用第j个组合按出来的，最少方案数。然后预处理一下，两两技能不同组合之间转移时需要多按的键数便可。

 1 #include<cstdio>
 2 #include<tr1/unordered_map>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const char jn[15][10][10]={
 7     {{"QQQ"},{"QQQ"},{"QQQ"},{"QQQ"},{"QQQ"},{"QQQ"}},
 8     {{"QQW"},{"WQQ"},{"QWQ"},{"QQW"},{"WQQ"},{"QWQ"}},
 9     {{"QQE"},{"EQQ"},{"QEQ"},{"QQE"},{"EQQ"},{"QEQ"}},
10     {{"WWW"},{"WWW"},{"WWW"},{"WWW"},{"WWW"},{"WWW"}},
11     {{"QWW"},{"WQW"},{"WWQ"},{"QWW"},{"WQW"},{"WWQ"}},
12     {{"WWE"},{"EWW"},{"WEW"},{"WWE"},{"EWW"},{"WEW"}},
13     {{"EEE"},{"EEE"},{"EEE"},{"EEE"},{"EEE"},{"EEE"}},
14     {{"QEE"},{"EQE"},{"EEQ"},{"QEE"},{"EQE"},{"EEQ"}},
15     {{"WEE"},{"EWE"},{"EEW"},{"WEE"},{"EWE"},{"EEW"}},
16     {{"QWE"},{"QEW"},{"WQE"},{"WEQ"},{"EWQ"},{"EQW"}},
17 };
18 const int N=1e5+11,inf=1e9+7;
19 int val[15][15][15][15],dp[N][15];
20 char s[N];
21 tr1::unordered_map<char,int> mmp;
22 void init(){
23     mmp['Y']=0;mmp['V']=1;mmp['G']=2;mmp['C']=3;mmp['X']=4;
24     mmp['Z']=5;mmp['T']=6;mmp['F']=7;mmp['D']=8;mmp['B']=9; 
25     for(int i=0;i<10;i++)
26         for(int j=0;j<10;j++)
27             for(int k=0;k<6;k++)
28                 for(int l=0;l<6;l++){
29                     for(int q=0,p;q<=3;q++){
30                         for(p=q;p<3;p++)
31                             if(jn[i][k][p]!=jn[j][l][p-q]) break;
32                         if(p>=3){
33                             val[i][j][k][l]=q;
34                             break;
35                         }
36                     }
37                 }
38 }
39 int main(){
40     init();
41     while(~scanf("%s",s)){
42         int lens=strlen(s);
43         for(int i=0;i<lens;i++)
44             for(int j=0;j<6;j++) dp[i][j]=inf;
45         for(int i=0;i<6;i++) dp[0][i]=4;
46         for(int i=1;i<lens;i++){
47             int j1=mmp[s[i-1]],j2=mmp[s[i]];
48             for(int k1=0;k1<6;k1++)
49                 for(int k2=0;k2<6;k2++)
50                     dp[i][k2]=min(dp[i][k2],dp[i-1][k1]+val[j1][j2][k1][k2]+1);
51         }
52         int ans=inf;
53         for(int i=0;i<6;i++) ans=min(ans,dp[lens-1][i]);
54         printf("%d
",ans);
55     }
56     return 0;
57 }
这就是我为什么不玩dota

1010 哎，字符串循环节水题，当时忘了，就没做这题。我们需要知道的任意长度后缀里的循环节长度是多少，那倒序求一遍kmp即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long ll;
 6 const int N=1e7+11;
 7 const ll inf=1e18+7;
 8 char s1[N],s2[N];
 9 int ne[N];
10 void getne(char *s){
11     int i=0,j=-1,lens=strlen(s);
12     ne[0]=-1;
13     while(i<lens){
14         if(j==-1||s[i]==s[j]) ne[++i]=++j;
15         else j=ne[j]; 
16     }
17 }
18 int main(){
19     int a,b;
20     while(~scanf("%d%d%s",&a,&b,s1)){
21         int lens1=strlen(s1),lens2;
22         for(int i=0;i<lens1;i++){
23             if(s1[lens1-1-i]=='.'){
24                 s2[i]='

相关推荐