首页 博客列表 精选博客 智能问答 chat-GPT 关于我
Codeforces 刷水记录
发布日期：2021-08-19 11:09:42 浏览次数：5 分类：技术文章

本文共 45993 字，大约阅读时间需要 153 分钟。

题目大意：给出一个有序数列a,这个数列中每两个数，如果满足一个数能整除另一个数，则这两个数中间是有一条边的，现在有这样的图，求最大联通子图。

题解：并不需要把图搞出来，可以直接dp，$f[i]$表示以第$i$个数为开头的最大的联通子图，转移类似最长上升子序列，$f[i]=max(f[i],f[j]+1)$

Code:

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 1000010int N,a[MAXN],dp[MAXN],ans,id[MAXN];int main(){    N=read();    for (int i=1; i<=N; i++) a[i]=read(),id[a[i]]=i;    for (int i=1; i<=N; i++) dp[i]=1;    for (int i=1,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]+1);    for (int i=1; i<=N; i++) ans=max(ans,dp[i]);    printf("%d\n",ans);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long longinline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define P 1000000007#define MAXN 2001int N,M,K;LL step[MAXN],fac[200010],inv[200010];inline LL qp(LL x,int y){    LL re=1;    for (int i=y; i; i>>=1,x=x*x%P) if (i&1) re=re*x%P;    return re;}inline LL Inv(int x) {
    return qp(x,P-2);}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
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 100010int N;struct TreeNode{
    int x,h;}a[MAXN];int main(){    N=read(); if (N==1) {puts("1"); return 0;}    for (int i=1; i<=N; i++) a[i].x=read(),a[i].h=read();    int ans=2,last=a[1].x;    for (int i=2; i<=N-1; last=max(a[i].x,last),i++)        if (a[i].x-a[i].h>last) ans++;            else if (a[i].x+a[i].h
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}int N,M,B,P,a[510],dp[2][510][510],ans;int main(){    N=read(),M=read(),B=read(),P=read();    for (int i=1; i<=N; i++) a[i]=read();    dp[0][0][0]=1;    for (int i=1; i<=N; i++)        for (int j=0; j<=M; j++)            for (int k=0; k<=B; k++)                dp[i&1][j][k]=( ( (k-a[i]>=0 && j-1>=0) ? dp[i&1][j-1][k-a[i]]:0) +dp[(i-1)&1][j][k])%P;    for (int i=0; i<=B; i++) ans=(ans+dp[N&1][M][i])%P;    printf("%d\n",ans);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int x,y,z;double f[101][101][101],rock,scissor,paper;int main(){    scanf("%d%d%d",&x,&y,&z);    f[x][y][z]=1;    for (int i=x; i>=1; i--)        for (int j=y; j>=1; j--)            for (int k=z; k>=1; k--)                f[i-1][j][k]+=(double)i*k/(i*j+i*k+k*j)*f[i][j][k],                f[i][j-1][k]+=(double)i*j/(i*j+i*k+k*j)*f[i][j][k],                f[i][j][k-1]+=(double)k*j/(i*j+i*k+k*j)*f[i][j][k];    for (int i=1; i<=x; i++)        for (int j=0; j<=y; j++)            rock+=f[i][j][0];    for (int i=1; i<=y; i++)        for (int j=0; j<=z; j++)            scissor+=f[0][i][j];    for (int i=1; i<=x; i++)        for (int j=0; j<=z; j++)            paper+=f[i][0][j];    printf("%.10lf %.10lf %.10lf\n",rock,scissor,paper);    return 0;}
540D

 

 

题目大意：给出一个N个数的环，每次给出一个b，对这个环分段，每段必须相邻，且每段的和$<=b$，求最小段数。

题解：首先展环为链，然后处理。首先，尽可能的多取，一定比少取要优。定义$st[i]$表示以$i$位置为最后的方案的开始点，$cnt[i]$表示以$i$位置为最后的方案的方案数。

然后就可以dp..扫一遍环，得到前一段的末尾$j$就可转移$$st[i]=st[j],cnt[i]=cnt[j]+1$$

Code:

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long longinline LL read(){    LL x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 1000100int N,Q,a[MAXN<<1],st[MAXN<<1],cnt[MAXN<<1];LL sum[MAXN<<1];int main(){    N=read(),Q=read();    for (int i=1; i<=N; i++) a[i]=a[i+N]=read(),st[i]=i;    for (int i=1; i<=2*N; i++) sum[i]=sum[i-1]+a[i];    while (Q--)        {            LL b=read();            for (int j=1,i=N+1; i<=N*2; i++)                {                    while (sum[i]-sum[j]>b) j++;                    st[i]=st[j];                    cnt[i]=cnt[j]+1;                    if (i-st[i]>=N) {printf("%d\n",cnt[i]); break;}                }        }    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long longinline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 200010 int N,p[MAXN],a[MAXN];struct EdgeNode{
    int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;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==-1) return; AddEdge(u,v); AddEdge(v,u);}LL dp[2][MAXN];#define INF 0x7fffffff inline void DFS(int now){    dp[1][now]=-INF,dp[0][now]=0;    for (int i=head[now]; i; i=edge[i].next)        if (edge[i].to!=p[now])            {                DFS(edge[i].to);                LL dp1=dp[1][now],dp0=dp[0][now];                dp[1][now]=max(dp0+dp[1][edge[i].to],dp1+dp[0][edge[i].to]);                dp[0][now]=max(dp0+dp[0][edge[i].to],dp1+dp[1][edge[i].to]);            }    dp[1][now]=max(dp[1][now],dp[0][now]+a[now]);}int main(){    N=read();    for (int i=1; i<=N; i++) p[i]=read(),a[i]=read(),InsertEdge(p[i],i);    DFS(1);    printf("%I64d\n",max(dp[0][1],dp[1][1]));    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;int n,t;double p,dp[2010][2010];int main(){    scanf("%d%lf%d",&n,&p,&t);    dp[0][0]=1.0;    for (int i=1; i<=t; i++)        for (int j=0; j<=n; j++)            {                if (j==0) {dp[i][j]=(1.0-p)*dp[i-1][j]; continue;}                if (j==n) {dp[i][j]=p*dp[i-1][j-1]+dp[i-1][j]; continue;}                dp[i][j]+=p*dp[i-1][j-1]+(1.0-p)*dp[i-1][j];            }    double ans=0;    for (int i=1; i<=n; i++) ans+=dp[t][i]*i;    printf("%.7lf\n",ans);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 200010int N,val[MAXN];struct PointNode {
    int x,w;}p[MAXN];inline bool cmp(PointNode A,PointNode B) {
    return A.x+A.w
           
            >1; Build(ls,l,mid); Build(rs,mid+1,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)>>1; 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
            
             =r) return tree[now].maxx; int mid=(l+r)>>1,re=0; 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=1; i<=N; i++) p[i].x=read(),p[i].w=read(),val[i]=p[i].x+p[i].w; sort(p+1,p+N+1,cmp); sort(val+1,val+N+1); Build(1,1,N); for (int i=1,j; i<=N; i++) j=upper_bound(val+1,val+N+1,p[i].x-p[i].w)-val -1, Modify(1,i,Query(1,1,j)+1); printf("%d\n",tree[1].maxx); return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           using namespace std;#define LL long longint N,K,a[30],Mx;LL S,fac[30],ans;map
            
             cnt[30];inline void back(int now,int k,LL sum){ if (sum<0) return; if (now==N/2) {cnt[k][sum]++; return;} if (a[now]<=Mx && k) back(now-1,k-1,sum-fac[ a[now] ]);//变后再选 back(now-1,k,sum-a[now]);//直接选 back(now-1,k,sum); //不选 }inline void front(int now,int k,LL sum){ if (sum>S) return; if (now==N/2+1) { for (int i=k; i<=K; i++) ans+=cnt[i][sum]; return;} if (a[now]<=Mx && k
             
              S) {Mx=i-1; break;} for (int i=1; i<=N; i++) scanf("%d",&a[i]); sort(a+1,a+N+1); back(N,K,S); front(1,0,0); printf("%I64d\n",ans); return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 200010int N;struct EdgeNode{
    int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;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[2][MAXN],tot;#define INF 0x7fffffffinline void DFS(int now,int last,int opt){    bool flag=0;    for (int i=head[now]; i; i=edge[i].next)        if (edge[i].to!=last)            {                flag=1;                DFS(edge[i].to,now,opt^1);                if (opt)                     f[1][now]+=f[0][edge[i].to];                else                     f[0][now]=min(f[0][now],f[1][edge[i].to]);            }                if (!flag) f[0][now]=f[1][now]=1,tot++;}int main(){    N=read();    for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);    memset(f[0],127,sizeof(f[0])); memset(f[1],0,sizeof(f[1]));    DFS(1,0,0);    DFS(1,0,1);    printf("%d %d\n",tot/2-f[0][1]+1,f[1][1]);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long long#define P 1000000007int N,a[510],f[510][510];int main(){    scanf("%d",&N);    for (int i=1; i<=N; i++) scanf("%d",&a[i]);    for (int i=1; i<=N; i++) f[i][i]=1;    for (int len=2,l,r; len<=N; len++)        for (int i=1; i+len-1<=N; i++)            {                l=i,r=l+len-1;                for (int k=l+1; k<=r; k++)                    if (k==r || a[l+1]
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long longinline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; 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<<2];    #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=0;        if (l==r) {tree[now].minx=h[l]; return;}        int mid=(l+r)>>1;        Build(ls,l,mid); Build(rs,mid+1,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=0;        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+=1; tree[now].minx+=1; return;}        int mid=(l+r)>>1;        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)>>1; 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=1; i<=N; i++) h[i]=read();    SegmentTree::Build(1,0,N+1);    for (int i=1; i<=N; i++) SegmentTree::Modify(1,0,i-1),pre[i]=SegmentTree::Query(1,0,i);    SegmentTree::Build(1,0,N+1);    for (int i=N; i>=1; i--) SegmentTree::Modify(1,i+1,N+1),suf[i]=SegmentTree::Query(1,i,N+1);//    for (int i=1; i<=N; i++) printf("%d  %d\n",pre[i],suf[i]);    for (int i=1; i<=N; i++) ans=max(ans,min(pre[i],suf[i]));    printf("%I64d\n",ans);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define P 100000000int N,M,K1,K2,dp[101][101][2];int main(){    scanf("%d%d%d%d",&N,&M,&K1,&K2);    for (int i=1; i<=K1; i++) dp[i][0][0]=1;    for (int i=1; i<=K2; i++) dp[0][i][1]=1;    for (int i=1; i<=N; i++)        for (int j=1; j<=M; j++)            {                for (int k1=1; k1<=K1 && k1<=i; k1++) (dp[i][j][0]+=dp[i-k1][j][1])%=P;                for (int k2=1; k2<=K2 && k2<=j; k2++) (dp[i][j][1]+=dp[i][j-k2][0])%=P;            }    printf("%d\n",(dp[N][M][0]+dp[N][M][1])%P);    return 0;}
118D

 

 

题目大意：给出N个物品，每个物品有w,h两种权值，给出一个初始的w,h，求用给定的N个物品组成 最长的 以给出的初始为开头的 严格上升的序列，输出一种可行解。 物品的比较满足二维偏序。

题解：二维偏序显然可以排序乱搞...先排序，然后dp； $$dp[i]=max(dp[j]+1,dp[i]) \qquad a_{j}<a_{i}$$ 输出可行解，就在转移的时候记录从哪一个转移过来，最后倒叙统计一下并输出即可。

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 5001int 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
           
            
             w && a[i].h>h) { for (int j=0; j<=i-1; j++) if (a[j].w
             
              =1; i--) printf("%d ",Ans[i]); puts(""); return 0;}
