Codeforces Round #454 Div. 1

2022-08-02 08:41:18

　　B：考虑2*m怎么构造。因为要求相邻的数不能再相邻，容易想到黑白染色之类的东西，考虑染个色然后大概把黑点扔一边白点扔一边。显然m<=3时无解。对m>4，m为偶数时，如1 2 3 4 5 6   7 8 9 10 11 12，就变换成1 3 5 2 4 6   8 10 12 7 9 11；m为奇数时，如1 2 3 4 5   6 7 8 9 10，就变换成1 3 5 2 4   7 9 6 8 10（当然奇偶没有本质区别）。非常开心的发现我们只要把2*m的方案往下复制就可以得到n*m的方案了。n>3和m>3没有本质区别。上面的构造对m=4不适用，直接把样例搬过来就好，但要判n为奇数的情况，最后一行特殊处理。最后特判一下n=m=3和n=m=1，随便构造一组即可。

#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 n,m,a[2][N],b[2][N];

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	cin>>n>>m;

	if (n==1&&m==1) {cout<<"YES"<<endl;cout<<"1";return 0;}

	if (n==3&&m==3)

	{

		cout<<"YES"<<endl;

		cout<<"6 1 8"<<endl;

		cout<<"7 5 3"<<endl;

		cout<<"2 9 4"<<endl;

		return 0;

	}

	if (n<=3&&m<=3) {cout<<"NO";return 0;}

	cout<<"YES"<<endl;

	if (m>3)

	{

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

		if (m>4)

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

		{

			if (i<=(m+1>>1)) b[0][i]=a[0][i*2-1];else b[0][i]=a[0][(i-(m+1>>1))<<1];

			if (i<=(m>>1)) b[1][i]=a[1][i*2];else b[1][i]=a[1][(i-(m>>1))*2-1];

		}

		else

		{

			b[0][1]=a[1][1];b[0][2]=a[0][4];b[0][3]=a[1][3];b[0][4]=a[0][2];

			b[1][1]=a[0][3];b[1][2]=a[1][2];b[1][3]=a[0][1];b[1][4]=a[1][4];

		}

		for (int i=0;i<n-(m==4&&(n&1));i++)

		{

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

			printf("%d ",b[i&1][j]+(i-(i&1))*m);

			printf("\n");

		}

		if (m==4&&(n&1)) cout<<n*m-2<<' '<<n*m<<' '<<n*m-3<<' '<<n*m-1<<endl;

	}

	else

	{

		swap(n,m);

		for (int i=1;i<=m;i++) a[0][i]=(i-1)*n+1,a[1][i]=(i-1)*n+2;

		if (m>4)

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

		{

			if (i<=(m+1>>1)) b[0][i]=a[0][i*2-1];else b[0][i]=a[0][(i-(m+1>>1))<<1];

			if (i<=(m>>1)) b[1][i]=a[1][i*2];else b[1][i]=a[1][(i-(m>>1))*2-1];

		}

		else

		{

			b[0][1]=a[1][1];b[0][2]=a[0][4];b[0][3]=a[1][3];b[0][4]=a[0][2];

			b[1][1]=a[0][3];b[1][2]=a[1][2];b[1][3]=a[0][1];b[1][4]=a[1][4];

		}

		swap(n,m);

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

		{

			for (int j=0;j<m-(n==4&&(m&1));j++)

			printf("%d ",b[j&1][i]+j-(j&1));

			if (n==4&&(m&1))

			{

				if (i==1) cout<<2*m;

				if (i==2) cout<<4*m;

				if (i==3) cout<<1*m;

				if (i==4) cout<<3*m;

			}

			printf("\n");

		}

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　C：冷静一下可以发现交换操作顺序对结果并没有影响，于是暴力枚举对哪个点集操作即可。但枚举完暴力验证可能不能做到很优美的复杂度。注意到最后一步操作的点一定是与所有点相连的，于是暴力dfs过程中压位记录每个点与其他点是否直接相连，操作的影响可以O(n)更新，即可做到O(2n·n)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 22

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][N],f[N],size[1<<N],LG2[1<<N],ans,End;

bool flag[1<<N];

void dfs(int i,int *f)

{

	flag[i]=1;

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

	if (!flag[i|(1<<j)])

	{

		int g[N];

		for (int x=0;x<n;x++) g[x]=f[x];

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

		if (g[j]&(1<<x)) f[x]|=g[j];

		dfs(i|(1<<j),f);

		for (int x=0;x<n;x++) f[x]=g[x];

	}

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

	if (f[j]==(1<<n)-1&&size[ans]>size[i]) ans=i,End=j;

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read(),m=read();if (m==n*(n-1)/2) {cout<<0;return 0;}

	while (m--)

	{

		int x=read()-1,y=read()-1;

		a[x][y]=a[y][x]=1;

	}

	for (int i=1;i<(1<<n);i++) size[i]=size[i^(i&-i)]+1,LG2[i]=size[i]==1?LG2[i>>1]+1:0;

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

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

		if (a[i][j]||i==j) f[i]|=1<<j;

	ans=(1<<n)-1;

	dfs(0,f);

	cout<<size[ans]+1<<endl;

	while (ans) cout<<LG2[ans&-ans]<<' ',ans^=ans&-ans;

	cout<<End+1;

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　D：经典trick？恶心至极的就是判扩展欧拉定理要不要+φ(p)，写的乱七八糟不知道是啥。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cassert>

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 n,m,p[70],a[N],pre[N],pos[N],cnt,q;

int ksm(int a,int k,int P)

{

	int s=1;

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

	return s;

}

ll KSM(int a,ll k)

{

	ll s=1;if (k>32) return 2000000000;

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

	{

		s*=a;

		if (s>=2000000000) break;

	}

	return s;

}

ll get(int l,int r)

{

	ll s=1;

	for (int i=pre[r];i>=l;i=pre[i-1])

	{

		s=KSM(a[i],s);

		if (s>=2000000000) break;

	}

	return s;

}

signed main()

{

#ifndef ONLINE_JUDGE

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

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

#endif

	n=read(),p[0]=read();

	m=0;

	while (p[m]>1)

	{

		m++;int x=p[m]=p[m-1];

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

		if (x%i==0){p[m]/=i;p[m]*=i-1;while (x%i==0) x/=i;}

		if (x>1) p[m]/=x,p[m]*=x-1;

	}

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

	for (int i=1;i<=n;i++) if (a[i]==1) pos[++cnt]=i,pre[i]=pre[i-1];else pre[i]=i;

	pos[++cnt]=n+1;

	q=read();

	while (q--)

	{

		int l=read(),r=read(),ans=1;

		int u=*lower_bound(pos+1,pos+cnt+1,l);

		ll t=get(min(min(r,l+m),u-1)+1,r);if (u<=min(r,l+m)) t=1;

		for (int i=min(min(r,l+m),u-1);i>=l;i--)

		{

			ans=ksm(a[i],ans,p[i-l]);t=KSM(a[i],t);

			if (i>l&&t>=p[i-l]) ans+=p[i-l];

		}

		printf("%d\n",ans%p[0]);

	}

	return 0;

	//NOTICE LONG LONG!!!!!

}

　　

上一篇：前端用verify.js写验证码（普通、滑动、点选验证码）


下一篇：关于IDEA连接MySQL数据库时解决serverTimezone报错