本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-25 12:02:36

A

题意

给定一棵 $n$ 个节点的，带有点权的树（编号从 $1$ 开始），点权可能有负。

你需要求出这棵树的一个连通块，其点权和尽可能大。

你只需要输出那个最大的点权和，保证答案在 $int$ 范围内。

思路

树形DP板子题。类似最大子段和。

不难推出状态转移方程：

$$ f_x= \max(f_x,f_x+f_v)$$

其中，$x$ 为当前节点，$v$ 为 $x$ 的儿子。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>


using namespace std;

#define ll long long


const int N=1e5+5;\/\/注意修改
const int mod=1e9+7;

vector <int> g[N];
int a[N],f[N];

void dfs(int x,int fa){
    f[x]=a[x];
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        if(v==fa) continue ;
        dfs(v,x);
        f[x]=max(f[x],f[x]+f[v]);
    }
}

int main(){
\/\/    freopen(".in","r",stdin);
\/\/    freopen(".out","w",stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    int maxx=0;
    for(int i=1;i<=n;i++){
        maxx=max(maxx,f[i]);
    }
    cout<<maxx;
    return 0;
\/\/    fclose(stdin);
\/\/    fclose(stdout);
}

\/*


 *\/

B

题意

给定一个长度为 $n$ 的序列 $A$ ，你可以进行任意次如下的操作：

选择两个相邻且相等的数字，把它们合并成一个数，合并结果为原数值加一。

求你能得到的最大的数字。

$a_i \le 40 $

$ n \le 262144$

思路

一开始想用区间DP解，可惜数据范围 $n^3$ 搞不了。(听说mx数据贼几把水，$n^3$ 可过)

这道题状态十分的不好想。

设 $f_{i,j}$ 为合并出 $i$ ，左端点为 $j$，右端点的位置。

我们可以利用倍增的思想，请看下图：

又出现了一个问题：我们枚举 $i$ 要枚举到哪个数。首先，$a_i \le 40$,并且 $n \le 2^{18}$，不难发现，$i$ 最大就是 $40+18=58$ 。

所以状态转移方程为：

$$ f_{i,j}=f_{i-1,f_{i-1,j}}$$

时间复杂度：$O(58n)$。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>


using namespace std;

#define ll long long


const int N=5e3+5;\/\/注意修改
const int mod=1e9+7;

vector <int> g[N];
int a[N],f[60][(1<<20)+10],b[N];



int main(){
\/\/    freopen(".in","r",stdin);
\/\/    freopen(".out","w",stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        f[t][i]=i+1;
    }
    int maxx=0;
    for(int i=2;i<=58;i++){
        for(int j=1;j<=n;j++){
             if(f[i][j]==0) f[i][j]=f[i-1][f[i-1][j]];
             if(f[i][j]) maxx=i;
        }
    }
    cout<<maxx;
    return 0;
\/\/    fclose(stdin);
\/\/    fclose(stdout);
}

\/*


 *\/

C

题意

给定一个长度为 $n$ 的序列 $A$ 和一个长度为 $m$ 的序列 $B$ ，求它们的最长公共上升子序列。

你只需要输出该子序列的长度。

思路

板子题。

这道题是最长公共子序列和最长上升子序列的混合体。

设 $f_{i,j}$ 为 $A$ 序列取前 $i$ 个数，$B$ 序列取前 $j$ 个数的最长公共上升子序列的长度。

当 $a_i \ne b_j$ ，$f_{i,j} = f_{i-1,j}$ 。

当 $a_i = b_j$ ，$f_{i,j}= \max(f_{i,j},f_{i-1,k}+1) [1\le k \le j ,b_k<b_j ]$

只有 $b_k<b_j $ 时，序列才是严格上升子序列。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>


using namespace std;

#define int long long


const int N=5e3+5;\/\/注意修改
const int mod=1e9+7;

vector <int> g[N];
int a[N],f[N][N],b[N];



signed main(){
\/\/    freopen(".in","r",stdin);
\/\/    freopen(".out","w",stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int m;
    cin>>m;
    for(int i=1;i<=m;i++) cin>>b[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i]!=b[j]) f[i][j]=f[i-1][j];
            else{
                for(int k=1;k<=j;k++){
                    if(b[k]<b[j]){
                        f[i][j]=max(f[i][j],f[i-1][k]+1);
                    }
                }
            }
        }
    }
    int maxx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            maxx=max(maxx,f[i][j]);
        }
    }
    cout<<maxx;
    return 0;
\/\/    fclose(stdin);
\/\/    fclose(stdout);
}

\/*


 *\/

e

题意

给定一个长度为 $n$ 的序列 $A$，下标从 $1$ 开始。

你需要删掉一些元素，剩余元素相对位置不动，得到一个新序列 $B$，下标同样从 $1$ 开始。

你的目标是最大化新序列中 $B_i=i$ 的数量。

输出这个最大的数量。

思路

设 $f_{i,j}$ 表示以 $i$ 结尾，偏移量为 $j$ 的数量。

不 难列出状态转移方程： $$f_{i,j}= \max(f_{i,j},f_{i-1,j}+(a_i==i-j))$$

我们发现，当 $a_i=i-j$ 时，这个数字刚好能对上，所以可能数要加一。

如果有偏移量，如果我们删去一个数，那么总个数减一，偏移量也减一，这里也要判断一下。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>


using namespace std;

#define int long long


const int N=5e3+5;\/\/注意修改
const int mod=1e9+7;

vector <int> g[N];
int a[N],f[N][N],b[N];\/\/fij表示以i结尾，偏移量为j



signed main(){
\/\/    freopen(".in","r",stdin);
\/\/    freopen(".out","w",stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int maxx=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<n;j++){
            int d=0;
            if(a[i]==i-j) d=1;
            f[i][j]=max(f[i][j],f[i-1][j]+d);
            if(j){
                f[i][j]=max(f[i][j],f[i-1][j-1]);
            }
            maxx=max(maxx,f[i][j]);
        }
    }
    cout<<maxx;
    return 0;
\/\/    fclose(stdin);
\/\/    fclose(stdout);
}

\/*


 *\/

f

题意

给出两个长度为 $n$ 的正整数序列 $a$ 和 $b$

你需要回答 $q$ 次询问，每次给出 $[l,r]$，问进行以下操作的最少次数使得 $\forall i\in [l,r] \,,a_i=b_i$，或报告无解

询问之间互相独立

一次操作定义为选出一个长度为 $k$（$k$ 是偶数）的正整数序列 $pos$，满足 $l\le pos_1<pos_2<\ldots<pos_{k-1}<pos_k\le r$，将 $a_{pos_1},a_{pos_3},\ldots,a_{pos_{k-1}}$ 加一，将 $b_{pos_2},b_{pos_4},\ldots,b_{pos_k}$ 加一。

思路

不难发现，我们这个操作只与 $b_i-a_i$ 有关，与 $a_i$ $b_i$ 本身无关。所以，我们设 $c_i=b_i-a_i$ ，最终要求 $?$ 序列某段区间全为 0 的最小操作次数。

那么，每次操作就是 $l \le p_1 < p_2 < ... < p_{k}$，$c_{p_{2i}}$ 加一， $c_{p_{2i+1}}$ 减一。

不难发现，$ {\textstyle \sum_{i=l}^{r}} c_i$ 为定值，对于 $\forall i \in \left [ l,r \right ] $，无论如何操作，${\textstyle \sum_{j=l}^{i}} c_i$ 都 不会减（若 $r-l+1$ 为奇数，则 ${\textstyle \sum_{j=l}^{i}} c_i$ 会加）。

我们可以把+1看成左括号，-1看做右括号，括号的最大层数就是答案。

换句话说，如果 $ \left [ l,r \right ] $ 是一个合法的括号序列，那么其答案就是其括号层数。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>


using namespace std;

#define int long long
#define ll long long



const int N=1e5+5;\/\/注意修改
const int mod=1e9+7;
inline int read(){
    int re=0;char ch=getchar();
    while(ch>'9'||ch<'0') ch=getchar();
    while(ch>='0'&&ch<='9') re=10*re+ch-'0',ch=getchar();
    return re;
}
int a[N],b[N];
int mx[22][N],mn[22][N];
int s[N];
int n,q;
void init(){
    for(int i=1;i<=n;i++)
        mx[0][i]=mn[0][i]=s[i];
    for(int i=1;i<=19;i++)
        for(int j=1;j+(1<<i)-1<=n;j++){
            mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]),
            mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
        }
    return;
}
ll Max(int l,int r){
    int len=log2(r-l+1);
    return max(mx[len][l],mx[len][r-(1<<len)+1]);
}
ll Min(int l,int r){
    int len=log2(r-l+1);
    return min(mn[len][l],mn[len][r-(1<<len)+1]);
}

signed main(){
\/\/    freopen(".in","r",stdin);
\/\/    freopen(".out","w",stdout);
    
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        a[i]=t-a[i];
    }
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
    init();
    while(q--){
        int l,r;
        cin>>l>>r;
        if(s[r]-s[l-1]!=0||Min(l,r)<s[l-1]) cout<<-1<<endl;
        else{
            cout<<Max(l,r)-s[l-1]<<endl;
        }
    }
    
    return 0;
\/\/    fclose(stdin);
\/\/    fclose(stdout);
}

\/*


 *\/