Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

sg定理的简单应用 代码很矬 500+ms

Posted by zengshiyuan at 2014-10-15 12:13:02 on Problem 2960
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int s[110],k,sg[10010];
vector<int>pre[10010];
bool used[10010];
void getsg()
{
    for(int i=0;i<=10000;i++)
        pre[i].clear();
    memset(sg,0,sizeof(sg));
    for(int i=0;i<=10000;i++)
        for(int j=1;j<=k;j++)
            if(i+s[j]<=10000)
                pre[i+s[j]].push_back(i);
    for(int i=1;i<=10000;i++)
        if(pre[i].size())
    {
        memset(used,0,sizeof(used));
        for(int j=0;j<pre[i].size();j++)
            used[sg[pre[i][j]]]=1;
        for(int j=0;;j++)
            if(!used[j])
        {
            sg[i]=j;
            break;
        }
    }
}
int main()
{
    int n,m,q;
    string str;
    while(scanf("%d",&k),k)
    {
        for(int i=1;i<=k;i++)
            scanf("%d",&s[i]);
        getsg();
        str="";
        int ans=0;
        scanf("%d",&n);
        while(n--)
        {
            scanf("%d",&m);
            ans=0;
            while(m--)
            {
                scanf("%d",&q);
                ans^=sg[q];
            }
            if(ans) str=str+"W";
            else str=str+"L";
        }
        cout<<str<<endl;
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator