NOIP十连测

$A$：A. 22NOIP十连 Day 1 报数：$100/100$

先将所有的数字排序。枚举平均数的位置，假设 $a_i$ 是第⼀个能被选的数字。我们需要选尽量多大于等于 $a_i$ 的数字满足平均数小于 $a_i$，于是只要考虑尽量多的选取⼀个前缀即可

$B$：B. 22NOIP十连 Day 1 数列：$100/100$

可以考虑从前往后，按顺序贪心确定每条边的大小。对于⼀条非树边 $(u,v)$，考虑生成树上 $u,v$ 之间的路径上有 $k$ 条树边没确定，那么把这些树边按顺序从小到大赋值，然后把这条树边赋上 $k+1$ 即可。因为⼀条边被赋完值之后不会再被修改，所以可以用 并查集 实现，也就是确定的边直接缩起来，时间复杂度 $O(n\log n)$

$C$：C. 22NOIP十连 Day 1 方差：$20/100$

可以发现，最后肯定是删除经过某些位置的所有区间

记 $dp[i]$，表示当前切到 $i$ 这个位置，然后从大到小枚举上⼀段切什么地方，然后考虑 $[i,j]$ 之间的区间只保留价值最大的 $k$ 个，用堆维护一下就可以了。时间复杂度 $O(n^2\log n)$

$D$：D. 22NOIP十连 Day 1 棋局：$0/100$（没想部分分：$-10$）

将一个矩形内部的的格子都加 $1$，容易想到差分，相当于四个端点分别加上⼀个数，然后⼀个查询相当于左下的数字之和

⾸先把横的和斜的移动分开来考虑

对于横的移动，相当于加了给⼀条横的线整体加了⼀个数，我们对于竖着⽅向扫描线，相当于区间加，区间求和

对于斜的移动，不妨考虑斜率为 $-1$。对于⼀个询问点，考虑所有 $x+y\le px+py$ 的线段，那么交集为线段的⻓度分别减去 $x,y$ 超出的部分，所以对 $x+y$ 扫描，分别维护⼀下 $x,y$ 的线段树即可

$A$：A. noip十连测day2-t1：$50/100$（完全背包挂了：$-50$）

发现到 $a_i$ 和 $x$ 一共只有十种不同的数，也就是说砝码的出现情况只有 $2^{10}=1024$ 种

那么可以预处理对于这 $2^{10}=1024$ 种方法，每一种重量能不能称出来。复杂度是 $O(2^{10}\times m)$。用线段树维护区间覆盖，区间中有哪些数即可。因为只有 $1024$ 个数，所以用一个 $\text{int}$ 存储即可

$B$：B. noip十连测day2-t2：$60/100$（没有预处理 $i^n$：$-20$）

显然 $L_1$ 到 $L_n$ 中最大值要等于 $L_{n+1}$ 到 $L_{n+m}$

那么可以枚举最大值计算答案：$ans=\sum\limits_{i=1}^k (i^n-(i-1)^n)(i^m-(i-1)^m)$ 时间复杂度 $O(k\log n)$

$C$：C. noip十连测day2-t3：$0/100$（暴力挂了：$-40$）

可以看成是一颗树，每条边选择一个颜色，让相邻边不 同的最多。可以发现如果一条边有三种颜色，那么这条边一定可以选出一种颜色使得于另外两边颜色都不相同，所以可以看成只有一种以前没有出现过的颜色

记 $f[u][j][0/1][0/1]$ 表示从 $u$ 往上跳 $2^j$ 步，最前面和后面的两条边分别是第一种颜色还是第二种颜色。预处理后倍增转移即可

时间复杂度 $O(2^4\times n\log n)$

$D$：D. noip十连测day2-t4：$0/100$（$O(n^2)$ $\text{dp}$ 写挂：$-30$）

$30$ 分做法：设 $dp[u][j]$ 表示以 $u$ 为根的树，$A_i=j$ 的权值最大和。直接转移即可：$dp[u][j]=\sum \max_{k\le w-j}(dp[v][k])$

$A$：A. noip十连测day3-难：$40/100$

发现对于 $abcb$，可能会在 $ab+cb$，$abc+b$ 中被重复计算，就考虑用所有情况减去重复的情况

用一个桶记录每个字母在 $b$ 中出现了几次，枚举 $a$ 中的每个字母，减去对应的次数即可

$B$：B. noip十连测day3-点：$28/100$

中位数 $\le a_u$ 这个限制相当于 $>a_u$ 的数不超过 $\left \lfloor \dfrac{deg_u-1}{2} \right \rfloor $ 个

设 $dp[u][0/1]$ 表示考虑以 $u$ 为根的子树，$u$ 的父边是否可以 $>a_u$ 的答案

转移的时候先对于 $u$ 的每个儿子，求出 $(u,v)$ 这条边在 $\le a_u$ 和 $>a_u$ 两种情况下的最大答案，设为 $w[v][0/1]$。先默认所有的 $(u,v)$ 都选 $w[v][0]$，然后按照 $w[v][1]-w[v][0]$ 从大到小排序贪心选择即可

$C$：C. noip十连测day3-不：$30/100$

相当于要找到一个最大的 $d$ 满足 $f(d)=\sum\limits_{i=1}^n[d|a_i]>\left \lfloor \dfrac{n}{2} \right \rfloor$

枚举一个 $a_i$，并钦定 $a_i$ 在答案中被选择。此时 $d$ 必须是 $a_i$ 的约数。暴力找出 $a_i$ 的所有约数，并用后缀和对每个 $a_i$ 的约数 $d$ 求出 $f(d)$

直接枚举 $a_i$ 还是会爆炸。但是我们发现随机选一个 $a_i$ 在最优解中的概率至少是 $\dfrac{1}{2}$。因此可以先把 $a$ 随机重排一下，只需要对 $a_{1\cdots k}$ 做一遍即可。这个做法的正确率至少为 $1-\dfrac{1}{2^k}$

$D$：D. noip十连测day3-多：$10/100$

$A$：A. noip十连测day4-暗物质（Dark Matter）：$100/100$

除了 $1^n\le 1\times n$，都有 $a^b\ge a\times b$，所以只要数列中第一个 $1$ 之后的全部变为 $1^n$，前面直接算就是最优的

$B$：B. noip十连测day4-零（Zero）：$80/100$

枚举每一条在生成树里的边 $e$，可以算出有多少条还未加入的边的瓶颈路为 $e$（注意要减去原来就在图里的边），如果之前需要添加边加上原来边权 $j]g_{i-1,k}$，$h_i=\sum g_{i,j}$

时间复杂度 $O(n\log^2 m)$

$B$：B. 勿忘我：$33/100$

我们可以一个一个地添加顶点，并用一个链表维护当前合法的路径

如果当前的路径全都存在边或全都不存在边，则我们直接将其添加到路径的结尾即可；否则，我们找到状态切换的位置 $x$，可以发现我们已经可以将顶点插入到对应的位置中

例如，若当前的顶点 $u$ 与切换点 $x$ 之间的关系与 $x-pre_x$ 的关系相同，则将 $u$ 插入到 $x$ 与 $bk_x$ 中间，否则插入到 $a$ 与 $x$ 中间

$C$：C. 君子兰：$20/100$

$D$：D. 郁金香：$25/100$