anyiak
立身须正,为人当明

编程
文章归档

洛谷 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 阅读全文