CFR423 div1

CFR423 div1

本来vp的开局很好的,写完C是unofficial的22名,结果这个D看完就会一直写错,1h13min都没过qwq(调试30min),讲道理根本原因还是写着写着动摇想法,或者本来打算要注意的点后面忘了

另外罚时也是致命伤,B忘判一种情况,C开小空间+写错小地方

但单论质量感觉题目不太行,前4题没意思,E和F也没啥思考难度,就是F稍有些细节

CF827A String Reconstruction

请先思考后再展开

因为一定有解,模拟,覆盖上去后,从左往右,每次保留剩余长度最长的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string a[N];int b[N];
void main()
{
int n=qread();int ln=0;
fo(i,1,n)
{
cin>>a[i];int k=qread();
while(k--){int pos=qread();chmax(ln,pos+sz(a[i])-1);if(sz(a[b[pos]])<sz(a[i]))b[pos]=i;}
}
int now=0,tt=0;
fo(i,1,ln)
{
tt++;if(b[i] and sz(a[b[i]])>sz(a[now])-tt+1) now=b[i],tt=1;
if(tt<=sz(a[now])) putchar(a[now][tt-1]);
else putchar('a');
}
}

CF827B High Load

请先思考后再展开

贪心,考虑从菊花图开始调整,只有把一个叶子放到另一个叶子下面才能减少叶子数量,那么就直接分k段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int a[N];
void main()
{
int n=qread(),K=qread();
int tt=(n-1)/K;fo(i,1,K) a[i]=tt;
int left=(n-1)-tt*K,ans=tt*2;if(left==1)ans++;if(left>1) ans+=2;
write2(ans);
fo(i,1,K) {if(left>0)a[i]++,left--;}
int cur=2;
fo(i,1,K)
{
write1(1),write2(cur);
fo(j,cur+1,cur+a[i]-1) write1(j-1),write2(j);
cur+=a[i];
}
}

CF827C DNA Evolution

请先思考后再展开

看到明显是模ln,套路地分块,$O(q*(10^2+10n/T+T)) \ge O(q \sqrt {10n})$,code

现在想想分块是无意义的,对每种模数写个树状数组就好了,就是个区间询问的事,当然实现复杂度都差不多

CF827D Best Edge Weight

请先思考后再展开

就是道思博题,把MST建出来,如果是非树边就是路径max-1,同时将路径上的树边对当前边权-1做min

第一个可以倍增实现,第二个可以树剖得出区间,离线扫+可删堆实现,$O(mlog^2)$,code

upd:第二部分基于势能写并查集就能降低到$O(mlogn)$,感觉实现复杂度都差不多

CF827E Rusty String

请先思考后再展开

众所周知周期这东西满足,$\forall d \in Per,i*d \le n的i*d \in Per$

而对于$\forall s_i=A,s_j=B,|i-j|*any \notin Per$,可见ban比找好做,枚举倍数判断即可

这是个卷积,$C_t=\sum A_iB_{i+t}+B_iA_{i+t},A’*i=A*{n-i},C_t=(A’*B)_{n-t}+(A’*B)_{n+t}$

$O(nlogn)$,code

CF827F Dirty Arkady’s Kitchen

题意:给出n点$m \le 5e5$边的无向图,每条边有可用的时间区间,从时刻0在点1出发到n求最短路径,且不能停下脚步

请先思考后再展开

因为是无向的,将每个点周围的边按照相交分成k个独立的组,然后把这个点拆2k份,表示这个组意义下,到达时间奇偶性为0/1的最早时间,那么可用时间就是+若干2,剩下大致上就是个最短路,但是有些细节需要推敲推敲

$O(mlogm)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int n,m;vc< pair<int,pr> > to[N];
vc<pr> hh[N],real[N][2];int findid(int op,int x,int tim){return upper_bound(all(real[x][op]),MP(tim,INF))-real[x][op].begin()-1;}
int dis[N];priority_queue< pr,vc<pr>,greater<pr> > qq;
struct Edge{int x,y,l,r;}e[N];
int cur[N][2];pr bak[N];
pr fix(pr now,int op){if((now.FR&1)^op)now.FR++;/*if((now.SE&1)^op)now.SE--;else now.SE-=2;*/return now;}//debug 因为当时这里写的东西搞了十年
void main()
{
n=qread(),m=qread();fo(i,1,m){int x=qread(),y=qread(),l=qread(),r=qread();hh[x].PB({l,r});hh[y].PB({l,r});e[i]={x,y,l,r};}
int tim=1;
fo(x,1,n) if(sz(hh[x]))
{
sort(all(hh[x]));
fo(op,0,1)
{
pr now=fix(hh[x][0],op);
fo(t,1,sz(hh[x])-1)
{
pr h=fix(hh[x][t],op);if(h.FR>=h.SE)continue;if(now.FR>=now.SE){now=h;continue;}
if(h.FR<=now.SE) chmax(now.SE,h.SE); else real[x][op].PB(now),now=h;
}
if(now.FR<now.SE) real[x][op].PB(now);
cur[x][op]=tim,tim+=sz(real[x][op]);fo(i,cur[x][op],tim-1) bak[i]={x,op};
}
}
if(n==1){write(0);return;}if(!sz(real[1][0]) or real[1][0][0].FR>0) {write(-1);return;}
fo(i,1,m)
{
int x=e[i].x,y=e[i].y;
fo(op,0,1)
{
pr now=fix({e[i].l,e[i].r},op);if(now.FR>=now.SE)continue;
to[cur[x][op]+findid(op,x,now.FR)].PB({y,now}),to[cur[y][op]+findid(op,y,now.FR)].PB({x,now});
}
}
memset(dis,0x3f,sizeof dis);dis[1]=0;qq.push({0,1});int ans=INF;
while(sz(qq))
{
pr now=qq.top();qq.pop();int rx=now.SE,x=bak[rx].FR,op=bak[rx].SE;if(now.FR!=dis[rx]) continue;
for(auto t:to[rx])
{
int y=t.FR,l=t.SE.FR,r=t.SE.SE,go=max(now.FR,l);
if(go>=r) continue;
if(y==n) {chmin(ans,go+1);continue;}
int ry=cur[y][op^1]+findid(op^1,y,go+1);
if(findid(op^1,y,go+1)>=0 and dis[ry]>go+1) dis[ry]=go+1,qq.push({go+1,ry});
}
}
write(ans==INF?-1:ans);
}

cty的写法就不像我的这么多细节

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