20200530模拟-六中

六中(lhy+dqa)的场

赛况大概是,rose100+50+100,除pb外会A
后面写暴力有点赶,写B的20写得心情烦躁,导致没有检查出C题意看错,补个离散化可得60,另B的20也丢了

感觉更正确的顺序应该是,在写B之前仔细检查别的题,确保没事干后再开写,毕竟20换心态=血亏


补完题感觉,这已经是近几次比赛中最简单的了,但我现在的思维深度、广度虽然海星,但速度是真的不太行

不知咋办啊,因为打abc的时候是不会这么觉得的

CF1348F Phoenix and Memory

题意:给出n个区间,值域为n,保证存在至少一种方案,能在每个区间中选出一个数,最终组成一个排列,问能否构造任意两个不同的方案

请先思考后再展开

先贪心找到这个一个方案:从左往右考虑,每次在覆盖左端点的区间中,挑右端点最小的

然后看做一个$n\times n$的网格,第i行是提供数i的那个区间(当做类似主元的东西),两行能交换当且仅当区间包含了对方的主元,而如果是环形那种交换方式,考虑到每行都是区间,所以一定能找到可行交换的两行,所以只需要判断行的交换

ST表,$O(nlogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vc<pii> on[N];pii a[N];int b[N],ans[N];int max2(int x,int y){return a[b[x]].SE>a[b[y]].SE?x:y;}
int LOG[N],mx[20][N];int ask(int l,int r){ int lg=LOG[r-l+1];return max2(mx[lg][l],mx[lg][r-bin(lg)+1]); }
void main()
{
fo(i,2,N-1) LOG[i]=LOG[i>>1]+1;
int n=qread();fo(i,1,n) on[i].clear();
fo(i,1,n){ int l=qread(),r=qread();on[l].PB({r,i}),a[i]={l,r}; }
priority_queue< pii,vc<pii>,greater<pii> > now;
fo(i,1,n)
{
while(sz(now) and now.top().FR<i) now.pop();
for(auto in:on[i]) now.push(in);
int id=now.top().SE;now.pop();ans[b[i]=id]=i;
}
fo(i,1,n) mx[0][i]=i;fo(t,1,19) fo(i,1,n-bin(t)+1) mx[t][i]=max2(mx[t-1][i],mx[t-1][i+bin(t-1)]);
pii more={0,0};fo(x,1,n) if(a[b[x]].FR<x){ int hh=ask(a[b[x]].FR,x-1);if(a[b[hh]].SE>=x) more={hh,x}; }
puts(more.FR?"NO":"YES");
fo(i,1,n) write1(ans[i]);puts("");
if(more.FR){ swap(b[more.FR],b[more.SE]);fo(i,1,n) ans[b[i]]=i;fo(i,1,n) write1(ans[i]); }
}

B

题意:$n \le 5e5$条值域1e9的线段从1到n编号,显然有$(n+1)n/2$种方案选择一段区间的线段,每个方案的权值为区间内所有线段的并集长度,输出权值前$K \le 1e9$大的方案的权值和

请先思考后再展开

只想到了空间$O(n)$时间$O(loga*nlogn)$的做法:记位置为区间序列下标,pos为值域位置(离散化后)

基本思路是,考虑到被覆盖次数是非负数,每次只关心0的pos的信息,可以当做维护最小值的相关信息

先二分,要求权值不超过mid的区间数,双指针+线段树维护最小值的个数;这同时也求出了每个右端点对应的左端点,那么接下来只需要在二分外求答案

再次重复该过程,右移右端点,那么就是对于每个cnt=0的pos考虑其在左端点左边,最晚出现的位置,对这东西求和,这就是在右移左端点的时候做区间修改,很好做

发现瓶颈在第一部分,但不太会优化……


不及格的OI选手忘记了很基本的套路,见套路集锦-其他-5

因此,右移右端点的时候,维护每个位置的答案,那么插入一个区间的时候,就是做若干区间加,因为是双指针可以直接差分实现,这样第一部分就优化成了$O(loga*n)$

然而有了这些分析后,第二部分也可以优化成线性了,毕竟我们已经时刻维护着整个信息了(当然对答案贡献需要稍作讨论)

两部分没法合并,因为第二步求前缀和的时候需要求的是严格>第k大的和

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
struct Data{int l,r,c;friend bool operator < (Data x,Data y){return x.r!=y.r?x.r<y.r:x.l<y.l;} };
int cx[N];vc<Data> a[N];
void main()
{
int n=qread();ll K=qread();set<Data> ss;ss.insert({1,INF,0});
fo(i,1,n)
{
int l=qread(),r=qread()-1,bkl=l;//原题意为,数轴区间
while(l<=r)
{
set<Data>::iterator it=ss.lower_bound({0,l,0});
if(i==2)
deb;
if(it==ss.end() or (*it).l>l) break;
Data now=*it;ss.erase(it);int tl=max(now.l,l),tr=min(now.r,r);l=tr+1;
a[i].PB({now.c+1,i,tr-tl+1});
if(now.l<tl) ss.insert({now.l,tl-1,now.c});
if(tr<now.r) ss.insert({tr+1,now.r,now.c});
} ss.insert({bkl,r,i});
}
ll lim=0;//lim=第k大是什么
for(int l=1,r=INF;l<=r;)
{
int mid=(l+r)/2;ll s=0;mem(cx,0);
for(int i=1,j=0,now=0;i<=n;i++)
{
for(auto in:a[i]){ cx[in.l]+=in.c,cx[in.r+1]-=in.c;if(in.l<=j) now+=in.c; }
while(now+cx[j+1]>=mid) j++,now+=cx[j];s+=j;
}
if(s>=K) l=mid+1,lim=mid; else r=mid-1;
}
ll s=0,sum=0,ans=0;mem(cx,0);
for(int i=1,j=0,now=0;i<=n;i++)
{
for(auto in:a[i])
{
assert(in.r==i);sum+=1ll*max(j-in.l+1,0)*in.c;
cx[in.l]+=in.c,cx[in.r+1]-=in.c;if(in.l<=j) now+=in.c;
}
while(now+cx[j+1]>lim) j++,now+=cx[j],sum+=now;s+=j;ans+=sum;
}
write( ans+lim*(K-s) );
}

C

题意:给一个长度为$n \le 5e4$的序列,构造操作方案使其有序,每次翻转一段区间,要求翻转区间长度之和不超过2e7

请先思考后再展开

感觉模型和解法都好熟悉啊,排序题都这样?

其实想过归并、快排的,先把归并排除了,然后对快排的理解有偏差,最终与正解擦肩而过惹……

对排列做快排,对于当前区间对应值域$[l,r]$,将$[l,(l+r)/2]$的数移动都左边,然后分治下去

那么现在就是要解决子问题:只有0和1,要排序

我想到的做法是,将连续的0、1缩起来,每次操作可以将0101变成0110,四个四个做,一层做下来的总长为n,块数/=2

标算做法是,归并排序,两边做好后是00011111|0000111,一次交换即可,十分优美,这我tm都没想到

复杂度为$O(nlog^2)$

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