杂题乱做2 • lomit

其实就两种情况，一个是 $j$ 和 $j-1$ 相邻，那么就相当于是要求 $i-1$ 个，然后 $j-1$ 开头且作为山谷的方案数，因为互补不难想到可以直接用 $f[i-1][i-(j-1)]$ 然后把这些状态的全部取互补就是一样的了。另一种情况是 $j$ 和 $j-1$ 不相邻，那么发现这种情况下把 $j$ 和 $j-1$ 互换貌似对结构没啥影响，一样是满足条件的状态，于是就可以直接加上 $f[i][j-1]$

所以就 $f[i][j] = f[i-1][i-(j-1)]+f[i][j-1]$

冲就完事了

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

P2485 [SDOI2011] 计算器 ↗#

拼接题

第一个问题用快速幂，第二个用exgcd，第三个用BSGS即可

刚好复习一下

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

P2503 [HAOI2006] 均分数据 ↗#

一眼模拟退火（功力还在，确信）

但是不记得怎么写了

浅谈模拟退火 ↗

void SA() {
	for(double t = Bt; t > Et; t = t * Ct) {
		int x = rand() % n + 1, y = rand() % n + 1;//随机一个新状态
		calc(); //计算新状态的答案
		if(ans < ANS) ANS = ans,nowx = x, nowy = y;//如果小于最优解就接受
		else if(exp((ANS - ans)*1.0 / t) > (double)rand() / RAND_MAX)
		 		//否则有一定概率接受, (double)rand() / RAND_MAX的取值是在[0,1]之间的
		 		//这里的符号一定不能打错!!!!(血的教训)
	}
}

cpp

P2511 [HAOI2008] 木棍分割 ↗#

第一反应二分答案

结果发现它要求的是方案数

不过没关系，先把长度二分出来，然后简单DP即可

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

P2519 [HAOI2011] problem a ↗#

第一步转化就不记得了

老了

首先第一步是可以转化为若干个排名区间，然后保留最多的区间

区间之间要么重叠，要么不交

同一个区间出现的次数不能超过区间长度

于是我们可以按照区间右端点从小到大排序，然后DP即可

具体看代码会比较好理解

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

P2607 [ZJOI2008] 骑士 ↗#

怎么感觉这题的代码不是我写的

首先不难发现一定是一个基环树森林

对于每个基环树，我们只需要随便找环上的一条边断开，然后对于边上的两个点分别强制其中一个不选（一开始考虑强制其中一个选，另一个不选发现假了，应该是只强制不选）

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

P2619 [国家集训队] Tree I ↗#

wqs二分板子题，不知道为什么当年会觉得这个算法难

现在感觉挺显然的

不懂了

https://www.luogu.com.cn/article/29g0lu2h ↗

哦没事了，翻看以前的blog发现难点是要看出来答案函数是凸函数

浅谈wqs二分 ↗

P2634 [国家集训队] 聪聪可可 ↗#

一眼点分治板子

浅谈树分治 ↗

P3953 [NOIP 2017 提高组] 逛公园 ↗#

首先建个反图，跑个最短路得到 $dis[u]$

然后设 $f[u][k]$ 表示从 $u$ 到 $n$ 距离为 $dis[u] + [k]$ 的方案数

转移不难转移， $-1$ 的情况就是出现环

看代码不难理解

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

P2657 [SCOI2009] windy 数 ↗#

数位DP板子题

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

P2672 [NOIP 2015 普及组] 推销员 ↗#

首先不难发现第一个的位置是可以暴力找出来的,假设为 $pos$

然后第一个位置确定后，剩下的被分成两部分，前面那部分就只和 $A[i]$ 相关

后面那部分的贡献是 $2*(S[i]-S[pos])+A[i]$

左右分别用优先队列维护即可

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

P2680 [NOIP 2015 提高组] 运输计划 ↗#

这题非暴力数据结构做法还真有点意思

答案显然满足可二分性，所以先二分答案 $mid$ ，然后考虑所有的航道

对所有大于 $mid$ 的航道求个交，如果交为空显然就不成立

否则就取路径交上最大的那一条边即可

路径求交可以直接树上查分，用倍增求LCA即可

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

