比赛链接：https://ac.nowcoder.com/acm/contest/11257
F,H,I,10，还行。后期一直在做J，但还是没做出来。
F
分析：
构造题。一种方法是把牛排按\( t \)从大到小排序，再限制一下盘子的时长\( tim \)，然后往盘子里填充；
\( tim \)肯定至少是用时最多的牛排的\( t \)；填充过程就是如果超出盘子时长，就把它分成两半，一半填在当前盘子最后，另一半填在下一个盘子最前；这两段时间不会相交，因为如果相交，说明这个牛排的\( t > tim\)，是不会发生的。
盘子要尽量填满，所以\( tim \)最好是\( sum(t) / m \)向上取整；这个和最大\( t \)取一个\( max \)，就是最终的\( tim \)了。
注意\( long long \)。
代码如下：
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int const N=1e5+5;
int n,m;
struct Nd{
int num,p[2]; ll l[2],r[2];
}ans[N];
struct It{
int t,id;
}a[N];
bool cmp(It x,It y){return x.t>y.t;}
ll mx(int x,ll y){return x>y?x:y;}
int main()
{
scanf("%d%d",&n,&m); ll tim=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i].t),a[i].id=i,tim+=a[i].t;
sort(a+1,a+n+1,cmp);
int pan=1; ll nw=0; tim=mx(a[1].t,(tim+m-1)/m);//
for(int i=1;i<=n;i++)
{
int id=a[i].id; ll t=a[i].t;
if(nw+t<=tim)
{
ans[id].num=1; ans[id].p[0]=pan;
ans[id].l[0]=nw; ans[id].r[0]=nw+t;
nw+=t;
}
else
{
ans[id].num=2; ans[id].p[0]=pan;
ans[id].l[0]=nw; ans[id].r[0]=tim;
t-=(tim-nw); nw=0; pan++;
ans[id].p[1]=pan; ans[id].l[1]=nw; ans[id].r[1]=nw+t;
nw=t;
}
if(nw==tim)pan++,nw=0;
}
for(int i=1;i<=n;i++)
{
printf("%d ",ans[i].num);
if(ans[i].num==1)printf("%d %lld %lld\n",ans[i].p[0],ans[i].l[0],ans[i].r[0]);
else
{
if(ans[i].l[0]<ans[i].l[1])
printf("%d %lld %lld %d %lld %lld\n",ans[i].p[0],ans[i].l[0],ans[i].r[0],ans[i].p[1],ans[i].l[1],ans[i].r[1]);
else
printf("%d %lld %lld %d %lld %lld\n",ans[i].p[1],ans[i].l[1],ans[i].r[1],ans[i].p[0],ans[i].l[0],ans[i].r[0]);
}
}
return 0;
}
me
H
分析：
由于兔子移动位置有周期性，所以最多有\( d*d \)个起点；在\( (0,0) -- (d,d) \)这个正方形里的起点决定了兔子可以走的所有位置；
所以把所有矩形都用这个\( d*d \)网格分割，放在\( (0,0) -- (d,d) \)这个正方形里，找一个没有被覆盖的点作为起点；这就需要用线段树维护矩形面积并了。
分割矩形的过程老是写不对……最后借鉴了下别人的写法才过。
代码如下：
#include<iostream>
#include<vector>
#define pb push_back
#define ls (u<<1)
#define rs ((u<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
int const N=1e5+5,inf=1e9;
int n,d,tr[N<<2],lz[N<<2];
struct Nd{
int l,r,s;
};
vector<Nd>v[N];
int rd()
{
int ret=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',c=getchar();
return ret*f;
}
void f(int u,int s){tr[u]+=s; lz[u]+=s;}
void pdn(int u)
{
if(!lz[u])return;
f(ls,lz[u]); f(rs,lz[u]); lz[u]=0;
}
void pup(int u){tr[u]=min(tr[ls],tr[rs]);}
void upt(int u,int l,int r,int ql,int qr,int s)
{
if(l>=ql&&r<=qr){f(u,s); return;}
pdn(u);
if(mid>=ql)upt(ls,l,mid,ql,qr,s);
if(mid<qr)upt(rs,mid+1,r,ql,qr,s);
pup(u);
}
/*
int qry(int u,int l,int r,int ql,int qr)
{
if(l>=ql&&r<=qr)return tr[u];
pdn(u); int ret=inf;
if(mid>=ql)ret=min(ret,qry(ls,l,mid,ql,qr));
if(mid<qr)ret=min(ret,qry(rs,mid+1,r,ql,qr));
return ret;
}
*/
int fnd(int u,int l,int r)
{
if(l==r)return l;
pdn(u);
if(tr[ls]==0)return fnd(ls,l,mid);
else return fnd(rs,mid+1,r);
}
void add(int x1,int y1,int x2,int y2)
{
x1=((x1%d+d)%d)+1; y1=((y1%d+d)%d)+1;
x2=(x2%d)?(x2%d+d)%d:d; y2=(y2%d)?((y2%d+d)%d)+1:d+1;
v[y1].pb((Nd){x1,x2,1}); v[y2].pb((Nd){x1,x2,-1});
}
void cal(int &x){x=(x%d+d)%d;}
void op1(int x1,int x2,int y1,int y2){
if(x1>=x2||y1>=y2)return;
v[y1+1].pb((Nd){x1+1,x2,1});
v[y2+1].pb((Nd){x1+1,x2,-1});
}
void op(int x1,int x2,int y1,int y2){
if(y2-y1>=d){op1(x1,x2,0,d);return;}
cal(y1),cal(y2);
if(y1>y2){op1(x1,x2,y1,d),op1(x1,x2,0,y2);}
else op1(x1,x2,y1,y2);
}
int main()
{
n=rd(); d=rd(); bool fl=1;
for(int i=1,x1,y1,x2,y2;i<=n;i++)
{
x1=rd(); y1=rd(); x2=rd(); y2=rd();//注意负数
if(x2-x1>=d&&y2-y1>=d)fl=0;
if(fl)
{
/*
if(x2-x1>=d)add(0,y1,d,y2);
else if(y2-y1>=d)add(x1,0,x2,d);
else
{
if((x1+1)/d==x2/d&&(y1+1)/d==y2/d)add(x1,y1,x2,y2);
else if((x1+1)/d==x2/d)add(x1,y1,x2,d),add(x1,0,x2,y2);
else if((y1+1)/d==y2/d)add(x1,y1,d,y2),add(0,y1,x2,y2);
else add(x1,y1,d,d),add(0,y1,x2,d),add(x1,0,d,y2),add(0,0,x2,y2);
}
*/
if(x2-x1>=d){op(0,d,y1,y2);continue;}
cal(x1),cal(x2);
if(x1>x2){op(x1,d,y1,y2),op(0,x2,y1,y2);}
else op(x1,x2,y1,y2);
}
}
if(!fl){printf("NO\n"); return 0;}
for(int y=1;y<=d;y++)
{
for(Nd it:v[y])upt(1,1,d,it.l,it.r,it.s);
//if(qry(1,1,d,1,d))continue;
if(tr[1])continue;
int ax=fnd(1,1,d);
printf("YES\n%d %d\n",ax-1,y-1);
return 0;
}
printf("NO\n");
return 0;
}
me
I
分析：
要找一组区间，让这组区间的交恰好等于给定若干区间的并；
那就每次把给定区间中两个相邻区间的间隙去掉即可。
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
int const N=1005;
int T,n,m;
struct Nd{
int l,r;
}a[N],b[N];
int rd()
{
int ret=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',c=getchar();
return ret*f;
}
bool cmp(Nd x,Nd y){return x.l<y.l;}
int main()
{
T=rd();
while(T--)
{
n=rd(); m=rd();
for(int i=1;i<=m;i++)
{
a[i].l=rd(); a[i].r=rd();
if(a[i].l>a[i].r)a[i].r+=n;
}
sort(a+1,a+m+1,cmp); int cnt=0,p=1,L,R;
while(p<=m)
{
L=a[p].l;
while(p+1<=m&&a[p].r+1==a[p+1].l)p++;
b[++cnt]=(Nd){L,a[p].r};
p++;
}
printf("%d\n",cnt);
for(int i=1,j=cnt;i<=cnt;i++,j++)
{
if(j>cnt)j=1;
L=b[i].l; R=b[j].r;
if(R>n)R-=n;
printf("%d %d\n",L,R);
}
}
return 0;
}
me
J
分析：
偶数点的连通块直接加即可。考虑奇数点的连通块：
首先，要删除（也就是贡献为负）的点彼此之间一定是孤立的；否则如果删除一个连通块，它一定包含\( \geq 3 \)的奇数个点，那可以分出一个点，剩下偶数个点贡献还是正的。
其次，删除的这些孤立点一共是奇数个，这样才能剩下偶数个点。
然后，我们假设要删除的孤立点一共有\( \geq 3 \)个，那么这些点一定都是割点，否则只删其中代价最小的那个非割点会更优。
如果在原图中单独删除这些点中的某一个，剩下的几个子树一定存在奇数个点的（至少两个，因为剩余总点数是偶数）；否则全是偶数个点的，那就没必要再删其他点了。这些奇数个点的子树里面一定还有要删除的点。
所以对于一个要删除的点，其他要删除的点分布在它的奇数个点的子树中；
但是这样的话总会有某些要删除的点在最边缘，它只有一边是其他的要删除的点（可以给原图建立一个圆方树，然后依据要删除的点提取一棵虚树，总有点处在叶子位置）；单独删除它的话不满足上面说到的性质。
所以假设不成立。所以一个奇数点的连通块中只会删除一个点。
于是tarjan找到所有割点，其中所有子树都是偶数的割点可能作为答案；所有非割点也可能作为答案；比较一下它们的代价即可。
（重温了一下tarjan，点双连通分量，无向图的割点和桥，圆方树，虚树；真是怀念。）
代码如下：
#include<iostream>
#define ll long long
using namespace std;
int const N=1e6+5,inf=1e9+5;
int T,n,m,a[N],hd[N],cnt,nxt[N<<1],to[N<<1],ccol,col[N],num[N];
int dfn[N],cdfn,low[N],rt,son,siz[N],mn;
bool ok[N],vis[N];
ll ans;
int rd()
{
int ret=0,f=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+c-'0',c=getchar();
return ret*f;
}
void add(int x,int y){nxt[++cnt]=hd[x]; hd[x]=cnt; to[cnt]=y;}
void dfs(int u)
{
col[u]=ccol; num[ccol]++;
for(int i=hd[u],v;i;i=nxt[i])
if(!col[v=to[i]])dfs(v);
}
void tarjan(int u)
{
dfn[u]=low[u]=++cdfn; siz[u]=1;
for(int i=hd[u],v;i;i=nxt[i])
{
if(!dfn[v=to[i]])
{
tarjan(v); siz[u]+=siz[v];
low[u]=min(low[u],low[v]);
if(u==rt)son++;
if(low[v]>=dfn[u]&&siz[v]%2)ok[u]=0;//是割点且有奇数点子树(包括根)
}
else
low[u]=min(low[u],dfn[v]);
}
if(u==rt&&son<=1)ok[rt]=1;
}
void dfs2(int u)
{
vis[u]=1;
if(ok[u])mn=min(mn,a[u]);
for(int i=hd[u],v;i;i=nxt[i])
if(!vis[v=to[i]])dfs2(v);
}
void work(int x)
{
rt=x; son=0; cdfn=0;
tarjan(x);
//for(int i=1;i<=n;i++)printf("ok[%d]=%d\n",i,ok[i]);
mn=inf; dfs2(x);
ans-=2*mn;
}
int main()
{
T=rd();
while(T--)
{
n=rd(); m=rd(); cnt=0; ccol=0; ans=0;
for(int i=1;i<=n;i++)
a[i]=rd(),ans+=a[i],hd[i]=0,col[i]=0,ok[i]=1,dfn[i]=0,low[i]=0,vis[i]=0,siz[i]=0;
for(int i=1,x,y;i<=m;i++)
x=rd(),y=rd(),add(x,y),add(y,x);
for(int i=1;i<=n;i++)
{
if(col[i])continue;
ccol++; num[ccol]=0;
dfs(i);
if(num[ccol]%2)work(i);
}
printf("%lld\n",ans);
}
return 0;
}
me