洛谷 P3205 [HNOI2010]合唱队 区间DP

这篇文章没有摘要

    2021-01-03    31    0 阅读全文

最短路计数问题

定义cnt[i]表示源点到i点的最短路条数。 通过v点松弛源点r到u的距离时，若成功松弛（d[v]+val[i]<d[u]），r→v的最短路条数取代了r→u的最短路条数（cnt[u]=cnt[v];），因为最短路不是同一个长度了，所以之前记录的作废。 若新路径和目前最短路长度一样（d[v]+v…

    2020-12-25    34    0 阅读全文

OI学习路线

ver. 1.0.1 假设你已经熟练掌握C++语言和OI有关的部分。 贪心和DP并没有被加入其中，原因是我觉得贪心和动态规划是一种思想，需要长期练习，不能被简单地归入某个学习阶段。 Part 1 算法基础 排序栈、队列、链表二分查找和二分答案前缀和和差分dfs和bfs （…

    2020-12-24    54    0 阅读全文

CF1463A Dungeon 简单模拟

“每 7 次开炮为增强版 ”，说明六次开炮是普通开炮，造成 $1$ 点伤害，一次开炮是增强版，给每个怪物造成 $1$ 点伤害，三个怪物就是 $3$ 点。 所以每 $7$ 次开炮共计能造成 $1∗6+3=9$ 点伤害。 要想在某次增强版开炮后所有的怪物都挂掉， $a+b+c$ 就必须是 $9$ 的…

    2020-12-20    36    0 阅读全文

洛谷 P2629 好消息，坏消息 双单调队列

先预处理出前缀和，从$1$到$n$扫一遍统计可行的$k$。$i$把$1～n$分成$1～i-1$和$i～n$两部分。用两个单调队列Ql,Qr,分别维护$1～i-1$部分和$i～n$部分的最坏心情。一开始$i=1$时，所有元素都已经进入Qr中(可能已经出队)，i逐渐增加的过程中，新进Ql的元素如果在Qr中存…

    2020-12-09    53    0 阅读全文

组合数学找门

写在前面 为什么不是“入门”而是“找门”呢？因为受我水平限制，这篇文章写得实在是太粗浅了，仅仅带你看到了组合数学的大门，实在是无力带你走进去QAQ。 前置知识 阶乘 一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且$0$的阶乘为$1$…

    2020-10-08    151    0 阅读全文

NOIP初赛知识点笔记

二叉树的遍历 先序遍历：根左右后序遍历：左右根中序遍历：左根右 哈夫曼树 哈夫曼（Huffman）算法是一种采用了贪心思想的算法。 在哈夫曼树中，叶结点的个数比非叶结点个数多 1。 哈夫曼树权值较大的结点离根较近。 排序 稳定排序： 插入…

    2020-08-11    161    0 阅读全文