2018ACM-ICPCWorldFinals部分题题解
Problem C. Conquer the World &&loj6405 征服世界
题⽬⼤意：给定⼀棵树，树有边权。每个点上有a_i个⼠兵，且每个点最终需要b_i个⼠兵。
router求最⼩代价。
n\leq2.5*10^5,a_i,b_i\leq1e9。
题解：显然，我们可以直接⽤这棵树跑费⽤流。但n太⼤了。所以我们只能模拟⼀下费⽤流的过程了。
⾸先，为了保证所有的b_i都能选满，我们先给每个b_i加⼀个-INF的权值。
考虑维护两个堆，分别记录a的信息和b的信息。
DFS这棵树，设当前节点为u。将u的所有⼉⼦的堆全部合并，每个点的初始权值是dis_i和dis_i-INF，
指的是i到1号节点的距离。这个可以⽤左偏树或者stl⾥的pb_ds实现。
将⼦树信息上传完成后，开始尝试将它们两两配对。
配对终⽌的条件是两个堆顶元素匹配的权值\geq 0。
然后考虑如何像费⽤流那样进⾏反悔操作。
如果当前的⼀个匹配点和另外⼀个点匹配了，那么就要撤销之前的匹配。列出两次匹配的关系式，我们就可以分别得出计算a,b反悔代价的算式。
因为⼀个点的a和b不会同时反悔，且\sum b_i也不⼤，所以做法是正确的。
具体的反悔实现可以看我的代码。
时间复杂度：O(nlogn)
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memt(x,y,sizeof(x))
#define STS system("pau")
template<class D>I read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
const ll INF=1e12+7;
struct E{
int to,nt,w;
}e[505000];
#define T e[k].to
queue<int>q;
struct Dat{
ll w,f;
Dat(ll _w=0,ll _f=0){w=_w;f=_f;}
friend bool operator < (Dat x,Dat y){return x.w>y.w;}
}d[2000000];
int now,cnt,ch[2000000][2],dis[2000000],root[303000],rt[303000];
int n,m,X,Y,W,a[303000],b[303000],head[303000],tot,sum;
ll dep[303000],ans;
IN new_node(){
re res;
pty())return ++cnt;
res=q.front();q.pop();
ch[res][0]=ch[res][1]=dis[res]=d[res].w=d[res].f=0;
return res;
}
I add(int x,int y,int w){e[++tot].to=y;e[tot].nt=head[x];head[x]=tot;e[tot].w=w;}
IN merge(int x,int y){
if(!x||!y)return x+y;
if(d[x]<d[y])swap(x,y);
ch[x][1]=merge(ch[x][1],y);
if(dis[ch[x][0]]<dis[ch[x][1]])swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
I D_1(int x,int fa,ll depth){
dep[x]=depth;
if(a[x])d[x]=Dat(dep[x],a[x]),root[x]=x,dis[x]=0;el root[x]=0;
if(b[x])d[x+n]=Dat(dep[x]-INF,b[x]),rt[x]=x+n,dis[x+n]=0;el rt[x]=0;
for(re k=head[x];k!=-1;k=e[k].nt){
if(T==fa)continue;
D_1(T,x,depth+e[k].w);
root[x]=merge(root[x],root[T]);
rt[x]=merge(rt[x],rt[T]);
}
while(root[x]&&rt[x]&&d[root[x]].w+d[rt[x]].w-2*dep[x]<0){
ll vala=d[root[x]].w,valb=d[rt[x]].w,tmp=min(d[root[x]].f,d[rt[x]].f),nowa=d[root[x]].f-tmp,nowb=d[rt[x]].f-tmp;
ans+=(vala+valb-2*dep[x])*tmp;
//cout<<"!"<<root[x]<<" "<<rt[x]<<" "<<tmp<<" "<<vala<<" "<<valb<<" "<<dep[x]<<" "<<nowa<<" "<<nowb<<endl;
root[x]=merge(ch[root[x]][0],ch[root[x]][1]);
rt[x]=merge(ch[rt[x]][0],ch[rt[x]][1]);
高中数学课本if(tmp){
now=new_node();d[now]=Dat(2*dep[x]-valb,tmp);dis[now]=0;root[x]=merge(root[x],now);
now=new_node();d[now]=Dat(2*dep[x]-vala,tmp);dis[now]=0;rt[x]=merge(rt[x],now);
}
if(nowa)now=new_node(),d[now]=Dat(vala,nowa),dis[now]=0,root[x]=merge(root[x],now);
if(nowb)now=new_node(),d[now]=Dat(valb,nowb),dis[now]=0,rt[x]=merge(rt[x],now);
}
}
int main(){
read(n);C(head,-1);tot=-1;cnt=n<<1;dis[0]=-1;
F(i,1,n-1){
read(X);read(Y);read(W);
add(X,Y,W);add(Y,X,W);
}
F(i,1,n){
read(a[i]),read(b[i]);
re tmp=min(a[i],b[i]);a[i]-=tmp;b[i]-=tmp;
sum+=b[i];
}
D_1(1,0,0);
/*while(rt[1]){
ll vala=d[root[1]].w,valb=d[rt[1]].w,tmp=min(d[root[1]].f,d[rt[1]].f),nowa=d[root[1]].f-tmp,nowb=d[rt[1]].f-tmp;
ans+=(vala+valb-2*dep[1])*tmp;//cout<<"!"<<tmp<<endl;
root[1]=merge(ch[root[1]][0],ch[root[1]][1]);
rt[1]=merge(ch[rt[1]][0],ch[rt[1]][1]);
majestyif(nowa)++now,d[now]=Dat(vala,nowa),dis[now]=0,root[1]=merge(root[1],now);
if(nowb)++now,d[now]=Dat(valb,nowb),dis[now]=0,rt[1]=merge(rt[1],now);
//cout<<now<<endl;
}*/
printf("%lld",ans+(ll)INF*sum);
return 0;
}
/*
3
1 2 5
3 1 5
2 1
5 0
1 3
6
1 2 2
1 3 5
1 4 1
2 5 5
2 6 1
0 0
1 0动画片埃及王子
2 1
2 1
0 1
0 1
*/
Problem I. Triangles && loj6411
题⽬⼤意：给出⼀张毒瘤的图，求其中包含的三⾓形个数。
题解：
我们先考虑只求出所有下三⾓。上三⾓可以将整张图翻转然后求出。（以下将r,c统称为n）
⾸先，我们将整张图扫⼀遍，求出三个东西：每个点x能够向左上，右上和向右延伸多少。
我们按照由右到左，由左上到右下的顺序遍历每个点，看以它为下顶点能组成多少个三⾓形。
发现这时我们只需要考虑当前点能和多少个上⾯的横线匹配，因为我们已经求出了每个点向左上和右上延伸的距离。考虑满⾜条件的直线⼀定是⼀段后缀，所以可以考虑⽤树状数组来维护。
我们求出了每个点向右延伸的距离，那么也就可以算出⼀条横线被撤销的时间。⽤vector记录下就⾏。
最后再这样枚举⼀下左下⾓没被做到的东西就⾏了。
代码实现⼀定要⼩⼼，记得每次做完要清空树状数组的元素。
时间复杂度：O(nmlogn)。
代码：
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define F(x,y,z) for(re x=y;x<=z;x++)
#define FOR(x,y,z) for(re x=y;x>=z;x--)
typedef long long ll;
#define I inline void
#define IN inline int
#define C(x,y) memt(x,y,sizeof(x))
#define STS system("pau")
template<class D>I read(D &res){
res=0;register D g=1;register char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')g=-1;
ch=getchar();
}
小学英语教学论文网while(isdigit(ch)){
res=(res<<3)+(res<<1)+(ch^48);
ch=getchar();
}
res*=g;
}
struct BIT{
int t[101000];
IN lbt(int x){return x&(-x);}
I modi(int x,int w,int N){
while(x<=N)t[x]+=w,x+=lbt(x);
}
IN ques(int x){
re res=0;while(x)res+=t[x],x-=lbt(x);return res;
}
}B;
蛇行char s[6060][12020];
int n,m,r,c;
ll ans;
int ul[6002][10020],ur[6002][10020],rd[6002][10020];
vector<int>del[6060];
int main(){
// freopen("f.out","w",stdout);
read(r);read(c);r=(r<<1)-1;c=(c<<1)-1;
F(i,1,r){
gets(s[i]+1);
F(j,1,c)if(s[i][j]=='\0')s[i][j]=' ';
}
re len=(r+1)>>1;
F(i,1,r){
FOR(j,c,1){
if(s[i][j]!='x')continue;
if(s[i][j+1]=='-'&&s[i][j+2]=='-'&&s[i][j+3]=='-'&&s[i][j+4]=='x')rd[i][j]=rd[i][j+4]+1;el rd[i][j]=0; if(s[i-1][j-1]!=' '&&i>1&&j>1)ul[i][j]=ul[i-2][j-2]+1;el ul[i][j]=0;
if(s[i-1][j+1]!=' '&&i>1&&j<c)ur[i][j]=ur[i-2][j+2]+1;el ur[i][j]=0;
//cout<<"!"<<i<<" "<<j<<" "<<rd[i][j]<<" "<<ul[i][j]<<" "<<ur[i][j]<<endl;
}
}
FOR(nowj,c,1){
if(s[1][nowj]!='x')continue;
fossilization
// cout<<"N"<<nowj<<endl;
for(re i=1,j=nowj;i<=r&&j<=c;i+=2,j+=2){
if(i==1){
if(rd[i][j]){
if((rd[i][j]<<1)+1<=r)del[1+(rd[i][j]<<1)].emplace_back(1);
el del[0].emplace_back(1);
}
continue;
}
ans+=B.ques((i+1)>>1)-B.ques(((i-1)>>1)-min(ul[i][j],ur[i][j]));
if(rd[i][j]){
if((rd[i][j]<<1)+i<=r)del[(rd[i][j]<<1)+i].emplace_back(i);
el del[0].emplace_back(i);
}
for(auto d:del[i])B.modi((d+1)>>1,-1,len);//,cout<<"d"<<((d+1)>>1)<<endl;
del[i].clear();
}
for(auto d:del[0])B.modi((d+1)>>1,-1,len);//,cout<<"D"<<((d+1)>>1)<<endl;
del[0].clear();
广东二级建造师报名时间}
F(nowi,2,r){
if(s[nowi][1]!='x')continue;
for(re i=nowi,j=1;i<=r&&j<=c;i+=2,j+=2){
ans+=B.ques((i+1)>>1)-B.ques(((i-1)>>1)-min(ul[i][j],ur[i][j]));
if(rd[i][j]){
if((rd[i][j]<<1)+i<=r)del[(rd[i][j]<<1)+i].emplace_back(i);
el del[0].emplace_back(i);
}
for(auto d:del[i])B.modi((d+1)>>1,-1,len);//,cout<<"D"<<((d+1)>>1)<<endl;
del[i].clear();
}
for(auto d:del[0])B.modi((d+1)>>1,-1,len);//,cout<<"D"<<((d+1)>>1)<<endl;
del[0].clear();
}
rever(s+1,s+1+r);
//F(i,1,r)puts(s[i]+1);
F(i,1,r){
FOR(j,c,1){
if(s[i][j]!='x')continue;
if(s[i][j+1]=='-'&&s[i][j+2]=='-'&&s[i][j+3]=='-'&&s[i][j+4]=='x')rd[i][j]=rd[i][j+4]+1;el rd[i][j]=0; if(s[i-1][j-1]!=' '&&i>1&&j>1)ul[i][j]=ul[i-2][j-2]+1;el ul[i][j]=0;
if(s[i-1][j+1]!=' '&&i>1&&j<c)ur[i][j]=ur[i-2][j+2]+1;el ur[i][j]=0;
}
}
FOR(nowj,c,1){
if(s[1][nowj]!='x')continue;
// cout<<"N"<<nowj<<endl;
for(re i=1,j=nowj;i<=r&&j<=c;i+=2,j+=2){
if(i==1){
if(rd[i][j]){
if((rd[i][j]<<1)+1<=r)del[1+(rd[i][j]<<1)].emplace_back(1);
el del[0].emplace_back(1);
}
continue;
}
ans+=B.ques((i+1)>>1)-B.ques(((i-1)>>1)-min(ul[i][j],ur[i][j]));
if(rd[i][j]){
if((rd[i][j]<<1)+i<=r)del[(rd[i][j]<<1)+i].emplace_back(i);
el del[0].emplace_back(i);
}
for(auto d:del[i])B.modi((d+1)>>1,-1,len);//,cout<<"d"<<((d+1)>>1)<<endl;
del[i].clear();
}
for(auto d:del[0])B.modi((d+1)>>1,-1,len);//,cout<<"D"<<((d+1)>>1)<<endl;
del[0].clear();
}
F(nowi,2,r){
if(s[nowi][1]!='x')continue;
for(re i=nowi,j=1;i<=r&&j<=c;i+=2,j+=2){
ans+=B.ques((i+1)>>1)-B.ques(((i-1)>>1)-min(ul[i][j],ur[i][j]));
if(rd[i][j]){
if((rd[i][j]<<1)+i<=r)del[(rd[i][j]<<1)+i].emplace_back(i);
el del[0].emplace_back(i);
distinct是什么意思
}
for(auto d:del[i])B.modi((d+1)>>1,-1,len);//,cout<<"d"<<((d+1)>>1)<<endl;
del[i].clear();
}
for(auto d:del[0])B.modi((d+1)>>1,-1,len);//,cout<<"D"<<((d+1)>>1)<<endl;
del[0].clear();
}
printf("%lld",ans);
return 0;
}
/*
3 3
x---x
\ /
x
wenchuan/ \
x x
4 10
x x---x---x x
\ / / \
x x---x x x
/ \ / \ \
x x---x---x---x
/ / \ \ / \
x---x---x---x---x
*/Processing math: 0%
