CSP-S 模拟105

2019/11/09 10:43
阅读数 0

 

 


 

   小W的魔术

    总的方案数减去满意的方案数

    考虑s序列由原序列的两端拼合而成,或者就是两端中的一端

    先看由两端拼合的方案,确定序列有长度x的前缀与S的前缀相同,那么有长度为len-x的后缀与S的后缀相同

    为了不重不漏,序列的x+1的位置一定不等于S的x+1的位置,因为这种情况在 长度为x+1的前缀与S相同的情况会被考虑到,所以方案总数$25*26^{n-len-1}$

    枚举x发现x有len个(前缀就等于S也考虑进去),则方案数 $len*25*26^{n-len-1}$

    最后看后缀为S的方案,显然最后len为确定$26^{n-len}$,但是又因为当序列第一个字母等于S的第一个字母且后缀和S相同的情况会在x==1时考虑进去

    所以序列第一个字母确定,有25中情况,那后缀的方案数为$25*26^{n-len}$

    总方案 $26^n-25*26^{n-len-1}*len-25*26^{n-len}$

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 long long n,len;
 6 char s[1100000];
 7 const long long mod=998244353;
 8 long long qpow(long long a,long long b){
 9     if(b<0) return 0;
10     long long ans=1;
11     a%=mod;
12     while(b){
13         if(b&1) ans=ans*a%mod;
14         b>>=1;
15         a=a*a%mod;
16     }
17     return ans;
18 }
19 int main(){
20     freopen("magic.in","r",stdin);
21     freopen("magic.out","w",stdout);
22     scanf("%lld%s",&n,s+1);
23     len=strlen(s+1);
24     long long ans=0;
25     ans=(ans+qpow(26,n-len-1)*25%mod*len%mod)%mod;
26     ans=(ans+qpow(26,n-len))%mod;
27     printf("%lld\n",(qpow(26,n)-ans+mod)%mod);
28 }
View Code


  小Y的图

    货车运输原题,最小生成树+树上倍增维护路径最大值 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 struct node{
 6     int l,r,z;
 7     bool operator < (const node b)const{
 8         return z<b.z;
 9     }
10 }e[310000];
11 int n,m,Q,ances[310000],fa[310000][20],maxn[310000][20],dis[310000];
12 int to[610000],nex[610000],head[310000],c[610000],tot;
13 int find(int x){return ances[x]==x?x:ances[x]=find(ances[x]);}
14 void add(int x,int y,int z){
15     to[++tot]=y,nex[tot]=head[x],head[x]=tot,c[tot]=z;
16 }
17 void dfs(int x,int pre){
18     dis[x]=dis[pre]+1;
19     fa[x][0]=pre;
20     for(register int i=1;i<=18;i++){
21         fa[x][i]=fa[fa[x][i-1]][i-1];
22         maxn[x][i]=max(maxn[x][i-1],maxn[fa[x][i-1]][i-1]);
23     }
24     for(register int i=head[x];i;i=nex[i]){
25         int y=to[i];
26         if(y==pre) continue;
27         maxn[y][0]=c[i];
28         dfs(y,x);
29     }
30 }
31 int lca(int x,int y){
32     if(dis[x]>dis[y]) swap(x,y);
33     int ans=0;
34     for(register int i=18;i>=0;i--){
35         if(dis[fa[y][i]]>=dis[x]){
36             ans=max(ans,maxn[y][i]);
37             y=fa[y][i];
38         }
39     }
40     if(x==y) return ans;
41     for(register int i=18;i>=0;i--){
42         if(fa[y][i]!=fa[x][i]){
43             ans=max(ans,maxn[y][i]);
44             ans=max(ans,maxn[x][i]);
45             y=fa[y][i];
46             x=fa[x][i];
47         }
48     }
49     return max(ans,max(maxn[x][0],maxn[y][0]));
50 }
51 int main(){
52     freopen("graph.in","r",stdin);
53     freopen("graph.out","w",stdout);
54     scanf("%d%d%d",&n,&m,&Q);
55     for(register int i=1;i<=m;i++)    scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].z);
56     sort(e+1,e+m+1);
57     for(register int i=1;i<=n;i++) ances[i]=i;
58     for(register int i=1;i<=m;i++){
59         int x=find(e[i].l),y=find(e[i].r);
60         if(x!=y){
61             add(e[i].l,e[i].r,e[i].z);
62             add(e[i].r,e[i].l,e[i].z);
63             ances[x]=y;
64         }
65     }
66     for(register int i=1;i<=n;i++){
67         if(!dis[i]){
68             dfs(i,0);
69         }
70     }
71     int x,y;
72     while(Q--){
73         scanf("%d%d",&x,&y);
74         if(find(x)!=find(y)) puts("-1");
75         else printf("%d\n",lca(x,y));
76     }
77 }
View Code

 

  小L的数

    答案一定小于等于4,因为任意一个数都可以由 01,02,04,08组成(每一位的数(0~9),都可以由0,1,2,4,8组成)

    验证1,2,3个喜欢的数的能否拼成,否则就是4

    从低到高枚举询问的数在该位的数字,三维DP f[i][j][k],表示第i位向下一位进0或1或2位,且有k(k<8)的状态表示三个数分别是否到最高位的方  案是否存在

    简单DP,最后看询问的最高位的进位为0是否存在即可

    在线求时间稍慢,大力卡常就好,大神yxs预处理碾压我

    

    

        

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define mu(x) ((x)<10?(x):((x)>=20?(x)-20:(x)-10))
 5 #define div(x) ((x)<10?0:((x)>=20?2:1))
 6 using namespace std;
 7 int T,a,b,c,d,u,v;
 8 char f[20][3][1<<3],p[20];
 9 long long now;