4D

 

 

题目大意：给出一个树，树上边的长度为1，求有多少无序点对，满足距离恰好为K。

题解：可以直接树形dp得到，设状态$dp[x][k]$表示到第$x$个节点距离恰好为$k$的点数，转移很显然$$dp[x][k]=\sum _{y=son} dp[y][k-1]$$ 可以在dp的过程中统计答案，注意要开longlong

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long longinline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 50010int N,K;LL ans,dp[MAXN][501];struct EdgeNode{
    int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;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][0]=1;    for (int i=head[now]; i; i=edge[i].next)        if (edge[i].to!=last)            {                DFS(edge[i].to,now);                for (int k=0; k<=K-1; k++) ans+=(LL)dp[now][K-k-1]*dp[edge[i].to][k];                for (int k=1; k<=K; k++) dp[now][k]+=dp[edge[i].to][k-1];            }}int main(){    N=read(),K=read();    for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);    DFS(1,0);    printf("%I64d\n",ans);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 1010int N,M,a[MAXN][MAXN],dp[4][MAXN][MAXN],ans;int main(){    N=read(),M=read();    for (int i=1; i<=N; i++)        for (int j=1; j<=M; j++) a[i][j]=read();    for (int i=1; i<=N; i++)        for (int j=1; j<=M; j++)            dp[0][i][j]=max(dp[0][i-1][j],dp[0][i][j-1])+a[i][j];    for (int i=N; i>=1; i--)        for (int j=M; j>=1; j--)            dp[1][i][j]=max(dp[1][i+1][j],dp[1][i][j+1])+a[i][j];    for (int i=N; i>=1; i--)        for (int j=1; j<=M; j++)            dp[2][i][j]=max(dp[2][i+1][j],dp[2][i][j-1])+a[i][j];    for (int i=1; i<=N; i++)        for (int j=M; j>=1; j--)            dp[3][i][j]=max(dp[3][i-1][j],dp[3][i][j+1])+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=2; i<=N-1; i++)        for (int j=2; j<=M-1; j++)            ans=max(ans , max( dp[0][i-1][j]+dp[1][i+1][j]+dp[2][i][j-1]+dp[3][i][j+1],                               dp[0][i][j-1]+dp[1][i][j+1]+dp[2][i+1][j]+dp[3][i-1][j]) );    printf("%d\n",ans);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 510int N,a[MAXN],dp[MAXN][MAXN];int main(){    N=read();    for (int i=1; i<=N; i++) a[i]=read();    memset(dp,127,sizeof(dp));    for (int i=1; i<=N; i++) dp[i][i]=1;    for (int len=2; len<=N; len++)        for (int i=1; i+len-1<=N; i++)            {                int l=i,r=l+len-1;                for (int k=l; k<=r; k++)                    dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);                if (a[l]==a[r]) dp[l][r]=min(dp[l][r], l+1>r-1? 1:dp[l+1][r-1]);            }    printf("%d\n",dp[1][N]);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long long#define P 1000000007inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 1010char s[MAXN];int N,pa[MAXN],st[MAXN],tp,f[MAXN][MAXN][3][3],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 0;    if (r-l+1==2)         if ((x && !y) || (!x && y)) return f[l][r][x][y]=1;            else return f[l][r][x][y]=0;    //这里是一个特判相邻的两个正好匹配，显然情况就4种且方案数都为1     LL tmp=0;    if (pa[l]==r)//这里是处理l，r正好匹配的时候         if ((x && !y) || (!x && y))//这是在保证匹配的时候xy颜色合法             for (int xx=0; xx<=2; xx++)                for (int yy=0; yy<=2; yy++)                    if (!(x && xx && xx==x) && !(y && yy && yy==y))                         tmp=(tmp+dp(l+1,r-1,xx,yy))%P;                    else;        else return f[l][r][x][y]=0;    else //这里是处理l，r不匹配的时候，区间断开统计的情况         for (int xx=0; xx<=2; xx++)            for (int yy=0; yy<=2; yy++)                if (!(xx==yy && xx))                     tmp=(tmp+(LL)dp(l,pa[l],x,xx)*dp(pa[l]+1,r,yy,y)%P)%P;    return f[l][r][x][y]=tmp;}int main(){    scanf("%s",s+1); N=strlen(s+1);    for (int i=1; i<=N; i++)        if (s[i]=='(') st[++tp]=i;            else pa[i]=st[tp--];    for (int i=1; i<=N; i++)         if (pa[i]) pa[ pa[i] ]=i;//    for (int i=1; i<=N; i++) printf("%d   ",pa[i]); puts("");    memset(f,-1,sizeof(f));    for (int x=0; x<=2; x++)        for (int y=0; y<=2; y++)            ans=(ans+dp(1,N,x,y))%P;    printf("%d\n",ans);    return 0;}
