比赛 EYOI与SBOI开学欢乐赛10th 评测结果 AWWAAWAAWW
题目名称 捡字母 最终得分 50
用户昵称 op_组撒头屯 运行时间 0.431 s
代码语言 C++ 内存使用 67.08 MiB
提交时间 2022-10-10 20:15:01
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=2000+5;
int n;
char s[N];
int win[N][N][4]={0};
int sg(int l,int r,int d){
    if (l>r)return 2;
    if (win[l][r][d]!=-1)return win[l][r][d];
    int &now=win[l][r][d];
    if (d==0){
        int x=sg(l+1,r,1),y=sg(l,r-1,2);
        if (x==0&&y==0)return now=1;
        if (x==1||y==1)return now=0;
        return now=2;
    }
    else{
        int x=sg(l+1,r,0),y=sg(l,r-1,0);
        if (x==0&&y==0)return now=1;
        if (x==1||y==1)return now=0;
        char p=(d==1)?s[l-1]:s[r+1];
        if (x==2&&y==2){
            if (s[l]<p||s[r]<p)return now=0;
            if (s[l]==p||s[r]==p)return now=2;
            return now=1;
        }
        if (x==0){
            if (s[r]==p)return now=2;
            if (s[r]<p)return now=0;
            return now=1;
        }
        else{
            if (s[l]==p)return now=2;
            if (s[l]<p)return now=0;
            return now=1;
        }
    }
}
int main(){
	freopen ("PickLetter.in","r",stdin);
	freopen ("PickLetter.out","w",stdout);
	scanf("%s",s+1);
	n=strlen(s+1);
    memset(win,-1,sizeof(win));
	int ans=sg(1,n,0);
	if (ans==0)printf("lhzwin!\n");
	else if (ans==1)printf("orzben\n");
	else printf("draw\n");
	return 0;
}