可能更好的阅读体验

一些闲话

本人在学校机房打的这场比赛，看了 T1 感觉其实不算很难，但是赛时就是没有做出来别骂了别骂了我知道我菜。赛后半个小时不到就写出来了，还是有点让人遗憾的。

思路

不难想到可以把一堆的牌拆成若干堆“三张牌”加上一堆一张牌或者两张牌（或者这堆牌的数量可以被 $3$ 整除就没有最后面的一堆。

因为我们发现，出牌的方式其实只有三种：

1. 单走
2. 对子
3. 三带一

为什么没有炸弹？因为四张牌一起出，就相当于是“三带一”的特殊情况（即三张和一张牌的类型相同）。

那么，我们就从最难处理的三张牌入手。

我们想要快速打完三张牌，考虑先两张再一张打肯定不可能。不难发现，我们肯定是三带一的方式比较节省步骤。

那么，没有一张牌怎么办？

我们观察到，两张牌就是两个一张牌，所以说，打出两个三张牌与一个两张牌的最快步骤就是两步（即把两张牌拆成两个一张牌然后打三带一）。

所以，我们可以针对以下情况分类讨论：

我们记 $cnt1$，$cnt2$，$cnt3$ 分别为 $1$ 张牌，$2$ 张牌，$3$ 张牌的数量。

如果所有三张牌都可以和一张牌进行匹配，那么答案就是 $cnt2+cnt1$。（这个应该很好理解）。

否则，就让多出来的三张牌和两张牌进行匹配：

如果三张牌的种类数量为偶数种，那么直接二对一即可。 此时，如果两张牌的类型特别多（即所有三张牌都可以和两张牌进行匹配），那么答案就是 $cnt3$ 加上多出来的两张牌。如果两张牌不多，也就是说有几种类型的三张牌剩下来，那么就把剩下来的三张牌单独出（关于只有三张牌怎么出我们后面会讲）。

如果三张牌的种类为奇数种，还是按照上面的套路分类讨论，但是可能会略有不同：

由于奇数类 $3$ 可以看作偶数类 $3$ 加上一类 $3$，所以前面的偶数类三直接处理，最后一张我们直接分两次出出去。

以上就是大体的思路。

接下来回收一下文章中间的问题：我剩下一堆的 $3$ 怎么出步骤更少？

我们枚举一下看看。

首先，不难想到，$4$ 类三张牌就可以分为 $3$ 个三带一出出去，所以我们尽量四张四张出。

那么不到四张怎么办？

直接手模：$1$ 类牌出 $2$ 次（三带一加上单走），$2$ 类牌出 $2$ 次（三带一加上对子），$3$ 类牌出 $3$ 次（两个三代一并且单走）。

所以说，我们可以得到一个结论：

记 biao 数组表示 $i$ 类三张牌需要出几次：

假设说我们有 $p$ 类的三张牌没出出去，我们就可以得到一个式子：

$ans = biao[p \mod 4] + biao[4] * (p / 4)$。

那么这就是所有的情况了。

一些可能遇到的状况

如果说 $50$ 分，那就是没开 long long 见祖宗。

如果说 $40$ 分 RE，注意一下请不要直接打表求出所有三张牌出出去的情况数。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e6+10;
int a[maxn],biao[maxn+10] = {2},cnt1,cnt2,cnt3,t,n;

signed main(){
	cin >> t;
	biao[0] = 0,biao[1] = 2;
	for(int i = 2;i <= 20;i++){
		biao[i] = biao[i - 1];
		if((i - 1) % 4 == 0) biao[i] += 2;
		else if((i - 1) % 2 == 0) biao[i] += 1;
	} 
	while(t--){
		cin >> n;
		int ans = 0;
		cnt1 = 0,cnt2 = 0,cnt3 = 0;
		for(int i = 1;i <= n;i++) cin >> a[i];
		for(int i = 1;i <= n;i++){
			if(a[i] == 0) continue;
			cnt3 += (a[i] / 3);
			if(a[i] % 3 == 1) cnt1++;
			else if(a[i] % 3 == 2) cnt2++;	
		}
		if(cnt1 >= cnt3){
			cout << cnt1 + cnt2 << '\n';
		}else{
			cnt3 -= cnt1;
			ans += cnt1;
			if(cnt3 % 2 == 0){
				if(cnt2 * 2 >= cnt3){
					ans += cnt3;
					ans += cnt2 - (cnt3 / 2);
				}else{
					cnt3 -= cnt2 * 2;
					ans += cnt2 * 2 + biao[cnt3 % 4]  + biao[4] * (cnt3 / 4);
				}
			}else{
				if(cnt2 * 2 >= cnt3){
					ans += cnt3 - 1;
					ans += 2;
					ans += (cnt2 - 1 - cnt3 / 2); 
				}else{
					ans += (cnt2 * 2);
					cnt3 -= cnt2 * 2;
					ans += biao[cnt3 % 4] + biao[4]  * (cnt3 / 4);
				}
			}
			cout << ans << '\n';
		}
	}
	return 0;
} 

后记

这一道下位绿题（甚至可能只能评黄）可能会让我终生难忘，因为这道题目也教会了我一些 OI 以外的东西。

这道题目仔细想想并不难，只不过**我太菜了**赛场上可能不太冷静，导致头脑有些混乱，代码也就越写越乱。

做题之前一定要保证清晰的头脑，冷静的心态，才可以把自己的能力大幅度地发挥出来。

希望自己 NOIP 不要重蹈覆辙吧。