UVa 10561 - Treblecross
2881 단어 uva
게임 SG XX 나 X. X 가 나 오 면 안 돼 요. 그러면 다음 사람 이 이 겨 요.
매 거 하 다
1. 이미 나 타 났 어 요. XXX 상대 가 이미 졌 다
2. 마침 나타 나 면 XX 혹은 X. X 상대 가 이기다
3. 한 곳 의.. X 가 된다 면 XX 나 X 는 안 나 와 요. 이 부분 들 을 하나하나 나 누 어 주세요. SG
코드:
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define ll long long
#define lint long long
using namespace std;
const int N=205;
int sg[N];
int dp(int x)
{
if(sg[x]!=-1)
return sg[x];
if(x==0)
return (sg[x]=0);
bool ok[N];
memset(ok,false,sizeof(ok));
for(int i=1;i<=x;++i)
{
int k=(dp(max(0,i-3))^dp(max(0,x-i-2)));
ok[k]=true;
}
for(int i=0;i<N;++i)
if(!ok[i])
{sg[x]=i;break;}
return sg[x];
}
bool ok(string s)
{
for(unsigned int i=0;i<s.size()-2;++i)
{
if(s[i]=='X'&&s[i+1]=='X'&&s[i+2]=='X')
return true;
}
return false;
}
bool ok1(string s)
{
for(unsigned int i=0;i<s.size();++i)
if(s[i]=='.')
{
s[i]='X';
if(ok(s))
return false;
s[i]='.';
}
int nim=0;
int tmp=0;
for(unsigned int i=0;i<s.size();++i)
{
if(s[i]=='X'||(i>=1&&s[i-1]=='X')||(i>=2&&s[i-2]=='X')||(i+1<s.size()&&s[i+1]=='X')||(i+2<s.size()&&s[i+2]=='X'))
{nim=(nim^dp(tmp));tmp=0;}
else
++tmp;
}
nim=(nim^dp(tmp));
if(nim==0) return true;
return false;
}
void solve(vector<int> &vt,string &s)
{
for(unsigned int i=0;i<s.size();++i)
if(s[i]=='.')
{
s[i]='X';
if(ok(s)||ok1(s))
vt.push_back(i+1);
s[i]='.';
}
}
int main()
{
//freopen("data.in","r",stdin);
memset(sg,-1,sizeof(sg));
int T;
cin>>T;
while(T--)
{
string s;
cin>>s;
vector<int>vt;
solve(vt,s);
if(vt.size()==0)
cout<<"LOSING"<<endl;
else
cout<<"WINNING"<<endl;
for(unsigned int i=0;i<vt.size();++i)
{
if(i>0) cout<<" ";
cout<<vt[i];
}
cout<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)제목 대의: s점에서 t점까지의 최소 거리를 구하는 그림을 주세요. 확인: 적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.