JOI2020 final

link

T1 「JOI 2020 Final」只不过是长的领带

请先思考后再展开

微扰易知最优匹配方案为两边排序后对应配,$O(n)$

1
2
3
4
5
6
7
8
pii a[N];int b[N],pre[N],suf[N],ans[N];
void main()
{
int n=qread();fo(i,1,n+1) a[i]={qread(),i};sort(a+1,a+n+2);fo(i,1,n) b[i]=qread();sort(b+1,b+n+1);
fo(i,1,n+1) pre[i]=max(pre[i-1],max(a[i].FR-b[i],0));
fd(i,n+1,1) suf[i]=max(suf[i+1],max(a[i].FR-b[i-1],0));
fo(i,1,n+1) ans[a[i].SE]=max(pre[i-1],suf[i+1]);fo(i,1,n+1) write1(ans[i]);
}

T2 「JOI 2020 Final」JJOOII 2

请先思考后再展开

显然可以理解为先做开头和结尾,再做中间,即找个子串,然后匹配子序列。

问题变成寻找K级JOI串的最短母串,直接记录每种字符第几次在哪出现即可,$O(nlogn)$,想线性可以移动指针

1
2
3
4
5
6
7
8
9
10
11
int n=qread(),K=qread();scanf("%s",str+1);fo(i,1,n) pos[i]=sz(in[str[i]]),in[str[i]].PB(i);
int mi=INF;
fo(l,1,n) if(str[l]=='J')
{
int r=l;
int wt=pos[r]+K-1;if(wt>=sz(in['J'])) continue;
r=lower_bound(all(in['O']),in['J'][wt])-in['O'].begin();if(r>=sz(in['O'])) continue;r=in['O'][r];
wt=pos[r]+K-1;if(wt>=sz(in['O'])) continue;
r=lower_bound(all(in['I']),in['O'][wt])-in['I'].begin();if(r>=sz(in['I'])) continue;r=in['I'][r];
wt=pos[r]+K-1;if(wt>=sz(in['I'])) continue;r=in['I'][wt];chmin(mi,r-l+1-K*3);
}write(mi==INF?-1:mi);

T3 「JOI 2020 Final」集邮比赛 3

请先思考后再展开

直接DP,$O(n^3)$

1
2
3
4
5
6
7
8
int n=qread(),L=qread();fo(i,1,n) pos[i]=qread();fo(i,1,n) tim[i]=qread();pos[n+1]=L;
mem(dp,0x3f);dp[0][n+1][0][0]=0;int ans=0;
fo(cnt,0,n) fo(i,0,n) fd(j,n+1,0) fo(lst,0,1) if(i<j)
{
int now=dp[i][j][cnt][lst];if(now==INF) continue;chmax(ans,cnt);
if(i<n){ int t=now+(lst?(pos[i+1]-pos[i]):(L-pos[j]+pos[i+1]));chmin(dp[i+1][j][cnt+(t<=tim[i+1])][1],t); }
if(j>0){ int t=now+(lst?(L-pos[j-1]+pos[i]):(pos[j]-pos[j-1]));chmin(dp[i][j-1][cnt+(t<=tim[j-1])][0],t); }
}write(ans);

T4 「JOI 2020 Final」奥运公交

题意补充:是1到n来回

请先思考后再展开

分为边方向相同起点不同的两张图考虑,那么问题就是翻转某条边后最短路,则只需考虑终点到根路径上的最短路树边,只有$O(n)$条,枚举考虑每一条,直接翻转后暴力建图,稠密图$O(n^3)$

T5 「JOI 2020 Final」火灾

简洁题意:快速模拟,每时刻$a’*i=max\ a*{i-1},a_i$,询问某时刻区间和

请先思考后再展开

想了个不知复杂度的暴力,写个算复杂度的code过了所有数据:将一段相同的数看做一个块,将递减的块看做一条链,那么每次就是遍历至少两个块的链,修改首尾两个块的大小。求和口胡是可以dsu+树状数组上二分的,但需要先知道复杂度

考虑良久觉得是线性(下面都是讨论$\sum 至少两个块的链个数$,忽略数据结构的复杂度),和rose讨论半天卡成$O(nlogn)$:从一个链开始分割,每次把一条链均匀分成两个($(A)>(B) \to (A>C),(B>D)$),这样是log层,每层$O(n)$

因为没法证明复杂度,就没有写代码的动力的,不然还是个暴力的身份,虽然走位很蛇皮

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
struct Nod{ int l,r,num,siz; }p[N];
struct Link{ int ed,siz;bool gg; }A[N];//A[i].st=stpos=i
void merg(int x,int y)
{
int aa=A[x].ed,bb=y;A[y].gg=1,A[x].siz+=A[y].siz;
if(p[aa].num==p[bb].num) p[aa].siz+=p[bb].siz,bb=p[bb].r;
if(bb) p[aa].r=bb,p[bb].l=aa,A[x].ed=A[y].ed;
}vc<int> big;
void main()
{
int n=qread(),q=qread();fo(i,1,n) A[i].ed=i,p[i].num=qread(),A[i].siz=p[i].siz=1;
int lst=1;fo(i,2,n) if(p[A[lst].ed].num>=p[i].num) merg(lst,i); else lst=i;
fo(i,1,n) if(!A[i].gg and i!=A[i].ed) big.PB(i);
int cnt=0;
fo(tim,1,n)
{
vc<int> big2;
fd(t,sz(big)-1,0)
{
int id=big[t];
p[id].siz++,p[A[id].ed].siz--;
if(!p[A[id].ed].siz)
{
A[id].ed=p[A[id].ed].l;
int nxt=id+A[id].siz;if(nxt>n) continue;
assert(!A[nxt].gg);merg(id,nxt);cnt++;
}
}
for(auto id:big) if(!A[id].gg and id!=A[id].ed) big2.PB(id);big=big2;
}
write1(n),write2(cnt);
}//半成品

正解是$O(nlogn)$的,然而对比较麻烦的数据结构题不感兴趣

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