题目大意：给出一个有序数列a,这个数列中每两个数，如果满足一个数能整除另一个数，则这两个数中间是有一条边的，现在有这样的图，求最大联通子图。
题解：并不需要把图搞出来，可以直接dp，$f[i]$表示以第$i$个数为开头的最大的联通子图，转移类似最长上升子序列，$f[i]=max(f[i],f[j]+1)$
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 1000010
int N,a[MAXN],dp[MAXN],ans,id[MAXN];
int main()
{
N=read();
for (int i=; i<=N; i++) a[i]=read(),id[a[i]]=i;
for (int i=; i<=N; i++) dp[i]=;
for (int i=,now=a[i]; i<=N; i++,now=a[i])
while (now+a[i]<=a[N]) now+=a[i],dp[id[now]]=max(dp[id[now]],dp[i]+);
for (int i=; i<=N; i++) ans=max(ans,dp[i]);
printf("%d\n",ans);
return ;
}
566F
题目大意：给出一个棋盘，棋盘上有K个障碍，问从左上角走到右下角的方案数，棋盘大小$10^{5}*10^{5}$，障碍点数目$2000$，只能向右或者向下走。
题解：这种题，显然有两种做法，数据范围小，显然可以随便dp，当然也可是直接利用组合数计算，这里只能直接利用组合数计算。
显然从左上角走到点$(x,y)$的方案数是$\textrm{C}^{x-1}_{x-1+y-1}$
$step[i]$表示从左上角到第$i$个障碍点的步数，显然$$step[i]=\textrm{C} ^{x_{i}-1}_{x_{i}-1+y_{i}-1} - \sum ^{j}_{x_{j}<=x_{i},y_{j}<=y_{i}}step[j]* \textrm{C}^{x_{i}-x_{j}}_{x_{i}-x_{j}+y_{i}-y_{j}}$$
然后再计算点$(N,M)$的答案即可。
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define P 1000000007
#define MAXN 2001
int N,M,K;
LL step[MAXN],fac[],inv[];
inline LL qp(LL x,int y)
{
LL re=;
for (int i=y; i; i>>=,x=x*x%P) if (i&) re=re*x%P;
return re;
}
inline LL Inv(int x) {return qp(x,P-);}
struct PointNode{int x,y;}ct[MAXN];
inline LL C(int n,int m) {return fac[n]*inv[m]%P*inv[n-m]%P;}
inline bool cmp(PointNode A,PointNode B) {return A.x==B.x? A.y<B.y : A.x<B.x;}
int main()
{
N=read(),M=read(),K=read();
fac[]=; inv[]=Inv(fac[]);
for (int i=; i<=N+M; i++) fac[i]=fac[i-]*i%P,inv[i]=Inv(fac[i]);
for (int i=; i<=K; i++) ct[i].x=read(),ct[i].y=read();
sort(ct+,ct+K+,cmp);
for (int i=; i<=K; i++)
{
step[i]=C(ct[i].x-+ct[i].y-,ct[i].x-);
for (int j=; j<=K; j++)
if (i!=j && ct[j].x<=ct[i].x && ct[j].y<=ct[i].y)
step[i]=(step[i]-step[j]*C(ct[i].x-ct[j].x+ct[i].y-ct[j].y,ct[i].x-ct[j].x)%P+P)%P;
}
LL ans=C(N-+M-,N-);
for (int i=; i<=K; i++) ans=(ans-step[i]*C(N-ct[i].x+M-ct[i].y,N-ct[i].x)%P+P)%P;
printf("%I64d\n",ans);
return ;
}
559C
题目大意：给出一些树，每个树有两个信息，x表示树的位置，h表示树的高度，每次砍树，被砍的树会向左右两边其中一边倒下，即覆盖$[x_{i}-h_{i},x_{i}],[x_{i},x_{i}+h_{i}]$，但是如果一棵树倒下会和其他树（倒下或不倒下）发生重合，则不能向那边倒下，问最多砍掉的树的个数。
题解：开始以为是很标准的二分，于是开始想，二分出一个height把大于height的可以砍得树砍掉，然后看能砍的棵树。然后意识到，这个题完全不用什么二分，可以直接贪心。
首先第1棵树和最后一棵树显然可以砍到，只要让他们分别往没树的方向倒即可，这样对于2~N-1棵树，可以从左到右贪心，对于一棵树，如果它可以向左倒，那么它一定向左倒，因为这样不会对之后有任何影响；对于一棵树，如果它不能向左倒，那么如果它向右倒不会覆盖右边的没砍的树，那么就让他向右倒下；这样扫一遍得到答案。
这样显然是正确的，首先能向左倒不向右倒显然，至于第二种方式，可以分情况讨论：
假如x向右倒不会覆盖到x+1，让x向右倒，这时加入x+1向左倒，不会和倒下的x覆盖，那么让x+1向左倒，这样这两棵树仍对后面无影响，且最优；
假如x向右倒不会覆盖到x+1，让x向右倒，这时加入x+1向左倒，恰好会覆盖倒下的x，那么x+1不能向左，这样看起来有影响后面的决策，那么假设x不能倒，这样往后转移，最优砍树答案数是不变的，仅仅是砍树的方案发生改变。（自己表述有问题，不过还是比较好想的）
所以就可以这样贪心的扫一遍得到答案。 同时感觉这题可以dp，一种类似背包的dp。
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 100010
int N;
struct TreeNode{int x,h;}a[MAXN];
int main()
{
N=read(); if (N==) {puts(""); return ;}
for (int i=; i<=N; i++) a[i].x=read(),a[i].h=read();
int ans=,last=a[].x;
for (int i=; i<=N-; last=max(a[i].x,last),i++)
if (a[i].x-a[i].h>last) ans++;
else if (a[i].x+a[i].h<a[i+].x) ans++,last=a[i].x+a[i].h;
printf("%d\n",ans);
return ;
}
545C
题目大意：$N$个人打$M$行代码，第$i$个人会打一行代码会出错$a_{i}$次，现在询问总错误数$<=B$的方案数。
题解：比较简单的dp，状态$dp[i][j][k]$表示前$i$个人打了$j$行出错数为$k$的方案数。
转移可以枚举第$i$个人打多少行得到$$dp[i][j][k]=\sum ^{j}_{l=1}dp[i-1][j-l][ k-l*a[i] ]$$
然而这个转移太愚蠢了，同样的状态可以做到$O(N^{3})$转移。$$dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][ k-a[i] ]$$
然后这样内存开不下，把$i$这一维滚动掉就可以了。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
int N,M,B,P,a[],dp[][][],ans;
int main()
{
N=read(),M=read(),B=read(),P=read();
for (int i=; i<=N; i++) a[i]=read();
dp[][][]=;
for (int i=; i<=N; i++)
for (int j=; j<=M; j++)
for (int k=; k<=B; k++)
dp[i&][j][k]=( ( (k-a[i]>= && j->=) ? dp[i&][j-][k-a[i]]:) +dp[(i-)&][j][k])%P;
for (int i=; i<=B; i++) ans=(ans+dp[N&][M][i])%P;
printf("%d\n",ans);
return ;
}
543A
题目大意：现在存在$x$个石头，$y$个剪刀，$z$个包袱，每当两个见面，输的人会淘汰，求最后剩下的为石头、剪刀、包袱的概率分别是多少。
题解：弱智概率dp，设状态$f[i][j][k]$表示还剩$i$个石头，$j$个剪刀，$k$个包袱的概率。
显然$f[x][y][z]=1$然后可以逆推出各种状态，$f[i-1][j][k]$表示$i$和$k$见面，这样转移显然就是$f[i-1][j][k]+=\frac {i*k}{i*k+i*j+k*j}*f[i][j][k]$其余同理。最后分别统计答案即可。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int x,y,z;
double f[][][],rock,scissor,paper;
int main()
{
scanf("%d%d%d",&x,&y,&z);
f[x][y][z]=;
for (int i=x; i>=; i--)
for (int j=y; j>=; j--)
for (int k=z; k>=; k--)
f[i-][j][k]+=(double)i*k/(i*j+i*k+k*j)*f[i][j][k],
f[i][j-][k]+=(double)i*j/(i*j+i*k+k*j)*f[i][j][k],
f[i][j][k-]+=(double)k*j/(i*j+i*k+k*j)*f[i][j][k];
for (int i=; i<=x; i++)
for (int j=; j<=y; j++)
rock+=f[i][j][];
for (int i=; i<=y; i++)
for (int j=; j<=z; j++)
scissor+=f[][i][j];
for (int i=; i<=x; i++)
for (int j=; j<=z; j++)
paper+=f[i][][j];
printf("%.10lf %.10lf %.10lf\n",rock,scissor,paper);
return ;
}
540D
题目大意：给出一个N个数的环，每次给出一个b，对这个环分段，每段必须相邻，且每段的和$<=b$，求最小段数。
题解：首先展环为链，然后处理。首先，尽可能的多取，一定比少取要优。定义$st[i]$表示以$i$位置为最后的方案的开始点，$cnt[i]$表示以$i$位置为最后的方案的方案数。
然后就可以dp..扫一遍环，得到前一段的末尾$j$就可转移$$st[i]=st[j],cnt[i]=cnt[j]+1$$
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define LL long long
inline LL read()
{
LL x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 1000100
int N,Q,a[MAXN<<],st[MAXN<<],cnt[MAXN<<];
LL sum[MAXN<<];
int main()
{
N=read(),Q=read();
for (int i=; i<=N; i++) a[i]=a[i+N]=read(),st[i]=i;
for (int i=; i<=*N; i++) sum[i]=sum[i-]+a[i];
while (Q--)
{
LL b=read();
for (int j=,i=N+; i<=N*; i++)
{
while (sum[i]-sum[j]>b) j++;
st[i]=st[j];
cnt[i]=cnt[j]+;
if (i-st[i]>=N) {printf("%d\n",cnt[i]); break;}
}
}
return ;
}
526E
题目大意：每个人有一个领导，1节点除外，同时每个点有一个权值，从这棵树中取出一些点，使得每个领导领导的人数是偶数，且权值和最大，输出权值和。
题解：这个题的题意比较绕，注意的题意是：假设U有三个儿子，可以选两个合法的儿子，并且从第三个儿子的子孙里再选偶数个合法子孙。
真正读懂题之后就比较好考虑怎么做了，分子树选到的儿子孙的奇偶来dp；$dp[x][0/1]$表示以x为根的子树中选了奇数个和偶数个的合法的方案数。
这样转移就可以奇偶交替进行。$$dp[x][0]=max(dp0+dp[v][0],dp1+dp[v][1])$$ $$dp[x][1]=max(dp[x][0]+a[x],max(dp0+dp[v][1],dp1+dp[v][0]))$$
其中最后的答案就是$max(dp[1][1],dp[1][0])$
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define LL long long
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 200010
int N,p[MAXN],a[MAXN];
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {if (u==-) return; AddEdge(u,v); AddEdge(v,u);}
LL dp[][MAXN];
#define INF 0x7fffffff
inline void DFS(int now)
{
dp[][now]=-INF,dp[][now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=p[now])
{
DFS(edge[i].to);
LL dp1=dp[][now],dp0=dp[][now];
dp[][now]=max(dp0+dp[][edge[i].to],dp1+dp[][edge[i].to]);
dp[][now]=max(dp0+dp[][edge[i].to],dp1+dp[][edge[i].to]);
}
dp[][now]=max(dp[][now],dp[][now]+a[now]);
}
int main()
{
N=read();
for (int i=; i<=N; i++) p[i]=read(),a[i]=read(),InsertEdge(p[i],i);
DFS();
printf("%I64d\n",max(dp[][],dp[][]));
return ;
}
533B
题目大意：有N个人，每秒有p的概率有一个人进入电梯，总共有t秒，求期望。
题解：比较简单的概率dp，设状态$dp[i][j]$表示$i$秒有$j$个人的概率；转移很显然：$$dp[i][j]=p*dp[i-1][j-1]+(1-p)*dp[i-1][j]$$
但是这少考虑了一种情况，如果$j==n$了之后，$dp[i][j]$会完全继承$dp[i-1][j]$的状态，所以当$j==n$时，转移就是：$$dp[i][j]=p*dp[i-1][j-1]+dp[i-1][j]$$
答案是期望，那就dp之后再扫一遍求一下即可。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,t;
double p,dp[][];
int main()
{
scanf("%d%lf%d",&n,&p,&t);
dp[][]=1.0;
for (int i=; i<=t; i++)
for (int j=; j<=n; j++)
{
if (j==) {dp[i][j]=(1.0-p)*dp[i-][j]; continue;}
if (j==n) {dp[i][j]=p*dp[i-][j-]+dp[i-][j]; continue;}
dp[i][j]+=p*dp[i-][j-]+(1.0-p)*dp[i-][j];
}
double ans=;
for (int i=; i<=n; i++) ans+=dp[t][i]*i;
printf("%.7lf\n",ans);
return ;
}
518D
题目大意：有N个点，每个点有两个数值$x_{i}$和$w_{i}$，定义两个点$<u,v>$有边，需要满足$|x_{i}-x_{j}|>=w_{i}+w_{j}$，现在要求找一个点集，使得这个点集中的点两两有边，求最大点数。
题解：首先考虑两点有边的情况，需要满足$|x_{i}-x_{j}|>=w_{i}+w_{j}$，但是由于边无序性，假设$x_{i}>=x_{j}$，则这就可以化成$x_{i}-x_{j}>=w_{i}+w_{j}$，进一步转化，就可以得到：$$x_{i}-w_{i}>=x_{j}+w_{j}$$
这样可以先贪心的先对点进行排序，关键字为$x_{i}+w_{i}$。
考虑dp，dp方程显然$dp[i]$表示以第$i$个点结尾的点集，最大的点数，转移也很显然：$$dp[i]=max(dp[i],dp[j]+1),<i,j>相连$$
这样对于点$i$，就是找$x_{j}-w_{j}<=x_{i}+w_{j}$的点中，$dp[j]$最大$j$的转移，这显然可以利用线段树优化转移，单次转移复杂度$logN$，总复杂度$O(NlogN)$。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 200010
int N,val[MAXN];
struct PointNode {int x,w;}p[MAXN];
inline bool cmp(PointNode A,PointNode B) {return A.x+A.w<B.x+B.w;}
namespace SegmentTree
{
struct {int l,r,maxx;}tree[MAXN<<];
#define ls now<<1
#define rs now<<1|1
inline void Update(int now) {tree[now].maxx=max(tree[ls].maxx,tree[rs].maxx);}
inline void Build(int now,int l,int r)
{
tree[now].l=l; tree[now].r=r;
if (l==r) return;
int mid=(l+r)>>;
Build(ls,l,mid); Build(rs,mid+,r);
}
inline void Modify(int now,int pos,int D)
{
int l=tree[now].l,r=tree[now].r;
if (l==r) {tree[now].maxx=D; return;}
int mid=(l+r)>>;
if (pos<=mid) Modify(ls,pos,D); else Modify(rs,pos,D);
Update(now);
}
inline int Query(int now,int L,int R)
{
if (R<L) return ;
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r) return tree[now].maxx;
int mid=(l+r)>>,re=;
if (L<=mid) re=max(re,Query(ls,L,R));
if (R>mid) re=max(re,Query(rs,L,R));
return re;
}
}
using namespace SegmentTree;
int main()
{
N=read();
for (int i=; i<=N; i++) p[i].x=read(),p[i].w=read(),val[i]=p[i].x+p[i].w;
sort(p+,p+N+,cmp); sort(val+,val+N+);
Build(,,N);
for (int i=,j; i<=N; i++)
j=upper_bound(val+,val+N+,p[i].x-p[i].w)-val -,
Modify(,i,Query(,,j)+);
printf("%d\n",tree[].maxx);
return ;
}
527D
题目大意：给出N个数，K个操作，每个操作可以把一个数变成它的阶乘，取任意多个数，加和后答案恰好为S的方案数。
题解：这题感觉可以dp，但是并不能表示状态；
这个题每个数的状态有3种，1.直接选它2.不选它3.把他变成阶乘后选它，所以总状态数就是$3^{N}$，这里$N<=25$，显然空间和时间都不允许。
一种思想交过Meet-in-the-middle，就是把一个大的问题分成两段来解决，和分治有点像。
这个题也是一样，把序列分成$[1,\frac{N}{2}]和[\frac{N}{2}+1,N]$然后两段分别处理。
对前一段爆搜，把每种状态的答案记录下来，然后再对后一段爆搜，搜到已有状态就可以直接加到答案里。
这样每次爆搜的复杂度就是$O(3^{\frac{N}{2}})$的，就可以通过。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
#define LL long long
int N,K,a[],Mx;
LL S,fac[],ans;
map<LL,int>cnt[];
inline void back(int now,int k,LL sum)
{
if (sum<) return;
if (now==N/) {cnt[k][sum]++; return;}
if (a[now]<=Mx && k) back(now-,k-,sum-fac[ a[now] ]);//变后再选
back(now-,k,sum-a[now]);//直接选
back(now-,k,sum); //不选
}
inline void front(int now,int k,LL sum)
{
if (sum>S) return;
if (now==N/+) {for (int i=k; i<=K; i++) ans+=cnt[i][sum]; return;}
if (a[now]<=Mx && k<K) front(now+,k+,sum+fac[ a[now] ]);
front(now+,k,sum+a[now]);
front(now+,k,sum);
}
int main()
{
scanf("%d%d%I64d",&N,&K,&S);
fac[]=; for (int i=; i<= && fac[i-]<=S; i++) fac[i]=fac[i-]*i;
for (int i=; i<=; i++) if (fac[i]>S) {Mx=i-; break;}
for (int i=; i<=N; i++) scanf("%d",&a[i]);
sort(a+,a+N+);
back(N,K,S); front(,,);
printf("%I64d\n",ans);
return ;
}
525E
题目大意：给出一个树，开始时两个人位于根节点，两个人轮流操作，先手第一个人希望达到的点尽可能大，后手第二个人希望达到的点尽可能小，两个人绝顶聪明，有一个操控全局的人，他可以任意指定叶节点的值，求能够到达的最大值和最小值。
题解：这道题真TM恶心。
首先可以先考虑一下这种游戏时自己的决策，如果想要达到的最大，那么一定会向一个大数多的，且数值大的子树移动，找最小是相同的。
设计状态$f[0/1][i]$表示最优情况下最大/最小到$i$点子树中第$f[0/1][i]$大/小的那个子树，然后可以分奇偶转移，$$f[0][i]=min(f[0][i],f[0][j]) (deep为奇数)$$ $$f[0][i]=\sum f[0][j] (deep为偶数)$$
然后就可以dp，初始化$f[0][i]=INF,f[1][i]=0$先手后手两遍dp即可得到答案。
Code：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 200010
int N;
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int f[][MAXN],tot;
#define INF 0x7fffffff
inline void DFS(int now,int last,int opt)
{
bool flag=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
{
flag=;
DFS(edge[i].to,now,opt^);
if (opt)
f[][now]+=f[][edge[i].to];
else
f[][now]=min(f[][now],f[][edge[i].to]);
}
if (!flag) f[][now]=f[][now]=,tot++;
}
int main()
{
N=read();
for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
memset(f[],,sizeof(f[])); memset(f[],,sizeof(f[]));
DFS(,,);
DFS(,,);
printf("%d %d\n",tot/-f[][]+,f[][]);
return ;
}
538E
题目大意:给出一个程序段，求用这个程序段去遍历一棵树，得到给定序列的不同的树的方案数。
used[1 ... n] = {0, ..., 0};
procedure dfs(v):
print v;
used[v] = 1;
for i = 1, 2, ..., n:
if (a[v][i] == 1 and used[i] == 0):
dfs(i);
dfs(1);
题解：这显然就是dfs序,,,但是这里是邻接矩阵存的图，所以一个根的几个儿子一定是从小到大开始输出的。
这样就可以dp，状态$dp[l][r]$表示$[l,r]$这段可能的树的数量，显然，这样定义状态$l$一定是这一段的根，转移显然是利用乘法原理统计答案：$$dp[l][r]=\sum ^{r}_{k=l+1} dp[l+1][k]*dp[k][r] \qquad 满足a_{l+1}<a_{i+1}$$
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define LL long long
#define P 1000000007
int N,a[],f[][];
int main()
{
scanf("%d",&N);
for (int i=; i<=N; i++) scanf("%d",&a[i]);
for (int i=; i<=N; i++) f[i][i]=;
for (int len=,l,r; len<=N; len++)
for (int i=; i+len-<=N; i++)
{
l=i,r=l+len-;
for (int k=l+; k<=r; k++)
if (k==r || a[l+]<a[k+])
(f[l][r]+=(LL)f[l+][k]*f[k][r]%P)%=P;
}
printf("%d\n",f[][N]);
return ;
}
509F
题目大意：给出一行方块组成的塔，每个位置的高度为$h_{i}$，每次操作可以将所有暴露在外面的方块消掉，暴露在外面指的这个方块有四联通的一边是空，问最少需要消多少次能消完。
题解：找一找规律就很好做了；首先每次消暴露在外面，这样，显然每一个位置的塔至少最上端一定会被消去，最左最右一定全部被消去，然后每个中间的位置可能会被消去更多的，当且当它的左右有比他低的。
这就很好做了，所以第一次的变换就可以写出来：$$h[i]-->h'[i]=min(h[i-1],min(h[i+1],h[i]-1))$$同理，能得到多次操作后的$h'[i]$的值：$$h[i]-->h'[i]=min^{i}_{j=1}(h[i-j+1]-(k-j),h[i+j-1]-(k-j)) \qquad k表示轮数$$
然后这个东西随便搞搞就可以出来了，前后扫一遍。
（不想自己翻译题目，于是找别人的题目大意，然后看见别人标题是线段树+dp，就顺手写了个线段树，然后发现这弱智东西扫一遍就可以得到了吧！）
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define LL long long
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 100010
#define INF (1LL<<60)
int N,h[MAXN];
LL ans,pre[MAXN],suf[MAXN];
namespace SegmentTree
{
struct SgtTreeNode{int l,r; LL tag,minx;}tree[MAXN<<];
#define ls now<<1
#define rs now<<1|1
inline void Update(int now) {tree[now].minx=min(tree[ls].minx,tree[rs].minx);}
inline void Build(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r; tree[now].tag=;
if (l==r) {tree[now].minx=h[l]; return;}
int mid=(l+r)>>;
Build(ls,l,mid); Build(rs,mid+,r);
Update(now);
}
inline void PushDown(int now)
{
if (tree[now].l==tree[now].r || !tree[now].tag) return;
LL delta=tree[now].tag; tree[now].tag=;
tree[ls].tag+=delta; tree[rs].tag+=delta;
tree[ls].minx+=delta; tree[rs].minx+=delta;
}
inline void Modify(int now,int L,int R)
{
PushDown(now);
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r) {tree[now].tag+=; tree[now].minx+=; return;}
int mid=(l+r)>>;
if (L<=mid) Modify(ls,L,R);
if (R>mid) Modify(rs,L,R);
Update(now);
}
inline LL Query(int now,int L,int R)
{
PushDown(now);
int l=tree[now].l,r=tree[now].r;
if (L<=l && R>=r) return tree[now].minx;
int mid=(l+r)>>; LL re=INF;
if (L<=mid) re=min(re,Query(ls,L,R));
if (R>mid) re=min(re,Query(rs,L,R));
return re;
}
}
int main()
{
N=read();
for (int i=; i<=N; i++) h[i]=read();
SegmentTree::Build(,,N+);
for (int i=; i<=N; i++) SegmentTree::Modify(,,i-),pre[i]=SegmentTree::Query(,,i);
SegmentTree::Build(,,N+);
for (int i=N; i>=; i--) SegmentTree::Modify(,i+,N+),suf[i]=SegmentTree::Query(,i,N+);
// for (int i=1; i<=N; i++) printf("%d %d\n",pre[i],suf[i]);
for (int i=; i<=N; i++) ans=max(ans,min(pre[i],suf[i]));
printf("%I64d\n",ans);
return ;
}
573B
题目大意：有两种不同的兵种，兵种1有N个单位，兵种2有M中单位，现在将这些兵排成一行，要求兵种1最多连续不超过K1个，兵种2最多连续不超过K2个。
题解：显然可以dp，状态$dp[i][j][0/1]$表示兵种1有$i$个，兵种2有$j$个，最后一个是兵种1/兵种2的符合条件的方案数，然后转移就是瞎枚举$$dp[i][j][0]=\sum ^{min(K1,i)}_{i'=1} dp[i-i'][j][1]$$ $$dp[i][j][1]=\sum ^{min(K2,j)}_{j'=1} dp[i][j-j'][0]$$
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define P 100000000
int N,M,K1,K2,dp[][][];
int main()
{
scanf("%d%d%d%d",&N,&M,&K1,&K2);
for (int i=; i<=K1; i++) dp[i][][]=;
for (int i=; i<=K2; i++) dp[][i][]=;
for (int i=; i<=N; i++)
for (int j=; j<=M; j++)
{
for (int k1=; k1<=K1 && k1<=i; k1++) (dp[i][j][]+=dp[i-k1][j][])%=P;
for (int k2=; k2<=K2 && k2<=j; k2++) (dp[i][j][]+=dp[i][j-k2][])%=P;
}
printf("%d\n",(dp[N][M][]+dp[N][M][])%P);
return ;
}
118D
题目大意：给出N个物品，每个物品有w,h两种权值，给出一个初始的w,h，求用给定的N个物品组成 最长的 以给出的初始为开头的 严格上升的序列，输出一种可行解。 物品的比较满足二维偏序。
题解：二维偏序显然可以排序乱搞...先排序，然后dp； $$dp[i]=max(dp[j]+1,dp[i]) \qquad a_{j}<a_{i}$$ 输出可行解，就在转移的时候记录从哪一个转移过来，最后倒叙统计一下并输出即可。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 5001
int N,w,h,dp[MAXN],ans,from[MAXN],Ans[MAXN],top;
struct Node{int w,h,id;}a[MAXN];
inline bool cmp(Node A,Node B) {return A.w==B.w? A.h<B.h:A.w<B.w;}
int main()
{
N=read(); w=read(); h=read();
for (int i=; i<=N; i++) a[i].w=read(),a[i].h=read(),a[i].id=i;
sort(a+,a+N+,cmp);
for (int i=; i<=N; i++)
if (a[i].w>w && a[i].h>h)
{
for (int j=; j<=i-; j++)
if (a[j].w<a[i].w && a[j].h<a[i].h)
from[i]=(dp[i]<dp[j]+)? j:from[i],
dp[i]=max(dp[j]+,dp[i]);
}
for (int i=; i<=N; i++) ans=max(dp[i],ans);
for (int i=; i<=N && !top; i++)
if (dp[i]==ans)
for (int now=i; now; now=from[now]) Ans[++top]=a[now].id;
printf("%d\n",ans);
if (!ans) return ;
for (int i=top; i>=; i--) printf("%d ",Ans[i]); puts("");
return ;
}
4D
题目大意：给出一个树，树上边的长度为1，求有多少无序点对，满足距离恰好为K。
题解：可以直接树形dp得到，设状态$dp[x][k]$表示到第$x$个节点距离恰好为$k$的点数，转移很显然$$dp[x][k]=\sum _{y=son} dp[y][k-1]$$ 可以在dp的过程中统计答案，注意要开longlong
Code：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 50010
int N,K;
LL ans,dp[MAXN][];
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
inline void DFS(int now,int last)
{
dp[now][]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
{
DFS(edge[i].to,now);
for (int k=; k<=K-; k++) ans+=(LL)dp[now][K-k-]*dp[edge[i].to][k];
for (int k=; k<=K; k++) dp[now][k]+=dp[edge[i].to][k-];
}
}
int main()
{
N=read(),K=read();
for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
DFS(,);
printf("%I64d\n",ans);
return ;
}
161D
题目大意：给出一个网格，第一个人从$(1,1)-->(N,M)$第二个人从$(N,1)-->(1,M)$，两个人路径上经过一次的点可以得到这个点的权值，被两个人都经过的点将无法得到这个点的权值，求最大权值。
题解：因为两个人都经过的点无法得到权值，且权值$>=0$，而且两个人不可避免会相交，所以显然越少相交越好，所以可以贪心的枚举哪个点相交。
剩下的答案可以dp得到，$dp[0/1/2/3][i][j]$分别表示从$(1,1)-->(N,M) / (N,M)-->(1,1) / (N,1)-->(1,M) / (1,M)-->(N,1)$的最大权值，然后这个瞎搞就搞出来了。
然后暴力枚举每个内层点为断点就可以了，枚举的时候讨论一下即可。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 1010
int N,M,a[MAXN][MAXN],dp[][MAXN][MAXN],ans;
int main()
{
N=read(),M=read();
for (int i=; i<=N; i++)
for (int j=; j<=M; j++) a[i][j]=read();
for (int i=; i<=N; i++)
for (int j=; j<=M; j++)
dp[][i][j]=max(dp[][i-][j],dp[][i][j-])+a[i][j];
for (int i=N; i>=; i--)
for (int j=M; j>=; j--)
dp[][i][j]=max(dp[][i+][j],dp[][i][j+])+a[i][j];
for (int i=N; i>=; i--)
for (int j=; j<=M; j++)
dp[][i][j]=max(dp[][i+][j],dp[][i][j-])+a[i][j];
for (int i=; i<=N; i++)
for (int j=M; j>=; j--)
dp[][i][j]=max(dp[][i-][j],dp[][i][j+])+a[i][j]; // puts("");
// for (int k=0; k<=3; k++,puts("================"))
// for (int i=1; i<=N; i++,puts(""))
// for (int j=1; j<=M; j++)
// printf("%d ",dp[k][i][j]); for (int i=; i<=N-; i++)
for (int j=; j<=M-; j++)
ans=max(ans , max( dp[][i-][j]+dp[][i+][j]+dp[][i][j-]+dp[][i][j+],
dp[][i][j-]+dp[][i][j+]+dp[][i+][j]+dp[][i-][j]) );
printf("%d\n",ans);
return ;
}
429B
题目大意：给出一个序列，每次可以消去一段连续的回文，消去之后两边合并，求最少消几次能全部消完。
题解：区间dp好题！
首先状态表示为$dp[l][r]$表示消去$[l,r]$这段的最小步数，这很显然，然后正常枚举断点转移$dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r])$也很显然
难点在于处理消回文，开始想错了，$O(N^3)$的复杂度感觉可以再枚举一下跟区间的开头一样的位置，判断是否可以当回文删掉，但这样并不科学，因为就算找到也没法科学地判断是否是回文，而且最难搞的是没法处理删掉这段回文之后，其余的两段合并起来，正解是比较巧妙的方法。
首先，先假设已经在处理$dp[l][r]$的时候，它的所有小的部分已经搞定了，那么假如$a_{l}==a_{r}$则这两个可以当做一个回文的最左最右边，和回文一起删掉，而这样的答案就是$dp[l+1][r-1]$，而且区间$[l+1,r-1]$消除到最后，一定会剩下一个回文串（最差剩下一个单一的），而回文串两边各加上相同的，显然还是个回文，所以可以一并删掉，所以回文的转移就得到了：$$dp[l][r]=min(dp[l][r],dp[l+1][r-1]) \qquad (a_{l}==a_{r} 且 l+1<=r-1)$$
这样就在$O(N^3)$的时间复杂度下解决问题了。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 510
int N,a[MAXN],dp[MAXN][MAXN];
int main()
{
N=read();
for (int i=; i<=N; i++) a[i]=read();
memset(dp,,sizeof(dp));
for (int i=; i<=N; i++) dp[i][i]=;
for (int len=; len<=N; len++)
for (int i=; i+len-<=N; i++)
{
int l=i,r=l+len-;
for (int k=l; k<=r; k++)
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+][r]);
if (a[l]==a[r]) dp[l][r]=min(dp[l][r], l+>r-? :dp[l+][r-]);
}
printf("%d\n",dp[][N]);
return ;
}
607B
题目大意：给出一个括号序列，每个括号可以上色或不上，上色又有两种不同的颜色可以上，但必须满足要求：1.相互匹配的一对括号，有且只有一个能上色2.相邻两个括号不能同时同上一种颜色，但可以同时不上色。问合法方案数。
题解：这个题非常好！很显然可以区间dp，但是又比较麻烦..$f[l][r][x][y]$表示$[l,r]$段合法的方案数，$x$表示$l$位置的上色方案为$x$,$y$表示$r$位置的上色方案为$y$，其中$0$表示无色，$1/2$分别代表两种不同的颜色
然后这样就可以区间dp了，然后转移很能搞事，需要讨论很多种情况。
如果$l和r的括号恰好匹配$那么，转移可以$$f[l][r][x][y]=\sum f[l+1][r-1][x'][y'] \qquad (l和l+1满足条件2，且r-1和r满足条件2)$$
如果不匹配，那就需要拆区间，假设$pa[l]$表示与$l$匹配的括号位置，那么转移就是$$f[l][r][x][y]=\sum {f[l][pa[l]][x][x']*f[pa[l]+1][r][y'][y]} \qquad (x'和y'符合条件2)$$
这里$l$和$pa[l]$的限制就放到递归中限制了。
这道题写递推简直蛋疼，所以写的记搜，速度还是很可观的。
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define LL long long
#define P 1000000007
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 1010
char s[MAXN];
int N,pa[MAXN],st[MAXN],tp,f[MAXN][MAXN][][],ans;
inline int dp(int l,int r,int x,int y)
{
// printf("<%d %d %d %d> :: ",l,r,x,y);
if (~f[l][r][x][y]) return f[l][r][x][y];
if (l>r) return ;
if (r-l+==)
if ((x && !y) || (!x && y)) return f[l][r][x][y]=;
else return f[l][r][x][y]=;
//这里是一个特判相邻的两个正好匹配，显然情况就4种且方案数都为1
LL tmp=;
if (pa[l]==r)//这里是处理l，r正好匹配的时候
if ((x && !y) || (!x && y))//这是在保证匹配的时候xy颜色合法
for (int xx=; xx<=; xx++)
for (int yy=; yy<=; yy++)
if (!(x && xx && xx==x) && !(y && yy && yy==y))
tmp=(tmp+dp(l+,r-,xx,yy))%P;
else;
else return f[l][r][x][y]=;
else //这里是处理l，r不匹配的时候，区间断开统计的情况
for (int xx=; xx<=; xx++)
for (int yy=; yy<=; yy++)
if (!(xx==yy && xx))
tmp=(tmp+(LL)dp(l,pa[l],x,xx)*dp(pa[l]+,r,yy,y)%P)%P;
return f[l][r][x][y]=tmp;
}
int main()
{
scanf("%s",s+); N=strlen(s+);
for (int i=; i<=N; i++)
if (s[i]=='(') st[++tp]=i;
else pa[i]=st[tp--];
for (int i=; i<=N; i++)
if (pa[i]) pa[ pa[i] ]=i;
// for (int i=1; i<=N; i++) printf("%d ",pa[i]); puts("");
memset(f,-,sizeof(f));
for (int x=; x<=; x++)
for (int y=; y<=; y++)
ans=(ans+dp(,N,x,y))%P;
printf("%d\n",ans);
return ;
}
149D
题目大意：给出一棵单向边组成的“树”，求出用最小的操作使得令一个点为根时，这个点能到达其余所有点，每次操作是将一条边反向，并输出可行的点。
题解：这个题刚上来觉得有些蛋疼，想的仅仅是单向连边然后从每个点拓展，记录一下答案，然后再整个跑一下统计答案，感觉求出最小操作数是可以的，但是没法所有最小操作数可行的点。
但启发了思路，其实这题很简单，正常的连边，记录一下边的正反，树形dp两遍。
第一遍是强行以1为根，$f[x]$表示以$x$为根的子树在以1为根的情况下需要反转边几次，这个随意搞搞就出来了，得到了$f[]$之后，再进行一遍树形dp就可以得到以各点为整棵树根的答案，然后就可以了。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 200010
int N;
struct EdgeNode{int next,to,opt;}edge[MAXN<<];
int cnt=,head[MAXN];
inline void AddEdge(int u,int v,int k) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].opt=k;}
inline void InsertEdge(int u,int v) {AddEdge(u,v,); AddEdge(v,u,);}
int f[MAXN],g[MAXN];
inline void DFS_1(int now,int last)
{
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
g[edge[i].to]=edge[i].opt,
DFS_1(edge[i].to,now),
f[now]+=f[edge[i].to]+(g[edge[i].to]? :);
}
inline void DFS_2(int now,int last)
{
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
f[edge[i].to]=f[now]+(g[edge[i].to]? :-),DFS_2(edge[i].to,now);
}
int main()
{
N=read();
for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
DFS_1(,);
DFS_2(,);
int ans=0x7fffffff;
for (int i=; i<=N; i++) ans=min(ans,f[i]);
printf("%d\n",ans);
for (int i=; i<=N; i++) if (f[i]==ans) printf("%d ",i);
return ;
}
219D
题目大意：给出N个字符串，两个人进行K轮游戏，每个人每次添加一个字符，要求组成的字串为给出字符串中任意串的前缀，交替进行，直到不能放符合条件的字符为败，上一轮游戏的败者为下轮的先手，整个过程的胜者，定义为第K局结束的胜者。
题解：这题真的有点蛋疼..又把博弈和树结合起来。
根据题目中游戏的定义，肯定先会联想到Trie树，就转换成两个人在Trie树上博弈，因为树的形态是一定的，所以先手和后手的每种状态的结局也是确定不变的，所以可以进行树形dp求得；
首先Trie树的叶节点深度显然先手必胜/必败，然后可以统计出每个非叶节点是否存在必胜、必败子节点。
这个博弈是最标准的博弈，先手必胜当子节点中存在必胜态，后手必胜当所有子节点全是必胜态，这样dp一遍就能得到所有节点的状态；
然后讨论答案：
1.如果初始的先手玩家存在必胜套路同时也存在失败套路，显然他可以一直输，最后一局翻盘；
2.如果初始玩家先手没有必胜套路，也就是说后手玩家一定存在至少一种方法可以令先手必败，这样先手一定一直输；
3.如果先手玩家只有必胜套路，怎么都不会输，那么整个过程的胜者就取决于K轮数的奇偶了；
Code：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAXN 100010
int N,K;
char s[MAXN];
int son[MAXN][],sz=;
inline void Insert(char str[])
{
int now=,len=strlen(str+);
for (int i=; i<=len; i++)
if (son[now][str[i]-'a'+]) now=son[now][str[i]-'a'+];
else son[now][str[i]-'a'+]=++sz,now=sz;
}
int tree[MAXN][];
inline void DFS(int now,int opt)
{
bool w=opt^,f=opt^,flag=;
for (int i=; i<=; i++)
if (son[now][i])
{
flag=;
DFS(son[now][i],opt^);
if (opt) w=w||tree[son[now][i]][],f=f||tree[son[now][i]][];
else w=w&&tree[son[now][i]][],f=f&&tree[son[now][i]][];
}
if (flag) tree[now][]=w,tree[now][]=f;
else tree[now][opt]=,tree[now][opt^]=;
}
int main()
{
scanf("%d%d",&N,&K);
for (int i=; i<=N; i++) scanf("%s",s+),Insert(s);
DFS(,);
// for (int i=1; i<=sz; i++) printf("%d %d\n",tree[i][0],tree[i][1]);
if (!tree[][]) {puts("Second"); return ;}
if (tree[][]) {puts("First"); return ;}
if (K&) puts("First"); else puts("Second");
return ;
}
455B
题目大意：给出N个数，取任意个数，问能否使取得数的和%M恰好为0
题解：这个题还是很水的，可以直接一个01背包水过去，但是复杂度是$O(NM)$的，过不了，然后就得利用鸽巢原理。
就是说，N个数，共有N种前缀和，而%M得到的值，只有M种，所以，根据鸽巢原理，当N>M时，一定有至少两个前缀和%M后得到的值是相同的，所以N>M一定能取到%M=0的情况，所以是必然YES。
剩下的做个背包，复杂度$O(M^{2})$。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
int N,M,a[];
bool dp[][];
inline bool DP()
{
dp[][]=;
for (int i=; i<=N; i++)
for (int j=M-; j>=; j--)
if (dp[i-][((j-a[i])%M+M)%M]) {dp[i][j]=; if (!j) return ;}
else if (dp[i-][j]) dp[i][j]=;
return ;
}
int main()
{
N=read(),M=read();
for (int i=; i<=N; i++) a[i]=read();
if (N>M) return puts("YES"),;
else return puts(DP()? "YES":"NO"),;
}
577B
题目大意：给出一棵树，每个点有点权，每次可以处理一条从根开始的一些相互连通的点，可以对这些点的点权+1，或-1，问最少需要几次才能使树中所有节点权值全部为0
题解：这个题还是很容易的，每次改变必须从根开始，所以肯定贪心的从叶子一次一次的变成0，这样$dp[0/1][x]$第$x$节点的最多+1/-1多少次。
一开始想的是，这个东西可以通过它的儿子的$dp[0/1]$值相加得到，但是立马发现了不对，因为一次改变可以是根到两个它的儿子一起变，这样他只会改变1次，所以直接取max就好了。
然后初步得到$dp[0/1][x]$之后，就得到了当前点的权值是多少，然后再直接计算把这个节点变成0，需要+1/-1多少次，统计起来即可。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define LL long long
inline LL read()
{
LL x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 100010
int N;
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; }
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
LL dp[][MAXN],val[MAXN];
inline void DFS(int now,int last)
{
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
{
DFS(edge[i].to,now);
dp[][now]=max(dp[][now],dp[][edge[i].to]);
dp[][now]=max(dp[][now],dp[][edge[i].to]);
}
val[now]=val[now]+dp[][now]-dp[][now];
dp[][now]+= val[now]<? -val[now]:;
dp[][now]+= val[now]>? val[now]:;
}
int main()
{
N=read();
for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
for (int i=; i<=N; i++) val[i]=read();
DFS(,);
// for (int i=1; i<=N; i++) printf("<%d,%d>\n",dp[0][i],dp[1][i]);
printf("%I64d\n",dp[][]+dp[][]);
return ;
}
274B
题目大意：给出N个点和M条边，要求支持两种操作：1.询问x所在树的直径 2.给出x，y合并x，y所在的树，且合并的后的直径尽量小。
题解：求树的直径随便求啊，两遍dfs就可以得到，合并操作需要考虑。
两树相连合并，要想合并后的直径最大，显然是用两个树直径的端点相连；最小，显然是将两个直径的中点相连，这样合并后的直径就可以算出来了$$L_{xy}=max(L_{x},L_{y},\frac{L_{x}+1}{2}+\frac{L_{y}+1}{2}+1)$$
然后就可以用并查集维护一下。
利用dfs时间戳就可以对初始不同的树划分，然后对每棵不同的树进行两遍dfs，在求直径的时候，注意单点的情况；再每棵树用一个并查集维护，这题就可以了。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 300010
int N,M,Q;
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int deep[MAXN],side,l,belong[MAXN],dfn;
namespace UnionFind
{
int f[MAXN],L[MAXN];
inline void init() {for (int i=; i<=dfn; i++) f[i]=i;}
inline int F(int x) {if (f[x]==x) return x; else return f[x]=F(f[x]);}
inline void Merge(int x,int y)
{
if (F(x)==F(y)) return;
int fx=F(x),fy=F(y);
L[fx]=max( max(L[fx],L[fy]) , (L[fx]+)/+(L[fy]+)/+ );
f[fy]=fx;
}
}
using namespace UnionFind;
inline void DFS(int now,int last)
{
belong[now]=dfn;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
{
deep[edge[i].to]=deep[now]+;
DFS(edge[i].to,now);
}
if (deep[now]>l) l=deep[now],side=now;
}
inline void GetL(int now)
{
dfn++; side=now;
l=; deep[now]=; DFS(now,);
l=; deep[side]=; DFS(side,);
L[dfn]=l;
}
int main()
{
N=read(); M=read(); Q=read();
for (int i=,x,y; i<=M; i++) x=read(),y=read(),InsertEdge(x,y);
for (int i=; i<=N; i++) if (!belong[i]) GetL(i);
init();
// for (int i=1; i<=N; i++) printf("%d ",belong[i]); puts("");
while (Q--)
{
int opt=read(),x,y;
switch (opt)
{
case : x=read(); printf("%d\n",L[ F(belong[x]) ]); break;
case : x=read(),y=read(); Merge(belong[x],belong[y]); break;
}
// for (int i=1; i<=N; i++) printf("%d ",L[F(belong[i])]); puts("");
}
return ;
}
455C
题目大意：给出一棵树，求树中一个联通子图，使得点权最大的点和点权最小的点点权差值不超过d，问有多少种联通子图。
题解：看了数据范围，发现$O(N^{2})$就可以，所以暴力就好，因为是联通子图，所以枚举以每个点为最大/最小的点，并向相邻的点暴力，统计答案即可。
唯一稍微蛋疼一点的，就是如果有权值相同的可能会重复计算，这样限制一下点的序号的就可以了
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define P 1000000007
#define MAXN 3010
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
int N,a[MAXN],d,ans,dp[MAXN],s;
inline bool DFS(int now,int last)
{
if (a[now]+d<a[s]) return ;
if (a[now]==a[s] && s<now) return ;
if (a[now]>a[s]) return ;
dp[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
{
bool f=DFS(edge[i].to,now);
if (f) dp[now]=((LL)dp[now]*(dp[edge[i].to]+))%P;
}
return ;
}
int main()
{
d=read(); N=read();
for (int i=; i<=N; i++) a[i]=read();
for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
for (int i=; i<=N; i++) s=i,DFS(i,),ans=(ans+dp[i])%P;
printf("%d\n",ans);
return ;
}
486D
题目大意：给出一个字符串，和Q个询问，每次询问$[l,r]$中，回文串的数量。
题解：愚蠢的区间dp，可以先$O(N^{2})$的预处理出$ok[l][r]$表示$[l,r]$是否是回文串，然后就可以$O(N^{2})$一遍dp求出答案。$$dp[l][r]=dp[l+1][r]+dp[l][r-1]-dp[l+1][r-1]+ok[l][r]$$
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 5010
char s[MAXN];
int Q,N,dp[MAXN][MAXN],ok[MAXN][MAXN],x,y;
int main()
{
scanf("%s",s+); N=strlen(s+);
for (int i=; i<=N; i++) ok[i][i]=;
for (int len=; len<=N; len++)
for (int l=,r=l+len-; l+len-<=N; l++,r=l+len-)
ok[l][r]=len==? s[l]==s[r] : s[l]==s[r]&&ok[l+][r-];
for (int i=; i<=N; i++) dp[i][i]=;
for (int len=; len<=N; len++)
for (int l=,r=l+len-; l+len-<=N; l++,r=l+len-)
dp[l][r]=dp[l+][r]+dp[l][r-]-dp[l+][r-]+ok[l][r];
Q=read();
while (Q--) x=read(),y=read(),printf("%d\n",dp[x][y]);
return ;
}
245H
题目大意：给出一个序列，可以任意调整序列的顺序，使得给出的式子的值最小
题解：这题有点意思，可以先贪心的，先对整个序列排序，然后对序列“分块”，最后进行一遍dp，求出答案。
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 300010
int N,K,a[MAXN],dp[][];
int main()
{
N=read(),K=read();
for (int i=; i<=N; i++) a[i]=read();
sort(a+,a+N+);
int sz1=N%K,sz2=K-N%K,len1=N/K+,len2=N/K;
a[]=a[];
for (int i=; i<=sz1; i++)
for (int j=,k; j<=sz2; j++)
k=(i-)*len1+j*len2,
dp[i][j]=max( dp[i][j] , (i? (dp[i-][j]+a[k+]-a[k]) : dp[i][j] ) ),
k=i*len1+(j-)*len2,
dp[i][j]=max( dp[i][j] , (j? (dp[i][j-]+a[k+]-a[k]) : dp[i][j] ) );
// for (int i=0; i<=sz1; i++,puts(""))
// for (int j=0; j<=sz2; j++)
// printf("%d ",dp[i][j]);
printf("%d\n",a[N]-a[]-dp[sz1][sz2]);
return ;
}
571B
题目大意：给出两个字符串，求有多少种第一个串的拆分出的子串，使之全部包含第二个串。
题解：先用KMP求出匹配的位置，然后$f[i]$表示第$i$位的答案，$g[i]=\sum f[j]$表示前$i$位的答案，也就是$f[i]$的前缀和，转移的时候用$g[i]$前缀和优化。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define P 1000000007
#define MAXN 100010
char a[MAXN],b[MAXN];
int f[MAXN],g[MAXN],sum[MAXN],ok[MAXN],Next[MAXN],N,M;
inline void GetNext()
{
Next[]=;
for (int i=,j=; i<=M; i++)
{
while (j && b[j+]!=b[i]) j=Next[j];
if (b[j+]==b[i]) ++j;
Next[i]=j;
}
}
inline void KMP()
{
for (int i=,j=; i<=N; i++)
{
while (j && b[j+]!=a[i]) j=Next[j];
if (b[j+]==a[i]) ++j;
if (j==M) ok[i]=;
}
}
int main()
{
scanf("%s%s",a+,b+); N=strlen(a+),M=strlen(b+);
GetNext();
KMP();
// for (int i=1; i<=M; i++) printf("%d ",Next[i]); puts("");
for (int i=; i<=N; i++)
if (!ok[i])
f[i]=f[i-],g[i]=(g[i-]+f[i])%P,sum[i]=(sum[i-]+g[i])%P;
else
f[i]=sum[i-M]+i-M+,g[i]=(g[i-]+f[i])%P,sum[i]=(sum[i-]+g[i])%P;
printf("%d\n",g[N]);
return ;
}
494B
Codeforces-335B
题目大意：给出一个字符串长度为$5*10^{4}$，求这个如果这个字符串存在长度恰好为100的回文子串，则输出，否则输出最长回文子串。
题解：很容易想到区间dp，但是复杂度是$O(N^{2})$的，显然不行，那么利用鸽巢原理，当字符串长度$>=2600$时，显然至少有一种字符数量是$>=100$的，所以可以直接输出100个这个字符。
所以需要DP的实际是$N<=2600$这样是可以区间dp的，也很简单。要输出方案，开始的想法是利用string直接记录，但是会被卡MLE，所以需要在DP完之后进行一遍dfs统计方案。
值得注意的一点，就算$N<=2600$，也不代表就可以直接dp完输出方案，因为答案也有可能$>100$，所以还是得特别考虑！！！！(这里一开始忽略了）
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
char s[];
string ans[][];
int N,dp[][],a[]; int main()
{
scanf("%s",s+); N=strlen(s+);
if (N>=)
{
for (int i=; i<=N; i++) a[s[i]-'a'+]++;
for (int i=; i<=; i++)
if (a[i]>=)
{for (int j=; j<=; j++) printf("%c",char(i+'a'-)); return ;}
}
for (int i=; i<=N; i++) dp[i][i]=,ans[i][i]=s[i];
for (int len=; len<=N; len++)
for (int l=,r=l+len-; l+len-<=N; l++,r=l+len-)
{
if (s[l]==s[r])
dp[l][r]=dp[l+][r-]+,
ans[l][r]=s[l]+ans[l+][r-]+s[r];
else
dp[l][r]=max(dp[l+][r],dp[l][r-]),
ans[l][r]=dp[l+][r]>dp[l][r-]? ans[l+][r] : ans[l][r-];
if (dp[l][r]==)
{
for (int j=; j<ans[l][r].length(); j++) putchar(ans[l][r][j]);
return ;
}
}
for (int j=; j<ans[][N].length(); j++) putchar(ans[][N][j]);
return ;
}
CF355B(MLE)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string.h>
using namespace std;
char s[],ans[];
int N,dp[][],a[],cnt;
inline void print(int l,int r)
{
if (l>r) return;
if (l==r) {ans[++cnt]=s[l]; return;}
if (s[l]==s[r]) ans[++cnt]=s[l],print(l+,r-),ans[++cnt]=s[r];
else
if (dp[l+][r]>dp[l][r-]) print(l+,r); else print(l,r-);
}
int main()
{
scanf("%s",s+); N=strlen(s+);
if (N>=)
{
for (int i=; i<=N; i++) a[s[i]-'a'+]++;
for (int i=; i<=; i++)
if (a[i]>=)
{for (int j=; j<=; j++) printf("%c",char(i+'a'-)); return ;}
}
for (int i=; i<=N; i++) dp[i][i]=;
for (int len=; len<=N; len++)
for (int l=,r=l+len-; l+len-<=N; l++,r=l+len-)
{
if (s[l]==s[r])
dp[l][r]=dp[l+][r-]+;
else
dp[l][r]=max(dp[l+][r],dp[l][r-]);
if (dp[l][r]==)
{
print(l,r);
for (int i=; i<=cnt; i++) putchar(ans[i]);
return ;
}
}
print(,N);
if (cnt>=)
{
for (int i=; i<=; i++) putchar(ans[i]);
for (int i=; i>=; i--) putchar(ans[i]);
return ;
}
for (int i=; i<=cnt; i++) putchar(ans[i]);
return ;
}
CF355B
Codeforces-721C
题目大意：给出一个N个点M条边的DAG，和一个限制条件T，问从1~N路径长度<=T时最多经过的点数，并输出方案。
题解：很显然是拓扑dp，$dp[i][j]$表示到$i$这个点经过点数为$j$的最短路径长度，拓扑排序时$N^{2}$的暴力转移即可。
记录一下路径，最后答案倒着扫一遍后倒推出方案。
Code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 5010
int N,M,T,ans[MAXN],tot,d[MAXN],dp[MAXN][MAXN],from[MAXN][MAXN];
struct EdgeNode{int next,to,d;}edge[MAXN];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].d=w;}
inline void toposort()
{
queue<int>q;
for (int i=; i<=N; i++) if (!d[i]) q.push(i);
dp[][]=;
while (!q.empty())
{
int now=q.front(); q.pop();
for (int i=head[now]; i; i=edge[i].next)
{
for (int j=; j<=N; j++)
if (dp[now][j-]+edge[i].d<dp[edge[i].to][j])
dp[edge[i].to][j]=dp[now][j-]+edge[i].d,from[edge[i].to][j]=now;
if (!--d[edge[i].to]) q.push(edge[i].to);
}
}
}
int main()
{
N=read(),M=read(),T=read();
for (int i=,x,y,z; i<=M; i++) x=read(),y=read(),z=read(),AddEdge(x,y,z),d[y]++;
memset(dp,,sizeof(dp));
toposort();
for (int i=N; i; i--)
if (dp[N][i]<=T)
{
printf("%d\n",i);
for (int now=N; now; now=from[now][i],i--) ans[++tot]=now;
for (int j=tot; j; j--) printf("%d ",ans[j]);
break;
}
return ;
}
CF721C
Codeforces-212E
题目大意：每个点可以涂两种颜色，满足没有相邻的两个点颜色相同，求最大染色方案时的方案数和两个颜色的数目。
题解：显然最大染色数为N-1，可以枚举每个节点为根，其子树可以组成的答案，利用背包求解。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
inline int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 5050
int N,M,ans,dp[MAXN][MAXN],size[MAXN],ok[MAXN];
struct EdgeNode{int next,to;}edge[MAXN<<];
int head[MAXN],cnt=;
inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}
inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}
inline void DFS(int now,int last)
{
dp[now][]=; size[now]=;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i].to!=last)
{
DFS(edge[i].to,now);
size[now]+=size[edge[i].to];
for (int j=M; j>=; j--)
if (j+size[edge[i].to]<=M)
dp[now][j+size[edge[i].to]]=dp[now][j]? :dp[now][j+size[edge[i].to]];
}
for (int j=M; j>=; j--)
if (j+N-size[now]<=M)
dp[now][j+N-size[now]]=dp[now][j]? :dp[now][j+N-size[now]];
}
int main()
{
N=read(); M=N-;
for (int i=,x,y; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);
DFS(,);
// for (int i=1; i<=N; i++) printf("%d ",size[i]); puts("");
for (int i=; i<=N; i++)
for (int j=; j<=M-; j++)
if (dp[i][j] && !ok[j]) ok[j]=,ans++;
printf("%d\n",ans);
for (int i=; i<=M-; i++) if (ok[i]) printf("%d %d\n",i,M-i);
return ;
}
CF212E