小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