杂题乱做1 • lomit

主要是以前写过的一些luogu上的蓝题，口胡+补一下简易题解

P1053 [NOIP 2005 提高组] 篝火晚会 ↗#

不然发现，最终状态就两种，从 $1$ 开始构造之后就顺时针和逆时针两种情况。但是环是可以旋转的，所以一共会有 $2n$ 种情况，怎么快速判断旋转多少会让答案最优呢？只需要让最终的状态与初始状态的每个位置做差，看看相同差值的个数最多的是哪一个，旋转那么多次就是最佳答案。

正反都做一遍就好了。

https://www.luogu.com/paste/fpchzse6 ↗

P1073 [NOIP 2009 提高组] 最优贸易 ↗#

一开始想的是直接缩点，然后在 DAG 上 DP，感觉没啥问题

看自己以前的代码发现直接一个暴力dfs干过去了，闹麻了

后来感觉题解说的分层图+SPFA也很有道理

https://www.luogu.com.cn/article/l1losgoo ↗

P1129 [ZJOI2007] 矩阵游戏 ↗#

重新看的时候一开始想着不是直接算一下 $1$ 的数量就好了吗?后来点开标签看到了二分图,然后就会做了. 说白了就是考虑单独的某一列,发现这一列上的点只能匹配到某一行上面,也就是这题实际上是要用行去匹配列. 对于一个点的位置 $(i,j)$ 就让 $i$ 行向 $j$ 列连边,拆成二分图跑Dinic就完事了

不过我的代码貌似是匈牙利算法

https://www.luogu.com.cn/paste/h1tkqgk7 ↗

P1272 重建道路 ↗#

一眼树上背包

令 $f[u][s]$ 表示对于当前以 $u$ 为根节点的子树, 包含 $s$ 个节点的答案

初始状态令 $f[u][1]=in[u]$ 入度个数就完事了

https://www.luogu.com.cn/paste/v7pp62ll ↗

P1306 斐波那契公约数 ↗#

经典结论题

\gcd(fib_n,fib_m)=fib_{\gcd(n,m)}

矩阵乘法加速转移就完事了,不记得怎么证明了

https://www.luogu.com.cn/paste/pj9lnh95 ↗

P1343 地震逃生 ↗#

第一眼网络流

第二眼看标签又不确定了,点开题解发现就是裸的网络流

闹麻了

https://www.luogu.com.cn/paste/l6r84sku ↗

P1357 花园 ↗#

第一眼看出来状压dp,然后用矩阵优化

但是没想出来环怎么处理,老了啊

看之前写的代码才想起来,只需要枚举所有的状态,看每个初始状态经历 $n$ 次装转移后仍然回到初始状态的方案数求和就是答案了

https://www.luogu.com.cn/paste/9oyltdq2 ↗

P1399 [NOI2013] 快餐店 ↗#

代码难度大于思维难度的一题

https://blog.csdn.net/qq_38944163/article/details/89470928 ↗

P1447 [NOI2010] 能量采集 ↗#

一眼丁真，鉴定为

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} 2\gcd(i,j)-1

随便做做就完了

上一题不必这一题难多了，为什么都是蓝？

https://www.luogu.com.cn/paste/zpoqmbsb ↗

P1450 [HAOI2008] 硬币购物 ↗#

降大智了

一共才4种货币，先跑个完全背包，然后暴力容斥就完事了

https://www.luogu.com.cn/paste/s261ojim ↗

P1463 [POI 2001 ] [HAOI2007] 反素数 ↗#

第一眼搜索

注意到答案质因数分解完指数一定是非递增的

剪枝一下就完事了

https://www.luogu.com.cn/paste/wc881720 ↗

P1472 [USACO2.3] 奶牛家谱 Cow Pedigrees ↗#

一看数据范围还以为是什么科技题

直接dp就完事了，设 $f[i][j]$ 表示用了 $i$ 个节点，层数 $\le j$ 的方案数

随便转移一下，做个差就是答案了

https://www.luogu.com.cn/paste/h4v87qoz ↗

P1484 种树 ↗#

属于是见过一次就会做，没见过很难自己yy出来的题了

叫反悔贪心，应该也可以用模拟费用流分析，现在脑子不好用了

看看代码吧

https://www.luogu.com.cn/paste/5v8danb9 ↗

最关键的性质就是假设已经有解的情况下，对于第一行的每一个蓄水站，能覆盖的一定是最后一行的连续一段区间，于是乎可以用dfs预处理出若干个区间，然后就变成简单的区间覆盖问题了

可以直接DP，也可以直接贪心

代码是dp

https://www.luogu.com.cn/paste/wjvdr6ho ↗

