AtCoder AGC022C Remainder Game (图论)

题目链接

https://atcoder.jp/contests/agc022/tasks/agc022_c

题解

大水题一道

就他给的这个代价，猜都能猜到每个数只能用一次

仔细想想，我们肯定是按顺序从大到小用，一个数用多次肯定没意义，于是证完了

并且所有元素独立

所以我们就是要从大到小贪心判断每个元素是否能不用

比如当前要判断\(x\)是否能不用，那么就判断用当前已经确定要用的集合并上所有小于\(x\)的数能不能达到目的

这个东西建个图判一下连通性就行了

时间复杂度\(O(N^4)\)

代码

#include<cstdio>

#include<cstdlib>

#include<iostream>

#define llong long long

using namespace std;

void read(int &x)

{

    int f=1;x=0;char s=getchar();

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

    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

    x*=f;

}

const int N = 50;

int f[N+3][N+3];

int a[N+3];

int b[N+3];

int n;

bool check(llong sta)

{

	for(int i=0; i<=N; i++) for(int j=0; j<=N; j++) f[i][j] = i==j?1:0;

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

	{

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

		{

			if(sta&(1ll<<j)) {f[i][i%j] = 1;}

		}

	}

	for(int k=0; k<=N; k++)

	{

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

		{

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

			{

				f[i][j] |= (f[i][k]&f[k][j]);

			}

		}

	}

	bool ret = true;

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

	{

		if(!f[a[i]][b[i]]) {ret = false; break;}

	}

	return ret;

}

int main()

{

	scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); for(int i=1; i<=n; i++) scanf("%d",&b[i]);

	llong sta = (1ll<<38)-2;

	if(!check(sta)) {puts("-1"); return 0;}

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

	{

		llong tmp = sta^(1ll<<i);

		if(check(tmp)) {sta = tmp;}

	}

	printf("%lld\n",sta);

	return 0;

}

巴特西

AtCoder AGC022C Remainder Game (图论)

题目链接

题解

代码

最新文章

热门文章