DP 1
本文是个人对算法竞赛中一些 DP（动态规划）题目的经验总结。 文章偏向经验分享和归纳总结，而非教程，适合有一定 DP 基础的同学进阶。我尽量把思考过程写得详细些。 笔者在队内对 DP 的主要贡献是发现 DP 然后喂给队友，检查做法的合法性，有时候也会参与优化 DP。所以写过的 DP 经典题并不多，文章里的例子大多是 24, 25 年区域赛题。 文章的目录是按自己的理解设计的，可能与传统的 DP 教学大纲有些出入，具体理由写在各章节里。 （不保证表述绝对严谨。 DP 概述 基本概念与分类 一般认为，DP（Dynamic Programming，动态规划）是一种将原问题分解为简单子问题求解复杂问题的方法。广义上说，递推也可以算作 DP 的一种。 从定义就能看出，DP 最重要的是 子问题 （即状态）。我们将一个复杂的问题 拆解 为若干个（在时空都允许范围内的）子问题，存储若干信息，再利用子问题 拼凑 出所需问题的解。 DP 问题按其功能大致有三类：最优化 、 计数 和 判定 。判定类 DP 可视为计数 DP 的一种，即方案数存 bool；也可视为最优化的一种，即对可行性取...
2024 ICPC 上海补题记录 (8 题 BCDEFGIJ)
The 2024 ICPC Asia Shanghai Regional Contest (The 3rd Universal Cup. Stage 29: Metropolis)
2024 ICPC 南京补题记录 (8 题 BCEGIJKM)
The 2024 ICPC Asia Nanjing Regional Contest (The 3rd Universal Cup. Stage 16: Nanjing)
〔主机註記〕第 88 周主机註記 (Oct.13 - Oct.19)
第 88 周主机註記 月 (Oct.13) 火 (Oct.14) 水 (Oct.15) 木 (Oct.16) 金 (Oct.17) 土 (Oct.18) 金線 武漢預測金線 81，我一直以爲我們會預測金。 但是我們去年也沒預測銀啊，打起來除了第一把不都在銀左右。有道理，所以還有 +50 的希望。也有可能是從網絡賽到區域賽之間突飛猛進了，該加訓了，讓我突飛猛進一下。 我一直覺得蛐蛐榜這種概率參考性不大，蒽，不如說對單支隊伍而言。預測基於曾經多場比賽，而最終的比賽只有一場，個體上發生了就是 100%。比如說人家都覺得很惡心但是賊對你胃口的場次，網絡賽 500 名都能拿金牌。 大數據是群體湧現的結果，比賽結果與預測的金線差不多，但內部每個隊伍的排名會完全不一樣。主要是你看銅區也就算了，可能真有不會做的。但你看金區銀區，哪個隊伍沒點本事的，線上也就是多過或者少過一兩題的區別，這就很明了了。 所以說，這個東西還是退役之後鬥蛐蛐好玩呢。現在抓緊備賽就好，蛐蛐榜並不能說明什麽，也不能改變什麽。看這個不如做法，求求題目更合胃口。 日 (Oct.19)
〔主机註記〕第 87 周主机註記 (Oct.6 - Oct.12)
第 87 周主机註記 月 (Oct.6) ——你是不是知道我在想什么？ ——我怎么知道？ ——你不能说你知道。 ——你有毛病吧！ 火 (Oct.7) 水 (Oct.8) 木 (Oct.9) 金 (Oct.10) 土 (Oct.11) 日 (Oct.12)
![Educational Codeforces Round 183 ABCDF [251007]](/img/posts/acm/codeforces-cover.webp)
Educational Codeforces Round 183 ABCDF [251007]
重操旧业了，CF 还是要好好打 A - Candies for Nephews 123456void solve() { int n; cin >> n; cout << ((3 - n % 3) % 3) << endl;} B - Deck of Cards 1234567891011121314151617181920212223242526272829void solve() { int n, k; cin >> n >> k; string s; cin >> s; if (k == n) { cout << string(n, '-') << endl; return; } int c0 = count(s.begin(), s.end(), '0'); int c1...
2025 CCPC Online 网络预选赛 ADEFGK
第十一届中国大学生程序设计竞赛网络预选赛（CCPC Online 2025）