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_pair
typedef 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 666666
Edgc
int 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 666666
typedef 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 666666
int 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_pair
typedef 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 666666
int 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");
}
}