HDU 4835 Find Numbers
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4835
题解
似乎有性质保证，每多少个数字中一定能拼出2^k。
所以，直接DFS即可。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
//while(true) RP++; #include<cstdio> #include<algorithm> using namespace std; const int Maxn=1<<16; int n; struct NumNode{ int num; int pos; }; NumNode num[Maxn+5]; int Mod; int ans[Maxn+5]; bool flag=false; bool cmp(NumNode a,NumNode b){ return a.num<b.num; } void dfs(int x,int cnt,int mod){ //printf("Now=%d Mod=%d\n",cnt,mod); if (flag) return; if (cnt>Mod && mod==0){ for (int i=1;i<=Mod;i++) if (i<Mod) printf("%d ",ans[i]); else printf("%d\n",ans[i]); flag=true; return; } if (x>n) return; if (cnt>Mod) return; ans[cnt]=num[x].pos; dfs(x+1,cnt+1,(mod+num[x].num)%Mod); dfs(x+1,cnt,mod); } inline void solve(int T){ scanf("%d",&n); Mod=(n+1)/2; for (int i=1;i<=n;i++) scanf("%d",&num[i].num); for (int i=1;i<=n;i++) num[i].pos=i-1; for (int i=1;i<=n;i++) num[i].num%=Mod; //printf("%d\n",Mod); sort(num+1,num+n+1,cmp); flag=false; printf("Case #%d:\n",T); dfs(1,1,0); if (!flag) printf("-1\n"); } int main(){ int T; while(scanf("%d",&T)!=EOF) for(int i=1;i<=T;i++) solve(i); return 0; } |
原文链接：HDU 4835 Find Numbers
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!