NOI-upsolve

[TOC]

1. NOI2019 D1T2 - 机器人 [Keter]

题面

有 $n$ 个柱子，第 $i$ 个柱子的高度是在 $[a_i,b_i]$ 内的整数 $h_i$

现在你从起点 $s$ 开始，你往左走走到第一个 $L$ 满足 $L=1$ 或 $h_{L-1}>h_s$，往右走走到第一个 $R$ 满足 $R=n$ 或 $h_{R+1}\ge h_s$

定义一个柱子的高度方案是好的，当且仅当从任意一个柱子开始，$|(R-s)-(s-L)|\le2$，求有多少柱子的高度方案是好的，答案对 $10^9+7$ 取模

$1\le n\le300,1\le a_i\le b_i\le10^9$

题解

令 $dp_{l,r,x}$ 表示在编号 $[l,r]$ 的柱子内，最大值 $\le x$，那么我们枚举最大值的位置 $k$，显然只能在中间的 $3$ 个位置，那么转移式为

$$dp_{l,r,x}=dp_{l,r,x-1}+\sum_kdp_{l,k-1,x}dp_{k+1,r,x-1}$$

我们进行搜索，发现在 $n=300$ 时用到的 $[l,r]$ 只有 $2047$ 个，复杂度是 $O(2047W)$，但是 $W$ 过大，无法通过。

考虑离散化之后最多只有 $O(n)$ 个段，而每段内的 $dp_{l,r,x}$ 值都是一个关于 $x$ 的 $r-l+1$ 次函数

因此我们可以考虑用拉格朗日插值，假设我们求出了每一段内最先的 $r-l+2$ 个 $x$ 的点值，一共 $O(2047n)$ 个状态，那么我们有了这个值，我们可以插出该段内最后一个 $x$ 的点值，从而使我们能够推出下一段的最先的 $r-l+2$ 个点值

因此我们只需要对每一段往后推即可，由于我们涉及的横坐标都是连续的，因此我们可以 $O(n)$ 拉插，总复杂度 $O(2047n^2)$

2. NOI2019 D2T1 - 弹跳 [Euclid/Keter]

题面

给定 $n,m,w,h$，在一个 $w\times h$ 内的点阵内有 $n$ 个城市，第 $i$ 个城市的坐标是 $(x_i,y_i)$，给定 $m$ 组边，每一组边有 $6$ 个参数 $p,t,l,r,d,u$，表示由点 $p$ 向所有满足 $l\le x_j\le r$ 且 $d\le y_j\le u$ 的点连长度为 $t$ 边，求 $1$ 到其他点的最短路

$1\le w,h\le n\le70000,1\le m\le150000$

题解

考虑 Dijkstra 的过程，每次选取距离最小的点并寻找到其所有出边，进行更新

那我们怎么样才能快速找到距离最小的点呢？

我们可以在松弛的过程中直接将所有 dis[u]+e[i].w 放入一个单调队列，这样每次取出来的边的末端如果没有没标记过就一定是距离最小的点，遮这样由于每组边内的 dis[u]+e[i].w 都是一样的，因此我们可以统一处理

具体地，我们弹出一个 dis[u]+e[i].w 时，需要将其连向的所有还没有被标记过的点的所有 dis[u]+e[i].w 加入单调队列，不难发现这样每个点的 dis[u]+e[i].w 只会被标记一次

那么我们需要支持查询矩形内还没有被标记的所有点、以及删除一个点

我们对横坐标建线段树，每个节点套一个 set，以纵坐标排序，对于查询操作我们直接将矩形的 $[l,r]$ 放入线段树查询，然后暴力在答案中加入所有 $O(\log n)$ 个区间中纵坐标在 $[d,u]$ 内的点，对于删除操作直接沿到祖先的路径删除即可，由于每个点处理时只会产生 $O(\log^2n)$ 的代价，所以这部分的总时间是 $O(m\log^2n)$

那么总时间就是 $O(m\log^2n)$

