暴力搜索是3^n，过不了。
但是我们可以使用折半搜索。
开个map存一下即可。
#include<bits/stdc++.h> #define LL long long #define N 30 #define re register using namespace std; LL read() { LL x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } int n;LL need; LL a[N],b[N],c[N]; LL ans=0;int m; map<LL,int>ma; LL quick(re LL a,re LL x) { re LL res=1; while(x) { if(x&1)res=res*a; a=a*a;x>>=1; } return res; } void dfs(re int x,re LL sum) { if(x==m+1) { if(!ma.count(sum))ma[sum]=1; else ma[sum]++; return; } if(sum>need)return; if(sum==need){ans++;return;} dfs(x+1,sum); dfs(x+1,sum+a[x]); dfs(x+1,sum+b[x]); } void dfs2(re int x,re LL sum) { if(x==n+1) { ans+=ma[need-sum]; return; } if(sum>need)return; if(sum==need){ans++;return;} dfs2(x+1,sum); dfs2(x+1,sum+a[x]); dfs2(x+1,sum+b[x]); } int main() { freopen("building.in","r",stdin); freopen("building.out","w",stdout); n=read();need=read();m=(n>>1)+(n&1); for(re int i=1;i<=n;++i)a[i]=read(); for(re int i=1;i<=n;++i) { LL x=a[i]; re int num=0; while(x) { if(x&1)num++; x>>=1; } b[i]=quick(2,num); } dfs(1,0);dfs2(m+1,0); printf("%lld\n",ans); } /* 20 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 */
重点是找到性质！（做题一定要抓住本质）。
#include<bits/stdc++.h> #define LL long long #define N 200003 #define M 300003 #define INF 300000000000003 using namespace std; int read() { int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } struct EDEG{ int nextt,to; }w[M]; struct edge{ int x,y,v; }e[M]; int tot=0; int n,m; int head[N],vis[N]; void add(int a,int b) { tot++; w[tot].nextt=head[a]; w[tot].to=b; head[a]=tot; } int cnt=0,top=0,timer=0; int dfn[N],low[N],stackk[N]; void tarjan(int x) { dfn[x]=low[x]=++timer; vis[x]=1; stackk[++top]=x; for(int i=head[x];i;i=w[i].nextt) { int v=w[i].to; if(!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if(vis[v])low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]) { int siz=0; int t; do{ t=stackk[top--]; vis[t]=0; siz++; }while(t!=x); if(siz>=2)cnt++; } } LL ans=INF; bool check(int mid) { for(int i=1;i<=n;++i)head[i]=0,vis[i]=0,dfn[i]=0,low[i]=0,stackk[i]=0; cnt=0;top=0;timer=0;tot=0; for(int i=1;i<=m;++i) if(e[i].v>mid)add(e[i].x,e[i].y); for(int i=1;i<=n;++i) if(!dfn[i])tarjan(i); if(cnt)return 0; else return 1; } int main() { freopen("pestc.in","r",stdin); freopen("pestc.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;++i) e[i].x=read(),e[i].y=read(),e[i].v=read(); int l=0,r=1000000005; while(l<r) { int mid=(l+r)>>1; if(check(mid))ans=mid,r=mid; else l=mid+1; } printf("%d\n",ans); } /* */
dsu on tree可做。然后我代码里打了所有的数据点。
#include<bits/stdc++.h> #define LL long long #define N 200003 #define INF 300000000000003 #define re register using namespace std; LL read() { LL x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f; } struct EDEG{ int nextt,to; }w[N*2]; int tot=0; int n; int head[N],ans[N][5],fa[N],a[N],b[N],du[N],son[N],tong[N],siz[N]; int c[N]; void add(int a,int b) { tot++; w[tot].nextt=head[a]; w[tot].to=b; head[a]=tot; } int query(int x) { int ans=0; while(x) { ans+=c[x]; x-=x&(-x); } return ans; } void modify(int x,int v) { while(x<=n) { c[x]+=v; x+=x&(-x); } } void work1() { for(re int i=2;i<=n;++i) { int x=fa[i]; while(x!=0) { if(a[x]>a[i])ans[x][1]++; else if(a[x]==a[i])ans[x][2]++; else ans[x][3]++; x=fa[x]; } } for(re int i=1;i<=n;++i)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]); } void work2() { int num=0; for(re int i=1;i<=n;++i) { if(!son[i]) { modify(a[i],1); tong[a[i]]++; num++; re int x=fa[i]; while(x!=0) { ans[x][2]+=tong[a[x]]; ans[x][1]+=query(a[x]-1); ans[x][3]+=num-ans[x][2]-ans[x][1]; tong[a[x]]++; modify(a[x],1); num++; x=fa[x]; } } } for(re int i=1;i<=n;++i)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]); } void work3() { for(re int i=2;i<=n;++i) { if(a[i]<a[1])ans[1][1]++; else if(a[i]==a[1])ans[1][2]++; else ans[1][3]++; } for(re int i=1;i<=n;++i)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]); } void dfs1(re int x) { siz[x]=1;re int maxson=0; for(re int i=head[x];i;i=w[i].nextt) { re int v=w[i].to; dfs1(v); if(siz[v]>maxson)maxson=siz[v],son[x]=v; siz[x]+=siz[v]; } } int SON; void update(re int x,re int k) { /*ans[x][2]+=tong[a[x]]; ans[x][3]+=query(a[x]-1); ans[x][1]+=n-ans[x][2]-ans[x][3];*/ for(re int i=head[x];i;i=w[i].nextt) { re int v=w[i].to; if(v==SON)continue; modify(a[v],k); tong[a[v]]+=k; update(v,k); } } void dfs2(re int x,re int op) { for(re int i=head[x];i;i=w[i].nextt) { re int v=w[i].to; if(v==son[x])continue; dfs2(v,0); } if(son[x])dfs2(son[x],1),SON=son[x],modify(a[son[x]],1),tong[a[son[x]]]++; update(x,1);SON=0; ans[x][2]+=tong[a[x]]; ans[x][1]+=query(a[x]-1); ans[x][3]+=siz[x]-1-ans[x][2]-ans[x][1]; // if(!op)update(x,-1); } void work4() { sort(b+1,b+1+n); int num=unique(b+1,b+1+n)-(b+1); for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+n,a[i])-b; //for(int i=1;i<=n;++i)printf("!!%d\n",a[i]); for(re int i=2;i<=n;++i)add(fa[i],i); memset(son,0,sizeof(son)); dfs1(1);dfs2(1,1); for(re int i=1;i<=n;++i)printf("%d %d %d\n",ans[i][1],ans[i][2],ans[i][3]); } int main() { freopen("ginkgo.in","r",stdin); freopen("ginkgo.out","w",stdout); n=read(); for(re int i=2;i<=n;++i)fa[i]=read(),son[fa[i]]++,du[fa[i]]++,du[i]++; for(re int i=1;i<=n;++i)b[i]=a[i]=read(); if(n<=1000){work1();return 0;} int flagg1=0,flagg2=0; for(re int i=1;i<=n;++i) { if(du[i]>2)flagg1=1; if(du[i]==n-1)flagg2=1; } if(!flagg1){work2();return 0;} if(flagg2){work3();return 0;} work4(); } /* 5 1 1 1 1 1 1 1 1 1 3 1 2 1 2 3 3 1 1 1 1 1 */
其实开桶也并不需要用启发式合并。
每次进入子树前记录一下桶里的值，出来的时候减去即可。
然鹅题解里的算法比较神奇。
因为一个求小于，一个求等于，所以开了两个树状数组。
2019.11.05（CSP模拟）（折半搜索+二分答案 判环+dsu on tree）
原文：https://www.cnblogs.com/yyys-/p/11805168.html
