本文章由 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);
}
\/*
*\/
鲁ICP备2025150228号