Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
数据很弱吧,0msAC,王记\n了搞了一次PE。。。【附代妈和注释】#include <iostream> #include <stdio.h> using namespace std; void quickSort(int s[], int l, int r) { if (l< r) { int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j]>= x) j--; if(i < j) s[i++] = s[j]; while(i < j && s[i]< x) i++; if(i < j) s[j--] = s[i]; } s[i] = x; quickSort(s, l, i - 1); quickSort(s, i + 1, r); } } int state[524288] = {0}; //0: 不确定 //1: 胜局 //-1: 败局 inline bool contain(int n, int num){ return (n & (1<<(num-2))) != 0; } void unset(int &n, int w){ n -= (1<<(w-2)); } void dfs(int n){ if(state[n] != 0) return; if(n == 0){ state[n] = -1; return; } bool existBai = false; int validList[22]; int validNum = 0; //int indexes[22] = {0}; for(int i = 2; i <= 20; i++){ if(!contain(n,i)) continue; validList[validNum] = i; //indexes[i] = validNum + 1; validNum ++; } for(int i = 0; i < validNum; i++){ //if(indexes[i] == 0) continue; //考慮去掉validList[i],得到的状態存在N中 int N = n; unset(N, validList[i]); for(int j = i+1; j < validNum; j++){ int tbus = validList[j]; while(1){ tbus -= validList[i]; if(tbus <= 1) break; if(!contain(N, tbus)){ unset(N, validList[j]); break; } } } dfs(N); if(state[N] == -1){ existBai = true; break; } } if(existBai) state[n] = 1; else state[n] = -1; } int main() { int cnt = 0; while(1){ cnt ++; int rem; scanf("%d", &rem); if(rem == 0) return rem; printf("Test Case #%d\n", cnt); int st = 0; int hehe[19] = {0}; int heheCnt = 0; for(int i = 0; i < rem; i++){ int temp; scanf("%d", &temp); hehe[heheCnt] = temp; heheCnt ++; st |= (1 << (temp-2)); } //dfs(st); int resList[19]; int resNum = 0; for(int i = 0; i < heheCnt; i++){ int N = st; unset(N, hehe[i]); for(int j = i+1; j < heheCnt; j++){ int tbus = hehe[j]; while(1){ tbus -= hehe[i]; if(tbus <= 1) break; if(!contain(N, tbus)){ unset(N, hehe[j]); break; } } } dfs(N); if(state[N] == -1){ resList[resNum] = hehe[i]; resNum ++; } } if(resNum == 0){ printf("There's no winning move.\n"); } else{ quickSort(resList, 0, resNum-1); printf("The winning moves are:"); for(int i = 0; i < resNum; i++){ printf(" %d", resList[i]); } printf("\n"); } printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator