A. Good ol’ Numbers Coloring

题意：给你两个数 aa 和 bb，现在对全体自然数进行染色处理。

染色规则如下：

  1. 00 为白色；
  2. 如果 x≥ax\geq a，并且 x−ax-a 是白色，那么 xx 是白色；
  3. 如果 x≥bx\geq b，并且 x−bx-b 是白色，那么 xx 是白色；
  4. 如果以上条件均不满足，那么这个数是黑色。

现在给定 aa 和 bb，询问黑色的数的数量是有限还是无限个。

解析：很明显，我们可以很快想到裴蜀定理：

ax+by=c (gcd⁡(a,b)=d) ax+by=c\ (\gcd (a,b)=d)

在这个式子中，任意 xx 和 yy 都能满足 cc 是 dd 的倍数。

所以如果 d≠1d\neq1，即 a,ba,b 不互质，那么肯定是无限个，因为只有 dd 的倍数会被染成白色，其他的全是黑色，此时为无限个；

所以如果 d=1d=1，即 a,ba,b 互质，答案为有限个，具体证明(其实我没看懂)见题解。

所以直接判断是否互质就行了。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int t,a,b;
int gcd(int a,int b)
{
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&a,&b);
		if(gcd(a,b)==1)
			printf("Finite\n");
		else
			printf("Infinite\n");
	}
	return 0;
}

B. Restricted RPS

题意：给出对手的石头剪刀布的出牌顺序，一共比赛 nn 次，其中你必须出 aa 次石头，bb 次布，cc 次剪刀，但是你可以自行安排出牌顺序，如果你赢了对手 ⌈n2⌉\lceil\frac{n}{2}\rceil 次，那么最终你就胜利，询问你最后能否能获得胜利。

解析：贪心题(为什么我考场上就做不对。。。，思路完全正确，码力有待加强)。能赢就赢，先把能够赢的次数用掉，最后再把剩下的次数随便用上去就行了。

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int t,n,a,b,c,ans;
char x[110],y[110];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		ans=0;
		scanf("%d%d%d%d\n",&n,&a,&b,&c);
		scanf("%s",x+1);
		for(int i=1;i<=n;i++)
		{
			if(x[i]=='R'&&b>0)
			{
				y[i]='P';
				b--;
				ans++;
			}
			if(x[i]=='P'&&c>0)
			{
				y[i]='S';
				c--;
				ans++;
			}
			if(x[i]=='S'&&a>0)
			{
				y[i]='R';
				a--;
				ans++;
			}
		}
		if(ans>=(n-n/2))
		{
			printf("YES\n");
			for(int i=1;i<=n;i++)
				if(!y[i])
				{
					if(a)
					{
						y[i]='R';
						a--;
					}
					else if(b)
					{
						y[i]='P';
						b--;
					}
					else
					{
						y[i]='S';
						c--;
					}
				}
			printf("%s\n",y+1);
		}
		else
			printf("NO\n");
	}
	return 0;
}

C. Constanze’s Machine

题意：给你一个替换法则，法则如下：

  1. 所有的 m 都要被替换为 nn；
  2. 所有的 w 都要被替换为 uu。

现在给出替换后的字符串，问替换前的字符串有几种可能，答案对 109+710^9+7 取模。

解析：很明显，如果给出的字符串中出现了 m 或者 w，那么这个字符串是不合法的，答案为 00。

接下来分析连续 n 或者 u 的个数与答案的关系，以 n 为例：

如果有一段为 nn，那么这一段有 22 种可能，分别是 nn 或者 m；

如果有一段为 nnn，那么这一段有 33 种可能，分别是 nnn，mn，nm；

如果有一段为 nnnn，那么这一段有 55 种可能，分别是 nnnn，mnn，nmn，nnm，mm；

······；

然后我们把表列出来：

nn 的个数 22 33 44 55 66 ···
可能的情况数 22 33 55 88 1313 ···

发现什么没有(疯狂暗示)？

