领导集团问题
考虑对每一个点暴力dpdpdp:fi,jf_{i,j}fi,j表示iii为根的子树选出来的点集最小值不小于jjj的点集元素个数最大值。
那么显然fi,j=∑max{fv,k≥j}+1f_{i,j}=\sum\max\{f_{v,k\ge j}\}+1fi,j=∑max{fv,k≥j}+1
直接上线段树合并来优化就完了。
注意要打懒标记
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=200005,M=8000005;
int n,a[N],rt[N],val[N],sig=0;
vector<int>e[N];
namespace SGT{
int son[M][2],mx[M],add[M],tot=0;
inline void pushup(int p){mx[p]=max(mx[son[p][0]],mx[son[p][1]]);}
inline void pushnow(int p,int v){if(!p)return;mx[p]+=v,add[p]+=v;}
inline void pushdown(int p){
if(!add[p]||!p)return;
pushnow(son[p][0],add[p]),pushnow(son[p][1],add[p]);
add[p]=0;
}
inline void update(int&p,int l,int r,int k,int v){
if(!p)p=++tot;
if(l==r){mx[p]=max(v,mx[p])+1;return;}
pushdown(p);
int mid=l+r>>1;
k<=mid?update(son[p][0],l,mid,k,max(v,mx[son[p][1]])):update(son[p][1],mid+1,r,k,v);
pushup(p);
}
inline int merge(int x,int y,int l,int r,int a,int b){
if(!x||!y)return pushnow(y,a),pushnow(x,b),x+y;
if(l==r)return mx[x]=max(mx[x],a)+max(mx[y],b),x;
pushdown(x),pushdown(y);
int mid=l+r>>1;
son[x][0]=merge(son[x][0],son[y][0],l,mid,max(a,mx[son[x][1]]),max(b,mx[son[y][1]]));
son[x][1]=merge(son[x][1],son[y][1],mid+1,r,a,b);
return pushup(x),x;
}
}
void dfs(int p){
for(ri i=0,v;i<e[p].size();++i)dfs(v=e[p][i]),rt[p]=SGT::merge(rt[p],rt[v],1,sig,0,0);
SGT::update(rt[p],1,sig,a[p],0);
}
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read(),val[++sig]=a[i];
sort(val+1,val+sig+1),sig=unique(val+1,val+sig+1)-val-1;
for(ri i=1;i<=n;++i)a[i]=lower_bound(val+1,val+sig+1,a[i])-val;
for(ri i=2;i<=n;++i)e[read()].push_back(i);
dfs(1);
cout<<SGT::mx[rt[1]];
return 0;
}
所罗门王的宝藏
考虑O(Tn2)O(Tn^2)O(Tn2)的枚举算法。
我们设cic_ici表示第iii行的增量,lil_ili表示第iii列的增量，如果存在两个点(x,y,w1),(x,z,w2)(x,y,w_1),(x,z,w_2)(x,y,w1),(x,z,w2)，那么ly−lz=w1−w2l_y-l_z=w_1-w_2ly−lz=w1−w2，同理如果存在两个点(x,y,w1),(z,y,w2)(x,y,w_1),(z,y,w_2)(x,y,w1),(z,y,w2)，那么cx−cz=w1−w2c_x-c_z=w_1-w_2cx−cz=w1−w2，这样对于每一个点更新一下任意两列的增量判断是否冲突即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1005;
inline int read(){
int ans=0;
bool f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return f?ans:-ans;
}
int a[N][N],n,m,k,detc[N][N],detl[N][N],X[N],Y[N],C[N];
bool vis[N][N],visc[N][N],visl[N][N];
int main(){
for(ri tt=read();tt;--tt){
n=read(),m=read(),k=read();
for(ri i=1;i<=n;++i)for(ri j=1;j<=m;++j)vis[i][j]=visc[i][j]=visl[i][j]=0;
for(ri i=1,x,y,c,det;i<=k;++i){
x=read(),y=read(),c=read();
X[i]=x,Y[i]=y,C[i]=c;
if(vis[x][y]&&(a[x][y]^c)){puts("No");goto XXX;}
vis[x][y]=1,a[x][y]=c;
for(ri j=1,mn,mx;j<i;++j){
det=c-a[X[j]][Y[j]];
if(Y[i]==Y[j]){
mn=min(X[i],X[j]),mx=max(X[i],X[j]);
if(X[i]>X[j])det*=-1;
if(visc[mn][mx]&&detc[mn][mx]!=det){puts("No");goto XXX;}
visc[mn][mx]=1,detc[mn][mx]=det;
if(X[i]>X[j])det*=-1;
}
if(X[i]==X[j]){
mn=min(Y[i],Y[j]),mx=max(Y[i],Y[j]);
if(Y[i]>Y[j])det*=-1;
if(visl[mn][mx]&&detl[mn][mx]!=det){puts("No");goto XXX;}
visl[mn][mx]=1,detl[mn][mx]=det;
if(Y[i]>Y[j])det*=-1;
}
}
}
puts("Yes");
XXX:;
}
return 0;
}
邮递员问题
咕咕咕