主要是以前写过的一些luogu上的蓝题,口胡+补一下简易题解
P2303 [SDOI2012] Longge 的问题 ↗#
容易想到答案就是
直接展开算就完事了
https://www.luogu.com.cn/paste/0gbib398 ↗
P2371 [国家集训队] 墨墨的等式 ↗#
一开始没啥想法,看了标签发现有个最短路
反应过来是同余最短路,但是不记得怎么写了,刚好复习一下
就是板子题,去最大的那个距离当模数,然后最短路跑出每个余数最少几次可以到达
答案直接差分一下求的就完事了
https://www.luogu.com.cn/paste/hkwsmi6g ↗
P2375 [NOI2014] 动物园 ↗#
没睡醒了属于是
其实就是在做kmp的时候顺便搞一个表示从这里开始网上还能跳几次
求出来后重新匹配一些,乘起来就完事了
https://www.luogu.com.cn/paste/mnhfbwlc ↗
P2424 约数和 ↗#
求前缀和,然后用的减去的答案即可
不难发现把式子列出来后用整除分块可以很方便的做这题
https://www.luogu.com.cn/paste/o0x2vuon ↗
P2447 [SDOI2010] 外星千足虫 ↗#
不难看出可以直接高斯消元,用bitset优化即可
https://www.luogu.com.cn/paste/n8u2qiit ↗
P2467 [SDOI2010] 地精部落 ↗#
一眼DP,想着类似P2059 [JLOI2013] 卡牌游戏 ↗这题一样设状态,然后转移
设表示考虑前个数,然后以开头作为山峰的方案数
但是发现不太会转移,懵了
不难发现可以先钦定第一个是山峰,最后答案乘二即可,可以直接取互补的那个状态就是山谷开始的了
既然想到互补,那么就可以考虑可以从哪些状态转移过来了
其实就两种情况,一个是和相邻,那么就相当于是要求个,然后开头且作为山谷的方案数,因为互补不难想到可以直接用然后把这些状态的全部取互补就是一样的了。另一种情况是和不相邻,那么发现这种情况下把和互换貌似对结构没啥影响,一样是满足条件的状态,于是就可以直接加上
所以就
冲就完事了
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]之间的
//这里的符号一定不能打错!!!!(血的教训)
}
}
cppP2511 [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发现难点是要看出来答案函数是凸函数
P2634 [国家集训队] 聪聪可可 ↗#
一眼点分治板子
P3953 [NOIP 2017 提高组] 逛公园 ↗#
首先建个反图,跑个最短路得到
然后设表示从到距离为的方案数
转移不难转移,的情况就是出现环
看代码不难理解
https://www.luogu.com.cn/paste/ptj7ceir ↗
P2657 [SCOI2009] windy 数 ↗#
数位DP板子题
https://www.luogu.com.cn/paste/cbxvyqhb ↗
P2672 [NOIP 2015 普及组] 推销员 ↗#
首先不难发现第一个的位置是可以暴力找出来的,假设为
然后第一个位置确定后,剩下的被分成两部分,前面那部分就只和相关
后面那部分的贡献是
左右分别用优先队列维护即可
https://www.luogu.com.cn/article/qd6x7mh4 ↗
P2680 [NOIP 2015 提高组] 运输计划 ↗#
这题非暴力数据结构做法还真有点意思
答案显然满足可二分性,所以先二分答案,然后考虑所有的航道
对所有大于 的航道求个交,如果交为空显然就不成立
否则就取路径交上最大的那一条边即可
路径求交可以直接树上查分,用倍增求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即可
https://www.luogu.com.cn/paste/t6h1yv1d ↗
P3403 跳楼机 ↗#
扫了一眼标签看见图论,才反应过来是同余最短路
https://www.luogu.com.cn/paste/8xtk42xu ↗
P3396 哈希冲突 ↗#
根号分治没看出来也是有点糖
对于小于 的 直接提前预处理即可
对于大于 的直接暴力跳来求和
https://www.luogu.com.cn/paste/2170ct3a ↗
P3507 [POI 2010] GRA-The Minima Game ↗#
有趣
首先不难发现排好序以后一定是一段一段取的
令表示记录最优的差值
然后转移就是
就是当前这个和上一个连起来一起取,或者单独取这个,然后和之前的差值做差得到新的
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] 球形空间产生器 ↗#
一眼看出来应该是高斯消元或者模拟退火
结果发现两个都行
高斯消元卡在第一步转换了,闹麻
实际上就直接拿个方程依次做差,得到个方程开解就完事了
https://www.luogu.com.cn/paste/a049o4w4 ↗
P4113 [HEOI2012] 采花 ↗#
这种问题一般都可以先将询问离线,然后按照右端点从小到大考虑
必须要至少两朵才算,我们可以用树状数组维护,每个颜色只让倒数第二个有1的贡献,其余的没有贡献即可,这个可以用树状数组简单维护
https://www.luogu.com.cn/paste/07m3op7e ↗
P4101 [HEOI2014] 人人尽说江南好 ↗#
脑子坏了,想不动了
扫了几个题解都没看懂
然后终于发现原来不管怎么操作,都可以是到达最终状态的步数一样
直接假设每次把一个大小为的和最大的合并,然后计算步数看看奇偶即可判断
https://www.luogu.com.cn/article/w2pmnzk3 ↗
P4127 [AHOI2009] 同类分布 ↗#
把原数看成原根了,懵逼了半分钟
一眼数位DP,但是发现考虑如果记录各个位数数字和作为余数的话在DP的过程中会变,感觉很gg,于是乎可以直接枚举每一个数字和,然后记录膜这玩意的余数即可
代码非常浅显易懂
https://www.luogu.com.cn/paste/aav9z6m0 ↗
CF593D Happy Tree Party ↗#
只要不是 的边最多跳log次, 只需要把 的全部用并查集合并起来就完事了
然鹅我以前的做法好像就只是暴力树链剖分
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
然后考虑设表示这个环的每个节点有哪些存在 中,然后强制 中最小的节点为起点, 为当前路径的终点,转移的时候不要改变起点(最小的节点),然后判断是否会连成环,加起来即可
https://www.luogu.com.cn/paste/i4resfgr ↗
P4170 [CQOI2007] 涂色 ↗#
被数据范围迷惑了
一眼dp,状态显然,但是转移有点懵
发现这题被初二的自己秒了,感觉有点麻
不难发现状态显然为
考虑怎么转移,可以发现有两种策略
当 的时候,直接
就是在染色的时候顺便染上另一个节点,感觉比较显然(但是刚刚没想到)
然后就是枚举中间节点,然后分开两部分分别染色再求和取最小值
区间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 ↗#
一眼子序列自动机,子序列自动机是啥来着?
定义一个数组, 表示从 开始字符 第一次出现的位置
这个倒过来循环跑一遍就可以搞出来,这玩意好像就是子序列自动机
然后在这个上面进行bfs 找到第一个 就好了
当然也可以在建立子序列自动机的时候顺便 dp 求答案
代码实现非常简单
https://www.luogu.com.cn/paste/z3b4i2p8 ↗
UVA1335 Beijing Guards ↗#
有点意思
没想到可以将问题转换,然后分割成两部分,然后再二分答案
https://www.luogu.com.cn/article/44crqg53 ↗
UVA10859 放置街灯 Placing Lampposts ↗#
没意识到无向无环图就是森林然后卡死在第一步有点难绷
如果只考虑总数最小,显然就是一个简单的dp
设 表示以对于子树 , 当前这个节点放不放灯的最优答案
可以用网络流常用套路(扩域?),将被一盏灯照亮的值变为 10000 + 1, 被两盏照亮的设为 , 这样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 ↗#
完全没往这个方向去想,有点意思
一开始以为是什么结论题,结果发现是数学题
设表示 向 传递的金币数量
移项变成
然后展开归纳变成
设
那么
只需要确定 的值即可得到别的
答案就是
不难发现这样就变成了小学奥数题(好像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大力求出来了
直接计算即可