没错，Fibonacci 数列！！

所以我们直接先预处理 Fibonacci 数列，然后把每种情况的可能相乘即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
char s[101010];
int len,sum1,sum2;
int f[101010],mod=1e9+7;
long long ans=1;
int main()
{
	scanf("%s",s+1);
	len=strlen(s+1);
	f[0]=1;
	f[1]=1;
	for(int i=2;i<=len;i++)
		f[i]=(f[i-1]%mod+f[i-2]%mod)%mod;
	for(int i=1;i<=len;i++)
	{
		if(s[i]=='m'||s[i]=='w')
		{
			printf("0");
			return 0;
		}
		if(s[i]!='n'&&sum1)
		{
			ans*=f[sum1];
			ans%=mod;
			sum1=0;
		}
		if(s[i]!='u'&&sum2)
		{
			ans*=f[sum2];
			ans%=mod;
			sum2=0;
		}
		if(s[i]=='n')
		{
			sum1++;
			continue;
		}
		if(s[i]=='u')
		{
			sum2++;
			continue;
		}
	}
	if(sum1)
		ans=ans*f[sum1]%mod;
	if(sum2)
		ans=ans*f[sum2]%mod;
	printf("%lld",ans%mod);
	return 0;
}

D. Shichikuji and Power Grid

题意：有 nn 个点，在第 ii 个点修建电站的费用为 cic_i，连接两个点的费用为 (ki+kj)(∣xi−xj∣+∣yi−yj∣)(k_i+k_j)(|x_i-x_j|+|y_i-y_j|)，连接两个点，如果其中一个点有电，那么另外一个点也会有电，问最小花费的方案，使每个点都有电。

解析：

原题：[USACO08OCT]打井Watering Hole。

对于建站的费用(即点权)，我们可以建一个超级原点，把原点往每个点上连一条边权为 cic_i 的边，这样就把点权转换为了边权。

然后就是一个最小生成树的裸题了，这题不卡 Kruskal，直接开始码。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,x[2010],y[2010];
long long c[2010],k[2010];
long long cnt=0;
long long fa[2010],v,e,ans1[2010],ans2[2010][2];
long long ans;
struct node
{
	long long next;
	long long to;
	long long num;
}edge[4001010];
bool cmp(node a,node b)
{
	return a.num<b.num;
}
void add(long long from,long long to,long long num)
{
	edge[++cnt].next=from;
	edge[cnt].to=to;
	edge[cnt].num=num;
}
long long dis(long long a,long long b)
{
	return (k[a]+k[b])*(abs(x[a]-x[b])+abs(y[a]-y[b]));
}
long long getfa(long long x)
{
	if(fa[x]==x)
		return x;
	return fa[x]=getfa(fa[x]);
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&x[i],&y[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&c[i]);
	for(int i=1;i<=n;i++)
		scanf("%lld",&k[i]);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			add(i,j,dis(i,j));
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;
		add(0,i,c[i]);
	}
	sort(edge+1,edge+cnt+1,cmp);
	for(int i=1;i<=cnt;i++)
	{
		int x=getfa(edge[i].next);
		int y=getfa(edge[i].to);
		if(x==y)
			continue;
		fa[x]=y;
		ans+=edge[i].num;
		if(edge[i].next==0)
		{
			ans1[++v]=edge[i].to;
			continue;
		}
		if(edge[i].to==0)
		{
			ans1[++v]=edge[i].next;
			continue;
		}
		if(edge[i].next!=0&&edge[i].to!=0)
		{
			ans2[++e][0]=edge[i].next;
			ans2[e][1]=edge[i].to;
			continue;
		}
	}
	printf("%lld\n",ans);
	printf("%lld\n",v);
	for(int i=1;i<=v;i++)
		printf("%lld ",ans1[i]);
	printf("\n");
	printf("%lld\n",e);
	for(int i=1;i<=e;i++)
		printf("%lld %lld\n",ans2[i][0],ans2[i][1]);
	return 0;
}