3. NOI2018 D1T2 - 冒泡排序 [Euclid]

题面

$t$ 组询问，每次给定 $n$ 和 $1\sim n$ 的排列 $q$，求有多少长为 $n$ 的排列 $p$ 满足 $p$ 的字典序严格大于 $q$，且对 $p$ 进行冒泡排序需要次数恰好为 $\frac12\sum|i-p_i|$，对 $998244353$ 取模

$1\le t\le 5,\sum n\le2\times10^6$

题解

充要条件是不存在 $i,j,k$ 使得 $ia_j>a_k$，证明给读者留作练习

那么考虑这个排列需要满足什么性质，不难发现对于这个排列中每一个前缀最大值 $x$，在它后面 $1\sim x-1$ 中还未出现的数一定递增出现（不一定连续）

那么我们只要确定了一种合法的所有前缀最大值的位置与数值，就可以确定出整个排列

我们可以将排列视作一个入栈过程：$1\sim n$ 依次入栈，前缀最大值 $x$ 表示入栈到 $x$，并弹出栈顶，否则直接弹出栈顶，那么长度为 $n$ 的合法排列就有 $C_n$ 种，其中 $C$ 是卡特兰数，当然这并没有任何用

我们可以考虑枚举 $p$ 是在哪一位第一次大于 $q$ 的

首先考虑 $n^2$ 的做法，我们枚举位置 $x$ 以及 $p_x$ 的值，我们显然可以求出前面的最大值，这限制我们后面有一个前缀的值一定要递增出现，那么我们后面还没填的部分就是一个长为 $n-x$ 的排列，还有一个 $y$，表示 $1\sim y$ 必须递增出现，我们称其为 $F(n-x,p_x)$，将所有的 $F$ 求和就可以得到答案

我们可以通过现代方法（OEIS）得出：

$$F(n,m)=\frac{(m+1)\binom{2n-m}n}{n+1}$$

原因：这相当于我们现在一共有 $x$ 个元素，其中 $1\sim y$ 已经在栈中，那么我们可以通过折线法得出

$$F(n,m)=\binom{2n-m}n-\binom{2n-m}{n+1}$$

不难发现这两个事情是等价的

但是这样计算复杂度仍然是 $O(n^2)$ 的，无法接受。

可以观察到我们算的 $F$ 永远是一个后缀和，那么我们不妨令 $G(n,A)=\sum_{A\le k\le n}F(n,k)$，我们又可以通过现代方法（mma）得出：

$$G(n,A)=\frac{(A+2)(2n-A+1)\binom{2n-A}n}{(n+1)(n+2)}$$

原因：$F$ 是两个组合数相减的形式，那么我们可以通过 $\sum_{n\le k\le m}\binom kn=\binom{m+1}{n+1}$ 得出

$$G(n,A)=\binom{2n-A+1}{n+1}-\binom{2n-A+1}{n+2}$$

不难发现这两个式子等价

那么我们可以 $O(1)$ 计算 $G$ 了，但是我们还要求出究竟 $1\sim y$ 递增出现中的 $y$ 是多少，而 $y$ 等于还未出现的小于前缀最大值的数的个数，可以用树状数组维护

复杂度 $O(n\log n)$

4. NOI2017 D1T1 - 整数 [Safe]

题面

有一个整数 $x$，有两种操作，使其加上 $a\times2^b$ 或查询二进制下第 $k$ 位的值

$1\le n\le10^6,|a|\le10^9,0\le b,k\le 30n$，保证任何时刻 $x\ge0$

题解

直接用 set 暴力维护连续 1 段，复杂度 $O(n\log^2n)$

5. NOI2016 D1T2 - 网格 [Keter]

题面

$n\times m$ 的网格，有 $c$ 个格子是障碍，请添加最少的障碍使得白色格子不连通，如果不可能则输出 -1

$1\le n,m\le10^9,1\le c\le10^5$

题解

92 分就近似 AC 了对吧。

考虑如果可能，那么答案一定 $\le2$，因此我们只用判断 -1,0,1,2

