8.9模拟赛

T1 一笔画

题目大意：

判断图是否存在欧拉通路

思路：

判断奇数度数点的个数是否有两个或没有以及图是否联通

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<vector>
 9 #include<set>
10 #define MAXN 100100
11 #define ll long long
12 #define inf 2139062143
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 int n,m,fa[MAXN],d[MAXN],ans,res;
22 int findset(int x) {return x==fa[x]?x:fa[x]=findset(fa[x]);}
23 void Merge(int a,int b)
24 {
25     int f1=findset(a),f2=findset(b);
26     if(f1!=f2) fa[f1]=f2;
27 }
28 int main()
29 {
30     freopen("euler.in","r",stdin);
31     freopen("euler.out","w",stdout);
32     int T=read(),a,b;
33     while(T--)
34     {
35         n=read(),m=read(),ans=res=0;
36         for(int i=1;i<=n;i++) d[i]=0,fa[i]=i;
37         while(m--) 
38         {
39             a=read(),b=read(),d[a]++,d[b]++;
40             Merge(a,b);
41         }
42         a=findset(1);
43         for(int i=1;i<=n;i++) if(findset(i)!=a) ans=1;
44         if(ans) {puts("NO");continue;}
45         for(int i=1;i<=n;i++) if(d[i]&1) res++;
46         if(res==2||res==0) puts("YES");
47         else puts("NO");
48     }
49 }

View Code

T2 复仇者联盟3

题目大意：

每个人都有0.5的概率死亡

有n个人的心愿他们希望一些人活下来

求满足i个人心愿的概率

思路：

因为n很小

可以状压，dp i j表示可能满足状态为i的人的心愿，补集中其他人都肯定不满足，dp进行到了j个人的概率

因为每个状态只可能向两个状态转移 dp i j+1，以及dp i&x j+1 (x为j+1个人在心愿单中人的补集)

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<vector>
 9 #include<set>
10 #define MAXN 100100
11 #define ll long long
12 #define inf 2139062143
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 const int mod=998244353,inv=499122177;
22 int n,m,t,g[7][MAXN],ans[7];
23 ll dp[35][MAXN];
24 int lowbit(int x) {return x&(-x);}
25 int main()
26 {
27     freopen("avengers3.in","r",stdin);
28     freopen("avengers3.out","w",stdout);
29     n=read(),m=read(),t=(1<<n)-1;int x,a;
30     for(int i=1;i<=n;i++)
31     {
32         x=read();
33         while(x--) a=read(),g[i][a]=1;
34     }
35     dp[t][0]=1;
36     for(int i=0;i<=m;i++)
37         for(int j=t,x;j>=0;j--)
38         {
39             x=t,(dp[j][i+1]+=(dp[j][i]*inv))%=mod;
40             for(int k=1;k<=n;k++)
41                 if(g[k][i+1]) x^=(1<<(k-1));
42             (dp[j&x][i+1]+=(dp[j][i]*inv))%=mod;
43         }
44     for(int i=0,tmp;i<=t;i++)
45     {
46         tmp=0;
47         for(int j=i;j;j-=lowbit(j)) tmp++;
48         (ans[tmp]+=dp[i][m])%=mod;
49     }
50     for(int i=0;i<=n;i++) printf("%d ",ans[i]);
51 }

View Code

T3 统计字符串

题目大意：

弱化版题解链接

此题n为高精度，需要高精度除以2

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<vector>
 9 #include<set>
10 #define MAXN 100100
11 #define ll long long
12 #define inf 2139062143
13 #define MOD 998244353
14 using namespace std;
15 inline int read()
16 {
17     int x=0,f=1;char ch=getchar();
18     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
19     while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
20     return x*f;
21 }
22 int m,nxt[60];
23 char c[60];
24 struct mat
25 {
26     ll num[60][60];
27     mat(){memset(num,0,sizeof(num));}
28 }ans,t;
29 struct bign
30 {
31     ll len,num[110];char ch[110];
32     void read()
33     {
34         scanf("%s",ch+1);len=strlen(ch+1);
35         for(int i=len;i;i--) num[i]=ch[len-i+1]-'0';
36     }
37     int Odd(){return num[1]&1;}
38     void div2()
39     {
40         for(int i=len,tmp=0,f=0;i;i--)
41         {
42             if(num[i]&1) f=1;else f=0;
43             num[i]=(num[i]+tmp)>>1;
44             if(f) tmp=10;else tmp=0;
45         }
46         if(!num[len]) len--;
47         if(len==1&&num[1]==0) len=0;
48     }
49 }n;
50 mat mul(mat a,mat b)
51 {
52     mat res;
53     memset(res.num,0,sizeof(res.num));
54     for(int i=0;i<m;i++)
55         for(int j=0;j<m;j++)
56             for(int k=0;k<m;k++)
57                 (res.num[i][j]+=a.num[i][k]*b.num[k][j])%=MOD;
58     return res;
59 }
60 int q_pow()
61 {
62     ll res=0;
63     while(n.len)
64     {
65         if(n.Odd()) ans=mul(ans,t);
66         t=mul(t,t);n.div2();
67     }
68     for(int i=0;i<m;i++) (res+=ans.num[0][i])%=MOD;
69     return res;
70 }
71 int main()
72 {
73     freopen("string.in","r",stdin);
74     freopen("string.out","w",stdout);
75     n.read();scanf("%s",c+1);m=strlen(c+1);
76     for(int i=2,j=0;i<=m;i++)
77     {
78         while(j&&c[j+1]!=c[i]) j=nxt[j];
79         if(c[j+1]==c[i]) j++;
80         nxt[i]=j;
81     }
82     for(int i=0;i<m;i++)
83         for(int j=0,tmp=i;j<26;tmp=i,j++)
84         {
85             while(tmp&&c[tmp+1]!=(char)(j+'a')) tmp=nxt[tmp];
86             if(c[tmp+1]==(char)(j+'a')) tmp++;
87             if(tmp!=m) t.num[i][tmp]++;
88         }
89     for(int i=0;i<m;i++) ans.num[i][i]=1;
90     printf("%d",q_pow());
91 }

View Code