| 比赛 | 
    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;
}