P1613 跑路 ↗#

这个数据范围居然没想到floyd，本质上就是预处理一个倍增的玩意，然后floyd完事了

https://www.luogu.com.cn/problem/solution/P1613 ↗

P1640 [SCOI2010] 连续攻击游戏 ↗#

一开始以为要按顺序，寻思这不就是贪心吗

后来发现装备可以随意用，然后就懵了

有个简单的思路是，二分答案，然后连边跑网络流判断是否合法

然而复杂度会炸

看自己以前的代码发现直接用匈牙利算法，一条一条路增广就完事了

https://www.luogu.com.cn/paste/d6irkvj2 ↗

P1641 [SCOI2010] 生成字符串 ↗#

一眼枚举第一个不合法的点，然后计算左右两边乘起来再加起来

左边卡特兰数，右边组合数

https://ctz45562.github.io/2019/05/30/%E6%B4%9B%E8%B0%B7-P1641-SCOI2010-%E7%94%9F%E6%88%90%E5%AD%97%E7%AC%A6%E4%B8%B2/ ↗

题解貌似又更好的做法，转换一下，画个图

发现从 $(0,0)$ 出发斜着走， $1$ 往右上， $0$ 右下

然后不能经过 $y=-1$ ,只需要在第一次到 $y=-1$ 的时候对称翻转一下

发现就变成从 $(0,-2)$ 开始走的情况了，随便推一下组合数即可

第一种解法用范德蒙德卷积化简一下应该也是一样的

https://www.luogu.com.cn/paste/l6rhuphf ↗

P1654 OSU! ↗#

根据期望的线性性，直接一次方，二次方，三次方分别维护

随便转移一下就好了

注意一次方和二次方的是钦定 $i$ 结尾的期望

https://www.luogu.com.cn/paste/j2aibvlf ↗

P1712 [NOI2016] 区间 ↗#

脑子转不动了，初中的自己来直接秒了，现在想半天

老想着先考虑覆盖哪个点，然后再求最优区间长度

不妨先把每个区间按照长度排个序，假设长度从大到小

一个一个区间的加入，可以用线段树维护覆盖次数，如果某个点的覆盖次数达到 $m$ 了就说明可以了

然后用加入的区间最长的长度减当前的长度即可

用two-pointer可以很容易实现

这样就把最优化问题转换为判定性问题了

https://www.luogu.com.cn/paste/yuai99ca ↗

P1730 最小密度路径 ↗#

第一眼没反应过来

第二眼发现应该是0/1分数规划

二分答案 $ANS$ ，然后每条边的边权 $- ANS$ 最后判断是否有非负路径

SPFA 随便跑跑就完事了

https://www.luogu.com.cn/paste/owdsufg9 ↗

P1772 [ZJOI2006] 物流运输 ↗#

一脸懵b，我之前是怎么做出来的？

看题解发现也不是那么好想啊这题

有个点就是要想到设 $dp[i]$ 表示前 $i$ 天的答案

然后处理出一个 $cost[i][j]$ 表示从第 $i$ 天到第 $j$ 天都走同一条路线的最小花费

然后就很好DP了

$cost$ 直接用SPFA搞一下就好了

https://www.luogu.com.cn/paste/xopmnix3 ↗

P1850 [NOIP 2016 提高组] 换教室 ↗#

经典的期望DP

设 $dp[i][j][0/1]$ 表示对于前 $i$ 门课，选了 $j$ 个，当前的选或不选

分情况讨论一下dp即可

https://www.luogu.com.cn/paste/kjsm64ha ↗

P1948 [USACO08JAN] Telephone Lines S ↗#

不难想到首先要一个二分答案

考虑如何建图，不难发现可以直接让<=mid的边权设为0，别的边设为1，然后跑最短路，看最短路是否 $<=k$ 即可。总的来说思路是挺清晰的，最短路可以用spfa, 也可以双端队列bfs

https://www.luogu.com.cn/paste/3v6ojw0x ↗

P1966 [NOIP 2013 提高组] 火柴排队 ↗#

降至题

首先不难发现，在 $a$ 中第 $i$ 高的要对应在 $b$ 中第 $i$ 高的

那么可以先将 $a,b$ 离散化,就变成排名了

然后设 $py[i]$ 表示 $a$ 数组中第 $i$ 高的在哪个位置

设 $p[i] = py[b[i]]$ 意思就是第 $i$ 个位置的最终要到 $py[b[i]]$ 这个位置

然后对 $p$ 求个逆序对就完事了

https://www.luogu.com.cn/paste/qirufjer ↗

P1967 [NOIP 2013 提高组] 货车运输 ↗#

