首页 > 代码库 > HAOI2015 泛做
HAOI2015 泛做
T1
有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑色，并将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少。N,K<=2000
这个树形dp不是很好想...因为贡献十分混乱...
题解十分神奇...我们记f[i][j]为i的子树有j个黑点的最大权值。
注意直接dp十分蛋疼，这个权值指的是，这个子树内部的贡献，以及i与父亲之间的边对答案的贡献（比如这条边对黑点对距离和的贡献就是子树内部的黑点数*子树外部的黑点数*这条边的权值）。
这个转移就是正常的子树合并...似乎子树合并的题目这个trick十分有用啊...
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <time.h>#include <stdlib.h>#include <string>#include <bitset>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <sstream>#include <stack>#include <iomanip>using namespace std;#define pb push_back#define mp make_pairtypedef pair<int,int> pii;typedef long long ll;typedef double ld;typedef vector<int> vi;#define fi first#define se second#define fe first#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}#define es(x,e) (int e=fst[x];e;e=nxt[e])#define cif(x) if(x) continue#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}#define TIMER cerr<<clock()<<"ms\n"#define gmax(a,b) if((a)<(b)) (a)=(b);#define gmin(a,b) if((a)>(b)) (a)=(b);#define SZ 666666Edgcint n,k,sz[SZ];ll dp[2333][2333],tmp[2333];void dfs(int x,int f=0,int fv=0){ int cs=1; for es(x,e) { int b=vb[e]; cif(b==f); dfs(b,x,vc[e]); int cc=cs+sz[b]; for(int i=0;i<=min(cc,k);i++) tmp[i]=0; for(int i=0;i<=cs&&i<=k;i++) { for(int j=0;j<=sz[b]&&j<=k;j++) { if(i+j>k) continue; gmax(tmp[i+j],dp[x][i]+dp[b][j]); } } for(int i=0;i<=min(cc,k);i++) dp[x][i]=tmp[i]; cs=cc; } sz[x]=cs; for(int i=0;i<=cs&&i<=k;i++) { if(cs+(k-i)>n) { dp[x][i]=-2147400000; continue; } //xblack=i xwhite=cs-i //wblack=k-i wwhite=n-cs-(k-i) dp[x][i]+=(ll)i*(k-i)*fv; dp[x][i]+=(ll)(cs-i)*(n-cs-(k-i))*fv; }}int main(){ scanf("%d%d",&n,&k); for(int i=1;i<n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); adde(a,b,c); } dfs(1); cout<<dp[1][k]<<"\n";}
T2
链剖裸题就不说了...
似乎有两遍dfs序的做法写了写没调出来...
#include <iostream>#include <stdio.h>#include <stdlib.h>using namespace std;#define SZ 666666typedef long long ll;ll a1[210001],a2[210001];ll qzh(int r){ ll s1=0,s2=0; for(int i=r;i>=1;i-=i&-i) s1+=a1[i], s2+=a2[i]; return (r+1)*s1-s2;}ll sum(int l,int r){ return qzh(r)-qzh(l-1);}void edt(ll a,ll s1){ ll s2=a*s1; for(;a<=210000;a+=a&-a) a1[a]+=s1, a2[a]+=s2;}void edt(int l,int r,ll a) {edt(l,a); edt(r+1,-a);}namespace lct{#define SZ 666666int n,S=0,ns[SZ],fs[SZ],ss[SZ],fa[SZ],siz[SZ],ws[SZ],dep[SZ],fe[SZ],top[SZ],X=0,ls[SZ];void ad_de(int x,int y){ ++S; ns[S]=fs[x]; fs[x]=S; ss[S]=y;}void adde(int x,int y) {ad_de(x,y); ad_de(y,x);}void dfs1(int cur){ siz[cur]=1; ws[cur]=0; int csc=-233; for(int x=fs[cur];x;x=ns[x]) { int c=ss[x]; if(c==fa[cur]) continue; fa[c]=cur; dep[c]=dep[cur]+1; dfs1(c); if(siz[c]>csc) csc=siz[c], ws[cur]=c; siz[cur]+=siz[c]; }}void dfs2(int cur,int tp){ fe[cur]=++X; top[cur]=tp; if(ws[cur]) dfs2(ws[cur],tp); for(int x=fs[cur];x;x=ns[x]) { int c=ss[x]; if(c!=ws[cur]&&c!=fa[cur]) dfs2(c,c); } ls[cur]=X;}void s1(int cur,int V){ edt(fe[cur],ls[cur],V);}ll s2(int x){ int u=1,v=x; ll ans=0; int f1=top[u],f2=top[v]; while(f1!=f2) { if(dep[f1]<dep[f2]) swap(f1,f2), swap(u,v); ans+=sum(fe[f1],fe[u]); u=fa[f1]; f1=top[u]; } if(dep[u]>dep[v]) swap(u,v); ans+=sum(fe[u],fe[v]); return ans;}}int qq[233333];int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",qq+i); } for(int i=1;i<n;i++) { int a,b; scanf("%d%d",&a,&b); lct::adde(a,b); } lct::dfs1(1); lct::dfs2(1,1); for(int i=1;i<=n;i++) edt(lct::fe[i],lct::fe[i],qq[i]); for(int i=1;i<=m;i++) { int p; scanf("%d",&p); if(p==1) { int x,a; scanf("%d%d",&x,&a); edt(lct::fe[x],lct::fe[x],a); } else if(p==2) { int x,a; scanf("%d%d",&x,&a); lct::s1(x,a); } else { int x; scanf("%d",&x); printf("%lld\n",lct::s2(x)); } }}
T3
这个sg题真是感人至深啊...
参考链接 http://blog.csdn.net/lych_cys/article/details/50896005
首先我们可以发现问题可以转化为存在若干白点，然后将所有点翻转成黑点，先全部翻转的为胜。因为如果从黑点开始翻转后手可以翻过来...
那么我们就可以假装只有一个白点，然后把sg值异或在一起。
算一下sg，可以发现一个白点i可以转移到2i，2i、3i，2i、3i、4i...
那就是说sg[i]=mex{sg[i]^sg[2i],sg[i]^sg[2i]^sg[3i]...}
经过仔细观察（归纳证明）可以发现sg[i]只与n/i有关。
那么我们就可以暴力像莫比乌斯反演那样做，预处理时大模拟显然是不超过O(n)的，对于<=根号n的我们直接存，>根号n的就用n除一下再存。
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>#include <time.h>#include <stdlib.h>#include <string>#include <bitset>#include <vector>#include <set>#include <map>#include <queue>#include <algorithm>#include <sstream>#include <stack>#include <iomanip>using namespace std;#define pb push_back#define mp make_pairtypedef pair<int,int> pii;typedef long long ll;typedef double ld;typedef vector<int> vi;#define fi first#define se second#define fe first#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}#define es(x,e) (int e=fst[x];e;e=nxt[e])#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}#ifdef LOCAL#define TIMER cerr<<clock()<<"ms\n"#else#define TIMER#endif#define SZ 666666int nxt(int x,int n){ if(x==n) return n+1; return n/(n/(x+1)); //end}int n,k,sg[SZ],fsg[SZ],Q,tmp[SZ];int main(){ scanf("%d%d",&n,&k); Q=sqrt(n)+1; for(int i=1;i<=n;i=nxt(i,n)) { int cur=0; tmp[cur]=i; for(int j=2;j<=i;j=nxt(j,i)) { int t=i/j,p=(t<=Q)?sg[t]:fsg[n/t]; tmp[cur^p]=i; if((i/t-i/(t+1))&1) cur^=p; } cur=0; while(tmp[cur]==i) ++cur; if(i<=Q) sg[i]=cur; else fsg[n/i]=cur; } while(k--) { int ans=0,m; scanf("%d",&m); for(int i=1;i<=m;i++) { int x; scanf("%d",&x); int t=n/x; ans^=(t<=Q)?sg[t]:fsg[n/t]; } if(ans) puts("Yes"); else puts("No"); }}
HAOI2015 泛做
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。