10 bool judge(){
11     memset(f,0,sizeof(f));
12     f[0][0][7]=1;
13     for(int t=1;t<=p[0];t++){
14         register int w=p[t],flag=0;
15         for(register int j=0;j<=2;j++){
16             if(f[t-1][j][1]||f[t-1][j][3]||f[t-1][j][5]||f[t-1][j][7]){
17                 if(mu(a+j)==w) f[t][div(a+j)][1]=1;
18                 if(mu(b+j)==w) f[t][div(b+j)][1]=1;
19             }
20             if(f[t-1][j][2]||f[t-1][j][3]||f[t-1][j][6]||f[t-1][j][7]){
21                 if(mu(c+j)==w) f[t][div(c+j)][2]=1;
22                 if(mu(d+j)==w) f[t][div(d+j)][2]=1;
23             }
24             if(f[t-1][j][4]||f[t-1][j][5]||f[t-1][j][6]||f[t-1][j][7]){
25                 if(mu(u+j)==w) f[t][div(u+j)][4]=1;
26                 if(mu(v+j)==w) f[t][div(v+j)][4]=1;
27             }
28             if(f[t-1][j][3]||f[t-1][j][7]){
29                 if(mu(a+c+j)==w) f[t][div(a+c+j)][3]=1;
30                 if(mu(a+d+j)==w) f[t][div(a+d+j)][3]=1;
31                 if(mu(b+c+j)==w) f[t][div(b+c+j)][3]=1;
32                 if(mu(b+d+j)==w) f[t][div(b+d+j)][3]=1;
33             }
34             if(f[t-1][j][5]||f[t-1][j][7]){
35                 if(mu(a+u+j)==w) f[t][div(a+u+j)][5]=1;
36                 if(mu(a+v+j)==w) f[t][div(a+v+j)][5]=1;
37                 if(mu(b+u+j)==w) f[t][div(b+u+j)][5]=1;
38                 if(mu(b+v+j)==w) f[t][div(b+v+j)][5]=1;
39             }
40             if(f[t-1][j][6]||f[t-1][j][7]){
41                 if(mu(c+u+j)==w) f[t][div(c+u+j)][6]=1;
42                 if(mu(c+v+j)==w) f[t][div(c+v+j)][6]=1;
43                 if(mu(d+u+j)==w) f[t][div(d+u+j)][6]=1;
44                 if(mu(d+v+j)==w) f[t][div(d+v+j)][6]=1;
45             }
46             if(f[t-1][j][7]){
47                 if(mu(a+c+u+j)==w) f[t][div(a+c+u+j)][7]=1;
48                 if(mu(a+c+v+j)==w) f[t][div(a+c+v+j)][7]=1;
49                 if(mu(a+d+u+j)==w) f[t][div(a+d+u+j)][7]=1;
50                 if(mu(a+d+v+j)==w) f[t][div(a+d+v+j)][7]=1;
51                 if(mu(b+c+u+j)==w) f[t][div(b+c+u+j)][7]=1;
52                 if(mu(b+c+v+j)==w) f[t][div(b+c+v+j)][7]=1;
53                 if(mu(b+d+u+j)==w) f[t][div(b+d+u+j)][7]=1;
54                 if(mu(b+d+v+j)==w) f[t][div(b+d+v+j)][7]=1;
55             }
56         }
57         if(!(f[t][0][1]+f[t][0][2]+f[t][0][3]+f[t][0][4]+f[t][0][5]+f[t][0][6]+f[t][0][7]+f[t][1][1]+f[t][1][2]+f[t][1][3]+f[t][1][4]+f[t][1][5]+f[t][1][6]+f[t][1][7]+f[t][2][1]+f[t][2][2]+f[t][2][3]+f[t][2][4]+f[t][2][5]+f[t][2][6]+f[t][2][7])) return 0;
58     }
59     for(register int i=1;i<=7;i++) if(f[p[0]][0][i]) return 1;
60     return 0;
61 }
62 int work(){
63     p[0]=0;
64     for(long long i=now;i;i/=10) p[++p[0]]=i%10;
65     for(a=0;a<=9;a++) for(b=a+(a!=0);b<=9;b++)
66         for(c=a;c<=9;c++) for(d=c+(c!=0);d<=9;d++)
67             for(u=c;u<=9;u++) for(v=u+(u!=0);v<=9;v++)
68                 if(judge()){
69                     int ans=0;
70                     if(a||b) ans++;
71                     if(c||d) ans++;
72                     if(u||v) ans++;
73                     return ans;
74                 }
75     return 0;
76 }
77 int main(){
78     freopen("number.in","r",stdin);
79     freopen("number.out","w",stdout);
80     scanf("%d",&T);
81     while(T--){
82         scanf("%lld",&now);
83         int ans=work();
84         if(ans) printf("%d\n",ans);
85         else puts("4");
86     }
87 }
View Code

 

 

 

展开阅读全文
mu
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部