2021.7.11
赛中过的C H

TC Coprime

题意：
给你一个序列，再给你一个操作，每次你可以把某个数变成任意的另一个数，问你最少多少次操作，使得序列中任意相邻两个数互质。序列长度<=1e5。

idea：
首先需要注意到互质的定义：gcd(a, b) == 1。
所以如果b是1，那么a必与b互质，尽管b既不是质数也不是合数。
然后贪一个，从左到右考虑，假设ab不互质，那么把a改成1不会比把b改成1更优。
证明：因为是从左到右考虑，所以a不改也不会与前一个冲突，而b改了之后就不和后边冲突了。
所以只需从左到右枚举所有相邻数对，如果发现二者不互质，就把后边那个搞成1。

ACcode：

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define N 101010
using namespace std;

LL n,a[N],ans = 0;

LL gcd(LL a,LL b)
{
	if( !b ) return a;
	else return gcd(b,a%b);
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}	
	for(int i=2;i<=n;i++)
	{
		if( gcd(a[i-1],a[i])!=1 )
		{
			a[i] = 1;
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

TH Huaji robot

题意：一个n*n的网格图，坐标范围为[(1,1),(n,n)]，横纵坐标互质的地方不能走，否则能走。每次能往上下左右以及斜对角线八个方向一动。给你两个点，问你能否互达。n<=1e9。

idea：先把图上能走的点打表打出来，然后就可以得到这个图

很难看是吧，好看点是这样的…

ACcode:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#define LL long long 
#define INF 0x3f3f3f3f
#define PII pair<LL,LL>
#define x first
#define y second
using namespace std;

LL gcd(LL a,LL b)
{
	if( !b ) return a;
	return gcd(b,a%b);
}

LL dx[9]={0,-1,1,0,0,-1,1,-1,1};
LL dy[9]={0,0,0,-1,1,1,1,-1,-1};
LL n;
PII s,t;
bool tag1 = false,tag2 = false,pd = false;
//map<PII,int> ma;
void bfs1()
{
	map<PII,int> ma;
	queue<PII> q;
	q.push(s);
	ma[s] = 1;
	if( s.x==s.y ) tag1 = 1;
	while( !q.empty() )
	{
		PII top = q.front();
		q.pop();
//		if( num++ <= 100 ) cout<<top.x<<" "<<top.y<<endl;
		if( top.x==t.x && top.y==t.y )
		{
			pd = true;
			return;
		}
		for(int i=1;i<=8;i++)
		{
			int xx = top.x + dx[i];
			int yy = top.y + dy[i];
			if( xx==yy )
			{
				tag1 = 1;
			}
			if( gcd( xx,yy )!=1 && xx!=yy && xx<=n && yy<=n && xx>=1 && yy>=1 )
			{
				ma[make_pair(xx,yy)];
				if( ma[make_pair(xx,yy)]==0 )
				{
					q.push( make_pair(xx,yy) );
					ma[make_pair(xx,yy)]++;
				}
			}
		}
	}
}

void bfs2()
{
	map<PII,int> ma;
	queue<PII> q;
	ma[t] = 1;
	q.push(t);
	if( t.x==t.y ) tag2 = 1;
	while( !q.empty() )
	{
		PII top = q.front();
		q.pop();
//		cout<<top.x<<top.y<<endl;
		if( top.x==s.x && top.y==s.y )
		{
			pd = true;
			return;
		}
		for(int i=1;i<=8;i++)
		{
			int xx = top.x + dx[i];
			int yy = top.y + dy[i];
			if( xx==yy )
			{
				tag2 = 1;
			}
			if( gcd( xx,yy )!=1 && xx!=yy && xx<=n && yy<=n && xx>=1 && yy>=1 )
			{
				ma[make_pair(xx,yy)];
				if( ma[make_pair(xx,yy)]==0 )
				{
					q.push( make_pair(xx,yy) );
					ma[make_pair(xx,yy)] = 1;
				}
			}
		}
	}
}

int main()
{
	cin>>n;
	cin>>s.x>>s.y>>t.x>>t.y;
	bfs1();
	if( pd==false ) bfs2();
//	cout<<pd<<" "<<tag1<<" "<<tag2<<endl;
	if( (tag1==true && tag2==true) || pd==true ) printf("gl");
	else printf("gg"); 
	return 0;
}