HZEZ OIer Dilute 的故事虽然已经结束……

但是接下来是属于 HIT ACMer Dilute 的时间！

不知道算是旧赛季的结束还是新赛季的开始，总之每年的省赛都是这个时间点的保留节目。

既然是赛季总结，那就先总结一下这个赛季的成绩吧。

省流：真的有钱，而且卸下压力之后的比赛竟然超常发挥了这么多，从各方面来讲都是充满了无数惊喜的一场比赛。

省流：过程很刺激，最后还是拿到队伍第一块 Au了

Day -n

在暑假的初期，突发奇想，准备和自己的好兄弟们来一场去年没能完成的旅行。

时隔3年 我终于又发了一篇正经题解

要不是lqr我可能这博客就卡在这里了

开场 10 分钟就有人过的 1D ，你值得拥有！

$\texttt{swap(B, D)}$ 警告。

这个 $0.777$ 让我想起了某位 EDG 的退役打野选手

—— Sooke

4396（无 端 迫 害）

线段树

首先观察数据范围，发现$a_i \le6$，这个是一个非常有用的性质。

发现$\mathrm{lcm}(1, 2, 3, 4, 5, 6)=60$，这个数有一个非常优美的性质：把$t$再$\mod 60$意义下进行不会影响结果的正确性。

分块 + 斜率优化

G真的比F2清真

首先，看到树上 + 子树操作，第一反应使用dfs序拍平。

那么这个问题就变成了支持：

• 区间$a_i += x$
• 询问区间$\max\{|a_i| * |b_i|\}$

瞎搞DP

CF出了H没出G 菜的真实

发现$k$从$\texttt{E}$题的$100$变成了$O(10^{12})$，考虑与$k$复杂度无关的做法。

我们考虑$f_{i, j}$表示以$s_i$开始，本质不同的长度为$j$的子序列数量。

线段树乱搞

考虑如果要重排一段区间使得它是回文的是可行的

首先对这段区间的长度分类讨论

哈希 + 二分 + DP

首先看到题面，很容易想到一个$DP$，令$f[i]$为划分到$i$为止的方案数。

然后朴素的暴力转移是$O(n^2)$的，非常显然一个状态$i$能够转移到的$j$是一段连续的，进而想到使用前缀和优化。

$set$ 瞎搞

首先非常显然，一个矩形$(x1, y1, x2, y2)$的代价就是$\displaystyle\sum_{i = x1}^{x2}\sum_{j = y1}^{y2} h[i][j] - \min_{x1 \le i \le x2, y1 \le j \le y2} h[i][j]$，我们用$f[i][j]$表示以$(i, j)$为左上角的矩形的代价。即矩形$(i, j, i + a - 1, j + b - 1)$的代价。

我们首先考虑如何求出$f[i][j]$。

Round 1

咕咕咕。

回头再补。

set​瞎搞

预处理

我们考虑一下，一只青蛙能够影响的区间是什么

我们发现，如果将每只青蛙能够吃到的文字区间$[l, r]$按照左端点$l$排序，然后把后面的区间和前面的区间的重复部分去掉，那么就可以得到一个青蛙真正可以吃到的蚊子的范围区间

看到学长txc爷的blog里写了个“最近写的题目”

然后心血来潮准备自己也弄个这个东西

有趣的交互题

我们考虑一件事情

如果我们询问的矩形中有一个端点

那么答案 $\mod 2 = 1$

否则答案 $\mod 2 = 0$

换句话说，就是如果询问到的答案$\mod 2 = 0$，那么这个矩形内要么没有端点，要么有两个端点

似乎莫得人是不用树剖的w

但是为什么的一只$\log$乱搞被树剖的两只$\log$爆踩啊

是因为我实现的太丑了吗

不管了直接讲做法好了

有趣的矩阵乘法

（为方便，下文中“大号宝石”代指连续的$m$个分裂出来的宝石，“小号宝石”代指未分裂的单个宝石）

