at1999

· · 题解

暴力

将a从大到小排序。

发现操作的顺序并不影响操作的结果。所以设 f[i][j] 为用了 i 次操作1,j 次操作2。此时的状态先手的胜(值为 1)负(值为 0)情况。

一次操作相当于取一些糖果,然后将对方变成先手。所以只要能转移的状态有一个为先手负,则该点为先手胜。

列出状态转移方程:f[i][j]=f[i+1][j]||!f[i][j+1]。

边界情况:f[i][a[i]]=1。

暴力代码

#include<iostream>
#include<algorithm>
using namespace std;
bool f[10005][10005];
#define A b<=10000&&c<=10000
int n,a[1000005];
bool fyr(int b,int c){
    if(b>=a[c]){
        return 1;
    }
    if(A&&f[b][c]){
        return f[b][c];
    }
    bool ykb=!(fyr(b+1,c)&&fyr(b,c+1));
    if(A){
        f[b][c]=ykb;
    }
    return ykb;
}
int main(){
    int i;
    cin>>n;
    for(i=0;i<n;i++){
        scanf("%d",a+i);
    }
    sort(a,a+n,greater<int>());
    cout<<(fyr(0,0)?"First":"Second");
    return 0;
}

正解

请先看暴力再继续。

f[i][j]=!f[i+1][j]||![i][j+1]①

f[i][j]=!(f[i+1][j]&&f[i][j+1]) ②

将②代入①得f[i][j]=(f[i+2][j]&&f[i+1][j+1])||(f[i+1][j+1]&&f[i][j+2])。

可以看出,f[i+1][j+1] 是必要条件,而 f[i+2][j] 与 f[i][j+2] 至少得满足其中一个。

所以f[i][j]=f[i+1][j+1]&&(f[i+2][j]||f[i][j+2])。

再次代入递推得 f[i][j]=f[i+2][j+2]&&(f[i+1][j+3]||f[i+3][j+1])。

所以得出一个结论:f[i][j]=f[i+a][j+a]&&(f[i+a-1][j+a+1]||f[i+a+1][i+a-1])

①左右都碰到了边界。

x x x
1 0 x
[0]() 1 x

必要点为0,说明负。

②左碰到边界,右未碰到。

x x x x x
1 0 1 0 1 x x x x
[0]() [1]() [0]() [1]() 1 0 1 0 x
0 1 0 1 0 [1]() 0 1 x

可能查询的值已用浅蓝色标出,发现0和1交替出现,即 f[i][i]=f[i-1][i+1],所以 f[0][0]=f[i-1][i+1]。

③左未碰到边界,右碰到了。 与②类似,自己手推。也可以参考代码。 ④左右都未碰到。 |||x||| | -----------: | -----------: | -----------: | -----------: | -----------: | | |?|x||| |B|?|x|x|x| | |[A]()|?|?|| | | |B| || 同样是判断奇偶性,但要上面的和右边的都要判断。 ```cpp #include<iostream> #include<cstdio> #include<algorithm> using namespace std; int a[1000005]; string s[5]={"Second","First"}; int main(){ int n,i,j; cin>>n; for(i=0;i<n;i++){ scanf("%d",a+i); } sort(a,a+n,greater<int>()); for(i=0;a[i]>i;i++){ } i--; if(a[i+1]<=i-1){ //右无。 if(i&&a[i-1]<=i+1){ //左无。//① cout<<s[0]; }else{ //③ cout<<s[(a[i]-1-i)&1]; } }else{ if(i&&a[i-1]<=i+1){ //② for(j=i;a[j]>i;j++){ //一直往前扫到碰到边界。 } cout<<s[(j-1-i)&1]; }else{ //④ for(j=i;a[j]>i;j++){ } cout<<s[((a[i]-1-i)&1)||((j-1-i)&1)]; //上右只有有一个为1即可输出First。 } } return 0; } ```