做题记录

【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

【UVa11292】贪心。code

【UVa11729】贪心。code

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

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

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

【UVa1030】留坑，还没打。

【UVa11464】状压。code

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

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

【UVa11384】二进制分解。code

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