2018九月刷题列表

Preface

开学了，于是我又开了全新的坑

由于文化课方面的压力（不存在的），所以那种日记形式的写法我也不想搞了（费时间）

话说写日记可以提升一个人的语文素养，然而我开学考作文扣了十几分

我尽量会写上简要的一句话题解（ORZ LX dalao）的。

9.28 Updata：发现如果整个下半年写一起的话看起来很不舒服太乱，所以决定每月写一篇。

---

List

• 信息学奥赛一本通——第 12 章 差分约束系统 差分约束其实不是很难水的一匹好吧？

• Luogu P3232 [HNOI2013]游走 把边的期望转化为点的期望然后高斯消元解，最后贪心一下

• Luogu P2634 [国家集训队]聪聪可可 比较简单的点分治，记录一下路径长度膜(3)的值即可

• Luogu P4457 [BJOI2018]治疗之雨 超级恶心的高斯消元，需要手动优化至(O(n^2))，最后注意一些特殊数据的特判。

• 信息学奥赛一本通——第 13 章 强连通分量 好多题目以前都做过，而且SCC的题目本身也比较好想

• LOJ #569. 「LibreOJ Round #11」Misaka Network 与测试 贪心找到一些性质之后转化为最大匹配问题，直接匈牙利即可

• CF 809 B. Glad to see you! 交互+二分，注意一些边界细节以及缓存的清空

• BZOJ 1181: [CROATIAN2009]IZBROI选举 又是一道二合一，求最大值贪心+模拟，求最小值贪心+二分+DP检验，对于数学推导和细节的考验也比较大

• BZOJ 3316: JC loves Mkk 非常好想的分数规划+单调队列检验，分奇偶位讨论，但是细节巨多，比较考验耐心

• NOIP模拟赛 伍 实力翻车，我连黄题都写不来，还是退役算了

• 信息学奥赛一本通——第 14 章 割点和桥 LOJ上面的题目还是非常简单的，并没有圆方树这一类的东西，比较模板化

• Luogu P2761 软件补丁问题 又是假的网络流24题，数据范围小，直接状压然后用SPFA转移即可。比较常见的套路，合理使用位运算可以大大简化代码。

• 学了下计算几何入门的一些东西，也就只会一些很简单的东西了吧，做了道叉积性质题：POJ 2318 TOYS ，比较简单。

• Luogu P4040 [AHOI2014/JSOI2014]宅男计划 黑题++，比较新颖的三分，检验的时候玄学贪心一下，不过那个神仙结论只能靠猜出题人就是这么说的，还有一些神仙的细节问题要注意。

• Luogu P4576 [CQOI2013]棋盘游戏 一道博弈论+对抗搜索的题，比较简单，并不需要(alpha-beta)剪枝注意是不可以，直接记忆化即可

• 信息学奥赛一本通——第 15 章 欧拉回路 终于把图论结束了，欧拉回路题一半是模板，一半是并查集性质的运用，不过神仙题也有但是CXRdalao会教我的

• NOIP模拟赛 陆 涨Rating战役，Rank2成功100+，发现map是真的又快又好用

• 信息学奥赛一本通——第 16 章 树状数组 DS的part1，十分之简单，毕竟没有涉及树状数组原理的题目

• NOIP 2015 提高组初赛试题 初赛也是要准备的，81感觉今年进不了复赛了

• NOIP 2016 提高组初赛试题 好像是第一次做初赛上90刚好90

• Luogu P3195 [HNOI2008]玩具装箱TOY 第一道斜率优化DP题，感觉有点迷不过还是坚持写掉了

• Luogu P3299 [SDOI2013]保护出题人 先写出DP方程发现就是一个裸的斜率式子。然后单调栈维护一个下凸壳，在凸壳上三分最大值。话说我没写EPS精度竟然比我写了的还好

• CF 606E. Freelancer's Dreams 线性规划，如果直接做的话就要在凸包上跑所以就根本不会。但是DLS给出了一种转化为对偶问题的做法，这样就可以上三分解决了

• Luogu P2054 [AHOI2005]洗牌 合理推导画图猜结论之后发现式子，之后直接快速幂+逆元即可。不过有坑点：会爆longlong尽管没有这种数据，并且由于模数不一定是素数，因此逆元要用exgcd求

• 信息学奥赛一本通——第 17 章 RMQ 问题 大部分都是简单题，开始默默改码风鬼畜的使用class

• 信息学奥赛一本通——第 18 章 线段树 题目基本上都做过，而且普遍都很简单感觉我其他随便找点线段树题都比里面的难

• Luogu P3198 [HNOI2008]遥远的行星 神仙题，由于结果的相对误差不超过 5% 即可，所以用近似算法可以解决，小范围暴力，大范围乱搞就过了。

