20200606模拟-六中

六中的场

赛况大概是,xgc和rose识别A,另xgc现场切了C,我切了A

A感觉可能以前打某次coj时被叫去看过,发现不一样后好像就没看了,连题解都没留下

想了1h会做了,写暴力加正解花了50min,然后就调了80min……调试主要时间花在gdb上,但我感觉静态查错花的时间可能差不多

「UNR #1」火车管理

题意:有$n \le 5e5$个栈,区间压数,单点弹栈,求区间栈顶和,强制在线

请先思考后再展开

调试时间这么长,一是这几个月基本没写过什么数据结构,然后区间修改的主席树是第一次写,但写错了……

做法比标算时空常数大,然后在uoj上面被hack了,所以就不具体说了,想看的见97pt代码


首先肯定是用个普通线段树实现个区间修改区间求和,现在只关心核心问题:如果求每个栈的下个元素

观察到一个性质:一个数被踢掉时新的栈顶,就是这个数当初被加入时的栈顶

记录$val_i$表示第i次插入的是啥,对于每次插入是个新的时间节点(弹出的话以后不会再访问到所以不用成为新时间节点,在当前时间节点修改就好了)

如果我们能维护每个时刻,每个栈上面的数其实是哪个时候插入的,就能轻松维护弹出了

可持久化线段树维护即可,时空$O(nlogn)$,rose和xgc常数为130N,我则是80N(嘻嘻

完整代码,另给出核心代码:

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
void insert(int fl,int fr,int c,int &x,int l,int r,int oth=-1)
{
if(!x) x=++id; else { int tmp=++id;p[tmp]=p[x];x=tmp; }
if(l==fl and r==fr){p[x].c=c;return;}
if(oth<0) oth=p[x].c;p[x].c=-1;
if(fr<=mid){ insert(fl,fr,c,p[x].lc,l,mid,oth);if(oth>=0) p[x].rc=++id,p[id].c=oth; }
else if(fl>mid){ insert(fl,fr,c,p[x].rc,mid+1,r,oth);if(oth>=0) p[x].lc=++id,p[id].c=oth; }
else insert(fl,mid,c,p[x].lc,l,mid,oth),insert(mid+1,fr,c,p[x].rc,mid+1,r,oth);
}
//---------------------------
if(op==2)
{
int hh=ask(l,rt[ask(l,rt[tim],1,n)-1],1,n);
SGT::ch(l,l,val[hh]),insert(l,l,hh,rt[tim],1,n);
}
else
{
int r=qread();r=(r+lst*ty)%n+1;if(l>r)swap(l,r);
if(op==1) write2(lst=SGT::ask(l,r));
else
{
int c=qread();val[++tim]=c;rt[tim]=rt[tim-1];
SGT::ch(l,r,c),insert(l,r,tim,rt[tim],1,n);
}
}

B

题意:输入$n \le 300$个点对,称一个点$x$是安全的当且仅当对于任意$v=(cos\theta ,sin\theta)(0\leq\theta<2*\pi)$,存在一个输入的点对$(a,b)$,$\exists\epsilon>0,\forall0<y<\epsilon,|a-x|>|a-x-y*v|,|b-x|>|b-x-y*v|$,即从$x$稍微往$v$这个方向走一点,到$a,b$的距离都变小。求安全区域的面积。

请先思考后再展开

考虑点x和点对$(a,b)$间关系,若方向向量为$v$,$v$逆时针旋转$90^{\circ}$得到$v’$

则距离更短等价于,a和b都在$(x,x+v’)$连线右侧那我们干脆就枚举$v’$,这样说起来比较方便

根据题意,合法区域就是各个方向上合法区域的交,而对于一个方向,合法区域就是找到最广的一个半平面,使得该半平面另一侧同时包含一组点

稍作思考,发现如果我们得出的半平面,只经过了一个关键点(至少一个),将$v’$稍微转动,经过的还是这个关键点x

将这种方向贡献到x上,那我们只枚举x与另一个关键点y间连线的方向作为$v’$,也能得到x应当贡献的范围(半平面的交会相同)

复杂度即$O(4n^2*半平面交)$

CF1329E Dreamoon Loves AA

题意:数轴上线段$[0,n]$,已经切开m个位置,递增给出,另外选择$k \le n-m$个位置切开,最小化各段长度的极差

$n \le 1e15,m \le 4e5$

请先思考后再展开

为了方便,算出m+1段的长度$L_i$,段数$K=k+(m+1)$,然后分配段数

思考发现,如果长为L的段要分z段,尽可能均匀分总是最优的(即$ (z-L\%z)*\lfloor L/z \rfloor+(L\%z)*\lceil L/z \rceil $)

考虑答案的值域区间为$[L,R]$,考虑每段的合法段数,相当于有两个限制:$\forall i, \lceil \frac{L_i}{R} \rceil \le \lfloor \frac{L_i}{L} \rfloor$,$ \sum \lceil \frac{L_i}{R} \rceil \le K \le \sum \lfloor \frac{L_i}{L} \rfloor$

条件二比较容易,二分求出最大的L0和最小的R0,则有限制$L \le L0,R \ge R0$,于是只需要关注条件一

如果$L0 \ge R0$,我们能做到答案为0:选取任意$L=R \in [R0,L0]$,已知$\forall i, \lceil \frac{L_i}{R} \rceil \ge \lfloor \frac{L_i}{L} \rfloor$,而条件二已满足,故$\forall i, \lceil \frac{L_i}{R} \rceil = \lfloor \frac{L_i}{L} \rfloor$

如果$L0<R0$,考虑到$\lceil \frac{L_i}{R} \rceil \le \lfloor \frac{L_i}{L} \rfloor+1$,如果第i个位置没满足,要么将上界提高1(相当于$L \le x_i$的限制),要么将下界降低1(相当于$L \ge y_i$的限制)。算上之前两个,把限制表示成二元组$(x_i,y_i),表示L \le x_i、R \ge y_i$至少满足一个,统一考虑。

按照x递增排序,则一个L可以只在乎一段前缀,维护他们的max即可

总复杂度为$O(mlogn)$

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
ll pos[N],L[N];
void main()
{
fo(T,1,qread())
{
ll n=qread();int m=qread();ll K=qread();
if(m==0){ write2(n%(K+1)==0?0:1);continue; } K+=(m+1);
fo(i,1,m) pos[i]=qread();pos[m+1]=n;fo(i,1,m+1) L[i]=pos[i]-pos[i-1];
ll L0=-1;
for(ll l=1,r=n;l<=r;)
{
ll mid=(l+r)/2;
ll gr=0;fo(i,1,m+1) gr+=L[i]/mid;
if(gr>=K) L0=mid,l=mid+1; else r=mid-1;
}
ll R0=-1;
for(ll l=1,r=n;l<=r;)
{
ll mid=(l+r)/2;
ll gl=0;fo(i,1,m+1) gl+=(L[i]+mid-1)/mid;
if(gl<=K) R0=mid,r=mid-1; else l=mid+1;
}
if(L0>=R0){ write2(0);continue; } assert(L0>0 and R0>0);
map<ll,ll> hh;hh[L0]=bin(60),hh[-bin(60)]=R0;
fo(i,1,m+1)
{
ll x=L[i]/L0,y=(L[i]+R0-1)/R0;
if(y>x) x++,y--,x=(L[i])/x,y=(y==0?bin(60):(L[i]+y-1)/y),chmax(hh[x],y);
}
ll ans=bin(60),premx=0;for(auto in:hh) chmin(ans,premx-in.FR),chmax(premx,in.SE);write2(ans);
}
}

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