11.4 考试
分类:
IT文章
•
2023-11-04 13:37:58
最近好爆炸啊,我已经做好随时退役的准备了...
T1 kill
题意:
给一个集合点,n个人,m个怪,在一条直线上,n<=m,每人一个怪,每个怪只被打一次,问所有走的路程的最大值的最小值
大家觉得这个题好简单啊,但是我怎么觉得好难啊
于是我就打了一个贪心加反悔$O(n^2logn)$,因为数据水,对了9个点,T了一个点QAQ...
大佬们都打了$O(nlogn)$的优秀算法
先把人和怪都排序
二分ans
贪心选择最左边的怪..
好像也挺简单
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define rint register int
using namespace std;
inline void read(int &x)
{
x=0; int ff=1; char q=getchar();
while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }
while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();
x*=ff;
}
inline void readll(ll &x)
{
x=0; int ff=1; char q=getchar();
while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }
while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();
x*=ff;
}
const int N=5006;
int n,m;
ll S,p[N],q[N];
int check(ll x)
{
int i,l=1;
for(i=1;i<=n;++i)
{
while( l<=m&&abs(p[i]-q[l])+abs(q[l]-S)>x )
++l;
if(l>m) return 0;
++l;
}
return 1;
}
ll work()
{
ll l=0,r=1e10,mid,ans=1e10;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int main(){
//freopen("T1.in","r",stdin);
rint i;
read(n); read(m); readll(S);
for(i=1;i<=n;++i)
readll(p[i]);
for(i=1;i<=m;++i)
readll(q[i]);
sort(p+1,p+1+n);
sort(q+1,q+1+m);
printf("%lld
",work());
}
T1
T2 beauty
题意:
n个节点的一棵树,给2*K个关键点
求$sum_{i|关键点}dis(u_i,v_i)$的最大值
又没做出来,郁闷ing~~~
把问题转化成 求LCA的深度之和最小值
考虑到一个节点,如果它的每一个儿子子树中关键点的个数都<=$frac{size_x}{2}$
那么x这颗子树中的关键点两两配对的LCA都可以是x
dfs一遍就行了
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define rint register int
using namespace std;
inline void read(int &x)
{
x=0; int ff=1; char q=getchar();
while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }
while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();
x*=ff;
}
const int N=100006;
int first[N],nt[N<<1],ver[N<<1],e;
void addbian(int u,int v)
{
ver[e]=v;
nt[e]=first[u];
first[u]=e++;
}
int n,K,op,allk;
int ans;
int ke[N];
int fa[N],size[N],dep[N];
void dfs1(int x)
{
int i;
for(i=first[x];i!=-1;i=nt[i])
if(ver[i]!=fa[x])
{
fa[ver[i]]=x;
dep[ver[i]]=dep[x]+1;
dfs1(ver[i]);
size[x]+=size[ver[i]];
}
}
void dfs(int x,int le)
{
//printf("x=%d le=%d size[x]=%d
",x,le,size[x]);
int i,id=0;
for(i=first[x];i!=-1;i=nt[i])
if(ver[i]!=fa[x]&&size[ver[i]]*2>size[x])
id=ver[i];
if(!id)
ans-=(size[x]-le)*dep[x];
else
{
if( (size[id]-le)*2<=size[x]-le )
ans-=(size[x]-le)*dep[x];
else
{
ans-=(size[x]-size[id])*2*dep[x];
dfs(id,le+size[x]-size[id]);
}
}
}
int main(){
//freopen("T2.in","r",stdin);
//freopen("T2.out","w",stdout);
rint i; int tin1,tin2;
mem(first,-1);
read(n); read(K); read(op);
allk=K<<1;
for(i=1;i<=allk;++i)
read(ke[i]),size[ke[i]]=1;
for(i=1;i<n;++i)
{
read(tin1); read(tin2);
addbian(tin1,tin2);
addbian(tin2,tin1);
}
fa[1]=-1; dfs1(1);
for(i=1;i<=allk;++i)
ans+=dep[ke[i]];
dfs(1,0);
printf("%d
",ans);
}
T2
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
#define rint register int
using namespace std;
inline void read(int &x)
{
x=0; int ff=1; char q=getchar();
while(q<'0'||q>'9') { if(q=='-') ff=-1; q=getchar(); }
while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();
x*=ff;
}
const int N=100006;
const int Inf=2e9;
int first[N],nt[N<<1],ver[N<<1],w[N<<1],id[N<<1],e;
void addbian(int u,int v,int _w,int _id)
{
ver[e]=v; w[e]=_w; id[e]=_id;
nt[e]=first[u];
first[u]=e++;
}
struct HSDAS
{
int first[N],nt[N<<1],ver[N<<1],e;
void clear()
{
mem(first,-1);
}
void addbian(int u,int v)
{
ver[e]=v;
nt[e]=first[u];
first[u]=e++;
}
}h;
struct JI
{
int u,v,w,order;
JI(){}
JI(int _u,int _v,int _w,int _order)
{
u=_u; v=_v; w=_w; order=_order;
}
bool friend operator < (JI a,JI b)
{
return a.w<b.w;
}
}ji[N];
int n,m,op;
bool isis[N],istree[N];
int uu[N],vv[N],ww[N];
int v[N],fan[N];
int mn[N<<2],mx[N<<2],laz[N<<2];
void pushdown(int x)
{
if(laz[x]!=Inf)
{
if(laz[x<<1]>laz[x]) laz[x<<1]=laz[x];
if(laz[x<<1|1]>laz[x]) laz[x<<1|1]=laz[x];
if(mn[x<<1]>laz[x]) mn[x<<1]=laz[x];
if(mn[x<<1|1]>laz[x]) mn[x<<1|1]=laz[x];
laz[x]=Inf;
}
}
void build(int l,int r,int x)
{
laz[x]=Inf;
if(l==r)
{
mn[x]=Inf; mx[x]=v[fan[l]];
return ;
}
int mid=(l+r)>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
mx[x]=max(mx[x<<1],mx[x<<1|1]);
}
void qqmax(int L,int R,int &an,int l,int r,int x)
{
if(L<=l&&r<=R)
{
if(an<mx[x]) an=mx[x];
return ;
}
int mid=(l+r)>>1;
if(L<=mid) qqmax(L,R,an,l,mid,x<<1);
if(mid<R) qqmax(L,R,an,mid+1,r,x<<1|1);
}
void qqmin(int pos,int &an,int l,int r,int x)
{
if(l==r)
{
if(an>mn[x]) an=mn[x];
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(pos<=mid) qqmin(pos,an,l,mid,x<<1);
else qqmin(pos,an,mid+1,r,x<<1|1);
}
void modi(int L,int R,int vv,int l,int r,int x)
{
if(L<=l&&r<=R)
{
if(mn[x]>vv) mn[x]=vv;
if(laz[x]>vv) laz[x]=vv;
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(L<=mid) modi(L,R,vv,l,mid,x<<1);
if(mid<R) modi(L,R,vv,mid+1,r,x<<1|1);
mn[x]=min(mn[x<<1],mn[x<<1|1]);
}
int fa[N],dep[N],size[N],son[N];
void dfs1(int x)
{
size[x]=1;
int i;
//printf("x=%d
",x);
for(i=h.first[x];i!=-1;i=h.nt[i])
{
//printf("i=%d
",i);
isis[(i>>1)+1]=1;
//printf("i=%d
",i);
}
//printf("x=%d
",x);
for(i=first[x];i!=-1;i=nt[i])
if(ver[i]!=fa[x])
{
fa[ver[i]]=x;
dep[ver[i]]=dep[x]+1;
v[ver[i]]=w[i];
dfs1(ver[i]);
size[x]+=size[ver[i]];
if(size[son[x]]<size[ver[i]])
son[x]=ver[i];
}
}
int dfn[N],tim,top[N];
void dfs2(int x,int tp)
{
top[x]=tp; dfn[x]=++tim;
fan[tim]=x;
if(son[x])
dfs2(son[x],tp);
int i;
for(i=first[x];i!=-1;i=nt[i])
if(ver[i]!=fa[x]&&ver[i]!=son[x])
dfs2(ver[i],ver[i]);
}
void Modi(int x,int y,int vv)
{
int fx=top[x],fy=top[y];
while(fx!=fy)
{
if(dep[fx]<dep[fy])
x^=y,y^=x,x^=y,
fx^=fy,fy^=fx,fx^=fy;
modi(dfn[fx],dfn[x],vv,1,n,1);
x=fa[fx]; fx=top[x];
}
if(dep[x]>dep[y]) x^=y,y^=x,x^=y;
if(x!=y) modi(dfn[x]+1,dfn[y],vv,1,n,1);
}
int QQMAX(int x,int y)
{
int fx=top[x],fy=top[y],an=0;
while(fx!=fy)
{
if(dep[fx]<dep[fy])
x^=y,y^=x,x^=y,
fx^=fy,fy^=fx,fx^=fy;
qqmax(dfn[fx],dfn[x],an,1,n,1);
x=fa[fx]; fx=top[x];
}
if(dep[x]>dep[y]) x^=y,y^=x,x^=y;
if(x!=y) qqmax(dfn[x]+1,dfn[y],an,1,n,1);
return an;
}
int bfa[N];
int fin(int x)
{
if(bfa[x]==-1) return x;
return bfa[x]=fin(bfa[x]);
}
void kru()
{
sort(ji+1,ji+1+m);
int x,y,nownum=0,i;
for(i=1;i<=m;++i)
{
x=fin(ji[i].u); y=fin(ji[i].v);
if(x!=y)
{
bfa[x]=y;
istree[ji[i].order]=1;
addbian(ji[i].u,ji[i].v,ji[i].w,ji[i].order);
addbian(ji[i].v,ji[i].u,ji[i].w,ji[i].order);
++nownum;
}
if(nownum==n-1)
break;
}
}
int main(){
//freopen("T3.in","r",stdin);
rint i; int tt;
h.clear();
mem(bfa,-1);
mem(first,-1);
read(n); read(m); read(op);
for(i=1;i<=m;++i)
{
read(uu[i]); read(vv[i]); read(ww[i]);
ji[i]=JI(uu[i],vv[i],ww[i],i);
h.addbian(uu[i],vv[i]);
h.addbian(vv[i],uu[i]);
}
kru();
fa[1]=-1; dfs1(1);
dfs2(1,1);
build(1,n,1);
for(i=1;i<=m;++i)
if(isis[i]&&!istree[i])
Modi(uu[i],vv[i],ww[i]);
for(i=1;i<=m;++i)
{
//printf("i=%d %d
",i,(isis[i]?1:0));
if(isis[i])
{
if(istree[i])
{
tt=Inf; qqmin(dfn[dep[uu[i]]>dep[vv[i]]?uu[i]:vv[i]],tt,1,n,1);
if(tt==Inf) tt=0;
--tt;
printf("%d ",tt);
}
else
printf("%d ",QQMAX(uu[i],vv[i])-1);
}
else
puts("0");
}
}