昨天晚上：明天我们考试，要考一道树形dp;
今天下午：考试时，第三题只要会最小生成树+dp就好了
考试结束前4分钟：第一道题就是找规律balabala……
——欧阳如是说
异或和
求1-n异或和
这是一道全员A的题
如果你看到数据范围，还不会打表找规律之类
呃……
染色
描述
有一颗N 个节点的树，节点用1, 2.....N 编号。你要给它染色，使得相邻节点的颜色不同。有M 种颜色，用1,2.....M 编号。每个节点可以染M 种颜色中的若干种，求不同染色方案的数量除以(10^9 + 7)的余数。
输入(color.in)
第1 行，2 个整数N,M，接下来N 行，第i 行表示节点i 可以染的颜色。第1个整数ki，表示可以染的颜色数量。接下来ki个整数，表示可以染的颜色编号。最后N-1 行，每行2个整数Ai,Bi表示边(Ai,Bi)。
输出(color.out)
一行一个数，即答案
树形DP,恶心取模；
#include<bits/stdc++.h> #define ll long long #define re return #define inc(i,l,r) for(int i=l;i<=r;++i) const int maxn=5005,mod=1000000007; using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x; } ll n,m,k,f[maxn][maxn],size[maxn]; vector<int>G[maxn];
//当然为了简化空间，用f[i][j]=1,来判断是否有此颜色
//开int，1LL* vector<int>::iterator it; int hd[maxn]; struct node{ int to,nt; }e[maxn<<1]; inline void add(int x,int y) { e[++k].to=y;e[k].nt=hd[x];hd[x]=k; e[++k].to=x;e[k].nt=hd[y];hd[y]=k; } inline void dfs(int x,int fa) { for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to; if(v==fa)continue; dfs(v,x); for(it=G[x].begin();it!=G[x].end();++it) { int j=*it; f[x][j]=(f[x][j]*(size[v]+mod-f[v][j]))%mod;
///size[v]在取模过程中可能小于f[v][j]，根据同余定理得 } } for(it=G[x].begin();it!=G[x].end();++it) { int j=*it; size[x]=(size[x]+f[x][j])%mod; } } int main() { int x,y; rd(n);rd(m); inc(i,1,n) { int j; rd(j); inc(k,1,j) { rd(x); G[i].push_back(x); f[i][x]=1; } } inc(i,1,n-1) { rd(x),rd(y); add(x,y); } dfs(1,0); printf("%lld",size[1]); re 0; }
新三国争霸
描述 Description
PP 特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。
在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。
PP可真是高手，不一会，就攻下了N-1座城市，加上原来的就有N座城市了，但他忽略了一点……那就是防守同样重要，不过现在还来的及。因为才打完仗所以很多城市都需要建设，PP估算了一下，大概需要T天。他现在无暇分身进攻了，只好在这T天内好好的搞建设了。所以他要派士兵占领一些道路，以确保任何两个城市之间都有路（不然敌人就要分而攻之了，是很危险的）。士兵可不是白干活的，每个士兵每天都要吃掉V的军粮。因为有灾害，所以方案可能有变化（每改变一次就需要K的军粮，初始方案也需要K的军粮）。
因为游戏是PP编的，所以他知道什么时候有灾害。PP可是一个很节约的人，他希望这T天在道路的防守上花最少的军粮。
输入格式 InputFormat
第一行有5个整数N，M，T，V，K。N表示有城市数，M表示道路数，T表示需要修养的天数，V表示每个士兵每天吃掉的军粮数，K表示修改一次花掉的军粮数。 以下M行，每行3个数A，B，C。表示A与B有一条路（路是双向的）需要C个士兵才能守住。 第M+2行是一个数P，表示有P个灾害。 以下P行，每行4个数，X，Y，T1，T2。表示X到Y的这条路，在T1到T2这几天都会受灾害。
输出格式 OutputFormat
T天在道路的防守上花费最少的军粮。
样例输入 SampleInput
3 3 5 10 30
1 2 1
2 3 2
1 3 4
1
1 3 2 5样例输出 SampleOutput
180数据范围和注释 Hint
对于所有数据：N<=300，M<=5000 ，T<=50，P<=8000
我们曾做过一个很类似的题叫做
[ZJOI2006]物流运输
不过那道题是 求最短路，
这道题是求 最小生成树
求最小生成树时，要注意[i-k]这段连续和的最小生成树
用了一种很妙的方法，前缀和 来判断[i-k]是否能用路径i;
#include<bits/stdc++.h> #define re return #define inc(i,l,r) for(int i=l;i<=r;++i) const int maxn=305,maxm=4005,maxt=55; using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x; } int n,m,T,V,K,P,hd[maxn]; int fa[maxn],f[maxt],flag[maxn][maxn],vis[maxn][maxn][maxt]; struct node{ int fr,to,val; bool operator<(node b)const { re val<b.val; } }e[maxm]; inline int find(int x) { re x==fa[x]?x:fa[x]=find(fa[x]); } inline int krus(int st,int ed) { inc(i,1,n)fa[i]=i; int cost=0; int cnt=0; inc(i,1,m) { int u=e[i].fr,v=e[i].to; if(vis[u][v][ed]-vis[u][v][st])continue;//如果有差，则这段时间不可用这条路 if(find(u)!=find(v)) { fa[fa[u]]=fa[v]; cost+=e[i].val; ++cnt; if(cnt==n-1)re cost; } } re 0; } int main() { int x,y,z,t1,t2; rd(n),rd(m),rd(T),rd(V),rd(K); inc(i,1,T)f[i]=2147483647; inc(i,1,m) { rd(x),rd(y),rd(z); e[i]=(node){x,y,z}; } sort(e+1,e+m+1); rd(P); inc(i,1,P) { rd(x),rd(y),rd(t1),rd(t2); inc(j,t1,t2) vis[x][y][j]=vis[y][x][j]=1; } inc(i,1,n)inc(j,i,n)inc(k,1,T) vis[i][j][k]+=vis[i][j][k-1]; inc(i,1,T) { inc(k,i,T) { int cost=krus(i-1,k); if(!cost)break; cost*=V; f[k]=min(f[k],f[i-1]+(k-i+1)*cost+K); } } printf("%d",f[T]); re 0; }