加载中...
题解 AT183 【1+1】

题目大意:

输入遵循以下格式。给出的数目都是整数。

分别表示以下规则中的要素的状态数 $n$ ,最大分割次数$ m$ ,加法规则$ r$。$-$ 表示状态 $(x,y)$,$x,y$ 被称为“要素”。

  • 初始状态是 $(1,1)$。

  • 各回合可以采取的“行动”是“选择”或“分割”中的一个。

  • 先攻后攻交替反复行动 $(0,0)$ 变成的话输。

  • 选择:选择自己不是 $0$ 的要素 $x$ 与对方不是 $0$ 的要素 $y$,将 $x$ 加法到选择的对方的要素,即 x+y。此时,应用以下任一加法规则 r。

  • 加法规则 $0$:$x+y$ 在 $n$ 以上时成为 $0$。

  • 加法规则 $1$:$x+y$ 在 $n$ 以上时成为 $x + $$y-n$。

  • 分割:一方的要素为 $0$、且另一个要素 $k$ 在 $2$ 以上的话,就可以进行“分割”。$a+b=k$,$a⩾1,b⩾1$的自然数 $a,b $选择$ (a,b)$。

  • 分割最大 $m$ 可旋转。

如果存在持续无限行动的程序,请输出 Infinite。这时,先手和后手可以协助他们继续无限的行动。

如果不存在的话,先手和后手选择以下的基准行动时,游戏的结果和游戏几回合结束。然后,先胜的情况First,后胜的情况 Second,在第 1 行输出。第 2 行输出游戏结束是第几回合。

当自己存在能取胜的手时,要选择那只手。自己胜利的手存在负数的时候从其中选择游戏以最短结束一样的手。

当自己只存在输掉的手时,选择用游戏最长结束的手。

解题思路:

机翻后总算读懂了题意,原来是这么回事。

所以我们可以直接从初始状态 $dfs$ ,检测是否有无限行动,即无解的情况。

如果有解,那么运用 $Dp$ 的思想(其实和$ dfs$ 差不多,只不过$ dfs $只是检测一下,而 $Dp$ 要算出答案),统计出答案。

详见代码,这是个很值得对着代码细细研究一番的题目。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Max_a1=17,Max_a2=17,Max_am=3,Max_b1=17,Max_b2=17,Max_bm=3;
const ll inf=1ll<<60;

char buf[1<<15],*fs,*ft;
inline char getc() { return (ft==fs&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),ft==fs))?0:*fs++; }
template<typename T>inline void read(T &x)
{
    x=0;
    T f=1, ch=getchar();
    while (!isdigit(ch) && ch^'-') ch=getchar();
    if (ch=='-') f=-1, ch=getchar();
    while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
    x*=f;
}

char Out[1<<24],*fe=Out;
inline void flush() { fwrite(Out,1,fe-Out,stdout); fe=Out; }
template<typename T>inline void write(T x)
{
    if (!x) *fe++=48;
    if (x<0) *fe++='-', x=-x;
    T num=0, ch[20];
    while (x) ch[++num]=x%10+48, x/=10;
    while (num) *fe++=ch[num--];
    *fe++='\n';
}

int n,m,rule;
inline ll add(ll x,ll y)
{
    if (x+y>=n) return !rule ? 0 : x+y-n;
    return x+y;
}

ll f[Max_a1][Max_a2][Max_am][Max_b1][Max_b2][Max_bm];
inline ll fun(int a1,int a2,int am,int b1,int b2,int bm)
{
    ll &res=f[a1][a2][am][b1][b2][bm];
    if (res^-1) return res;
    if (!a1 && !a2) return res=-inf;
    ll ans=-inf-1;
    if ( (!a1 || !a2) && am>0)
        for (int k=1; k<a1+a2; ++k) ans=max(ans,-fun(b1,b2,bm,k,a1+a2-k,am-1));
    if (a1 && b1) ans=max(ans,-fun(add(b1,a1),b2,bm,a1,a2,am));
    if (a1 && b2) ans=max(ans,-fun(b1,add(b2,a1),bm,a1,a2,am));
    if (a2 && b1) ans=max(ans,-fun(add(b1,a2),b2,bm,a1,a2,am));
    if (a2 && b2) ans=max(ans,-fun(b1,add(b2,a2),bm,a1,a2,am));
    if (ans<0) ++ans;
    if (ans>0) --ans;
    return res=ans;
}

int vis[Max_a1][Max_a2][Max_am][Max_b1][Max_b2][Max_bm];
inline bool dfs(int a1,int a2,int am,int b1,int b2,int bm)
{
    int &res=vis[a1][a2][am][b1][b2][bm];
    if (res==1) return false;
    if (res==2) return true;
    res=1;
    if (!a1 && !a2)
    {
        res=2;
        return true;
    }
    if ( (!a1 || !a2) && am>0)
        for (int k=1; k<a1+a2; ++k)
            if (!dfs(b1,b2,bm,k,a1+a2-k,am-1)) return false;
    if (a1 && b1) if (!dfs(add(b1,a1),b2,bm,a1,a2,am)) return false;
    if (a1 && b2) if (!dfs(b1,add(b2,a1),bm,a1,a2,am)) return false;
    if (a2 && b1) if (!dfs(add(b1,a2),b2,bm,a1,a2,am)) return false;
    if (a2 && b2) if (!dfs(b1,add(b2,a2),bm,a1,a2,am)) return false;
    res=2;
    return true;
}

int main()
{
    memset(f,-1,sizeof(f));
    read(n);read(m);read(rule);
    if (!dfs(1,1,m,1,1,m)) return puts("Infinite"),0;
    ll res=fun(1,1,m,1,1,m);
    if (res>0) puts("First"),write(inf-res),flush();
    if (res<0) puts("Second"),write(res+inf),flush();
    return 0;
}

  目录
劳动
快乐