P2698 [USACO12MAR] Flowerpot S ↗#

一眼二分+区间最大最小值

感觉这么做有点蠢

发现其实可以直接类似滑动窗口，两个单调队列维护最大最小值

具体可以看代码比较好理解

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

P2747 [USACO5.4] 周游加拿大Canada Tour ↗#

居然想不到怎么做，完蛋了

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

P3177 [HAOI2015] 树上染色 ↗#

这题倒不难，算是经典套路

考虑每一条边的贡献，然后设 $dp[u][i]$ 表示以 $u$ 为节点的子树，有 $i$ 个黑点的贡献

树上背包DP即可

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

P3403 跳楼机 ↗#

扫了一眼标签看见图论，才反应过来是同余最短路

https://www.luogu.com.cn/paste/8xtk42xu ↗

P3396 哈希冲突 ↗#

根号分治没看出来也是有点糖

对于小于 $\sqrt{n}$ 的 $p$ 直接提前预处理即可

对于大于 $\sqrt{n}$ 的直接暴力跳来求和

https://www.luogu.com.cn/paste/2170ct3a ↗

P3507 [POI 2010] GRA-The Minima Game ↗#

有趣

首先不难发现排好序以后一定是一段一段取的

令 $f[i]$ 表示记录最优的差值

然后转移就是 $f[i]=\max(f[i-1],a[i]-f[i])$

就是当前这个和上一个连起来一起取，或者单独取这个，然后和之前的差值做差得到新的

http://luogu.com.cn/paste/d01vfzif ↗

P3878 [TJOI2010] 分金币 ↗#

想了半天

突然发现自已以前是用模拟退火写的，草

实际上也可以直接折半搜索，然后对于每种情况，每种个数的用vector存起来

排个序，然后搜索另一边的时候直接二分即可

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

P3964 [TJOI2013] 松鼠聚会 ↗#

切比雪夫距离和曼哈顿距离的转换

https://www.luogu.com.cn/article/0aub49ev ↗

P4035 [JSOI2008] 球形空间产生器 ↗#

一眼看出来应该是高斯消元或者模拟退火

结果发现两个都行

高斯消元卡在第一步转换了，闹麻

实际上就直接拿 $n+1$ 个方程依次做差，得到 $n$ 个方程开解就完事了

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

P4113 [HEOI2012] 采花 ↗#

这种问题一般都可以先将询问离线，然后按照右端点从小到大考虑

必须要至少两朵才算，我们可以用树状数组维护，每个颜色只让倒数第二个有1的贡献，其余的没有贡献即可，这个可以用树状数组简单维护

https://www.luogu.com.cn/paste/07m3op7e ↗

P4101 [HEOI2014] 人人尽说江南好 ↗#

脑子坏了，想不动了

扫了几个题解都没看懂

然后终于发现原来不管怎么操作，都可以是到达最终状态的步数一样

直接假设每次把一个大小为 $1$ 的和最大的合并，然后计算步数看看奇偶即可判断

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

P4127 [AHOI2009] 同类分布 ↗#

把原数看成原根了，懵逼了半分钟

一眼数位DP，但是发现考虑如果记录各个位数数字和作为余数的话在DP的过程中会变，感觉很gg，于是乎可以直接枚举每一个数字和，然后记录膜这玩意的余数即可

代码非常浅显易懂

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

CF593D Happy Tree Party ↗#

只要不是 $1$ 的边最多跳log次, 只需要把 $1$ 的全部用并查集合并起来就完事了

然鹅我以前的做法好像就只是暴力树链剖分

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

CF558E A Simple Task ↗#

搞26棵线段树大力区间覆盖就完事了

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

CF449D Jzzhu and Numbers ↗#

