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

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

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

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

  • 牌的值仅为111010

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

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

有一个问题,有可能存在多个不同的n2n-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 个数的和

s1b(mod10),s20(mod10)\because s1\equiv b\pmod{10},s2\equiv0\pmod{10}

s3s1s2b0b(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