20191029模拟-xgc

xgc的场

「雅礼集训 2018 Day2」颜色

题意:给出一个长度为n的序列,q次强制在线询问,每次给出若干区间,回答这些区间一共有多少不同的数,$n,区间个数和 \le 1e5$,时限1.5s,空间20M

请先思考后再展开

$n(值域)=1e5,m(长度、询问数)=1e5$

因为是每次多个区间,我们要想办法快速合并信息,所以肯定不是直接用前缀和而是用bitset

不太好搞的合并信息,可以考虑一下根号算法,先给序列分块

如果每个块直接一个bitset到时候合并肯定时不行的,一个自然的想法是预处理每个块区间的bitset

直接这样做就是$(\frac{m}{T})^2*\frac{n}{w}+m*(2T+\frac{n}{w})$,注意到时间勉强(3亿)可以而空间是主要矛盾,现在是$(\frac{m}{T})^2*\frac{n}{w}$

注意到时间复杂度上,我们是$O(1)$获取了整块区间bitset,而其实改成$\frac{n}{w}$都是没有问题的,能否牺牲这个换空间?

再考虑核心矛盾主要用来存储范围是$\frac{m}{T}$的所有区间信息的合并,然而$[l,r]=[l,xx] \cup [xx+1,r]$,这些区间信息是可以通过预处理省去不少的

通俗来说就是ST表预处理,于是时间复杂度为$\frac{n}{w}*(\frac{m}{T})log(\frac{m}{T})+m*(2T+\frac{n}{w})$,空间复杂度为$\frac{n}{w}*(\frac{m}{T})log(\frac{m}{T})$,为了空间限制时间为2亿

其实可以进一步优化,回到题目的特性是多少不同的数,对于只出现一次的数,一个前缀和完事,于是$n(值域)=5e4,m(长度、询问数)=1e5$,于是块大小大概300就行了

XSY #3478 取石子

题意:一开始小A有x个石子,小B有y个石子。给出长为n的序列表示进行n轮游戏,奇数轮小A从小B那取走$a_i$个,偶数轮小B从小A那取走$a_i$个,如果某次取不了这么多就取到没有为止。多次询问,每次询问前修改x、y、a的某位,$n,q \le 1e6$

请先思考后再展开

$$
\\显然总和sum一定,只需要关注小A手上的石子,B_i=A_i*(i奇?1:-1),x=max(min(x+B_i,sum),0)
\\设B的和S,最小前缀和mi,最大前缀和mx,则如果mx-mx \ge S,答案与x无关
\\否则,答案为 min(max(x+S,0+(S-mi)),sum-(mx-S))
$$
将上述内容放到线段树上即可支持维护,查询就在上面二分,$O(nlogn)$

loj6558「CERC2018」Game of Stones

此题为候选,最后并没有出

请先思考后再展开

首先我不是特别懂sg的那套理论,本来想用点小聪明,通过设置两维状态来规避公平组合游戏中双方可行操作相同的限制,但似乎gg了

分类讨论,A=B直接巴什博弈;否则,大致思路是考虑尼姆博弈,即考虑将局面变成都在$C=min(A,B)$以内,然后考虑能否随心所欲掌控sg值,记住各个游戏间,操作顺序并没有意义

一、A>B

设只有一堆超过C,那么归纳或者感受一下可以发现,最后总是可以给对方一个【都在C内,sg异或和=0】的局面,因为自己的可行操作数严格大于对手;多堆的话,其他堆乱玩即可

二、A<B

假如只有一堆,那么能获胜当且仅当能一步把局面变成【都在C内,sg异或和=0】给对手。如果有多堆,那一定输,思维同上

code

CF1096E

终于有我会做的题了……

请先思考后再展开

$$
\\分子=\sum_{mx=r} \sum_{i=1} C_{n-1}^{i-1}/i*f(sum-i*mx,n-i,mx) ,分母=\sum_{mx} f(sum-mx,n-1)=\sum_{mx} C_{sum-mx+n-2}^{n-2}=C_{sum-r+n-1}^{n-1}
\\f表示和、数量、上界(开区间),f(sum,0,mx)=[sum=0],f(sum,n,mx)=\sum_{i=0}^n (-1)^i C_{n}^{i} C_{sum-i*mx+n-1}^{n-1}
\\分子=\frac{1}{n}*\sum_{mx=r}^{sum}[sum-n*mx=0] +\sum_{i=1}^{n-1} \sum_{j=0}^{n-i} C_{n-1}^{i-1}/i*(-1)^j C_{n-i}^j \sum_{mx=r}^{sum} C_{sum-(i+j)*mx+n-i-1}^{n-i-1},最坏O(Sn^2)
\\似乎除了fft也没啥再能优化的了,让我们回到最顶上那个式子
\\考虑分子算出来东西的本质,就是C_{n-1}^{最大值个数-1}/最大值个数*【剩下<最大值的方案数】=\frac{1}{n} *C_{n}^{最大值个数}*【剩下<最大值的方案数】
\\注意到后面的部分其实就是【最大值 \ge r】的方案数,直接调用一次f求,单组询问O(n)
$$

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