Codeforces Round #432 Div. 1

　　A：大胆猜想合法点不会很多，于是暴力检验，一旦发现不合法就break，可以random_shuffle一下。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 1010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,ans[N],cnt;

struct data{int x[5],i;

}a[N];

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

	for (int i=1;i<=n;i++)

	{

		a[i].i=i;

		for (int j=0;j<5;j++) a[i].x[j]=read();

	}

	srand(time(0));

	random_shuffle(a+1,a+n+1);

	for (int i=1;i<=n;i++)

	{

		for (int j=1;j<=n;j++)

			for (int k=1;k<j;k++)

			{

				int s=0;

				for (int x=0;x<5;x++) s+=(a[j].x[x]-a[i].x[x])*(a[k].x[x]-a[i].x[x]);

				if (s>0) goto out;

			}

		ans[++cnt]=a[i].i;

		out:;

	}

	cout<<cnt<<endl;

	sort(ans+1,ans+cnt+1);

	for (int i=1;i<=cnt;i++) cout<<ans[i]<<' ';

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：暴力的想法是枚举最后所有数的gcd的某个质因子。于是考虑乱搞，先求出每个质数是多少个数的公共因子，显然可以得到只删数的最优答案；并且注意到要使所有数都变成偶数需要的代价不会超过nY看起来很优秀，于是对其也先算一下。然后按照出现次数从大到小枚举每个质数，如果(n-cnt)*Y都不优于当前答案就不进行暴力检验。复杂度玄学。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 500010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,X,Y,a[N],p[N<<1],prime[N],c[N<<1],id[N<<1],cnt;

bool flag[N<<1];

ll ans=0;

bool cmp(const int&a,const int&b)

{

	return c[a]>c[b];

}

ll calc(int p)