首先，我们观察这题，考虑$DP​$，设状态$f_i​$表示已经取了$i​$个单元的方案数的不难推出一个朴素的$O(n^2) DP​$方程$f_i = \displaystyle\sum_{i - j \geq m} f_j +1​$（可以理解成上一个大号宝石放的位置，最后一个$1​$即为全部用小号宝石填满的方案）

我们再仔细看看这个式子，加个前缀和，不难优化到$O(n)$，然而数据范围$n \leq 10^{18}$，这让我们考虑$O(\log n)$级别的算法，我们接下来考虑矩阵乘法优化这个式子。

又双叒叕是题外话

今天模拟考是原题大战。

$T1​$是这题。
$T2$是某次$CF\ Div1\ E$题。
$T3​$反正是某道神仙题。

像我这样的菜鸡只能来做做相对可做的T1

虽然只是相对可做但是还是被全场切穿了啊喂

内心OS：这个不订正的理由真的nice

本篇题解讲述的为非完美做法，但是可以骗到96分

说实话我在网上找了好久结果都是这个$O(n^2)$的非正解树型$DP$

听说有个$O(N)​$的正解在某篇论文里？

算了反正我也看不懂

所以我接下来就介绍一下这个$O(n^2)$的树型$DP$吧QwQ

顺手丢一下我学习的这篇blog​吧

简单递归

首先我们如果要消灭一段区间$[l, r]$，我们可以有三种选择：

• 如果$[l, r]​$区间内没人，那么直接花费$A​$的代价将这段摧毁
• 如果$r > l​$（即这段区间长度$>2​$），可以选择把它切割成$\left[ l, \lfloor \frac{l + r}2\rfloor\right]​$ $\left[\lceil \frac{l + r}2\rceil, r\right]​$两段
• 如果$[l, r]$区间内有人，直接花费$b (r - l + 1)x$的代价将其摧毁。

题外话

我本来自己想到的的做法是跟别的大多数题解一样的

但是$LJC00118$大仙跟我讲了他的做法，据说常数更小一些，于是我就过来发（水）题（社）解（区）了（分）。

$Day\ 0$

早上八点的飞机从杭州飞到广东中山纪念。

飞机上跟旁边的$sjn$神犇聊了一会之后开始颓废，后来敲了$fhq\ Treap$、最大流、费用流三个板子。

到了广东之后做了3个小时的公交车

到了中山纪念之后觉得宿舍略破，不过至少有电QwQ

试了个机，T1水题，T2据说是去年PKUSC的D1T2，想出了DP的状态定义不会转移，结果后来Sooke教我了一下，感觉不是特别想敲=-=

试完机之后还有蛮长的一段时间吃饭，于是我们就打了一盘狼人杀（法官真好玩）

饭菜一般般，坐我旁边的Sooke想找人面基，但是最后也就来的路上遇到了bztQwQ

晚上吃完饭，又来了一盘狼人杀（我还是法官）（双预言家真好玩）

现在是晚上7点，我躺在床上跟LJC00118一起写游记

真是充（颓）实（废）的一天

​ 前段时间在机房里几个大爷的墙裂安利下学了发$fhq\ treap$ 于是就顺带着把$fhq\ treap$的区间操作给学了（比$Splay$的好理解多了）

似乎这么一点字太少了？那我放张图=-=

题外话

我们模拟赛考了这题。

模拟赛大概还剩一个半小时的时候，我想出了这题，并且说

“要是我这没A掉，我就不交卷了”

于是我就没有A掉。

其实赛后半个小时左右就调出来了（我才不会告诉你我比赛的时候那个建模是有锅的呢）

Ⅰ 什么是珂朵莉？

珂朵莉是世界上最幸福的女孩，没有之一，不接受任何反驳。

其实我很想吐槽这题

我比赛的时候疯狂$\text{WA on test 16}​$

然后死活找不出来哪儿错了

我觉得我数组开小了

于是我开到$MLE$都没有过掉

最后一看

被一个n = 2的点卡掉了……

才出4题，罚时爆炸，上黄失败，掉分哭唧唧

我们令$fa[i]$为$i$直接连向的点