如果 -1，一定是 $nm-c<2$ 或者 $nm-c=2$ 且两个白格联通

如果 0，那么一定是初始就不连通，我们采用如下的方法判断：将每个障碍周围的 $3\times3$ 方格拿出来直接四联通建图，如果在不考虑障碍的时候联通的白格在考虑障碍后不连通，说明不连通。

如果 1，那么一定是添加一个障碍后不连通，而这个障碍显然是在已经存在的障碍的八连通范围内的，那么我们可以把每个障碍的 $5\times5$ 方格拿出来四联通建图，判断有没有白格是割点，如果有，那么就是 1

否则就是 2

复杂度 $O(25c)$，但是我实现的太菜了，所以是 $O(25c\log c)$，所以过不去 /cy

6. NOI2019 D1T1 - 回家路线 [Euclid]

题面

有 $n$ 个点与 $m$ 辆车，以及三个正整数 $A,B,C$。你现在在 $1$ 号点，你要到 $n$。每辆车有四个属性 $u_i,v_i,p_i,q_i$，表示这条边从 $u_i$ 到 $v_i$，且仅在 $p_i$ 时刻出发，在 $q_i$ 时刻到达。当然，你可以在一个点上等待任意长的时间，但你等待 $t$ 个单位时间就会付出 $At^2+Bt+C$ 的代价，且你如果在 $z$ 时刻到达 $n$，那么会额外产生 $z$ 的代价

原题：$2\le n\le10^5,1\le m\le2\times10^5,0\le A\le10,0\le B,C\le10^6,0\le p_i<q_i\le10^3$

加强版：$2\le n\le10^5,1\le m\le10^6,0\le A\le10,0\le B,C\le10^7,0\le p_i<q_i\le4\times10^4$

题解

做法 1

原题数据水爆了，直接 $O(nt)$ dp 就可以过

令 $dp[t][x]$ 表示 $t$ 时刻刚刚到达 $x$ 的代价，那么转移是非常显然的

做法 2

应该是出题人想看到的做法。

考虑做法 1 的有效状态最多只有 $m$ 个，每条边一个

那么我们修改一下状态，令 $dp[i]$ 表示走完第 $i$ 条边的最小代价，那么 $dp[i]=\min_{u_i=v_j}(dp[j]+A(p_i-q_j)^2+B(p_i-q_j)+C)$

考虑斜率优化，经过一波推式子我们得出转移 $i$ 时 $j$ 比 $k$ 优的条件：当 $q_j2Ap_i$，其中 $f(x)=dp_x+Aq_x^2-Bq_x$

那么我们可以在每个节点上维护一个 $f$ 与 $q$ 值均单增的单调队列，进行斜率优化

我们按时间考虑，把每条边 $i$ 拆成两个事件，一个事件的时间是 $p$，当这个事件发生时我们求 $dp[i]$ 的值，另一个事件的时间是 $q$，当这个事件发生时我们将这条边加入第 $v_i$ 个点的队列

复杂度 $O(m\log m)$，瓶颈在于排序

7. NOI2016 D1T1 - 优秀的拆分 [Euclid]

题面

对于字符串 $x$，定义 $f(x)$ 表示有多少对非空串 $A,B$ 满足 $s=AABB$，给定 $t$ 个字符串 $s$，对每个字符串求它所有子串的 $f$ 值之和

$1\le t\le10,1\le |s|\le30000$

题解

定义 $a_i$ 表示有多少形如 AA 的串以第 $i$ 个位置结尾，$b_i$ 为有多少形如 BB 的串以第 $i$ 个位置开头，你们答案就等于 $\sum a_ib_{i+1}$

考虑如何求 $a_i$，我们枚举 A 的长度 $S$，将串分为 $\frac nS$ 段，我们想要在一个与 $\frac nS$ 有关的复杂度内求出所有 A 长为 $S$ 的答案