一下子没反应过来，以为是什么网络流树之类的

其实就是直接kruskal生成树，再加上一个倍增就完事了

很经典的题

https://www.luogu.com.cn/paste/jwuw2o2o ↗

P1972 [SDOI2009] HH的项链 ↗#

经典套路

先把询问离线，按照右端点排序

记 $pre[i]$ 表示上一个和 $i$ 种类相同的位置

然后每次加入右端点的时候 $add(i,1),add(pre[i],-1)$ 这样就能保证询问一个区间的时候，每一个种类的只有第一个出现的有贡献，这样就能保证每个种类只贡献一次

拿树状数组随便维护一下就好了

https://www.luogu.com.cn/paste/mz2ke5ag ↗

P2051 [AHOI2009] 中国象棋 ↗#

降大智了属于是

容易发现其实就是每一行，每一列最多放两个

一行一行来考虑

然后发现其实不用关心前 $i$ 列具体放了哪里，只需要知道有几列放了一个，几列放了两个就好了

可以设 $f[i][j][k]$ 表示考虑到 $i$ 行，前面一共有 $j$ 列放了一个， $k$ 列放了两个

随便转移一下即可

https://www.luogu.com.cn/paste/rgdxtymz ↗

P2059 [JLOI2013] 卡牌游戏 ↗#

这种程度的DP居然没看出来

脑子不好使了属于是

设 $f[i][j]$ 表示 $i$ 个人坐成一圈，第 $1$ 个人开始，最后 $j$ 赢的概率

假设现在抽到的卡牌为 $pos$

分两种情况讨论

$f[i][j] += f[i - 1][i - pos + j] / m, (pos > j)$

$f[i][j] += f[i - 1][j - pos] / m, (pos < j)$

随便转移一下即可

https://www.luogu.com.cn/paste/xehybpi7 ↗

不难发现一定是一段连续的

随便dp一下

https://www.luogu.com.cn/paste/x48kzfld ↗

P2161 [SHOI2009] 会场预约 ↗#

想了一会感觉可以用珂朵莉树

发现其实一个set就完事了

因为反正不可能重叠，随便搞搞

我自己的代码貌似是直接树状数组+二分出最后一个区间搞的

不如set

https://www.luogu.com.cn/paste/il8szf5z ↗

P2163 [SHOI2007] 园丁的烦恼 ↗#

看到第一眼主席树板子

发现确实是可以这么做

自己以前的代码是CDQ分治

不赖，刚好复习一下

https://www.luogu.com.cn/paste/xz3y6ydd ↗

P2219 [HAOI2007] 修筑绿化带 ↗#

想到了一个很暴力的做法，发现还真是

直接对于行和列，预处理一堆东西

然后行列分别做滑动区间最大值那样子就好了

看代码比较容易理解

https://www.luogu.com.cn/paste/bma8oezk ↗

P2221 [HAOI2012] 高速公路 ↗#

不难发现，答案就是

$\huge \frac{\sum\sum dis[i][j]}{C_{r-l+1}^2}$

但是不太好维护

可以考虑每条边的贡献，上面那部分就变成了

$\large \sum cost[i]*(i-l+1)*(r-i+1)$

把式子拆一下发现要维护的只有

$a[i], a[i]*i, a[i]*i*i$

线段树维护即可

https://www.luogu.com.cn/paste/huj8ii7i ↗

P2231 [HNOI2002] 跳蚤 ↗#

这题倒是一眼秒了

不难发现只要存在两个卡牌是互质的就好了

直接容斥即可，容斥系数就是莫比乌斯函数

$\large \sum\limits_{d|n} \mu(d)(m/d)^n$

大概就是这个亚子

https://www.luogu.com.cn/paste/ubt89rm2 ↗

P2261 [CQOI2007] 余数求和 ↗#

偷瞄一眼标签会了

$k \mod i$ 可以改写为 $k - \lfloor \frac{k}{i}\rfloor*i$

然后整除分块就完事了

https://www.luogu.com.cn/paste/th74g5on ↗

P2279 [HNOI2003] 消防局的设立 ↗#

第一眼直接DP，但是感觉有点复杂，也不是不能做

瞄一眼题解发现可以直接贪心，老了，脑子转不动了

从叶子结点开始贪心，每次取最深的叶子，然后往它爷爷那里塞一个就完事了

https://www.luogu.com.cn/article/cv2yki5g ↗

P2312 [NOIP 2014 提高组] 解方程 ↗#

没想法，闹麻了

看代码发现其实就是随便选一个膜数，然后大力枚举解然后check

https://www.luogu.com.cn/paste/zrr1z2o9 ↗