想到先做一个高维前缀和(FWT，然后按照二进制1的个数容斥

差不多就是这样

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

CF11D A Simple Task ↗#

看数据范围确定状压dp

然后考虑设 $f[S][i]$ 表示这个环的每个节点有哪些存在 $S$ 中，然后强制 $S$ 中最小的节点为起点， $i$ 为当前路径的终点，转移的时候不要改变起点（最小的节点），然后判断是否会连成环，加起来即可

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

P4170 [CQOI2007] 涂色 ↗#

被数据范围迷惑了

一眼dp，状态显然，但是转移有点懵

发现这题被初二的自己秒了，感觉有点麻

不难发现状态显然为 $f[l][r]$

考虑怎么转移，可以发现有两种策略

当 $st[l] == st[r]$ 的时候，直接 $f[l][r] = \min(f[l + 1][r], f[l][r - 1])$

就是在染色的时候顺便染上另一个节点，感觉比较显然（但是刚刚没想到）

然后就是枚举中间节点，然后分开两部分分别染色再求和取最小值

区间dp板子题吧算是

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

P4212 外太空旅行 ↗#

众所周知，最大团问题是 NPC 问题

然后我一看我的代码是暴力搜索过的，懵了

看了看之前自己写的题解，哎，年少轻狂，殊不知是悲剧的开始（羟基计划司马了）

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

SP3267 DQUERY - D-query ↗#

第一眼莫队板子，但是马上反应过来好像也可以用主席树做（做题直觉）

但是没想好具体怎么做

其实发现直接离线下来按照右端点排序，扫描线

然后对于每个颜色，如果没出现过就在这个位置设为1，否则就将上一个出现的位置设为0，然后再将这个位置设为1，每次查询一个区间和即可（后缀和）

然后显然如果强制在线的话用主席树做就好, 没写代码，但是显然不难写

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

AT_arc081_c [ARC081E] Don’t Be a Subsequence ↗#

一眼子序列自动机，子序列自动机是啥来着？

定义一个数组， $nxt[i][c]$ 表示从 $i$ 开始字符 $j$ 第一次出现的位置

这个倒过来循环跑一遍就可以搞出来，这玩意好像就是子序列自动机

然后在这个上面进行bfs 找到第一个 $0$ 就好了

当然也可以在建立子序列自动机的时候顺便 dp 求答案

代码实现非常简单

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

UVA1335 Beijing Guards ↗#

有点意思

没想到可以将问题转换，然后分割成两部分，然后再二分答案

https://www.luogu.com.cn/article/44crqg53 ↗

UVA10859 放置街灯 Placing Lampposts ↗#

没意识到无向无环图就是森林然后卡死在第一步有点难绷

如果只考虑总数最小，显然就是一个简单的dp

设 $f[u][0/1]$ 表示以对于子树 $u$ ，当前这个节点放不放灯的最优答案

可以用网络流常用套路（扩域？），将被一盏灯照亮的值变为 10000 + 1，被两盏照亮的设为 $10000$ , 这样dp出来就能保证在总灯数最小的前提下，只被一盏灯照亮的边最少（即同时被两盏照亮的最多）

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

UVA10891 Game of Sum ↗#

想着直接记差值来区间dp，不知道可不可行

看自己之前写的代码，是记录先手的最优得分来dp的，式子需要改一下

试了一下记差值也是可以 AC的，还方便理解

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

UVA11300 Spreading the Wealth ↗#

完全没往这个方向去想，有点意思

一开始以为是什么结论题，结果发现是数学题

设 $X_i$ 表示 $i$ 向 $i-1$ 传递的金币数量

$A[i] - X[i] + X[i + 1] = average$

移项变成

$X[i+1]=average + X[i] - A[i]$

然后展开归纳变成

$X[i] = (i-1) * average - A[1] - A[2] - ... - A[i - 1] + X[1]$

设 $C[i] = A[1] + A[2] + .. + A[i -1 ] - (i - 1) * average$

那么 $X[i] = X[1] - C[i]$

只需要确定 $X[1]$ 的值即可得到别的

答案就是 $|X[1]| + |X[2]| + ... + |X[n]|$

不难发现这样就变成了小学奥数题（好像atcoder也有一题类似: D - Inc, Dec - Decomposition ↗）

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

P4301 [CQOI2013] 新Nim游戏 ↗#

看错题了，没啥想法

看代码才发现可以从大到小插入线性基，把插不进去的加起来就好了

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

P4306 [JSOI2010] 连通数 ↗#

先大力用tarjan缩点，判断连通性那里我直接用dfs+bitset大力求出来了

直接计算即可

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