Source Code

Problem: 1143  User: yzhw 
Memory: 8484K  Time: 16MS 
Language: C++  Result: Accepted 

Source Code 
# include <iostream>
# include <vector>
# include <cstring>
using namespace std;
int refer[2100000];

void decode(int num,bool ans[])
{
     for(int i=20;i>=1;i--)
     {
        ans[i]=num%2;
        num/=2;
     }
}
int encode(bool pos[])
{
    int ans=0;
    for(int i=20;i>=1;i--)
    {
      ans+=pos[i]*(1<<(20-i));
    }
    return ans;
}
void change(bool tar[],int pos)
{
     for(int i=pos;i<=20;i+=pos)
     {
         tar[pos]=0; 
         for(int j=2;j<=20;j++)
           if(j+i<=20)
           {
              if(tar[j]==0) tar[i+j]=0;
           }
           else break;
         
     }
}
int deal(int pos)
{
    if(refer[pos]) return refer[pos];
    else if(pos==0) return 3;
    else
    {
        bool array[21];
        decode(pos,array);
        bool tmp[21];
        bool flag=false,flag1=true;
        for(int i=2;i<=20;i++)
        {
          memcpy(tmp,array,sizeof(tmp));
          if(tmp[i]==1)
          {
        
             change(tmp,i);
             if(deal(encode(tmp))==3) flag=true,flag1=false;
             else if(deal(encode(tmp))==1) flag1=false;
            
          }
        }
        if(flag) refer[pos]=2;
        else if(flag1) refer[pos]=3;
        else refer[pos]=1;
        return refer[pos];
        
    }
}
int main()
{
   bool ori[21];
   int num,co=1;
   memset(refer,0,sizeof(refer));
   refer[0]=3;
   while(cin>>num)
   {
      if(!num) break;
      vector<int> ans;
      memset(ori,0,sizeof(ori));
      for(int i=1;i<=num;i++)
      {
          int t;
          cin>>t;
          ori[t]=1;
      }   
     
      cout<<"Test Case #"<<co++<<endl;
       deal(encode(ori));
      for(int i=2;i<=20;i++)
          if(ori[i])
            {
                bool tmp[21];
                memcpy(tmp,ori,sizeof(tmp));
                change(tmp,i);
                if(refer[encode(tmp)]==3) ans.push_back(i);
            }
      if(ans.size()==0)
        cout<<"There's no winning move."<<endl<<endl;
      else
      {
          cout<<"The winning moves are:";
          for(int i=0;i<ans.size();i++)
            cout<<" "<<ans[i];
          cout<<endl<<endl;
      }                      
   }
   return 0;
    

} 

• Re:只能做到16ms了，各位大牛帮忙看看还有哪能优化，附代码 (250) lzqxh 2010-08-21 00:56:03