那么显然，$fa[i] \in \{a_{i, 1}, a_{i, 2}\}​$

假设$a_{i, 1}$为$fa[i]$，那么$a_{2, i} \in \{ a_{fa[i], 1}, a_{fa[i], 2} \}$

否则肯定有$a_{2, i} \not\in \{ a_{fa[i], 1}, a_{fa[i], 2} \}$

所以，如果有$a_{2, i} \in \{ a_{fa[i], 1}, a_{fa[i], 2} \}$，那么$fa[i] = a_{i, 1}$，否则$fa[i] = a_{i, 2}$

一道有点套路化的网格图上$DP$QwQ

我们用$f_{min}[i][j][0]$表示线头在$(i, j)$这个点的时候，线的方向朝__下__，我们能取到的最小的拐弯次数、用$f_{min}[i][j][1]$表示线头在$(i, j)$这个点的时候，显得方向朝__右__，能够取到的最小的拐弯次数

同理，我们用$f_{max}[i][j][0]$与$f_{max}[i][j][1]$表示线头在$(i, j)$位置是线朝下和朝右能够取到的最大的拐弯次数。

接下来，对于有障碍的点，我们直接不处理

显然，答案分别为$\max(f_{max}[n][m][0], f_{max}[n][m][1])$与$\min(f_{min}[n][m][0], f_{min}[n][m][1])$

对于这题，看到字符串匹配，第一反应想到字符串hash，同时看到$len \leq 8 $ ，考虑对于先给出的$n$个字符串，$O(len^2)$枚举它的子串，将其加入$map$中，但是要注意如果一个然后对于每个字符串，我们都统计一下它最后一次出现在哪里（于是就可以顺便判一下重）

然后我们在询问的时候，就可以直接输出这个字符串对应的出现次数以及最后一处出现的位置啦QwQ

我感觉思路隔壁题解给的不够清楚啊……

感觉我无法直接理解隔壁dalao的“正经的图上神搜”啊……

那本蒟蒻就补充一下吧QwQ

Day （不想算）

将RP耗尽在了初赛QwQ

Day 0

教练说这天Openday，随便打游戏，于是上午随手把最大流、费用流、树剖三个听说可能会考的板子给敲了一遍于是就去跟同学颓了一天的LOL

第一篇题解

我们都知道$lcm(a, b) = \frac{a * b}{\gcd(a, b)}$

∴ $\frac{lcm(a, b)}{a} = \frac{\frac{a * b}{\gcd(a, b)}}{a} = \frac{b}{\gcd(a, b)}$

题目的意思就被我们转化成了求$\frac{b}{\gcd(a, b)}$的种类数

又∵b是一个确定的数

∴$\frac{b}{\gcd(a, b)}$的种类数就等于$\gcd(a, b)$的种类数

由于$a$的范围在$[1, 10^{18}]$范围内，所以$\gcd(a, b)$的种类数就等于b的因数个数。

因数个数就可以$O(\sqrt n)$求辣QwQ

显然，我们可以发现一个序列是“好的”当且仅当这个序列中的最大值等于这个序列中的其他数之和相加，所以我们只需要保证序列单调递减，同时维护一下这个序列里面元素之和我们就可以$O(1)$判断一个序列是不是“好的”序列（$a_1 = Sum - a_1$）

由于题目要求求出去掉哪些元素之后，这个序列会变为一个“好的”序列，所以我们只需要把原序列排序之后再按照刚刚说过的办法$O(1)$判断，只需要吧把原序列之中的$Sum$减去我们需要去掉的元素即可

还有一点需要注意，我们需要特判去掉第一个的情况，这样删去后最大值就是原先的次大数，即$a_2$

上代码QwQ

首先我作为一个蒟蒻，拿到字符串题，首先看看能不能无脑哈希

然后于是我们就发现了一个绝妙的做法：暴力枚举每个字符串能够转换成的字符串

于是我们就获得了$O(N * 8^4)$的优秀复杂度

显然会T飞QwQ

我们考虑再这个基础上进行优化

前言