有两种满足要求的 AA，一种的 A 是整段，另一种的 A 在两端之间，第一个可以用哈希直接求出，第二种可以计算块 $i$ 与块 $i+1$ 的最长公共前缀和块 $i$ 与块 $i-1$ 的最长公共后缀得到满足条件的串的下标范围，然后用树状数组在 $a$ 数组上更新

$b$ 数组同理，复杂度 $O(t|s|\log^2|s|)$

8. NOI2018 D2T2 - 情报中心 [Keter]

题面

一棵 $n$ 个点的树，边有边权，有 $m$ 条路径，每条路径有一个代价 $w_i$，你要选择其中的两条路径，使得他们有交且并集的边权和减去两条路径的价值和最大

$1\le n\le2\times10^4,0\le m\le 10^5,\sum n\le1000233,\sum m\le1000233$

题解

如果一种选法 $(u_1,v_1),(u_2,v_2)$ 合法，那么价值为 $\frac12(dis(u_1,u_2)+dis(u_2,v_2)+dis(v_2,v_1)+dis(u_1,v_1)-w_{u_1,v_1}-w_{u_2,v_2})$（这里假设 $dis(u_1,u_2)\le dis(u_1,v_2)$）

我们将这种方案在 $lca(u_1,u_2)$ 上统计，设其为 $t$，令 $cost(v)=dis(u,v)-w_{u,v}+dep_u$，那么答案就为 $\frac12(cost(v_1)+cost(v_2)+dis(v_1,v_2)-2dep_t)$

由于直径的性质，那么我们可以用线段树合并来维护，下标是每个，在 dfs 到 $u$ 和 $v$ 的时候分别加入这条路径的 $cost(v)$ 和 $cost(u)$，在 dfs 到 $lca(u,v)$ 的儿子的时候删除

复杂度 $O((n+m)\log n)$

9. NOI2018 D2T1 - 屠龙勇士 [Safe]

题面

有 $n$ 条龙，第 $i$ 条龙有 $a_i$ 的生命值，回复能力为 $p_i$，你要依次击败他们。你有 $m$ 把剑，第 $i$ 把剑的攻击力为 $p_i$

游戏开始前，你需要选择一个 $x$。

在第 $i$ 回合，你会面对第 $i$ 条龙，你会使用攻击力 $\le a_i$ 的剑中攻击力最高的剑（如果不存在这样的剑则选择攻击力最低的），然后用这把剑连续攻击 $x$ 次，此时如果龙生命值是负数，那么龙让自己的血量增加 $p_i$，直到血量非负为止，你需要保证此时龙的血量为 $0$，这之后，你使用的这把剑攻击力会变为 $c_i$

请你求出最小的 $x$，如果不存在则输出 $-1$

$1\le n\le10^5,1\le m\le10^5,lcm(p_i)\le10^{12}$

题解

不难发现每回合我们使用的剑的攻击力都是确定的，不妨设其为 $b_i$，那第 $i$ 回合对 $x$ 的限制就是 $b_ix\equiv a\pmod{p_i}$

直接 excrt 即可，注意由于每次必须把龙的血量减到非正，因此 $x$ 是有一个下限的，不够的话加上若干个 lcm 即可

10. NOI2016 D1T3 - 循环之美 [Euclid]

题面

给定 $n,m,k$，求有多少最简分数 $\frac ij$ 使得 $1\le i\le n,1\le j\le m$ 且其在 $k$ 进制下为整数或者为纯循环小数

$1\le n,m\le10^9,2\le k\le2\times10^3$

题解

题目让求的就是 $\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1]$

推式子：

$$\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=1][\gcd(j,k)=1]\\ \sum_{d|k}\mu(d)\sum_{j=1}^{m/d}\sum_{i=1}^n[\gcd(i,jd)=1]\\ \sum_{d|k}\mu(d)\sum_{j=1}^{m/d}\sum_{i=1}^n[\gcd(i,j)=1][\gcd(i,d)=1]\\$$

我们发现，如果令原问题的答案为 $F(n,m,k)$，则 $F(n,m,k)=\sum_{d|k}\mu(d)F(\lfloor\frac md\rfloor,n,d)$

