模拟赛简要题解

发布时间 2023-12-27 09:57:24作者: Pengzt

11.16(C0389)

100+10+50=160,rk3。

本来 BC 都应该写出来的。

A:dp 或 贪心 都可以,贪心直接从下往上覆盖即可。

B:

注意:这里的 \(\oplus\) 指的是按位或

合法条件可以化简为:\(\oplus_{i=1}^{p}a_i = \oplus_{i = p+1}^{n}a_i\)

继续挖掘。看到位运算肯定想到拆位,考虑每一位第一次和最后一次出现的位置。枚举或和相等的位置 \(p\),令第 \(i\) 位为 \(1\) 的最左边的数为 \(l_i\),最右边为 \(r_i\)。则 \(\forall l_i,r_i\) 满足 \(\bigcap\limits_{i=0}^{k-1}[l_i, r_i]\neq \varnothing\) 时为合法条件。此时的方案数为 \(((2^p-1)(2^{n-p}-1)+1)^k\),但是最后的 \([l,r]\) 可能会有多个 \(p\) 产生贡献,所以要减去 \(((2^p-2)(2^{n-p}-1)+1)^k\),即强制 \(l_i = p\)

最后还要加上一个 \(1\),因为全 \(0\) 也是可以的。

C:

D:

11.17(C0390)

A:直接贪心即可。

B:

只会 \(\mathcal{O}(m^3\log m)\) 做法。

看到 \(n=10^9,m=200\) 是容易想到矩阵的。

考虑 dp。

\(f_{i, j}\) 表示填了 \(i\) 个数,前面有 \(j\) 个互不相同的数(包含 \(j\))。转移是容易的:\(f_{i, j} = (m - j + 1)\times f_{i - 1, j - 1} + \sum\limits_{k = j + 1}^{m - 1}f_{i - 1, k}\)

然后发现后面的东西可以直接矩阵优化,快速幂即可。

反正我是不会 \(\mathcal{O}(m\log m)\) 的做法的。

C:

大模拟什么东西,没调出来。

D:

DS,原题 P4690

校内模拟赛大常数 \(\mathcal{O}(n^\frac{5}{3})\) \(3s\)\(2\times10^5\) 也是离谱。

11.22(C0392)

考的很烂,T2 没写出来,只有 154pts。

A:

先写一下赛时做法。

首先肯定要拆掉绝对值的符号,先把 \(x\) 离散化,然后发现按 \(w_i\) 从大到小的选择一定最优。但是发现如果这样会有点被多次选择,于是就会退化到 \(\mathcal{O}(n^2)\)

优化的话直接上势能线段树即可。

题解是直接拆掉绝对值解不等式,即变为两个恒等式:

\( \left\{ \begin{aligned} x_i-x_j\le w_i-w_j \\ x_j-x_i\le w_i-w_j \end{aligned} \right. \)

然后再变一下:

\( \left\{ \begin{aligned} x_i-w_i\le x_j-w_j\\ x_i+w_i\ge x_j+w_j \end{aligned} \right. \)

现在将 \((-x_i+w_i, x_i+w_i)\) 看作一个点,则变为删一个点就删去它左下角的所有点,排序后做一下就行了。

B:

赛时为什么没有做出来呢?赛时为什么没有做出来呢?赛时为什么没有做出来呢?

你发现这个 \([S,T]\) 是很烦的,做一个容斥,分别统计 \(1\sim S-1\)\(1\sim T\)

然后把每个 \([A_i,B_i]\) 变成 \(2X_i+P_i\),这样就可以求出 \(X_i\) 的范围,也不需要考虑奇偶数了,然后还能求出 \(\sum X_i\) 的范围。

然后发现这玩意儿还是不好做,继续容斥。

因为很不爽的是这个 \(X_i\) 有上界,如果把上界去掉,就可以变为 \(X_1+X_2+\dots+X_n\in[L,R]\),同时减去所有下界,就变为 \(n\) 个非负整数在 \([L,R]\) 内,对 \([L,R]\) 再做容斥变成 \(1\sim L-1\)\(1\sim R\)。变为 \(\sum X_i\le V\)\(X_i\) 为非负整数。你这时候再加上一个数把小于变成等于,插板法即可。

C:做一个树形 dp。

具体地,你发现点性质,然后就能知道就是把树的直径的中间的那条边给提出来,对两边分别作。

就分为路径经过和不经过直径讨论一下,经过直径的路径在套一个桶上去就行了,然后要预处理一下 \(rt_{1/2}\to u\) 的高度。

代码

D:咕咕咕。

11.24(C0394)

没打,但是感觉挺简单。后面看一下 B。

11.24-26

烦烦烦,发烧了,头很晕。

11.27(C0398)

头很晕,直接垫底。

A:很简单其实,但是我写的很麻烦。

当时在想两个点满足所有 \(1\sim i\) 时,路径上有 \(i+1\) 就很麻烦,当时是解决了,但是是否能形成路径这上面有点问题,不想调了,于是就换了一种写法。

直接统计 \(ans\) 的后缀和的数组就十分简单了,就可以最后进行一个查分,然后判断是否是一条路径可以判断每个点的度数,然后因为最多加入 \(n\) 个点,所以这里可以暴力向上跳,对 \(u\) 周围所有的 \(d\) 都进行更新即可。

B:简单题,考场上因为头晕直接摆烂了,就只口胡了一下。

去掉所有平方因子是显而易见的。

先看 \(k=0\) 的情况。肯定想 dp,\(f_i=\min f_j+1\),条件是 \([j+1,i]\) 之间的数没有重复。但你这样是 \(\mathcal{O}(n^2)\) 的。然后优化挺显然,就是这个 \(f\) 单调递增,所以处理一个 \(pre\) 数组表示第 \(i\) 个数最前面的满足 \([pre_i+1,i]\) 无重复即可,这个 \(pre\) 显然可以预处理。

然后带修也差不多,处理 \(pre_{i,j}\) 表示第 \(i\) 个数经过 \(j\) 次修改后最前面能到哪,这个东西也比较好处理,dp 方程加一维带一个权就行了,复杂度变成 \(\mathcal{O}(nk^2)\)

C:

如果胜负不确定,有最优策略这个东西就很难做。

但是你发现后手必胜,具体地待会儿证明,然后就只需要知道有多少最终态。

肯定如果有空格的话,一定是 A_B 或 B_A 的形式,因为 A_A 中间能填一个 B,两个空格怎么都能继续填。然后是个环,所以先拆成链,然后去掉空格肯定是 ABABABABAB,最后肯定不是 A,因为是一个环,然后枚举空格数组合统计一下即可。

D:先咕一下。

11.29(C0400)