2 条题解
-
3
一些闲话
本人在学校机房打的这场比赛,看了 T1 感觉其实不算很难,但是赛时就是没有做出来
别骂了别骂了我知道我菜。赛后半个小时不到就写出来了,还是有点让人遗憾的。思路
不难想到可以把一堆的牌拆成若干堆“三张牌”加上一堆一张牌或者两张牌(或者这堆牌的数量可以被 整除就没有最后面的一堆。
因为我们发现,出牌的方式其实只有三种:
- 单走
- 对子
- 三带一
为什么没有炸弹?因为四张牌一起出,就相当于是“三带一”的特殊情况(即三张和一张牌的类型相同)。
那么,我们就从最难处理的三张牌入手。
我们想要快速打完三张牌,考虑先两张再一张打肯定不可能。不难发现,我们肯定是三带一的方式比较节省步骤。
那么,没有一张牌怎么办?
我们观察到,两张牌就是两个一张牌,所以说,打出两个三张牌与一个两张牌的最快步骤就是两步(即把两张牌拆成两个一张牌然后打三带一)。
所以,我们可以针对以下情况分类讨论:
我们记 ,, 分别为 张牌, 张牌, 张牌的数量。
如果所有三张牌都可以和一张牌进行匹配,那么答案就是 。(这个应该很好理解)。
否则,就让多出来的三张牌和两张牌进行匹配:
如果三张牌的种类数量为偶数种,那么直接二对一即可。 此时,如果两张牌的类型特别多(即所有三张牌都可以和两张牌进行匹配),那么答案就是 加上多出来的两张牌。如果两张牌不多,也就是说有几种类型的三张牌剩下来,那么就把剩下来的三张牌单独出(关于只有三张牌怎么出我们后面会讲)。
如果三张牌的种类为奇数种,还是按照上面的套路分类讨论,但是可能会略有不同:
由于奇数类 可以看作偶数类 加上一类 ,所以前面的偶数类三直接处理,最后一张我们直接分两次出出去。
以上就是大体的思路。
接下来回收一下文章中间的问题:我剩下一堆的 怎么出步骤更少?
我们枚举一下看看。
首先,不难想到, 类三张牌就可以分为 个三带一出出去,所以我们尽量四张四张出。
那么不到四张怎么办?
直接手模: 类牌出 次(三带一加上单走), 类牌出 次(三带一加上对子), 类牌出 次(两个三代一并且单走)。
所以说,我们可以得到一个结论:
记
biao
数组表示 类三张牌需要出几次:假设说我们有 类的三张牌没出出去,我们就可以得到一个式子:
。
那么这就是所有的情况了。
一些可能遇到的状况
如果说 分,那就是没开
long long
见祖宗。如果说 分 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 不要重蹈覆辙吧。
-
1
#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; const int N = 300010; int n, m; int g[N]; LL t[3]; int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * f; } int main() { int T; cin >> T; while (T -- ) { cin >> n; memset(t, 0, sizeof t); LL cnt = 0; // 三带的数量(三张相同) for (int i = 1; i <= n; i ++ ) { g[i] = read(); cnt += g[i] / 3; t[g[i] % 3] ++ ; } if (t[1] > cnt) cout << t[1] - cnt + cnt + t[2] << endl; // 带不走全部1 else { if ((cnt - t[1]) / 2 >= t[2]) // 还能带走2 { LL x = cnt - t[1] - 2 * t[2]; // 剩余三带数量 LL sum = t[1] + 2 * t[2] + x * 3 / 4; // x * 3 / 4是三带带自己 if (x * 3 % 4 == 3) sum += 2; // 带完还剩三张相同,(不能直接输出三张相同),就分为一个单牌和一个对子 else if (x * 3 % 4 == 2 || x * 3 % 4 == 1) sum ++ ; // 直接输出对子/单牌 cout << sum << endl; } // 带不走2 else cout << cnt + t[2] - (cnt - t[1]) / 2 << endl; } // (cnt - t[1]) / 2 是还能带走2的的数量 } return 0; }
- 1
信息
- ID
- 97
- 时间
- 3000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 742
- 已通过
- 194
- 上传者