【做题笔记】P6014 [CSGRound3]斗牛

仔细读题：另外两张牌和的个位数即为你所获得的点数。对于Subtask 1，枚举即可。50 分。
考虑：取 \(n-2\) 张牌和取答案的 \(2\) 张牌本质是一样的。因为若取符合条件的 \(n-2\) 张牌的和 \(sum\ \text{mod}\ 10\)必然为 0 。所以双重循环枚举所有的牌两两相加，把它们模 10 的余数与总和的余数对比，相等则输出。注意到若总和模 10 为 0 ，则直接输出 10。时间复杂度 \(O(n^2)\) ，80 分

#include <iostream>

#include <cstdio>

//#include <algorithm>

using namespace std;

int n,a[1000001],sum;

bool flag=false;

int main(){

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

		sum+=a[i];

	}

	sum%=10;

	if(sum==0){

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

		return 0;

	}

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

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

			if((i!=j)&&((a[i]+a[j])%10==sum)){

				printf("%d\n",(a[i]+a[j])%10);

				return 0;

			}

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

	return 0;

}

注意到一个性质：由于最后组成答案的只有两个数，且卡牌数值范围为 \(1\) ~ \(10\) ，也就说明答案只有可能是两个相同的数或不同的数。于是自然产生一种思路：用类似计数排序的方法，设一个数组 \(t\) ，记录每个数出现的次数。最后枚举每个数，若相同，则判断这个数出现的次数是否大于等于 2 ，若不同，则看这两个数是否都出现过。时间复杂度 \(O(n)\) ，可通过所有测试点。

#include <iostream>

#include <cstdio>

//#include <algorithm>

using namespace std;

int n,a[1000001],sum,t[100000001];

int main(){

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

		sum+=a[i];

		t[a[i]]++;

	}

	sum%=10;

	if(sum==0){

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

		return 0;

	}

	for(int i=1;i<=10;i++){

		for(int j=1;j<=10;j++){

			if((i==j)&&(t[i]>=2)&&((i+j)%10==sum)){

				printf("%d\n",(i+j)%10);

				return 0;

			}

			else

				if((i!=j)&&(t[i]&&t[j])&&((i+j)%10==sum)){ //注意这里首先要判断是否相等。为什么？

				printf("%d\n",(i+j)%10);

				return 0;

				}

		}

	}

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

	return 0;

}

巴特西

【做题笔记】P6014 [CSGRound3]斗牛

最新文章

热门文章