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; } |
刷刷POI，整个人都POI！
BZOJ 1098: [POI2007]办公楼biu 补图联通块直接DFS出来就行了，很容易TLE要用链表及时删点、
|
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
//WNJXYK //while(true) RP++; #include<iostream> #include<cstdio> #include<algorithm> #include<map> #include<set> #include<queue> #include<string> #include<cstring> using namespace std; const int Maxn=100010; const int Maxm=2000010; inline int read(){ int x = 0; char ch = getchar(); while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9'){ x = x * 10 + ch - '0'; ch = getchar(); } return x; } struct Edge{ int v,nxt; Edge(){} Edge(int v0,int n0){ v=v0; nxt=n0; } }; int head[Maxn]; Edge e[Maxm*2]; int nume; int n,m; inline void addEdge(int u,int v){ e[++nume]=Edge(v,head[u]);head[u]=nume; e[++nume]=Edge(u,head[v]);head[v]=nume; } int nxt[Maxn],pre[Maxn]; inline void del(int x){ int tmp=pre[x]; nxt[tmp]=nxt[x]; pre[nxt[x]]=tmp; } bool vis[Maxn]; int cnt; int siz[Maxn]; bool noEdge[Maxn]; int que[Maxn]; int l,r; int i; void bfs(int src){ que[0]=src; vis[src]=true; for (l = r = 0; l <= r; ++l){ int x=que[l]; //printf("%d\n",x); siz[cnt]++; for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=true; for (i=nxt[0];i<=n;i=nxt[i]){ if (!vis[i] && !noEdge[i]){ del(i); vis[i]=true; que[++r]=i; } } for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=false; } } inline void input(){ freopen("1098.in","r",stdin); //freopen("1098.out","w",stdout); } int main(){ //input(); n=read();m=read(); int x,y; for (i=1;i<=m;i++){ x=read(),y=read(); addEdge(x,y); } for (i=0;i<=n;i++){ nxt[i]=i+1; pre[i+1]=i; } for (i=nxt[0];i<=n;i=nxt[i]){ if (!vis[i]){ cnt++; del(i); bfs(i); } } sort(siz+1,siz+cnt+1); printf("%d\n",cnt); for (i=1;i<=cnt;i++){ printf("%d ",siz[i]); } printf("\n"); return 0; } |
BZOJ 1097: [POI2007]旅游景点atr 首先SPFA出前k+1个点的最短路,然后做状压DP. pre […]
