Feeling is all about thinking.
Gym – 101775J Straight Master
To give you n poker, you can produce 3 to 5 sheets each time and ask if you can finish it.
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
It is equivalent to reducing the total length of a 3~5 interval by 1 to 0.
Obviously, it is also possible to reduce an interval that is longer than 5 by 1 at a time, because 6 = 3 + 3, 7 = 3 + 4…
So the problem becomes an interval with a length greater than or equal to 3 each time.
The difference between the original sequence can be maintained first and then the whole interval minus 1 is equivalent to a[l]–, a[r+1]++.
So as long as the greedy enumeration of each position greater than 0, and then look for the next from his nearest less than 0 to match the number, subtract the former, the latter add, it is OK.
If the nearest distance is <, then 3 is not allowed.
#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\n", ca, flag?"Yes":"No"); } }
Gym – 101775L SOS
There is an array of N length. Panda and Sheep rotate the S or O in an empty location.
If someone is finished, it forms a continuous “SOS”, then the person wins.
Now that Panda is in the lead, and if two more people make enough decisions, who will win?
The flat output is “Draw”.
Sample Input 2 3 7 Sample Output Case #1: Draw Case #2: Panda
First, we can see that there must be a S_ _S in a winning state.
If this constitutes a winning state, n will win first and n even.
First, we discuss n as odd.
The obvious point is that when n> = 7, there must be a position where the first hand to put S can constitute a winning position, at this point the second hand is unable to stop him.
So n is odd and N > = 7, the first hand is the winner.
Another discussion is that n is even.
According to the above conclusion, the first hand must not want to form a S_S situation, so the first step must put O, as far as possible to prevent the second hand from forming this must win.
When can’t we stop it? When there are at least 8 points on the left or right side of O. At this point, n is 16.
To sum up, n% 2 = = 1 & amp; & amp; n & gt; = 7, win first; n% 2 = = 0 & amp; & amp; n & gt; = 16, win second; otherwise, draw.
#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\n", i); else if (t%2 == 0 && t >= 16) printf("Case #%d: Sheep\n", i); else printf("Case #%d: Draw\n", i); } }