149D

 

 

题目大意：给出一棵单向边组成的“树”，求出用最小的操作使得令一个点为根时，这个点能到达其余所有点，每次操作是将一条边反向，并输出可行的点。

题解：这个题刚上来觉得有些蛋疼，想的仅仅是单向连边然后从每个点拓展，记录一下答案，然后再整个跑一下统计答案，感觉求出最小操作数是可以的，但是没法所有最小操作数可行的点。

但启发了思路，其实这题很简单，正常的连边，记录一下边的正反，树形dp两遍。

第一遍是强行以1为根，$f[x]$表示以$x$为根的子树在以1为根的情况下需要反转边几次，这个随意搞搞就出来了，得到了$f[]$之后，再进行一遍树形dp就可以得到以各点为整棵树根的答案，然后就可以了。

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 200010int N;struct EdgeNode{
    int next,to,opt;}edge[MAXN<<1];int cnt=1,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,1); AddEdge(v,u,0);}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]? 0:1);}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]? 1:-1),DFS_2(edge[i].to,now);}int main(){    N=read();    for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);    DFS_1(1,0);    DFS_2(1,0);    int ans=0x7fffffff;    for (int i=1; i<=N; i++) ans=min(ans,f[i]);    printf("%d\n",ans);    for (int i=1; i<=N; i++) if (f[i]==ans) printf("%d ",i);    return 0;    }
