8.26~27NOIP五校联考模拟赛

解题报告

---

首先是每个题目的状况

Day1

T1

虽然ans开了long long，但是计算过程中的赋值没有用1ll来存储
就跪了。。。。。。

T2

看到三维的比较立马想起来前段时间做的三维偏序
然后就越看越感觉像CDQ分治
然后就果断放弃这题目了。。。
敲完暴力就又去看T3

T3

虽然想到了子任务4的做法，但是没能实现出来
子任务3只想到了偶数的状态是2，但是没有考虑到奇数的状态会是0

Day2

T1

第一眼就感觉像是贪心经典模型线段覆盖
然后也是按照线段覆盖写的
但是复杂度爆炸，跑不过大样例
想了一个小时也没想到能怎么优化(其实那么短的代码显然没法再优化了啊。。。当时就该换个思路重新做的)

T2

最后20分钟才想起来子任务2可以打表的，结果6 6跑了20分钟没跑出来就GG了

T3

近两个小时手玩m==2的几个情况，结果没找出来规律，又去考虑容斥原理，想想感觉不对就放了（真想扇自己一巴掌）

然后是考场代码

dice
sub
planar

meizi
matrix
random

最后是各个题目的正解思路

Day1

T1

考虑到连续滚动会出现循环，我们只需要对于每行先 $\Theta(1)$ 处理出循环
的部分，剩下的暴力模拟即可

STD

T2

离散化后用树状数组统计顺序三元组和逆序三元组即可即可
时间复杂度 $\Theta(n\log_2 n)$

STD

T3(根本没听懂)

f[i][0/1/2][0/1/2] 表示当前填到第 i 列，右上角的点颜色和左上角左下
角都不同/和左上角相同/左下角相同，右下角的点颜色和左上角左下角
都不同/和左上角相同/左下角相同的方案数。
然后用矩阵乘法进行转移

STD

Day2

T1

考虑到每次选择其实是将这段区间覆盖的位置都+1，最后从最左到最右扫过去，取所有位置上的最大值
把每个区间起点看作 +1，终点看作-1，做前缀和的同时取最大。
加上离散化的时候$n\log_2n$
时间复杂度$\Theta(n\log_2n)$

STD

T2

我们考虑容斥原理。答案 = 全部（每列至少一黑）- 一行全白（每列至少一黑）+ 两行全白（每列至少一黑）

$$ans=\sum_{k=0}^n(-1)^k {n\choose k}(2^{n-k}-1)^m$$
杨辉三角预处理组合数的复杂度是$\Theta(n^2)$，阶乘逆元计算组合数$\Theta(n\log_2n)$

小技巧：阶乘逆元计算可以先计算出最大的那个数字的阶乘逆元然后倒推回去

STD

T3

由期望的线性性:和的期望等于期望的和
我们只需要维护每个元素的值的期望即可
每次的交换操作，左区间每个元素有$\frac{1}{r_1-l_1+1}$的概率被交换，右区间每个元素有$\frac{1}{r_2-l_2+1}$的概率被交换
所以左区间的每个数字有$1-\frac{1}{r_1-l_1+1}$的概率等于原来的值，等于右区间的每个值的概率是$\frac{1}{(r_1-l_1+1)(r_2-l_2+1)}$，右区间同理
所以只需要实现区间加法，区间乘法，区间求和即可，线段树可过
时间复杂度$\Theta(n\log_2n)$
STD