Codeforces Hello 2019
分类:
IT文章
•
2025-01-06 08:15:13
A.直接判。
![]()
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
6 typedef long long ll;
7 using namespace std;
8
9 const int N=10;
10 char s[N][N];
11
12 int main(){
13 rep(i,1,6) scanf("%s",s[i]);
14 rep(i,2,6) if (s[i][0]==s[1][0] || s[i][1]==s[1][1]) { puts("YES"); return 0; }
15 puts("NO");
16 return 0;
17 }
A
B.2^n枚举每次是顺时针还是逆时针，模拟。
![]()
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<iostream>
5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
6 typedef long long ll;
7 using namespace std;
8
9 const int N=20;
10 int n,ss,a[N];
11
12 int main(){
13 scanf("%d",&n); ss=(1<<n)-1;
14 rep(i,1,n) scanf("%d",&a[i]);
15 rep(S,0,ss){
16 int s=0;
17 rep(i,1,n) if (S&(1<<(i-1))) s=(s+a[i])%360; else s=(s-a[i]+360)%360;
18 if (!s){ puts("YES"); return 0; }
19 }
20 puts("NO");
21 return 0;
22 }
B
C.将所有串分成三类：只能作为左半段的串、只能作为右半段的串、两边都能做的串。可以发现，第三类串只能和第三类串匹配。
![]()
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
5 using namespace std;
6
7 const int N=500010;
8 char s[N];
9 int n,ans,b[N],c[N];
10
11 int main(){
12 scanf("%d",&n);
13 rep(i,1,n){
14 scanf("%s",s+1);
15 int len=strlen(s+1),tot1=0,tot2=0,f1=1,f2=1;
16 rep(j,1,len){
17 if (s[j]=='(') tot1++; else tot2++;
18 if (tot2>tot1) f1=0;
19 }
20 tot1=tot2=0;
21 for (int j=len; j; j--){
22 if (s[j]=='(') tot1++; else tot2++;
23 if (tot1>tot2) f2=0;
24 }
25 if (f1 && f2) ans++;
26 else if (f1) b[tot1-tot2]++;
27 else if (f2) c[tot2-tot1]++;
28 }
29 ans>>=1;
30 rep(i,0,500000) ans+=min(b[i],c[i]);
31 printf("%d
",ans);
32 return 0;
33 }
C
D.发现这是一个积性函数，也就是可以对每个质因子做一遍DP，然后将结果乘起来。
![]()
1 #include<cmath>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<iostream>
6 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
7 typedef long long ll;
8 using namespace std;
9
10 const int N=30010,mod=1e9+7;
11 int tot,mx,b[N],c[N];
12 ll n,K,ans=1,a[N],inv[N],f[N][100];
13
14 int main(){
15 cin>>n>>K; ll ed=sqrt(n),t=n;
16 inv[0]=inv[1]=1; rep(i,2,100) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
17 rep(i,2,ed) if (t%i==0){
18 a[++tot]=i;
19 while (t%i==0) t/=i,b[tot]++;
20 mx=max(mx,b[tot]);
21 }
22 if (t>1) a[++tot]=t,b[tot]=1;
23 rep(x,1,tot){
24 rep(i,0,K) rep(j,0,mx) f[i][j]=0;
25 f[0][b[x]]=1;
26 rep(i,1,K){
27 for (int j=b[x]; ~j; j--)
28 rep(k,j,b[x]) f[i][j]=(f[i][j]+f[i-1][k]*inv[k+1])%mod;
29 }
30 ll res=0,s=1;
31 rep(i,0,b[x]) res=(res+f[K][i]*s)%mod,s=(s*a[x])%mod;
32 ans=ans*res%mod;
33 }
34 cout<<ans<<endl;
35 return 0;
36 }
D
F.先做一次莫比乌斯变换，回答询问的时候再反演回来。
具体来说，对每个集合用bitset维护f[i]表示i的倍数的个数的奇偶性。
操作一直接赋值。操作二就是异或。操作三发现只有两个集合中的f[i]都是奇数做笛卡尔积后才会是奇数，所以就是按位与。
操作四先预处理对每个询问x，x的哪些倍数会对答案产生贡献，然后直接按位与。
https://blog.****.net/Rose_max/article/details/85833951
![]()
1 #include<bitset>
2 #include<cstdio>
3 #include<iostream>
4 #include<algorithm>
5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
6 using namespace std;
7
8 const int N=7010,M=100010;
9 int n,T,t,x,y,z,c[N];
10 bitset<N>p[N],q[N],a[M];
11
12 int main(){
13 scanf("%d%d",&n,&T); c[1]=1;
14 rep(i,1,N-1) for (int j=i*2; j<N-1; j+=i) c[j]^=c[i];
15 rep(i,1,N-1) rep(j,1,N-1){
16 if (i%j==0) p[i][j]=1;
17 if (j%i==0) q[i][j]=c[j/i];
18 }
19 while (T--){
20 scanf("%d%d%d",&t,&x,&y);
21 if (t==1) a[x]=p[y];
22 else if (t==2) scanf("%d",&z),a[x]=a[y]^a[z];
23 else if (t==3) scanf("%d",&z),a[x]=a[y]&a[z];
24 else cout<<((a[x]&q[y]).count()&1);
25 }
26 return 0;
27 }
F
![]()
1 #include<cstdio>
2 #include<iostream>
3 #define rep(i,l,r) for (int i=(l);i<=(r);i++)
4 #define ll long long
5
6 using namespace std;
7
8 const int N=1e5+10,M=210,mod=1e9+7;
9 int n,k,x,y,cnt,h[N],sz[N],f[N][M],g[M],ans[M],S[M][M],fac[M],Ans;
10 struct edge{int to,nxt;}e[N<<1];
11
12 void adde(int x,int y){
13 e[++cnt].to=y; e[cnt].nxt=h[x]; h[x]=cnt;
14 }
15
16 inline void upd(int &x,int y){x+=y; x-=x>=mod?mod:0;}
17
18 void dfs(int u,int par){
19 sz[u]=1; f[u][0]=2;
20 for (int i=h[u],v;i;i=e[i].nxt)
21 if ((v=e[i].to)!=par){
22 dfs(v,u);
23 rep(j,0,min(sz[u],k)) g[j]=f[u][j],f[u][j]=0;
24 rep(j,0,min(sz[u],k))
25 rep(l,0,min(sz[v],k-j))
26 upd(f[u][j+l],(ll)g[j]*f[v][l]%mod);
27 rep(j,0,min(sz[v],k)) upd(ans[j],mod-f[v][j]);
28 sz[u]+=sz[v];
29 }
30 rep(i,0,min(sz[u],k)) upd(ans[i],f[u][i]);
31 for (int i=min(sz[u],k);i;i--) upd(f[u][i],f[u][i-1]);
32 upd(f[u][1],mod-1);
33 }
34
35 int main(){
36 scanf("%d%d",&n,&k);
37 rep(i,1,n-1) scanf("%d%d",&x,&y),adde(x,y),adde(y,x);
38 dfs(1,0); fac[0]=1;
39 rep(i,1,k) S[i][1]=1,fac[i]=(ll)fac[i-1]*i%mod;
40 rep(i,2,k) rep(j,1,i) S[i][j]=((ll)S[i-1][j]*j+S[i-1][j-1])%mod;
41 rep(i,0,k) upd(Ans,(ll)S[k][i]*fac[i]%mod*ans[i]%mod);
42 printf("%d
",Ans);
43 return 0;
44 }
