【赛题整理】校内模拟赛选整 · E1

校内模拟赛选整

大概难度都是TG里面$2$~$3$左右的。

$A$

给定直线上$n\leq 2000$个建筑的坐标,两种覆盖方式,$A:$覆盖长度为$L$,可以用$p$次;$B$:覆盖长度为$2L$,可以用$q$次。求最小的$L$.


首先就是可以知道$p,q$可以缩到$p+q\leq n$,否则答案就是$1$。

之后考虑二分一个$L$,$check$其正确性。$check$时感觉贪心并不是很好贪,可能会有比较妙的贪心,但这个地方选择一种更加稳妥的$dp$。考虑$f_{i,j}$表示两种覆盖分别用了$i,j$个最多能覆盖到哪个建筑,则

其中$go_x[P]$表示在位置$P$使用第$x$种覆盖能够覆盖多少建筑。于是最后复杂度$O(n^2\log n)$.

$B$

定义string类型的递推$f_0=’0’$,$f_1=’1’$,$f_i=f_{i-2}+f_{i-1}$,其中$+$表示string类型的连接。多组询问,询问$f_n$中区间$\rm [L,R]$内的串。$n\leq 1e9,~\rm L\leq R\leq 2e9,\sum (R-L)\leq 1e7$


拿到这题首先应该手写出前$6$项来找规律……

发现$f_i.size()$就是斐波那切数列的第$i$项,并且序号奇偶性相同的两项$f_i,f_j$,当$j<i$时满足$f_j$是$f_i$的前缀,这东西可以数学归纳出来并且肉眼看不出来

之后可以发现$\rm L,R\leq 2e9$,而斐波那切数列的第$50$项已经超过了这个范围。于是考虑对于一个询问$f_n[L,R]$,先把$n$缩到$50$以内,然后分奇偶性赋值为$48/49$,然后每次考虑把$f_n$分成$f_{n-2}+f_{n-1}$,分治下去。注意到其实是可以预处理一些状态来提速,于是选择预处理前$20$项左右。

1
2
3
4
5
void solve(int n, int L, int R){
if (n <= 20) return cout << f[n].substr(L, R - L + 1), void() ;
if (L < fib[n - 2]) solve(n - 2, L, min(R, fib[n - 2])) ;
if (R >= fib[n - 2]) solve(n - 1, max(0ll, L - fib[n - 2]), R - fib[n - 2]) ;
}

$C$

我们有一张方格纸,他大概长这样:

我们现在要从左上角$(0,0)$到右下角$(n,m)$画一条直线,然后询问它经过黑格子的长度与总长度的比值,并输出一个互质分数的形式。

sb结论题,以下是结论,觉得证的挺好的(

无论怎样,$rqy$太强了!!

以下是$rqy$给的严谨证明:

  • 对于每个二元组$(n,m)$,$(\frac{n}{\gcd(n,m)},\frac{m}{\gcd(n,m)})$ 的本质与$(n,m)$是一样的。

  • 当$n$是偶数或者$m$是偶数的时候,答案显然是$\frac{1}{2}$,因为我们可以考虑把所有的颜色翻转,答案是一样的。

  • 余下的情况,由于我们现在已经缩小了问题规模使得$n,m$互质,所以只有可能是$n、m$均为奇数,此时我们考虑如下(前方高能):

  • 由于横向有$m$段,纵向有$n$段,所以总共这条直线可以分成$n \times m$段,当然,有些段的颜色相同。我们这么做的目的是为了保证每一段不会跨过每个格子的边界,即同一段的每个部分都会是相同的颜色

  • 通过观察可以得到,对于从左上到右下的第$i$段,它应该在第$\lfloor \frac{i}{n} \rfloor$,第$\lfloor \frac{i}{m} \rfloor$。注意这个地方,虽然$n$表示的是行,但是$\lfloor \frac{i}{n} \rfloor$表示的是列。道理其实很简单:

    • 对于第$i$段,它占的部分是$\frac{i}{n \times m}$ ,所以所属的行应该是$\lfloor \frac{i}{n \times m} \cdot n \rfloor$,所属的列为$\lfloor \frac{i}{n \times m} \cdot m \rfloor$,约分一下答案显而易见。
  • 基于前两条,我们会有一个比较平凡的结论:对于某一段$i$,当$\lfloor \frac{i}{n} \rfloor + \lfloor \frac{i}{m} \rfloor$为偶数的时候,这一段在黑色的格子上;是奇数的时候,这一段在白色格子上。

  • 我们可以考虑对$\lfloor \frac{i}{n} \rfloor + \lfloor \frac{i}{m} \rfloor$搞一些事情:

上式的目的其实就是通过对$2$取模建立同余式,由于$n,m$均为奇数,所以在$\mod 2$意义下都是$1$,可以直接除掉。那么接下来我们考虑,这样的$i$有多少个呢?很显然的,在$0 \to n - 1$中,共有$\frac {n-1}{2}$个奇数,$\frac{n+1}{2}$个偶数;在$0 \to m-1$中,共有$\frac {m-1}{2}$个奇数,$\frac {m+1}{2}$个偶数。因为只有奇偶性相同时,才属于黑色格子,所以由中国剩余定理得

那么最终答案就是

$D$

给定一棵树,某些点是关键点。每条边有代价,每次可以删掉一条边并且获得这条边的代价。求最少的代价,使得所有关键点不连通。$n\leq 300,000$


直观的想法是$dp$,即记$f_x$表示处理完以$x$为根的子树内的关键点(不互相连通)的最少代价。但是发现这样似乎很难转移,因为转移时要考虑子树之间的关键点是否连通。于是考虑再记$g_x$表示处理完以$x$为根的子树内关键点互相不连通,且不与外界连通的最小代价。

那么考虑转移,记$x$为当前节点,$y$为$x$的子节点:

  • 当$x$为关键点时,有:

  • 当$x$不为关键点时,有

唔,这个第二个转移的$f_x$还是需要编一编的,大概就是考虑现在只需要不让子树内部连通,那么就可以选出一棵子树来内部不连通,其他子树都不和外部连通,可知这样是最优的(因为天选之子不需要“不和外部连通”)。

学习了,学习了。

$E$

现在有如下一个表达式: $0 ~a_1 b_1 a_2 b_2 … a_n b_n$。其中$a_i$为一个位运算符($\boldsymbol{and/or/xor}$),$b_i$是一 个整数。每一对$a_i,b_i$有$c_i$的概率会消失,求表达式的结果的期望。


需要建立某种神秘的条件反射,就是遇到位运算的题目就要想到“位与位之间是无关的”。那么就可以直接按位做,令$f_{i,0/1}$表示计算完前$i$对,现在这一位为$0/1$的概率是多少。转移时别忘了加上当前这一对被删除的概率,即$f_{i-1,0/1}$。