CFR637

CFR637 div1

A卡了1h,原因是多测时自以为某个一定能空掉的set在无解break时并不是空的

CF1340A Nastya and Strange Generator

code

CF1340B Nastya and Scoreboard

code

CF1340C Nastya and Unexpected Guest

题意:表示为$[0,n]$的线段上,总共$m \le 1e4$个点,坐标为d(不重,排序后$d_1=0,d_m=n$)。给定$g,r \le 1e3$,每走完g步必须恰好在点上,然后等待r秒,每步移动为$\pm 1$并花费1秒且只能在点上时换方向。求从0到$n \le 1e6$的最小时间,无解-1

请先思考后再展开

每个$(x,len\%G)=红灯次数$,一定在相同余数时取最小的红灯次数(轮数),转移走向相邻的话是个01最短路,$O(nG)$

1
2
3
4
5
6
7
8
9
10
11
12
int n=qread(),m=qread();fo(i,1,m) d[i]=qread();sort(d+1,d+m+1);int G=qread(),R=qread();
int ans=INF;mem(dis,0x3f);dis[1][0]=0;q.PB({1,0});
while(sz(q))
{
int x=q.front().FR,z=q.front().SE;q.pop_front();
if(z+n-d[x]<=G) chmin(ans, dis[x][z]*(R+G)+z+n-d[x] );
fo(op,-1,1) if(op!=0 and x+op>=1 and x+op<=m and z+abs(d[x]-d[x+op])<=G)
{
int y=x+op,z2=(z+abs(d[x]-d[y]))%G,ti2=dis[x][z]+(z2==0);
if(ti2<dis[y][z2]){ dis[y][z2]=ti2;if(z2==0) q.PB({y,z2}); else q.push_front({y,z2}); }
}
}write(ans==INF?-1:ans);

CF1340D Nastya and Time Machine

题意:给出一棵$n \le 1e5$的树,然后直接看题意中The following conditions must be met:下面的部分

请先思考后再展开

首先下界是$ans=\max d_x$,考虑能否得到这个下界

那肯定先考虑链,可以归纳地得到一个过程:$(x,1) \to (y,2) …. (y,1) \to (x,2) \to (x,0)$以及$(x,2) \to (x,0) \to (y,1) …. (y,0) \to (x,1)$,也就是准备前往父亲时总是进来时-1

这个过程可以移植到树上,设进来的时候是$(x,t<ans)$出去时是$(x,t-1)$,如果返回到x时(不用管子树内)的$t+1、t+2…t+sons$始终没有碰到ans,那么最后就是$(x,t+sons) \to (x,t-1)$;如果碰到了,那么设剩下还没访问的儿子个数为rest,则跳到$(x,(t-1)-rest)$就能在最后访问x时恰好在t-1而不需要再跳跃(显然空间总是足够的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int ans;vc<int> to[N];vc<pii> step;
void solve(int x,int fa,int t=0)
{
step.PB({x,t});int rest=sz(to[x])-(fa>0),cur=t;
for(auto y:to[x]) if(y!=fa)
{
if(cur==ans){ cur=(t-1)-rest;step.PB({x,cur}); }
solve(y,x,cur+1);cur++,rest--;step.PB({x,cur});
} if(fa and cur!=t-1) step.PB({x,t-1}),assert(cur>t-1);
}
void main()
{
int n=qread();fo(i,2,n){ int x=qread(),y=qread();to[x].PB(y),to[y].PB(x); } fo(i,1,n) chmax(ans,sz(to[i]));
solve(1,0);write2(sz(step));for(auto in:step) write1(in.FR),write2(in.SE);
}

CF1340E Nastya and Bees

这题据说锅了

CF1340F Nastya and CBS

咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/e289eabc.html
转载请注明出处,谢谢!