做题记录

本想没做一道题写一篇题解。刚立下这个 flag 我就后悔了。于是就写一句话题解吧。事实证明旗子不能随便插啊。

如果有题目我专门开一篇文章我会加上链接。

以前做过的觉得有趣的题目也会一点点地加上来。

如果有 CE 的，可以试试 -std=c++11。

Codeforces

【CF3D】将每个问号变成左括号和有括号都有一个代价，求是最终串匹配的最小代价。用堆贪心，括号匹配问题。code

【CF6E】单调队列。code

【CF7D】字符串哈希。code

【CF7E】dp，大细节题。code

【CF9D】dp 题，询问 \(n\) 个点组成二叉树，高度大于等于 \(h\) 的有多少个。令 \(f[i][j]\) 表示 \(i\) 个节点高度小于等于 \(j\) 的二叉树有几个。code

【CF10D】经典的 dp 题。code

【CF13C】\(\mathcal{O}(n^2)\) dp 可过，但有 \(\mathcal{O}(n\log n)\) 的贪心。dp code greedy code

【CF14D】树上问题，树形 dp+分类讨论。code

【CF22E】求让该图变成强联通图至少增加多少边并输出边。图构造。code

【CF57E】打表找规律好题。code

【CF77C】树形 dp+贪心。code

【CF351D】树状数组，HH 的项链的升级版。code

【CF434D】网络流，建图。code

【CF449C】数论+构造。code

【CF505E】二分答案+贪心。code

【CF551C】二分答案+贪心。code

【CF675E】树状数组/线段树优化基于贪心的 dp。code

【CF875E】二分答案+贪心。code

【CF933B】有关多项式的构造题。code

【CF986B】贪心+数学。code

【CF1037D】大力模拟 BFS。 code

【CF1045B】一道有趣的数学+字符串题。code

【CF1096D】打完才发现开错题目了……dp，每个状态是一个类似矩阵的二维数组。先定义 \(0, 1, 2, 3\) 四个状态，然后每个二维数组记录的是像邻接表一样的：从 \(1\) 状态向 \(2\) 状态需要花费多少，然后大力转移。其实可以加强一下支持区间查询（套一只线段树即可），单点修改。code

【CF1103B】交互题。需要发现结论：当 \(x<a\) 时，\(x \le 2x\pmod a\Leftrightarrow x\le a\le 2x\)，然后先倍增枚举 \(x\) 再定范围，最后二分。还有 \(1\) 需要特判。话说这询问次数卡得好紧啊……code

UVa

【UVa11292】贪心。code

【UVa11729】贪心。code

【Uva11300】贪心，需要一点数学分析。code

【UVa1388】贪心，感觉是假题，结论需要暴搜验证。code

【UVa10881】挺有趣的题，需要发现一些结论。code

【UVa1030】留坑，还没打。

【UVa11464】状压。code

【UVa1352】暴搜。书上说要打表，但似乎有点多此一举……code

【UVa11210】留坑吧，看不懂题意啊……

【UVa11384】二进制分解。code

【UVa10795】udebug 上标程好像是假的……被这组数据卡了。理所当然错误的程序也过了，于是我的代码也过了……code(wrong)