比赛

[CF1097X]Hello 2019

Posted by Dispwnl on January 4, 2019

上紫纪念

A　　Gennady and a Card Game

题目大意

每个元素有两个值a,ba,b，现在你有55个元素，问是否有一个元素与给定元素aa相等或者bb相等

题解

。

代码

# include<bits/stdc++.h>
using namespace std;
int A,B;
int a[5],b[5];
char s[5][10],qwq[10];
int main()
{
	scanf("%s",qwq);
	A=qwq[0],B=qwq[1];
	for(int i=0;i<5;++i)
	  {
	  	scanf("%s",s[i]);
	  	a[i]=s[i][0],b[i]=s[i][1];
	  	if(a[i]==A||B==b[i]) return printf("YES\n"),0;
	  }
	return printf("NO\n"),0;
}

B　　Petr and a Combination Lock

题目大意

给定nn个角度aia_i，初始在0°0°位置，第ii次操作顺/逆时针旋转ai°a_i°，问能否在nn次旋转后回到0°0°的位置

题解

nn最大才1515，状态压缩一下表示即可

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
int n;
int a[21];
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	  scanf("%d",&a[i]);
	for(int i=0;i<(1<<n);++i)
	  {
	  	int ans=0;
	  	for(int j=0;j<n;++j)
	  	  if(i&(1<<j)) ans+=a[j];
	  	  else ans-=a[j];
	  	if(ans%360==0) return puts("YES"),0;
	  }
	return puts("NO"),0;
}

C　　Yuhao and a Parenthesis

题目大意

给定nn个括号序列（不一定合法），每次可以选择两个没选过的序列首尾相连合并成一个括号序列，问合并之后最多有多少个合法括号序列

题解