• 信息学奥赛一本通——第 19 章 倍增求 LCA 个人感觉时DS里面最难的一块了（只是在LOJ的题目中），有一个平衡树+LCA维护虚树的是真的恐怖。

• 信息学奥赛一本通——第 21 章 平衡树 Treap 基本上全做过，一道题用Treap写不来，只会用Splay写，还有一题操作太明显就写了set

• NOIP 2017 提高组初赛试题 去年PJ初赛的时候就做过一些题，但是还是83好菜啊

• NOIP 2014 提高组初赛试题 我去差一点就90了89菜得要死 NOIp2014提高组初赛错题简析

• Luogu P3640 [APIO2013]出题人 中秋假期太无聊了就写个题答快乐一下。造数据卡别人的idea真的很赞。断断续续写了半天。主要是那个卡DJ的丧心病狂，我开始就差十几步就给他卡T了

• NOIP模拟赛 柒 220又是Rank2。T2以前翰爷上课讲过，不过开始OJ出了点问题变(frac{1}{4})rated了。所以本来应该涨80的现在才涨了20，不过终于破了1900的魔咒（我去我一不小心把Manchery搞出首页了）

• 信息学奥赛一本通——第 20 章 树链剖分 又有些模板做过，难点都在线段树，一道玄学记录端点以及一道动态开点的还是挺考验码量的好在我写树剖一般都很稳，一发过样例就AC

• Luogu P4139 上帝与集合的正确用法 随机找到的一道数学题，由于看起来很有趣就写了下。欧拉筛+扩展欧拉定理即可完成，最后加一个记忆化保证复杂度。

• 学了下Manacher算法，感觉不难主要是为了做最近的一道题。写了板子Luogu P3805 【模板】manacher算法

• Luogu P2053 [SCOI2007]修车 拆点+费用流的好题，首先引进贪心的思想（类似一堆人排队接水的那个题），然后为了保证符合常理用最大流维护。

• 信息学奥赛一本通——第 22 章 区间类动态规划 我连区间DP先枚举什么都不知道，所以全部都写了万能的记忆化搜索，然后就都很水了

• Luogu P4363 [九省联考2018]一双木棋chess 通过插板法（或爆搜）发现状态数才几十万，果断状压后用map存状态之后跑对抗搜索即可。

• CF 718C. Sasha and Array 看到斐波那契和区间修改就果断想到用线段树维护矩阵乘法。由于矩阵运算的前分配律所以是可以化加为乘的。略卡常数。

• Luogu P2568 GCD 数论好题。可以用莫比乌斯反演但是没有必要。归化问题之后发现可以直接用欧拉函数的前缀和来解。 Sol

• BZOJ 4804: 欧拉心算 数论好题。可以用莫比乌斯反演但是没有必要。将问题归化后可以利用上一题的结论然后再次转换为欧拉函数的前缀和搞，之后再套一个除法分块上去即可。 Sol

• Luogu P4092 [HEOI2016/TJOI2016]树 正解貌似是并查集不会。感觉树上很可做一想感觉可以上树剖。但实际上我们只需要利用欧拉序列来构造线段树即可。这里尝试写了标记永久化，速率快了一些。

• hihoCoder #1461 : Rikka with Number 吉利的神仙题。发现那个鬼畜的计算过程说白了就是个gcd的逆过程。所以我们rand得出答案（可过），通过猜结论数学分析发现答案在(n imes0.618)附近((0.618 approx frac{sqrt 5-1}{2})，即黄金分割)

• 信息学奥赛一本通——第 23 章 树型动态规划 难度比区间DP略有提升，不过也有一些不错的姿势像基环外向树等等，总体比较简单

• BZOJ 3563: DZY Loves Chinese&&BZOJ 3569: DZY Loves Chinese II&&BZOJ 3237: [Ahoi2013]连通图 三倍经验题，考虑生成树的性质，给非树边随机一个权值，并且将树边的权值设为非树边的权值异或和。然后对于每次询问如果不连通则可以在边集中找出一个子集的异或和为(0)。线性基处理即可。

• UVA11762 Race to 1 比较显然的有限状态自动机（或者叫马尔科夫过程？）常见套路是记忆化搜索或高斯消元，但这里的主元可以抵消一下，因此直接概率DP+记搜即可。

---

Postscript

不知不觉一个月过去了，感觉整个玖月都是相安无事呢

题目做的也挺多主要是天天晚上在机房

看来我就是那种真的把机房当成家的人了。

然而索性的是初三第一次月考出人意料的还可以没有爆炸。文科作业全不做+晚自习不去，我是真的刚。

语数外科社：(106+111+82(+frac{?}{30})+147+72)，英语市里的人机对话30分还没有出来

考到了久违的班里第一主要是语文从期初考的全班三四十名考到了第一

感觉运气有点好呢，还是希望这个学期这样浪下去然后文化课不要炸掉把。