T1 倒水
source：瞎编的，个人感觉难度。
直觉告诉我，这个过程应该是这样的：
定义操作5为：操作（1,2,4）若干次，然后此时的水都倒进桶里。
那么应该是：操作5执行若干次，然后再执行若干次，把此时一部分水倒进桶里。
对拍之后发现是对的。
于是我们定义表示最少几次，能让三个杯子恰好凑够的水，且都倒进了桶里，表示最少几次，我能让三个杯子中一部分水恰好是，且都倒进了桶里。
显然随时可以用，只有最后一次可以用。
那么我们就可以开心dp了，没有细节。
复杂度。
#include<bits/stdc++.h>
#define maxn 105*105*105
#define ll long long
using namespace std;
int x,y,z,mx;
int qx[maxn],qy[maxn],qz[maxn],cost[maxn],cost2[maxn],ans[maxn];
int head,tail;
int dis[102][102][102];
int dp[maxn];
void ins(int x,int y,int z,int d)
{
if (dis[x][y][z]!=-1) return;
dis[x][y][z]=d;
tail++; qx[tail]=x; qy[tail]=y; qz[tail]=z;
}
void check(int x,int d)
{
if (cost2[x]==-1) cost2[x]=d;
cost2[x]=min(cost2[x],d);
}
int main()
{
cin>>x>>y>>z>>mx;
head=1,tail=0;
memset(dis,-1,sizeof(dis));
memset(cost,-1,sizeof(cost));
memset(cost2,-1,sizeof(cost2));
ins(0,0,0,0);
while (head<=tail)
{
int X=qx[head],Y=qy[head],Z=qz[head],d=dis[X][Y][Z]; head++;
//倒干净
if (cost[X+Y+Z]==-1) cost[X+Y+Z]=d+(X!=0)+(Y!=0)+(Z!=0);
cost[X+Y+Z]=min(cost[X+Y+Z],d+(X!=0)+(Y!=0)+(Z!=0));
//只是倒出去一部分
check(X,d+1); check(Y,d+1); check(Z,d+1); check(X+Y,d+2); check(X+Z,d+2); check(Y+Z,d+2);
ins(x,Y,Z,d+1); ins(X,y,Z,d+1); ins(X,Y,z,d+1);
ins(0,Y,Z,d+1); ins(X,0,Z,d+1); ins(X,Y,0,d+1);
int tt;
tt=min(X,y-Y); ins(X-tt,Y+tt,Z,d+1);
tt=min(X,z-Z); ins(X-tt,Y,Z+tt,d+1);
tt=min(Y,x-X); ins(X+tt,Y-tt,Z,d+1);
tt=min(Y,z-Z); ins(X,Y-tt,Z+tt,d+1);
tt=min(Z,x-X); ins(X+tt,Y,Z-tt,d+1);
tt=min(Z,y-Y); ins(X,Y+tt,Z-tt,d+1);
}
memset(dp,-1,sizeof(dp));
memset(ans,-1,sizeof(ans));
dp[0]=0;
for (int i=0;i<mx;i++)
if (dp[i]!=-1)
{
for (int j=1;j<=x+y+z;j++)
if (cost[j]!=-1 && i+j<=mx)
{
if (dp[i+j]==-1) dp[i+j]=dp[i]+cost[j];
dp[i+j]=min(dp[i+j],dp[i]+cost[j]);
//倒一次
if (ans[i+j]==-1) ans[i+j]=dp[i]+cost[j];
ans[i+j]=min(ans[i+j],dp[i]+cost[j]);
}
for (int j=1;j<=x+y+z;j++)
if (cost2[j]!=-1 && i+j<=mx)
{
//倒一部分
if (ans[i+j]==-1) ans[i+j]=dp[i]+cost2[j];
ans[i+j]=min(ans[i+j],dp[i]+cost2[j]);
}
}
for (int i=1;i<=mx;i++) cout<<ans[i]<<" "; cout<<endl;
}
T2 联通
SOURCE：CF1706E
部分分做法略。这题简单死了。
第一种做法就是重构树了。
我们根据操作时间建立一棵重构树，在重构树上求出和最早连通的时间。
那么，对于每次询问，答案就是。
其实我想让大家练练整体二分的。
我们也可以通过整体二分来求。
一个超级好写的方式是，我们动态开点建一棵线段树，每个节点存当前答案在的询问有哪些。
然后直接跑遍模拟，每一遍模拟的过程中，一旦合并到询问对应的一半的时候，就把所有询问算一下，看看应该往左丢还是往右丢就行。
复杂度多一个，但是不是每道题都会多这个的。
需要注意的一个细节是，你不能递归建树，只能bfs的形式来建树，因为这样你编号的顺序才是按层数编号。
#include<bits/stdc++.h>
#define maxn 200005
#define ll long long
using namespace std;
int n,m,q;
int x[maxn],y[maxn],qx[maxn],qy[maxn];
int l[maxn<<2],r[maxn<<2],lson[maxn<<2],rson[maxn<<2],mid[maxn<<2],ans[maxn];
basic_string<int> query[maxn<<2];
int fa[maxn];
int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y) {x=find(x); y=find(y); if (x==y) return; fa[x]=y;}
int zd[maxn<<2];
#define LS (now<<1)
#define RS ((now<<1)|1)
#define MID ((l+r)>>1)
void build(int now,int l,int r)
{
if (l==r) {zd[now]=ans[l]; return;}
build(LS,l,MID); build(RS,MID+1,r);
zd[now]=max(zd[LS],zd[RS]);
}
int get(int now,int l,int r,int L,int R)
{
if (L>R) return 0;
if (L<=l && r<=R) return zd[now];
int ret=0;
if (L<=MID) ret=max(ret,get(LS,l,MID,L,R));
if (MID+1<=R) ret=max(ret,get(RS,MID+1,r,L,R));
return ret;
}
void work()
{
cin>>n>>m>>q;
for (int i=1;i<=m;i++) cin>>x[i]>>y[i];
for (int i=1;i<=q;i++) cin>>qx[i]>>qy[i];
l[1]=1; r[1]=m; mid[1]=(1+m)>>1;
int now=1,tot=1;
while (now<=tot)
{
if (l[now]==r[now]) {now++; continue;}
int ls=++tot,rs=++tot;
lson[now]=ls; rson[now]=rs;
l[ls]=l[now]; r[ls]=mid[now]; mid[ls]=(l[ls]+r[ls])>>1;
l[rs]=mid[now]+1; r[rs]=r[now]; mid[rs]=(l[rs]+r[rs])>>1;
now++;
}
for (int i=1;i<n;i++) query[1]+=i;
now=1;
while (now<=tot)
{
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=m;i++)
{
merge(x[i],y[i]);
if (i==mid[now])
{
if (l[now]!=r[now])
for (int id:query[now])
if (find(id)==find(id+1)) query[lson[now]]+=id;
else query[rson[now]]+=id;
else
for (int id:query[now]) ans[id]=mid[now];
now++;
}
}
}
build(1,1,n-1);
for (int i=1;i<=q;i++) cout<<get(1,1,n-1,qx[i],qy[i]-1)<<" "; cout<<endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
work();
}
T3 通信网络
对于一个部分分做法，我们只需要枚举每个点作为中继点，然后二分答案，一下每棵子树，看看子树内有多少个在范围内的点即可。
这个查询过程显然可以通过按dfs序建立的主席树来加速，可以做到两个。
一个的做法也很明显：我们直接把这个点当根的时候，对应的所有主席树都拿出来，然后从这些主席树的根节点处同时二分，这样复杂度就只有一个了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=3e5+5;
struct edge{
int to,next;
}e[MAXN<<1];
int head[MAXN],cnt,n,in[MAXN],out[MAXN],ind,fa[MAXN],w[MAXN],k,N;
int tot,ls[MAXN<<6],rs[MAXN<<6],s[MAXN<<6],rt[MAXN],mx,rev[MAXN];
int lm[MAXN],rm[MAXN],bd[MAXN],pos[MAXN],res[MAXN];
template<typename T>inline void read(T&num){
int f=1,ch=getchar();num=0;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){num=num*10+(ch^48);ch=getchar();}
num=num*f;
}
template<typename T>void print(T x){
if(x<0){putchar('-');x=-x;}
if(x>9)print(x/10);
putchar(x%10+48);
}
ll F(int x){return 1ll*x*(x-1)/2;}
inline void add(int u,int v){
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
#define mid ((l+r)>>1)
inline void push_up(int x){
s[x]=s[ls[x]]+s[rs[x]];
}
void ins(int pre,int&now,int l,int r,int p){
if(!now)now=++tot;
if(l==r){s[now]=s[pre]+1;return;}
if(p<=mid){rs[now]=rs[pre];ins(ls[pre],ls[now],l,mid,p);}
else{ls[now]=ls[pre];ins(rs[pre],rs[now],mid+1,r,p);}
push_up(now);
}
#undef mid
void predfs(int u,int f){
in[u]=++ind;fa[u]=f;rev[ind]=u;
for(int i=head[u];i;i=e[i].next){
int y=e[i].to;if(y==f)continue;
predfs(y,u);
}out[u]=ind;
}
int main(){
// freopen("networksample1.in","r",stdin);
// freopen("network.out","w",stdout);
read(n);read(k);
for(int i=1;i<=n;i++){
read(w[i]);mx=max(mx,w[i]);
}
N=mx+1;
for(int i=1;i<n;i++){
int u,v;read(u);read(v);add(u,v);add(v,u);
}
predfs(1,0);
for(int i=1;i<=n;i++){
ins(rt[i-1],rt[i],1,N,w[rev[i]]);
}
for(int i=1;i<=n;i++){
int cnts=0,L=rt[in[i]-1],R=rt[out[i]],ad=0;
lm[0]=rt[0];rm[0]=rt[n];bd[0]=0;
for(int j=head[i];j;j=e[j].next){
int y=e[j].to;if(y==fa[i])continue;
cnts++;lm[cnts]=rt[in[y]-1];rm[cnts]=rt[out[y]];
bd[cnts]=0;
}
int l=1,r=N;
while(l<r){
int mid=(l+r)>>1;
int al=s[ls[rm[0]]]-s[ls[lm[0]]]+bd[0],now=s[ls[R]]-s[ls[L]]+ad;
ll all=1ll*now*(al-now);all+=F(now);
// cerr<<"&"<<al<<" "<<now<<" "<<all<<endl;
for(int i=1;i<=cnts;i++){
// cerr<<"^"<<s[ls[rm[i]]]-s[ls[lm[i]]]+bd[i]<<endl;
all-=F(s[ls[rm[i]]]-s[ls[lm[i]]]+bd[i]);
}
// cerr<<i<<" "<<l<<" "<<r<<" "<<mid<<"*"<<all<<endl;
if(all<k){
l=mid+1;
L=rs[L];R=rs[R];ad=now;
for(int i=0;i<=cnts;i++){
bd[i]+=s[ls[rm[i]]]-s[ls[lm[i]]];
lm[i]=rs[lm[i]];rm[i]=rs[rm[i]];
}
}
else{
r=mid;L=ls[L];R=ls[R];
for(int i=0;i<=cnts;i++){
lm[i]=ls[lm[i]];rm[i]=ls[rm[i]];
}
}
}l--;
// cerr<<i<<" "<<l<<endl;
if(l==mx)res[i]=1000000;
else res[i]=l-w[i];
}
int ans=1e9;
for(int i=1;i<=n;i++){
ans=min(ans,res[i]);
}
print(ans);putchar('\n');
return 0;
}
T4 3sum
SOURCE：arc180D
部分分做法略。
这题当T4其实有点简单的（但是去年CSP/NOIP的T4好像还不如这个难）。
我们考虑对于每组询问，区间内的最大值显然是不可避免的要被选到的。
除了最大值所在位置以外（如果有多个，可以钦定最左/最右），一共就这么三种情况：
（1）选了，以及两个端点。
（2）选了三个区间。
为啥只有这两种形式呢？
我们考虑假设，那么，的最大值一定是，需要划分成两段区间，无论第二段区间是什么，我都可以疯狂把它右端点归给这一段，依旧不会改变的最大值。
所以一定只有上述两种情况。
第一种情况非常容易处理，不说了。
第二种情况，我们可以分在左边还是右边分别做。其实只用做一边，另一边就是翻转序列/询问再做一遍。
以下用在右边来设计算法：
我们考虑建立一个笛卡尔树。
那么每一个位置，都有一个管辖范围。
我们对于询问，想找的分割位置，实际上就是满足：
的所有中，的最小值。
对于每一个，我们可以在建笛卡尔树的过程中预处理出。
关键是，怎么对于每一组询问去求答案。
考虑扫描线。
我们按照从到的顺序来枚举。
首先，把所有的位置，插入到线段树中。在线段树中的下标是，值是。
然后，我们枚举所有的询问。此时，线段树中存储的所有元素，都满足，我们就只用关心一个限制了，直接在线段树中查询区间的最小值即可。
时间复杂度,常数有点大。
#include <bits/stdc++.h>
#define maxn 250005
#define ls (now<<1)
#define rs (now<<1|1)
#define mid ((l+r)>>1)
#define ll long long
#define mod 1000000007
using namespace std;
int zd[maxn<<2],zx[maxn<<2];
int n,q;
int a[maxn],ans[maxn];
struct nod{
int l,r,id,qid;
}Q[maxn];
void build(int now,int l,int r)
{
if (l==r) {zd[now]=zx[now]=l; return;}
build(ls,l,mid); build(rs,mid+1,r);
if (a[zd[ls]]>=a[zd[rs]]) zd[now]=zd[ls]; else zd[now]=zd[rs];
if (a[zx[ls]]<=a[zx[rs]]) zx[now]=zx[ls]; else zx[now]=zx[rs];
}
//找区间最大值所在id
int query(int now,int l,int r,int L,int R)
{
if (L<=l && r<=R) return zd[now];
int ret=0;
if (L<=mid)
{
int id=query(ls,l,mid,L,R);
if (ret==0 || a[id]>a[ret]) ret=id;
}
if (mid+1<=R)
{
int id=query(rs,mid+1,r,L,R);
if (ret==0 || a[id]>a[ret]) ret=id;
}
return ret;
}
//找区间最小值所在id
int query2(int now,int l,int r,int L,int R)
{
if (L<=l && r<=R) return zx[now];
int ret=0;
if (L<=mid)
{
int id=query2(ls,l,mid,L,R);
if (ret==0 || a[id]<a[ret]) ret=id;
}
if (mid+1<=R)
{
int id=query2(rs,mid+1,r,L,R);
if (ret==0 || a[id]<a[ret]) ret=id;
}
return ret;
}
int R[maxn],ansR[maxn]; //管辖右端点，以及答案
void get(int l,int r)
{
int id=query(1,1,n,l,r); //找到区间最大值
// cout<<l<<" "<<r<<" "<<id<<endl;
if (id==l) ansR[id]=1<<29;
else ansR[id]=a[id]+a[query2(1,1,n,l,id-1)]; //找到你左边最小值。
R[id]=r; //你最多管到r
if (l<=id-1) get(l,id-1);
if (id+1<=r) get(id+1,r);
}
int zx2[maxn<<2],lazy[maxn<<2]; //第二棵线段树只要最小值
int query3(int now,int l,int r,int L,int R)
{
if (L>R) return 1<<29;
if (L<=l && r<=R) {return zx2[now];}
if (lazy[now])
{
zx2[ls]=zx2[rs]=1<<29;
lazy[ls]=lazy[rs]=1;
lazy[now]=0;
}
int ret=1<<29;
if (L<=mid) ret=min(ret,query3(ls,l,mid,L,R));
if (mid+1<=R) ret=min(ret,query3(rs,mid+1,r,L,R));
return ret;
}
void ins(int now,int l,int r,int pos,int val)
{
if (l==r) {zx2[now]=min(zx2[now],val); return;}
if (lazy[now])
{
zx2[ls]=zx2[rs]=1<<29;
lazy[ls]=lazy[rs]=1;
lazy[now]=0;
}
if (pos<=mid) ins(ls,l,mid,pos,val);
else ins(rs,mid+1,r,pos,val);
zx2[now]=min(zx2[ls],zx2[rs]);
}
vector<nod> T[maxn];
vector<int> T2[maxn];
void work()
{
for (int i=1;i<=n;i++) T[i].clear();
build(1,1,n);
//case1：中间的最大值+两边两个值
//case2：中间的最大值+某一边两个值
for (int i=1;i<=q;i++)
{
int id=query(1,1,n,Q[i].l+1,Q[i].r-1);
ans[Q[i].qid]=min(ans[Q[i].qid],a[id]+a[Q[i].l]+a[Q[i].r]);
//找到你的mid所在
if (a[Q[i].l]>a[id]) id=Q[i].l;
if (a[Q[i].r]>a[id]) id=Q[i].r;
if (id-2>=Q[i].l)
ans[Q[i].qid]=min(ans[Q[i].qid],a[id]+a[Q[i].l]+a[Q[i].l+1]);
if (id+2<=Q[i].r)
ans[Q[i].qid]=min(ans[Q[i].qid],a[id]+a[Q[i].r]+a[Q[i].r-1]);
Q[i].id=id; //你这个询问最大值所在位置在这里。
T[Q[i].r].push_back(Q[i]);
}
// for (int i=1;i<=q;i++) cout<<Q[i].l<<" "<<Q[i].r<<" "<<Q[i].id<<endl;
get(1,n);
for (int i=1;i<=n;i++) T2[i].clear();
for (int i=1;i<=n;i++) T2[R[i]].push_back(i);
// for (int i=1;i<=n;i++) cout<<i<<" "<<R[i]<<" "<<ansR[i]<<endl;
//现在开始做第二棵线段树
lazy[1]=1; zx2[1]=1<<29;
for (int i=n;i>=1;i--)
{
for (int id:T2[i])
{
ins(1,1,n,id,ansR[id]);
}
for (auto tt:T[i])
{
//我要找的是tt以右，>=tt.r，且<=i的最小值
int val=query3(1,1,n,tt.id+1,tt.r);
ans[tt.qid]=min(ans[tt.qid],a[tt.id]+val);
}
}
}
void init()
{
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>q;
for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=q;i++) {cin>>Q[i].l>>Q[i].r; Q[i].qid=i;}
for (int i=1;i<=q;i++) ans[i]=1<<30;
work();
// cout<<ans[1]<<endl;
// return;
reverse(a+1,a+n+1);
for (int i=1;i<=q;i++) {Q[i].l=n+1-Q[i].l; Q[i].r=n+1-Q[i].r; swap(Q[i].l,Q[i].r);}
// for (int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl;
// for (int i=1;i<=q;i++) cout<<Q[i].l<<" "<<Q[i].r<<endl;
work();
for (int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
int main()
{
init();
}
我们会审查剪贴板内容，并对发布不合适内容的同学进行相应的处理