AtCoder AGC002E Candy Piles (博弈论)

神仙题。。表示自己智商不够想不到。。。

好几次读成最后拿的赢了，导致一直没看懂题解。。。

题目链接: https://atcoder.jp/contests/agc002/tasks/agc002_e

题解: 首先所有数从大到小排序，如果把每个数上面画出高度等于它数值的柱状图，那么就可以得到一条从左上角走到右下角的Lattice Path, 两人从原点开始每一步操作就相当于向右或向上走一格，走到边界的输。

那么朴素的DP是(O(sum a_i))的，考虑优化: 找规律可得从一个不在边界上的点每次往斜下方走一格，那么走的路径上的胜负状态都一样。所以可以从原点走到离边界恰好一格的地方。只需要求这个地方的胜负状态。

如果这里为先手必败，那么其上方和右侧均为先手必胜。找规律可得一个横着或者竖着的边界，边界上全为胜，边界的内部一格胜负交替，因此根据奇偶性可以判断。

很抱歉没有图片我也讲不太清楚，可以参考官方题解的图片。

代码

复制代码#include<cstdio> #include<cstdlib> #include<cstring> #include<cassert> #include<algorithm> #include<vector> using namespace std; const int N = 4e5; int a[N+3]; int d[N+3]; int dp[N+3][10]; vector<int> b; int n; bool cmp(int x,int y) {return x>y;} int main() { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); sort(a+1,a+n+1,cmp); int pos = 0; for(int i=1; i<=n; i++) { if(a[i]>=i && a[i+1]<=i) {pos = i; break;} } // printf("pos=%dn",pos); int len1 = 0; for(int i=pos+1; i<=n; i++) {if(a[i]>pos-1) len1++;} int len2 = a[pos]-pos; // printf("len1=%d len2=%dn",len1,len2); if((!(len1&1)) && (!(len2&1))) printf("Second"); else printf("First"); return 0; }

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
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 4e5;
int a[N+3];
int d[N+3];
int dp[N+3][10];
vector<int> b;
int n;

bool cmp(int x,int y) {return x>y;}

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1,cmp);
    int pos = 0;
    for(int i=1; i<=n; i++)
    {
        if(a[i]>=i && a[i+1]<=i) {pos = i; break;}
    }
//  printf("pos=%dn",pos);
    int len1 = 0;
    for(int i=pos+1; i<=n; i++) {if(a[i]>pos-1) len1++;}
    int len2 = a[pos]-pos;
//  printf("len1=%d len2=%dn",len1,len2);
    if((!(len1&1)) && (!(len2&1))) printf("Second");
    else printf("First");
    return 0;
}