对于 $m=1$ 的情况 $F(n,m,k)$ 是非常好算的，对于 $k=1$ 的情况可以推式子变成 $\sum_{d=1}^n\mu(d)\lfloor\frac nd\rfloor\lfloor\frac md\rfloor$，可以通过数论分块 + 杜教筛快速计算

然后直接暴力递归复杂度好像就对了。

复杂度 $O(玄学)$

11. NOI2019 D1T3 - 序列 [Apollyon]

题面

给定长为 $n$ 的序列 $a$ 和长为 $m$ 的序列 $b$，你需要在 $a$ 与 $b$ 中分别选出 $k$ 个互不相同的下标 $c_i$ 与 $d_i$，且保证 $c$ 与 $d$ 至少有 $l$ 个重复元素，求 $\sum a_{c_i}+\sum b_{d_i}$ 的最大值

$t\le10,1\le \sum n\le10^6,1\le l\le k\le n\le 2\times10^5$

题解

首先考虑费用流解这个问题，那我们按照这种方式建图即可

不难发现这样建图，然后用 $k$ 的流量去跑最大费用最大流，就能得到答案，但是数据范围过大，肯定无法通过

所以我们就要模拟费用流，每次模拟 spfa 的过程，找出增广路

由于一些魔法，我们只用考虑以下五种路径：

然后我们开五个堆，维护满足每种路径的 $u,v$，然后组合一下就能找出最优的增广路了

复杂度 $O(n\log n)$

12. NOI2017 D1T3 - 泳池 [Euclid]

题面

有一个 $n\times1001$ 的网格，每个格子有 $p$ 的概率是危险的，你需要选出一个面积最大的矩形，使得这个矩形经过第一列且没有危险的格子，求最大面积恰好等于 $k$ 的概率，对 $998244353$ 取模

$1\le n\le10^9,1\le k\le1000$

题解

恰好不好搞，我们转化成 $\le k$ 的概率，差分一下即可

令 $dp_{i,j}$ 表示在一个 $i$ 行的网格内，钦定前 $j$ 列都是不危险的，最大面积 $\le k$ 的方案数，那么我们枚举第 $j+1$ 列的第一个黑色 $dp_{i,j}=\sum_{a=1}^i(1-p)^{a-1}p\times dp_{a-1,j+1}\times dp_{i-a,j}+dp_{i,j+1}(1-p)^i$

如果 $ij>k$ 的话那么 $dp$ 值一定为 $0$

因此只有 $j=0$ 的时候复杂度不对，但我们可以发现，$dp_{i,0}$ 是一个关于 $dp_{j,0}(i-k\le j\le i-1)$ 递推的形式，因此我们可以用暴力的常系数齐次递推搞

具体地，如果一个递推式满足 $f_i=\sum_{j=1}^ka_jf_{i-j}$，那么我们令多项式 $F=x^k-\sum_{j=1}^ka_jx^{k-j}$，那我们不难发现 $x^n$ 对这个多项式取模之后用 $i$ 次项系数乘上 $f_i$ 的值之和就是 $f_n$ 的值，暴力乘就可以 $O(k^2\log k)$ 解决

13. NOI2013 D1T1 - 向量内积 [Keter]

题面

给定 $n$ 个 $d$ 维向量，要在这些向量里选出一对，使得它们点积被 $k$ 整除，无解输出 -1 -1

$1\le n\le10^5,1\le d\le30,2\le k\le3$

题解

以下均在模 $k$ 意义下讨论

首先注意到我们如果把这 $n$ 个向量当成一个 $n\times d$ 的矩阵 $A$，那么答案就相当于要找到 $A\times A^T$ 上的一个不在对角线上的 $0$

