Codeforces Round #440 Div. 1

时间：2023-03-08 21:05:26

　　A：显然应该尽量拆成4。如果是奇数，先拆一个9出来即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100010

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 q,n;

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	q=read();

	while (q--)

	{

		n=read();int ans=0;

		if (n<4) {cout<<-1<<endl;continue;}

		if (n&1)

		{

			if (n<9) {cout<<-1<<endl;continue;}

			n-=9;ans++;

			if (n==2) {cout<<-1<<endl;continue;}

		}

		ans+=n/4;

		printf("%d\n",ans);

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　B：注意到由异或的消去性，事实上可以通过2n次询问得到所有n2种询问的结果。然后若第一个数确定，整个排列就确定了，暴力枚举即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

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,a[N],b[N],c[N],d[N];

signed main()

{

	n=read();

	int u;

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

	{

		cout<<'?'<<' '<<0<<' '<<i<<endl;

		cin>>c[i];

		if (c[i]==0) u=i;

	}

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

	{

		cout<<'?'<<' '<<i<<' '<<u<<endl;

		cin>>a[i];

	}

	cout<<"!"<<endl;int ans=0;

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

	{

		for (int j=0;j<n;j++) d[j]=i^c[j];

		bool flag=0;

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

		{

			b[j]=i^a[j];

			if (b[j]==u&&i!=j)  {flag=1;break;}

		}

		for (int j=0;j<n;j++) if (b[d[j]]!=j) {flag=1;break;}

		if (!flag)

		{

			sort(b,b+n);

			for (int j=0;j<n;j++) if (b[j]!=j) {flag=1;break;}

			if (!flag) ans++;

		}

	}

	cout<<ans<<endl;

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

	{

		for (int j=0;j<n;j++) d[j]=i^c[j];

		bool flag=0;

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

		{

			b[j]=i^a[j];

			if (b[j]==u&&i!=j)  {flag=1;break;}

		}

		for (int j=0;j<n;j++) if (b[d[j]]!=j) {flag=1;break;}

		if (!flag)

		{

			for (int j=0;j<n;j++) cout<<(i^a[j])<<' ';return 0;

		}

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：同行同列相邻点连边，对每个连通块分别考虑。如果连通块构成一棵树，显然只要不选择所有直线，每种方案都能被构造出来。如果有环，考虑环上所有直线都可以被选中，而增加一个点和其相连至多会增加一条未选中直线，令该点选择该直线即可，所以所有直线都能同时被选中，所以方案都能被构造出来。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<map>

#include<cassert>

using namespace std;

#define ll long long

#define N 100010

#define P 1000000007

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=1,p[N],X[N],Y[N],t,u,v;

map<int,int> row,line;

bool flag[N];

struct data2{int to,nxt;

}edge[N<<4];

struct data

{

	int i,x,y;

	bool operator <(const data&a) const

	{

		return x<a.x;

	}

}a[N];

bool cmp1(const data&a,const data&b)

{

	return a.x<b.x;

}

void addedge(int x,int y)

{

	t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;

}

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;

}

void dfs(int k,int from)

{

	flag[k]=1;

	if (row.find(X[k])==row.end()) row[X[k]]=1,u++;

	if (line.find(Y[k])==line.end()) line[Y[k]]=1,u++;

	for (int i=p[k];i;i=edge[i].nxt)

	if (edge[i].to!=from)

		if (flag[edge[i].to]) v=0;

		else dfs(edge[i].to,k);

}

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++) X[i]=a[i].x=read(),Y[i]=a[i].y=read(),a[i].i=i;

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

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

	{

		int t=i;

		while (t<n&&a[t+1].x==a[i].x) t++;

		for (int j=i;j<t;j++) addedge(a[j].i,a[j+1].i),addedge(a[j+1].i,a[j].i);

		i=t;

	}

	for (int i=1;i<=n;i++) swap(a[i].x,a[i].y);

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

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

	{

		int t=i;

		while (t<n&&a[t+1].x==a[i].x) t++;

		for (int j=i;j<t;j++) addedge(a[j].i,a[j+1].i),addedge(a[j+1].i,a[j].i);

		i=t;

	}

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

	if (!flag[i])

	{

		row.clear();line.clear();

		u=0;v=1;dfs(i,i);

		ans=1ll*ans*(ksm(2,u)-v)%P;

	}

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：若两数互质，考虑其最小质因子，若其乘积<=n则显然两数距离为2，否则注意到可以通过2*质因子来过渡，所以只要两个数都不是>=n/2的质数或1距离就为3，否则为0。大力容斥大讨论即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 10000010

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,prime[N],phi[N],p[N],v[N],cnt;

ll ans;

bool flag[N],f[N];

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read();

	flag[1]=1;phi[1]=1;

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

	{

		if (!flag[i]) prime[++cnt]=i,phi[i]=i-1,p[i]=i,v[i]=-1;

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

		{

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

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

			if (i%prime[j]==0) {phi[prime[j]*i]=phi[i]*prime[j];break;}

			phi[prime[j]*i]=phi[i]*(prime[j]-1);

		}

	}

	ll tot=0;

	for (int i=2;i<=n;i++) tot+=phi[i],v[p[i]]++;

	ans+=1ll*n*(n-1)/2-tot; //dis=1

	int u=1;for (int i=1;i<=cnt;i++) if (prime[i]>n/2) u++;

	tot-=1ll*u*(n-1);tot+=1ll*u*(u-1)/2; //dis=0 tot=dis2+dis3

	ans+=tot*3;

	/*for (int i=2;i<=n;i++)

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

		if (gcd(i,j)==1&&1ll*p[i]*p[j]<=n) ans--;

	cout<<ans;return 0;*/

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

	if (prime[i]<=n/2)

	{

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

		if (prime[i]*prime[j]<=n) ans--;

		else break;

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

		if (prime[j]<=n/prime[i]) ans-=v[prime[j]];

		else break;

		for (int j=prime[i]*2;j<=n;j+=prime[i])

		if (p[j]<=n/prime[i]) ans++;

	}

	else break;

	u=0;

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

	if (flag[i])

	{

		ans-=i-2;

		ans+=i-1-phi[i];

		ans+=u;

		int v=i;while (v>1) ans-=!f[p[v]],f[p[v]]=1,v/=p[v];

		v=i;while (v>1) f[p[v]]=0,v/=p[v];

	}

	else u++;

	cout<<ans;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　

相关文章