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

## 只能做到16ms了，各位大牛帮忙看看还有哪能优化，附代码

Posted by yzhw at 2010-01-30 11:03:29 on Problem 1143
```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;

}

```

Followed by: