看到这道题的时候，其实我第一反应是“天哪，这道题这么难，nn这么大，不是 dp 就是记忆化吧”（蒟蒻之言，大佬勿喷 QAQ）

然后再仔细读了一下题，发现几件事情：

  • 不管nn有多大，始终会有两张牌不被选。

  • 因为被选上的n−2n-2张牌是1010的倍数，因此个位为00，所以剩下22张牌的个位和这nn个数之和的个位是一样的。

  • 牌的值仅为11至1010。

于是，我突然想到，既然正着算这n−2n-2个数不容易，那就反过来算剩下的两个数呗！

所以，最后我的办法是，算出nn个数的和，桶排每种数值的个数，暴力枚举出两个数，这两个数的和的个位等于所有数总和的个位。

有一个问题，有可能存在多个不同的n−2n-2个数的组合，比如：2,8,1,9{2,8,1,9}这组数，既可以选出2,8{2,8}，又可以选出1,9{1,9}，怎么办呢？

其实仔细想一下，不管怎么选，其答案是唯一的，因为所有数的和是唯一的，其个位也是唯一的，所以点数也是唯一的。

还是证明一下吧（蒟蒻用不来数学公式，只能语言描述 QAQ）：

令 s1=n 个数的总和，s2=符合要求的 n-2 个数的和，s3=剩下 2 个数的和

∵s1≡b(mod10),s2≡0(mod10)\because s1\equiv b\pmod{10},s2\equiv0\pmod{10}

∴s3≡s1−s2≡b−0≡b(mod10)\therefore s3\equiv s1-s2\equiv b-0 \equiv b\pmod{10}

综上所述，要求的 2 个数之和的个位与 n 个数之和的个位相同，所以点数是唯一的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
using namespace std;
int n,sum,b[11];//这个题数据较小，sum 用 int 也不会爆
int main()
{
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		int a;
		scanf("%d",&a);
		sum+=a;
		b[a]++;//桶排计算各种牌值的个数
	}
	for(int i=1; i<=10; i++)
		for(int j=1; j<=10; j++)//两重循环暴力求剩下的两个数
			if(((i==j&&b[i]>=2)||(i!=j&&b[i]>=1&&b[j]>=1))&&(i+j)%10==sum%10)//判断牌的个数够不够，以及这两张牌的和的个位是否与所有牌的和的个位相同
			{
				if((i+j)%10==0)//记得特判！！！
					printf("10");
				else
					printf("%d",(i+j)%10);
				return 0;//找到了就直接退出，因为点数是唯一的
			}
	printf("0");
	return 0;
}

其实这两重循环还可以再优化，但我觉得没有太大的必要了，毕竟这也只循环了100100次而已。

蒟蒻求赞 qwq