感觉全是思维乱搞题。
Gym - 101775J Straight Master
给你n种扑克，你每次可以出连续的3 ~ 5 张，问你能否出完。
Sample Input 2 13 1 2 2 1 0 0 0 0 0 0 0 0 0 13 1 1 1 1 0 1 1 0 0 0 0 0 0 Sample Output Case #1: Yes Case #2: No
相当于每次把一个长度为3~5的区间整体减1，问最后是否能够全部减成0。
显然，每次把一个长度大于5的区间整体减1也是可以的，因为6 = 3+3,7 = 3+4......
所以问题就变成了每次修改一个长度大于等于3的区间。
可以先维护原本序列的差分，然后区间整体减1就相当于a[l]--, a[r+1]++。
所以只要贪心的枚举每个大于0的位置，然后找后面的离他最近的小于0的数字匹配，把前者减，后者加，就可以了。
如果最近的距离 < 3那么就是不可以。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; const int maxn = 200000 + 100; int a[maxn]; LL c[maxn]; int main() { int t; scanf("%d", &t); for (int ca = 1; ca <= t; ca++) { memset(a, 0, sizeof(a)); int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n+1; i++) c[i] = a[i]-a[i-1]; bool flag = true; int r = 0; for (int i = 1; i <= n; i++) { while(c[i] > 0) { while(c[r] >= 0) if (++r > n+1) flag = false; if (r-i <= 2) flag = false; if (!flag) break; c[r] += c[i], c[i] = 0; if (c[r] > 0) c[i] = c[r], c[r] = 0; } if (!flag) break; } printf("Case #%d: %s ", ca, flag?"Yes":"No"); } }
Gym - 101775L SOS
有一个长度为n的数组，Panda和Sheep轮流往一个空的位置上放 "S" 或者是 "O"。
如果有人放完后，构成一个连续的 "SOS"，那么这个人就胜利。
现在是Panda先手，再两个人足够决策的情况下，谁会获胜？
平局输出"Draw"。
Sample Input 2 3 7 Sample Output Case #1: Draw Case #2: Panda
首先，可以看出一个必胜态一定存在一个S_ _S的情况。
如果构成了这个必胜态，n为奇数时先手胜，n为偶数时先手败。
先讨论n为奇数：
显然的一点就是当n >= 7时，一定存在一个位置，先手放S可以构成一个必胜态，此时后手是无法阻止他的。
所以n为奇数且n >= 7时，先手是必胜的。
再讨论n为偶数：
根据上面的结论，此时先手一定不想构成一个S_ _S的局面，所以第一步一定放O，来尽可能阻止后手构成此必胜态。
什么时候阻止不了呢？当放O的点左边或右边有至少8个点的时候。此时n为16。
综上，n%2 == 1 && n >= 7，先手胜；n%2 == 0 && n >= 16，后手胜；否则就是平局。
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; typedef long long LL; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { int t; scanf("%d", &t); if (t%2 == 1 && t >= 7) printf("Case #%d: Panda ", i); else if (t%2 == 0 && t >= 16) printf("Case #%d: Sheep ", i); else printf("Case #%d: Draw ", i); } }