把'('定为11，')'定为−1-1，可以记录每个括号序列的总和和最小前缀和，显然)...(这种是不可能组成合法的括号序列的，分总和>0,=0,<0>0,=0,<0三种情况讨论一下即可

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<map>
# include<algorithm>
using namespace std;
const int MAX=1e5+5;
int n,ans;
char a[MAX*5];
map<int,int> ma;
int main()
{
	scanf("%d",&n);
	for(int i=1,_n,w,_w;i<=n;++i)
	  {
	  	scanf("%s",a),_n=strlen(a),w=0,_w=1e9;
	  	for(int j=0;j<_n;++j)
	  	  {
	  	  	if(a[j]=='(') ++w;
	  		else --w;
	  		_w=min(_w,w); 
		  }
		if(!w&&_w>=0)
		{
			if(ma[w]) --ma[w],++ans;
			else ++ma[w];
		}
		if(w>0&&_w>=0)
		{
			if(ma[-w]) --ma[-w],++ans;
			else ++ma[w];
		}
		if(w<0&&_w>=w)
		{
			if(ma[-w]) --ma[-w],++ans;
			else ++ma[w];
		}
	  }
	return printf("%d",ans),0;
}

D　　Makoto and a Blackboard

题目大意

给定两个数n,kn,k，每次随机选择nn的某个因子aa使得n=an=a，问操作kk次后nn的期望值

题解

如果n=pmn=p^m（pp为素数）就可以直接暴力枚举mm然后dpdp了

因为n=p1m1×p2m2×…×plmln=p_1^{m_1}\times p_2^{m_2}\times…\times p_l^{m_l}（对nn质因子分解），所以答案为∏i=1lans(pimi)\prod_{i=1}^{l} ans(p_i^{m_i})，具体为什么不会证……听说好像是跟积性函数有关？管他呢A了就行了

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<map>
# include<algorithm>
# define LL long long 
using namespace std;
const int MAX=1e4+5,mod=1e9+7;
LL n;
int k,cnt,ans=1;
LL qwq[MAX];
int f[101][MAX];
map<LL,int> ma;
int Pow(LL a,int b)
{
	int ans=1;
	a%=mod;
	for(;b;b>>=1,a=1ll*a*a%mod)
	  if(b&1) ans=1ll*a*ans%mod;
	return ans;
}
int dfs(LL A,int x,int t=0)
{
	if(f[x][t]) return f[x][t];
	if(t==k) return Pow(A,x);
	int ans=0;
	for(int i=0;i<=x;++i)
	  ans=(ans+dfs(A,i,t+1))%mod;
	return f[x][t]=1ll*ans*Pow(x+1,mod-2)%mod;
}
int main()
{
	cin>>n>>k;
	for(int i=2;i<=sqrt(n);++i)
	  while(n%i==0)
	  {
	  	if(++ma[i]==1) qwq[++cnt]=i;
	  	n/=i;
	  }
	if(n!=1) if(++ma[n]==1) qwq[++cnt]=n;
	for(int i=1;i<=cnt;++i)
	  memset(f,0,sizeof(f)),ans=1ll*ans*dfs(qwq[i],ma[qwq[i]])%mod;
	return printf("%d",ans),0;
}

E　　Egor and an RPG game

F　　Alex and a TV Show

题目大意

给定nn个初始为空的集合（可重集），有四个操作：

  • 给定集合位置xx和一个数vv，然后Sx=vS_x={v}
  • 给定集合位置x,y,zx,y,z，然后Sx=Sy∪SzS_x=S_y∪S_z
  • 给定集合位置x,y,zx,y,z，然后Sx=gcd⁡(a,b)∣a∈Sy,b∈SzS_x={\gcd(a,b)\vert a\in S_y,b\in S_z}
  • 给定集合位置xx和一个数vv，然后输出集合xx中有多少个vv，答案%2\%2

题解

用fx,if_{x,i}表示集合SxS_x中ii的倍数出现次数的奇偶性，可以用bitset维护

因为值域才70007000，操作一可以直接n\sqrt{n}枚举修改

操作二发现都是11的时候答案是00，都是00的时候答案是00，一个是0,10,1的时候答案是11，所以就是一个异或操作

操作三发现都是11的时候答案是11，都是00的时候答案是00，一个是0,10,1的时候答案是00，所以就是一个与操作

操作四可以莫比乌斯反演一下：

设Fx,iF_{x,i}表示集合SxS_x中ii的出现次数，则有

fx,i=∑i∣jFx,jf_{x,i}=\sum_{i\vert j}F_{x,j}

Fx,i=∑i∣jμ(ji)fx,jF_{x,i}=\sum_{i\vert j}\mu(\frac{j}{i})f_{x,j}

因为fx,if_{x,i}只有0/10/1两种取值，所以μ\mu的值为−1-1和11没有区别，预处理一下即可

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<bitset>
# include<cmath> 
# include<algorithm>
using namespace std;
const int MAX=1e5+5,N=7e3+5;
int n,q,tot;
int u[N],pm[N];
bool use[N];
bitset<N> a[MAX],b[N],w[N];
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
int main()
{
	n=read(),q=read(),u[1]=1;
	for(int i=2;i<N;++i)
	  {
	  	if(!use[i]) pm[++tot]=i,u[i]=-1;
	  	for(int j=1;j<=tot&&i*pm[j]<N;++j)
	  	  {
	  	  	use[i*pm[j]]=1;
	  	  	if(i%pm[j]==0) break;
	  	  	u[i*pm[j]]=-u[i];
		  }
	  }
	for(int i=1,x;i<N;++i)
	  {
	  	x=sqrt(i);
	  	for(int j=1;j<=x;++j)
	  	  if(i%j==0) w[i][j]=w[i][i/j]=1;
	  }
	for(int i=1;i<N;++i)
	  for(int j=i;j<N;j+=i)
	    if(u[j/i]) b[i][j]=1;
	for(int i=1,op,x,y,z;i<=q;++i)
	  {
	  	op=read(),x=read(),y=read();
	  	if(op==1) a[x]=w[y];
	  	else if(op==2) z=read(),a[x]=a[y]^a[z];
	  	else if(op==3) z=read(),a[x]=a[y]&a[z];
	  	else if(op==4) printf("%d",(a[x]&b[y]).count()%2);
	  }
	return 0;
}
FRIENDS