219D

 

 

题目大意：给出N个字符串，两个人进行K轮游戏，每个人每次添加一个字符，要求组成的字串为给出字符串中任意串的前缀，交替进行，直到不能放符合条件的字符为败，上一轮游戏的败者为下轮的先手，整个过程的胜者，定义为第K局结束的胜者。

题解：这题真的有点蛋疼..又把博弈和树结合起来。

根据题目中游戏的定义，肯定先会联想到Trie树，就转换成两个人在Trie树上博弈，因为树的形态是一定的，所以先手和后手的每种状态的结局也是确定不变的，所以可以进行树形dp求得；

首先Trie树的叶节点深度显然先手必胜/必败，然后可以统计出每个非叶节点是否存在必胜、必败子节点。

这个博弈是最标准的博弈，先手必胜当子节点中存在必胜态，后手必胜当所有子节点全是必胜态，这样dp一遍就能得到所有节点的状态；

然后讨论答案：

1.如果初始的先手玩家存在必胜套路同时也存在失败套路，显然他可以一直输，最后一局翻盘；

2.如果初始玩家先手没有必胜套路，也就是说后手玩家一定存在至少一种方法可以令先手必败，这样先手一定一直输；

3.如果先手玩家只有必胜套路，怎么都不会输，那么整个过程的胜者就取决于K轮数的奇偶了；

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define MAXN 100010int N,K;char s[MAXN];int son[MAXN][27],sz=1;inline void Insert(char str[]){    int now=1,len=strlen(str+1);    for (int i=1; i<=len; i++)        if (son[now][str[i]-'a'+1]) now=son[now][str[i]-'a'+1];            else son[now][str[i]-'a'+1]=++sz,now=sz;}int tree[MAXN][2];inline void DFS(int now,int opt){    bool w=opt^1,f=opt^1,flag=0;    for (int i=1; i<=26; i++)        if (son[now][i])            {                flag=1;                DFS(son[now][i],opt^1);                if (opt) w=w||tree[son[now][i]][0],f=f||tree[son[now][i]][1];                    else w=w&&tree[son[now][i]][0],f=f&&tree[son[now][i]][1];            }    if (flag) tree[now][0]=w,tree[now][1]=f;        else  tree[now][opt]=1,tree[now][opt^1]=0;}int main(){    scanf("%d%d",&N,&K);    for (int i=1; i<=N; i++) scanf("%s",s+1),Insert(s);    DFS(1,1);//    for (int i=1; i<=sz; i++) printf("%d   %d\n",tree[i][0],tree[i][1]);    if (!tree[1][0]) {puts("Second"); return 0;}    if (tree[1][1]) {puts("First"); return 0;}    if (K&1) puts("First"); else puts("Second");    return 0;}
455B

 

 

题目大意：给出N个数，取任意个数，问能否使取得数的和%M恰好为0

题解：这个题还是很水的，可以直接一个01背包水过去，但是复杂度是$O(NM)$的，过不了，然后就得利用鸽巢原理。

就是说，N个数，共有N种前缀和，而%M得到的值，只有M种，所以，根据鸽巢原理，当N>M时，一定有至少两个前缀和%M后得到的值是相同的，所以N>M一定能取到%M=0的情况，所以是必然YES。

剩下的做个背包，复杂度$O(M^{2})$。

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}int N,M,a[1000010];bool dp[1010][1010];inline bool DP(){    dp[0][0]=1;    for (int i=1; i<=N; i++)        for (int j=M-1; j>=0; j--)            if (dp[i-1][((j-a[i])%M+M)%M]) {dp[i][j]=1; if (!j) return 1;}                else if (dp[i-1][j]) dp[i][j]=1;    return 0;}int main(){    N=read(),M=read();    for (int i=1; i<=N; i++) a[i]=read();    if (N>M) return puts("YES"),0;        else return puts(DP()? "YES":"NO"),0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long longinline LL read(){    LL x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 100010int N;struct EdgeNode{
    int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1; 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[2][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[0][now]=max(dp[0][now],dp[0][edge[i].to]);                dp[1][now]=max(dp[1][now],dp[1][edge[i].to]);            }    val[now]=val[now]+dp[0][now]-dp[1][now];    dp[0][now]+= val[now]<0? -val[now]:0;    dp[1][now]+= val[now]>0?  val[now]:0;}int main(){    N=read();    for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);    for (int i=1; i<=N; i++) val[i]=read();    DFS(1,0);//    for (int i=1; i<=N; i++) printf("<%d,%d>\n",dp[0][i],dp[1][i]);    printf("%I64d\n",dp[1][1]+dp[0][1]);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 300010int N,M,Q;struct EdgeNode{
    int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;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=1; 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]+1)/2+(L[fy]+1)/2+1 );        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]+1;                DFS(edge[i].to,now);            }    if (deep[now]>l) l=deep[now],side=now;}inline void GetL(int now){    dfn++; side=now;    l=0; deep[now]=0; DFS(now,0);    l=0; deep[side]=0; DFS(side,0);    L[dfn]=l;}int main(){    N=read(); M=read(); Q=read();    for (int i=1,x,y; i<=M; i++) x=read(),y=read(),InsertEdge(x,y);    for (int i=1; 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 1: x=read(); printf("%d\n",L[ F(belong[x]) ]); break;                    case 2: 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 0;}
455C

 

 

题目大意：给出一棵树，求树中一个联通子图，使得点权最大的点和点权最小的点点权差值不超过d，问有多少种联通子图。

题解：看了数据范围，发现$O(N^{2})$就可以，所以暴力就好，因为是联通子图，所以枚举以每个点为最大/最小的点，并向相邻的点暴力，统计答案即可。

唯一稍微蛋疼一点的，就是如果有权值相同的可能会重复计算，这样限制一下点的序号的就可以了

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define LL long longinline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define P 1000000007#define MAXN 3010struct EdgeNode{
    int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;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 0; dp[now]=1; 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]+1))%P; } return 1;}int main(){ d=read(); N=read(); for (int i=1; i<=N; i++) a[i]=read(); for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y); for (int i=1; i<=N; i++) s=i,DFS(i,0),ans=(ans+dp[i])%P; printf("%d\n",ans); return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 5010char s[MAXN];int Q,N,dp[MAXN][MAXN],ok[MAXN][MAXN],x,y;int main(){    scanf("%s",s+1); N=strlen(s+1);    for (int i=1; i<=N; i++) ok[i][i]=1;    for (int len=2; len<=N; len++)        for (int l=1,r=l+len-1; l+len-1<=N; l++,r=l+len-1)            ok[l][r]=len==2? s[l]==s[r] : s[l]==s[r]&&ok[l+1][r-1];    for (int i=1; i<=N; i++) dp[i][i]=1;    for (int len=2; len<=N; len++)         for (int l=1,r=l+len-1; l+len-1<=N; l++,r=l+len-1)            dp[l][r]=dp[l+1][r]+dp[l][r-1]-dp[l+1][r-1]+ok[l][r];    Q=read();    while (Q--) x=read(),y=read(),printf("%d\n",dp[x][y]);    return 0;}