某天我看到了memset0巨佬怒切17道网络流神仙题的时候，我顿时准备去做做看网络流24题以满足我内心的抖M之魂

于是，我这个蒟蒻看到某道费用流神题的时候，一脸懵逼地看着“费用流”的标签，决心去学一学这玩意

前言

单调队列一种非常经典的将O(n^2)的DP优化的O(n log n)的方式，在一个点可以更新一个范围的时候可以发挥很大作用。

记得当年NOIp2017我考PJ（那年的T4考到了单调队列），当时还不会，在考后听教练讲了一遍之后仍旧处于懵逼状态，大概1个月前照着题解打了一遍，但是到了现在已经忘得差不多了QwQ，于是写了一遍优化过的多重背包来练练手。

$$ \texttt{ Writer：世界最蒻Dilute}$$

$$\texttt{ #A 某脱碳甲醛的电磁炮题}$$

$$\texttt{ 出题人 Dilute}​$$

电流公式$I=\frac{U}{R}$大家都知道（不知道的话在题面中也给出了）

所以直接输出就可以了（ps：C++中除法自动向下取整）

首先我们考虑一件事：如果存在一个人，使任何一个人都不认识，我们称这种人为“孤独”的人，那么警察只能通过调查他来取得他的身份。

然后对于一个不“孤独”的人，我们发现他们肯定至少被一个那些“孤独”的人直接或间接的认识。

所以我们得出结论：只要统计“孤独”的人的数量即可。

你照着这么做，就可以获得100 mod 10分的好成绩。

一道非常好的练倍增的题目

思路很简单，就是倍增处理出每个点往后$2^i$个点的路径权值和与最小值，同时要注意一下$k​$要用longlong存，否则会挂掉

如果不会倍增的右转百度找其他博客去吧……我这里就不赘述了

欧洲退火！

没错你没有看错这么一道Heap的题我拿出了退火来做！

那么模拟退火的基本思路这里不讲了如果要看右转P1337去看。

废话不多说，上思路

竟然没有人写题解2333那本蒟蒻就来$H_2O$一篇吧

首先，看完题面不难想到DP，之后再看数据范围考虑$O(N^3)$DP，之后瞎搞一通可以想到

$f[i][j]$表示在前$i$个里面经历$k$次出逃可以取到最少的修改数

那么接下来我们就发现$f[i][j]$可以影响的范围为$f[u][j+1]$($i < u ≤n$)，然后我们就可以写出如下的程序：

暴力赛高！暴力是全世界最最最（以下省略2147483647个人最）NB的算法！

AC记录

这里似乎没有朴素的算法啊（啊当然Pascal不算哈）

我开始做题的时候还专门为了求稳去学习了一下$nlogn$的最长上升子序列呢

其实我们会发现，暴力的时间复杂度其实根本不是$O(n^2)$，就让我们来分析一下暴力的时间复杂度。

令人智熄的二分操作

AC记录

要看正常的解法请看其他题解

而且还蛮快的。。。

其实，这是非常奇葩的一个想法

总体思路就是：二分答案

你没听错，二分答案

我们从题面中可以看到，其实这道题的拥挤度也就$10000$而已，所以我们就会发现二分似乎可以？？？

存图存完之后直接二分，二分的$Check()$里面打一个$BFS$，来求能否通往终点，就好了

具体的东西就上代码来看吧

STL大法好！

（看到楼下的大佬们都没有用我这个方法，我就来脱碳甲醛一下辣~~）

以上都是废话

我所说的这个方法，具体思路是这样的：

• 最首先，基础的并查集大家应该都会，如果不会的话可以看代码或者出门右转P3367并查集模板
• 然后，STL中的Map可以直接方便地解决字符串哈希的问题
• 但是，每次都用一遍Map似乎显得有些不优美，似乎有些慢的说
• 所以，我们需要引进两个数组，一个Num和一个Names
• Num是一个Map，它的作用就是Num[“A”]表示名为A的人的编号
• 于是，Names就是反过来的Num，Name[i]表示编号为i的人的名字
• 总体而言，不仅加快了速度，还方便了调试