$k=2$ 时比较好做，因为如果无解，那么除对角线外所有的元素必定是 $1$，而对角线的元素我们可以 $O(nd) $ 的复杂度算出来，因此我们只要判断 $A\times A^T$ 是否等于我们臆想出来的这个矩阵即可，而这个可以用随机一个向量相乘的经典 trick 做，如果不等我们就可以得到是哪一行不相等，然后就可以直接把这一行的元素全部算出来挨个判断即可，复杂度 $O(nd)$

那 $k=3$ 的时候除对角线外的元素就有可能有 $1$ 或 $-1$ 两种情况，我们发现平方一下就可以统一，考虑如何平方

$C_{i,j}=(\sum A_{i,k}A^T_{j,k})^2=\sum(A_{i,k}A_{j,k})(A^T_{k,i}A^T_{k,j})$，那么我们定义一个 $n\times d^2$ 的矩阵 $B_{i,(j,k)}=A_{i,k}A_{j,k}$，$B\times B^T$ 就是我们想要的平方过的矩阵了

之后就像 $k=2$ 一样处理就可以了，复杂度 $O(nd^2)$

14. NOI2013 D1T2 - 树的计数 [Euclid]

题面

给定一棵 $n$ 个点的树的 dfs 序和 bfs 序（两个树在遍历的时候每个节点的儿子先后顺序相同），求满足条件的树的平均树高，保证有解

$2\le n\le2\times10^5$

题解

考虑首先把 bfs 序变为 $1\sim n$，相应地更改 dfs 序，那么在 dfs 的过程中，如果有多个儿子，我们会选择编号小的进行 dfs

这样的话一定满足 $dep_1\le dep_2\le dep_3\le\cdots\le dep_n$，而相邻两个点深度最多差 $1$，那么我们只要知道每个小于等于号是填什么就可以知道最终的树高了

如果有 $x+1$ 在 dfs 序中比 $x$ 靠前，那么 $dep_x<dep_{x+1}$

如果 $dfs_i<dfs_{i+1}$ 且 $dfs_i$ 到 $dfs_{i+1}$ 之间有小于号，因为 dfs 序的性质 $dep_{dfs_{i+1}}-dep_{dfs_i}\le1$，那么我们可以将在 $dfs_i$ 到 $dfs_{i+1}$ 之间所有不是小于号的全部赋为等于号

剩余的不是等于号也不是小于号的就可以随便选一个，因此一个小于等号对答案的贡献是 $0.5$

最后统计输出即可，复杂度 $O(n)$

15. NOI2020 D1T2 - 命运 [Euclid]

题面

给定 $n$ 个点的以 $1$ 为根的树以及 $m$ 条路径 $(u_i,v_i)$，保证 $u_i$ 是 $v_i$ 的祖先，求有多少种方案给树上的每条边赋 01 值，使得每一个路径上都至少有一个 $1$，对 $998244353$ 取模

$1\le n,m\le5\times10^5$

题解

令 $dp_{x,y}$ 表示考虑以 $x$ 为根的子树，完全被包含在子树内的路径已经全被满足，不完全被包含的未满足路径的 $u_i$ 最深的深度为 $\le y$ 的方案数，而 $f_x$ 表示所有经过 $x$ 子树的路径都被满足的方案数

那么我们对每条边，考虑它填 0 或 1，那么 $dp_{x,y}=\prod_{u\in child}(dp_{u,y}+f_u+dp_{u,dep_u-1})-f_x$，$f_x=\prod_{u\in child}(f_u+dp_{u,dep_u-1})$，并且我们如果称以 $x$ 为 $v_i$ 的路径最深的 $u_i$ 深度为 $up_x$，那么 $f_x$ 与 $dp_{x,i}(i<up_x)$ 的值都要赋值为 $0$，其余的值不变

我们可以不难发现，如果将 $f_x$ 定义为 $dp_{x,0}$，方程将变得更加简单，即 $dp_{x,y}=\prod_{u\in child}(dp_{u,y}+dp_{u,dep_u-1})$，而我们的答案就是 $dp_{1,0}$

我们可以用线段树维护这个东西，需要支持区间乘法，区间加法，以及单点查询，复杂度 $O(n\log n)$