2022年六月练习
P5024 [NOIP2018 提高组] 保卫王国
一颗树有 \(n\) 个点 \((1 \le n \le 10^5)\) , 带点权 。
给出 \(m\) 个询问 \((1 \le m \le 10^5)\) ，对于每个询问 ，你需要在树上选若干个点，满足如下条件：
- 树上每一条边所连的两个节点中有至少一个被选中；
- 限制询问相关的两个点必须被选中或不被选中；
要求你回答在满足上述条件的前提下，所选点点权的和的最小值，若无法满足上述条件则输出 \(-1\) 。
第一眼：要是没有条件 2 ，这就是一个骡的极小点覆盖集，再加上有 \(10^5\) 个询问，所以必然要使用倍增（或树剖）预处理。
考虑先不顾条件 2 ，考虑每个子树的根节点是否选的情况，用深搜做一遍子树点权和的DP；（然后就不晓得做了，果断贺 TJ ）
再进行一次深搜，处理出全树点权和减去当前子树点权和（同样也需考虑子树的根节点是否选的情况）
核心：随后处理出 \(ldp[u][g][0/1][0/1]\) ，意为节点 u 与距其 \(2^n\) 的祖先所构成的链与其上的子树的最小权值和（后两个下标为判断链的两端是否被选）
（如图，深搜第一次处理蓝色部分，第二次处理绿色部分，随后预处理链的情况，预计最多需 \(2 \log n\) 条小链构成图中红色的长链）
处理后分别解决每个询问，用 \(LCA\) 计算即可。时间复杂度 \(O(n \log n)\)
总结：这样的水体虽然是码农题，但是写一天实在是太过分了，要提高效率
code
#include
#define ll long long
#define rgi register int
using namespace std;
const int M=1e5+7;
const int inf=1e11+7;
inline int read(){
int w=0,r=1;char c=getchar();
while(!(isdigit(c)||c=='-'))c=getchar();
if(c=='-')r=-1,c=getchar();
while(isdigit(c))w=w*10+c-'0',c=getchar();
return w*r;
}
void gitgud(){
int ans=0;
for(int i=1;i<=100;i++)ans++;
}
int n,m,p[M],tim;
int head[M],tot;
struct edge{
int pre,to;
}line[M*2];
struct qst{
int u1,s1,u2,s2;
}q[M];
void add(int fr,int tr){
line[++tot].pre=head[fr];
head[fr]=tot;
line[tot].to=tr;
}
int up[18][M],depp[M];
int dp[2][M];
int ddp[2][M],ldp[18][M][2][2];
//up:2^n辈祖先 dp:子树节点选不选费用 ddp:全树减子树节点选不选费用 ldp:链两端(包含链旁的子树)节点选不选费用（题解思路）
void dfs(int u,int fa){
dp[1][u]=p[u];
up[0][u]=fa;
depp[u]=depp[fa]+1;
for(int i=head[u];i;i=line[i].pre){
int kid=line[i].to;
if(kid==fa)continue;
dfs(kid,u);
dp[0][u]+=dp[1][kid];
dp[1][u]+=min(dp[0][kid],dp[1][kid]);
}
// printf("*%d %d %d %d\n",u,fa,dp[0][u],dp[1][u]);
}
void dfs2(int u,int fa){
for(int i=head[u];i;i=line[i].pre){
int kid=line[i].to;
if(kid==fa)continue;
ddp[0][kid]=ddp[1][u]+dp[1][u]-min(dp[0][kid],dp[1][kid]);
ddp[1][kid]=min(ddp[0][u]+dp[0][u]-dp[1][kid],ddp[0][kid]);
dfs2(kid,u);
}
}
void preLCA(){
for(int i=2;i<=n;i++){
ldp[0][i][0][0]=inf;
ldp[0][i][0][1]=dp[0][up[0][i]]-dp[1][i];
ldp[0][i][1][0]=dp[1][up[0][i]]-min(dp[0][i],dp[1][i]);
ldp[0][i][1][1]=ldp[0][i][1][0];
// printf("***ldp[0][%d][0][0]=%lld ldp[0][%d][0][1]=%lld ldp[0][%d][1][0]=%lld ldp[0][%d][1][1]=%lld\n",i,ldp[0][i][0][0],i,ldp[0][i][0][1],i,ldp[0][i][1][0],i,ldp[0][i][1][1]);
}
for(int i=1;i<18;i++){
for(int j=2;j<=n;j++){
up[i][j]=up[i-1][up[i-1][j]];
ldp[i][j][0][0]=min(ldp[i-1][up[i-1][j]][0][1]+ldp[i-1][j][1][0],ldp[i-1][up[i-1][j]][0][0]+ldp[i-1][j][0][0]);
ldp[i][j][0][1]=min(ldp[i-1][up[i-1][j]][0][1]+ldp[i-1][j][1][1],ldp[i-1][up[i-1][j]][0][0]+ldp[i-1][j][0][1]);
ldp[i][j][1][0]=min(ldp[i-1][up[i-1][j]][1][1]+ldp[i-1][j][1][0],ldp[i-1][up[i-1][j]][1][0]+ldp[i-1][j][0][0]);
ldp[i][j][1][1]=min(ldp[i-1][up[i-1][j]][1][1]+ldp[i-1][j][1][1],ldp[i-1][up[i-1][j]][1][0]+ldp[i-1][j][0][1]);
}
}
}
ll num1[2],num2[2],sta1[2],sta2[2];
ll LCA(int u1,int u2,int s1,int s2){
num1[0]=num1[1]=num2[0]=num2[1]=inf;
sta1[0]=sta1[1]=sta2[0]=sta2[1]=0;
if(depp[u1]>depp[u2])swap(u1,u2),swap(s1,s2);
num1[s1]=dp[s1][u1],num2[s2]=dp[s2][u2];
// printf("st:%d %d %d %d %lld %lld\n",u1,s1,u2,s2,num1[s1],num2[s2]);
for(int i=17;i>=0;i--){
if(depp[up[i][u2]]>=depp[u1]){
sta2[0]=min(ldp[i][u2][0][0]+num2[0],ldp[i][u2][0][1]+num2[1]);
sta2[1]=min(ldp[i][u2][1][0]+num2[0],ldp[i][u2][1][1]+num2[1]);
num2[0]=sta2[0],num2[1]=sta2[1];
u2=up[i][u2];
}
}
if(u1==u2)return ddp[s1][u1]+num2[s1];
for(int i=17;i>=0;i--)
if(up[i][u2]!=up[i][u1]){
sta1[0]=min(ldp[i][u1][0][0]+num1[0],ldp[i][u1][0][1]+num1[1]);
sta1[1]=min(ldp[i][u1][1][0]+num1[0],ldp[i][u1][1][1]+num1[1]);
num1[0]=sta1[0],num1[1]=sta1[1];
sta2[0]=min(ldp[i][u2][0][0]+num2[0],ldp[i][u2][0][1]+num2[1]);
sta2[1]=min(ldp[i][u2][1][0]+num2[0],ldp[i][u2][1][1]+num2[1]);
num2[0]=sta2[0],num2[1]=sta2[1];
u1=up[i][u1],u2=up[i][u2];
}
// printf("st:%d %d %d %d %lld %lld\n",u1,s1,u2,s2,num1[s1],num2[s2]);
int lca=up[0][u1];
int an1=dp[0][lca]-dp[1][u1]-dp[1][u2]+num1[1]+num2[1]+ddp[0][lca];
int an2=dp[1][lca]-min(dp[0][u1],dp[1][u1])+min(num1[0],num1[1])-min(dp[0][u2],dp[1][u2])+min(num2[0],num2[1])+ddp[1][lca];
// printf("ed:%d %d %d %lld %lld %lld %lld %lld %lld\n",lca,u1,u2,an1,an2,num1[0],num1[1],num2[0],num2[1]);
return max(an1,an2);
}
int main(){
// freopen("text.in","r",stdin);
// freopen("text.out","w",stdout);
n=read(),m=read(),read();
for(int i=1;i<=n;i++)p[i]=read();
for(int i=1;i=inf)?-1:anss);
}
return 0;
}
/*
5 3 C3
2 4 1 3 9
1 5
5 2
5 3
3 4
1 0 3 0
2 1 3 1
1 0 5 0
别想直接复制
*/
「SNOI2017」炸弹
按照中的思路，复杂度为 \(O(n)\) 。
code
#include
#define ll long long
#define rgi register int
using namespace std;
const int M=5e5+7,inf=1e9+7,modd=1e9+7;
inline ll read(){
ll w=0,r=1;char c=getchar();
while(!(isdigit(c)||c=='-'))c=getchar();
if(c=='-')r=-1,c=getchar();
while(isdigit(c))w=w*10+c-'0',c=getchar();
return w*r;
}
void gitgud(){
int ans=0;
for(int i=1;i<=100;i++)ans++;
}
ll n,x[M],r[M],bl[M],br[M];
int main(){
gitgud();
n=read();
for(int i=1;i<=n;i++){
x[i]=read(),r[i]=read();
bl[i]=br[i]=i;
}
for(int i=2;i<=n;i++)while(bl[i]!=1&&x[i]-x[bl[i]-1]<=r[i]){
r[i]=max(r[i],x[bl[i]-1]+r[bl[i]-1]-x[i]);
bl[i]=bl[bl[i]-1];
}
for(int i=n-1;i;i--)while(br[i]!=n&&x[br[i]+1]-x[i]<=r[i]){
bl[i]=min(bl[i],bl[br[i]+1]);
br[i]=br[br[i]+1];
}
// for(int i=1;i<=n;i++)printf("**%lld %lld\n",bl[i],br[i]);
ll ans=0;
for(int i=1;i<=n;i++)ans=(ans+(ll)i*(br[i]-bl[i]+1)%modd)%modd;
printf("%lld\n",ans);
return 0;
}
/*
4
1 1
5 1
6 5
15 15
*/
P6794 [SNOI2020] 水池
同上。
code