245H

 

 

题目大意：给出一个序列，可以任意调整序列的顺序，使得给出的式子的值最小

题解：这题有点意思，可以先贪心的，先对整个序列排序，然后对序列“分块”，最后进行一遍dp，求出答案。

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 300010int N,K,a[MAXN],dp[5010][5010];int main(){    N=read(),K=read();    for (int i=1; i<=N; i++) a[i]=read();    sort(a+1,a+N+1);    int sz1=N%K,sz2=K-N%K,len1=N/K+1,len2=N/K;    a[0]=a[1];    for (int i=0; i<=sz1; i++)        for (int j=0,k; j<=sz2; j++)            k=(i-1)*len1+j*len2,            dp[i][j]=max( dp[i][j] , (i? (dp[i-1][j]+a[k+1]-a[k]) : dp[i][j] ) ),            k=i*len1+(j-1)*len2,            dp[i][j]=max( dp[i][j] , (j? (dp[i][j-1]+a[k+1]-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[1]-dp[sz1][sz2]);    return 0;}
571B

 

 

题目大意：给出两个字符串，求有多少种第一个串的拆分出的子串，使之全部包含第二个串。

题解：先用KMP求出匹配的位置，然后$f[i]$表示第$i$位的答案，$g[i]=\sum f[j]$表示前$i$位的答案，也就是$f[i]$的前缀和，转移的时候用$g[i]$前缀和优化。

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define P 1000000007#define MAXN 100010char a[MAXN],b[MAXN];int f[MAXN],g[MAXN],sum[MAXN],ok[MAXN],Next[MAXN],N,M;inline void GetNext(){    Next[1]=0;    for (int i=2,j=0; i<=M; i++)        {            while (j && b[j+1]!=b[i]) j=Next[j];            if (b[j+1]==b[i]) ++j;            Next[i]=j;        }}inline void KMP(){    for (int i=1,j=0; i<=N; i++)        {            while (j && b[j+1]!=a[i]) j=Next[j];            if (b[j+1]==a[i]) ++j;            if (j==M) ok[i]=1;        }}int main(){    scanf("%s%s",a+1,b+1); N=strlen(a+1),M=strlen(b+1);    GetNext();    KMP();//    for (int i=1; i<=M; i++) printf("%d  ",Next[i]); puts("");    for (int i=1; i<=N; i++)        if (!ok[i])            f[i]=f[i-1],g[i]=(g[i-1]+f[i])%P,sum[i]=(sum[i-1]+g[i])%P;        else             f[i]=sum[i-M]+i-M+1,g[i]=(g[i-1]+f[i])%P,sum[i]=(sum[i-1]+g[i])%P;    printf("%d\n",g[N]);    return 0;}
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
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;char s[50010];string ans[2601][2601];int N,dp[2601][2601],a[27];int main(){ scanf("%s",s+1); N=strlen(s+1); if (N>=2600) { for (int i=1; i<=N; i++) a[s[i]-'a'+1]++; for (int i=1; i<=26; i++) if (a[i]>=100) { for (int j=1; j<=100; j++) printf("%c",char(i+'a'-1)); return 0;} } for (int i=1; i<=N; i++) dp[i][i]=1,ans[i][i]=s[i]; for (int len=2; len<=N; len++) for (int l=1,r=l+len-1; l+len-1<=N; l++,r=l+len-1) { if (s[l]==s[r]) dp[l][r]=dp[l+1][r-1]+2, ans[l][r]=s[l]+ans[l+1][r-1]+s[r]; else dp[l][r]=max(dp[l+1][r],dp[l][r-1]), ans[l][r]=dp[l+1][r]>dp[l][r-1]? ans[l+1][r] : ans[l][r-1]; if (dp[l][r]==100) { for (int j=0; j
CF355B(MLE) 
#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;char s[50010],ans[50010];int N,dp[2601][2601],a[27],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+1,r-1),ans[++cnt]=s[r]; else if (dp[l+1][r]>dp[l][r-1]) print(l+1,r); else print(l,r-1);}int main(){ scanf("%s",s+1); N=strlen(s+1); if (N>=2600) { for (int i=1; i<=N; i++) a[s[i]-'a'+1]++; for (int i=1; i<=26; i++) if (a[i]>=100) { for (int j=1; j<=100; j++) printf("%c",char(i+'a'-1)); return 0;} } for (int i=1; i<=N; i++) dp[i][i]=1; for (int len=2; len<=N; len++) for (int l=1,r=l+len-1; l+len-1<=N; l++,r=l+len-1) { if (s[l]==s[r]) dp[l][r]=dp[l+1][r-1]+2; else dp[l][r]=max(dp[l+1][r],dp[l][r-1]); if (dp[l][r]==100) { print(l,r); for (int i=1; i<=cnt; i++) putchar(ans[i]); return 0; } } print(1,N); if (cnt>=100) { for (int i=1; i<=50; i++) putchar(ans[i]); for (int i=50; i>=1; i--) putchar(ans[i]); return 0; } for (int i=1; i<=cnt; i++) putchar(ans[i]); return 0;}
CF355B

 

 

Codeforces-721C

题目大意：给出一个N个点M条边的DAG，和一个限制条件T，问从1~N路径长度<=T时最多经过的点数，并输出方案。

题解：很显然是拓扑dp，$dp[i][j]$表示到$i$这个点经过点数为$j$的最短路径长度，拓扑排序时$N^{2}$的暴力转移即可。

记录一下路径，最后答案倒着扫一遍后倒推出方案。

Code：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}#define MAXN 5010int 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=1;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
            
             q; for (int i=1; i<=N; i++) if (!d[i]) q.push(i); dp[1][1]=0; while (!q.empty()) { int now=q.front(); q.pop(); for (int i=head[now]; i; i=edge[i].next) { for (int j=2; j<=N; j++) if (dp[now][j-1]+edge[i].d
CF721C

 

 

Codeforces-212E

题目大意：每个点可以涂两种颜色，满足没有相邻的两个点颜色相同，求最大染色方案时的方案数和两个颜色的数目。

题解：显然最大染色数为N-1，可以枚举每个节点为根，其子树可以组成的答案，利用背包求解。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
    if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 5050int N,M,ans,dp[MAXN][MAXN],size[MAXN],ok[MAXN];struct EdgeNode{
    int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;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][0]=1; size[now]=1;    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>=0; j--)                    if (j+size[edge[i].to]<=M)                         dp[now][j+size[edge[i].to]]=dp[now][j]? 1:dp[now][j+size[edge[i].to]];            }    for (int j=M; j>=0; j--)        if (j+N-size[now]<=M)            dp[now][j+N-size[now]]=dp[now][j]? 1:dp[now][j+N-size[now]];}int main(){    N=read(); M=N-1;    for (int i=1,x,y; i<=N-1; i++) x=read(),y=read(),InsertEdge(x,y);    DFS(1,0);//    for (int i=1; i<=N; i++) printf("%d  ",size[i]); puts("");    for (int i=1; i<=N; i++)        for (int j=1; j<=M-1; j++)            if (dp[i][j] && !ok[j]) ok[j]=1,ans++;    printf("%d\n",ans);    for (int i=1; i<=M-1; i++) if (ok[i]) printf("%d %d\n",i,M-i);    return 0;}
CF212E

 

 

转载于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/6006438.html

转载地址：https://blog.csdn.net/weixin_30924087/article/details/96936779 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：C#使用Tableadapter进行变量的模糊查询
下一篇：【BZOJ-3996】线性代数 最小割-最大流

发表评论

最新留言

逛到本站，mark一下
[***.202.152.39]2024年03月28日 20时18分47秒

关于作者

    喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！

推荐文章

MediaWiki安装 2019-04-27
Squid安装 2019-04-27
如何查看当前Linux的版本 2019-04-27
Ubuntu安装Nginx 2019-04-27
Ubuntu 下安装thttpd Web服务器 2019-04-27
用thttpd做Web Server 2019-04-27
服务器端开发经验总结 Linux C语言 2019-04-27
将网站程序放在tmpfs下 2019-04-27
使用Nginx的proxy_cache缓存功能取代Squid 2019-04-27
nginx 反向代理，动静态请求分离,proxy_cache缓存及缓存清除 2019-04-27
nginx 的proxy_cache才是王道 2019-04-27
Nginx proxy_cache 使用示例 2019-04-27
Nginx源代码分析 - 日志处理 2019-04-27
使Apache实现gzip压缩 2019-04-27
Memcached在大型网站中应用 2019-04-27
Hadoop简要介绍 2019-04-27
squid中的X-Cache和X-Cache-Lookup的意义 2019-04-27
squid 优化指南 2019-04-27
编程方式刷新Squid缓存服务器的五种方法 2019-04-27
centos vnc配置笔记 2019-04-27
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 307977435 位访客
访问时间: 2024-04-26 05:25:59 访问IP: 18.219.236.199     Copyright © 2020 - 2023 blog.css8.cn 京ICP备2021015314号-1 手机版