{

	ll s=0;

	for (int i=1;i<=n;i++) s+=min(1ll*X,1ll*(p-a[i]%p)%p*Y);

	return s;

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read(),X=read(),Y=read();

	for (int i=1;i<=n;i++) a[i]=read();

	flag[1]=1;

	for (int i=2;i<=1000000;i++)

	{

		if (!flag[i]) prime[++cnt]=i,p[i]=i;

		for (int j=1;j<=cnt&&prime[j]*i<=1000000;j++)

		{

			flag[prime[j]*i]=1;

			p[prime[j]*i]=prime[j];

			if (i%prime[j]==0) break;

		}

	}

	for (int i=1;i<=n;i++)

	{

		int u=a[i],P[40],t=0;

		while (u>1) P[++t]=p[u],u/=p[u];

		sort(P+1,P+t+1);

		t=unique(P+1,P+t+1)-P-1;

		for (int j=1;j<=t;j++) c[P[j]]++;

	}

	for (int i=1;i<=cnt;i++) id[i]=prime[i];

	sort(id+1,id+cnt+1,cmp);

	ans=1ll*X*(n-c[id[1]]);

	ans=min(ans,calc(2));

	for (int i=1;i<=cnt;i++)

	if (1ll*Y*(n-c[id[i]])<ans) ans=min(ans,calc(id[i]));

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：显然每个质因子是不相关的独立游戏。对于每一个质因子，当前状态只与各幂次是否出现有关。容易想到计算sg函数找找规律，发现非常困难，于是直接每次暴力算sg就过了。复杂度不会证。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

#define ll long long

#define N 10010

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,T,a[N];

map<int,int> id,f;

int dfs(int k)

{

	if (f.find(k)!=f.end()) return f[k];

	if (k==0) return 0;

	int u[32],t=0;

	for (int i=0;i<31;i++)

	if (k>=(1<<i)) u[++t]=dfs((k>>i+1)|(k&(1<<i)-1));

	for (int i=0;i<=t;i++)

	{

		for (int j=1;j<=t;j++)

		if (u[j]==i) goto out;

		return f[k]=i;

		out:;

	}

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

	for (int i=1;i<=n;i++)

	{

		int x=read();

		for (int j=2;j*j<=x;j++)

		if (x%j==0)

		{

			int t=0;

			while (x%j==0) t++,x/=j;

			if (id.find(j)==id.end()) id[j]=++T;

			a[id[j]]|=1<<t-1;

		}

		if (x>1)

		{

			if (id.find(x)==id.end()) id[x]=++T;

			a[id[x]]|=1;

		}

	}

	int ans=0;

	for (int i=1;i<=T;i++) ans^=dfs(a[i]);

	if (ans==0) cout<<"Arpa";else cout<<"Mojtaba";

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：考虑求出最少要多少个点。首先发现这个东西如果有解（事实上由paper得一定有解）点数不会超过61，由所有点度数之和的限制显然可得。容易想到设f[i][j][k]表示前i个数选了j个点其度数和为k是否合法，暴力O(m⁴)，bitset优化O(m³)。由dp数组即可求出点数并还原出一组合法方案。然后考虑构造，每次删去度数最大的点，考虑哪些点赢了它（即让这些点度数-1），显然为了满足定理的条件，应该修改度数较大的点。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<bitset>

using namespace std;

#define ll long long

#define N 32

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,a[N],b[N*N],ans[N*2][N*2],t;

bitset<N*N*2> f[N][N*2];

struct data

{

	int x,i;

	bool operator <(const data&a) const

	{

		return x<a.x;

	}

}c[N*2];

void get(int m,int n,int d)

{

	if (m==0) return;

	for (int i=1;;i++)

	if (f[m-1][n-i][d-a[m]*i])

	{

		get(m-1,n-i,d-a[m]*i);

		for (int j=1;j<=i;j++) b[++t]=a[m];

		return ;

	}

}

void make()

{

	for (int i=1;i<=n;i++) c[i].x=b[i],c[i].i=i;

	for (int i=n;i>=1;i--)

	{

		for (int j=i-1;j>=i-(i-1-c[i].x);j--)

		{

			ans[c[j].i][c[i].i]=1;

			c[j].x--;

		}

		for (int j=i-1-(i-1-c[i].x);j>=1;j--) ans[c[i].i][c[j].i]=1;

		sort(c+1,c+i);

	}

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	m=read();

	for (int i=1;i<=m;i++) a[i]=read();

	sort(a+1,a+m+1);

	f[0][0][0]=1;

	for (int i=1;i<=m;i++)

		for (int j=i;j<=62;j++)

		{

			f[i][j]|=f[i-1][j-1]<<a[i];

			f[i][j]|=f[i][j-1]<<a[i];

			f[i][j]=(f[i][j]>>(j*(j-1)/2))<<(j*(j-1)/2);

			//cout<<i<<' '<<j<<' '<<f[i][j]<<endl;

		}

	for (int i=m;i<=62;i++)

	if (f[m][i][i*(i-1)/2]) {n=i;break;}

	if (!n) {cout<<"=(";return 0;}

	get(m,n,n*(n-1)/2);

	cout<<n<<endl;

	make();

	for (int i=1;i<=n;i++)

	{

		for (int j=1;j<=n;j++)

		cout<<ans[i][j];

		cout<<endl;

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　E：不妨令第一个人取胜，设其两次获胜的状态分别为x和y，考虑每个变量，如果x和y在该位相同，其他两人的顺位可以任取，否则固定。容易发现这样的方案数即为2^{n-popcount(x^y)}。求出每种异或值出现多少次即可，裸的FWT。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<bitset>

using namespace std;

#define ll long long

#define N 21

#define P 1000000007

#define inv2 500000004

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,a[1<<N],p[N],ans;

char s[1<<N];

void FWT(int n,int *a,int op)

{

	for (int i=2;i<=n;i<<=1)

		for (int j=0;j<n;j+=i)

			for (int k=j;k<j+(i>>1);k++)

			{

				int x=a[k],y=a[k+(i>>1)];

				a[k]=(x+y)%P,a[k+(i>>1)]=(x-y+P)%P;

				if (op==1) a[k]=1ll*a[k]*inv2%P,a[k+(i>>1)]=1ll*a[k+(i>>1)]*inv2%P;

			}

}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();scanf("%s",s);

	for (int i=0;i<(1<<n);i++) a[i]=s[i]-'0';

	FWT(1<<n,a,0);

	for (int i=0;i<(1<<n);i++) a[i]=1ll*a[i]*a[i]%P;

	FWT(1<<n,a,1);

	for (int i=0;i<(1<<n);i++)

	{

		int u=n,j=i;

		while (j) j^=j&-j,u--;

		ans=(ans+1ll*a[i]*(1<<u))%P;

	}

	cout<<3ll*ans%P;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　F：考虑枚举最后变成了那个球。这样就只需要考虑只有两种球的情况了。于是我们要计算变成该球的概率*变成该球的期望步数（当然过程中该球不能全部消失）。显然相当于在数轴上随机游走。设f[i]为该球有i个时的上述值。不妨设p=i*(m-i)/m/(m-1)，即颜色发生改变的概率。有f[i]=f[i+1]*p+f[i-1]*p+f[i]*(1-2p)+i/m。最后一项不是1，因为我们只对变成该球的情况计算步数，而由众所周知的结论这个概率是i/m，所以在该点走一步产生的贡献是i/m。然后只要得到f[1]就能递推出整个数列，打表或推式子可得f[1]=(m-1)²/m。最后累加所有f[a_i]即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<bitset>

using namespace std;

#define ll long long

#define P 1000000007

#define N 2510

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,u,a[N],f[100010];

int ksm(int a,int k)

{

	int s=1;

	for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;

	return s;

}

int inv(int a){return ksm(a,P-2);}

signed main()

{

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

#endif

	n=read();

	for (int i=1;i<=n;i++) m+=a[i]=read(),u=max(u,a[i]);

	f[1]=1ll*(m-1)*(m-1)%P*inv(m)%P;

	for (int i=2;i<=u;i++) f[i]=((2*f[i-1]-f[i-2]-1ll*(m-1)*inv(m-i+1))%P+P)%P;

	int ans=0;

	for (int i=1;i<=n;i++) ans=(ans+f[a[i]])%P;

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

巴特西

Codeforces Round #432 Div. 1

最新文章

热门文章