愿我们都能在自己的季节里，生长成一片竹林

最短路B3601 最短路问题（Bellman-Ford）B3601 [图论与代数结构 201] 最短路问题 - 洛谷 这道题就是把每条边扫一遍。 因为边的顺序不知道，所以需要跑 n-1 轮。每一轮把所有边都松一遍，同时用 flag 记录这一轮有没有发生更新——用来判定全局是否最优：如果一整轮扫下来没有任何更新，就说明已经改完了，可以提前退出。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<bits/stdc++.h>using namespace std;using ll=long long;#define endl '\n'struct Edge{ ll u,v,w;};const ll maxn=2e9;int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n&g...

并查集P1955 程序自动分析（并查集 + 离散化）P1955 [NOI2015] 程序自动分析 - 洛谷 并查集 + 离散化，和算法竞赛那本书的例题一模一样。 思路：先建立并查集，把所有 e == 1（相等）的约束合并起来。因为还需要判断不相等的情况，所以得跑两轮——第二轮遇到 e == 0 且两个数已经在同一集合里，就说明前面的约束和它矛盾，直接 break。 变量范围到 1e9 而约束只有 1e5 条，所以要先离散化，把出现过的数映射到 1..m 的连续编号上。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include<bits/stdc++.h>using namespace std;using ll=long long;#define endl '\n'cons...

拓扑排序 拓扑序 = DAG 的线性化：把「u 在 v 前」的偏序展平成一条链。所以只有 DAG 才有拓扑序。队列弹出数 < n ⇒ 有环 —— 判环万能判据。 12345678// Kahn 模板骨架queue<int> q; for (i) if (!ind[i]) q.push(i);int cnt = 0;while (!q.empty()) { int u = q.front(); q.pop(); cnt++; for (v : e[u]) if (--ind[v] == 0) q.push(v);}// cnt < n , 有环 P1347 排序P1347 [ECNA 2001] 排序 - 洛谷 这道题就是边排序边判断，其他都可以套模板。每读入一条关系就重跑一遍拓扑，返回三种状态： -1：弹出点数 cnt < n，说明有环，矛盾； 1：cnt == n 且队列任何时刻都只有一个元素（sure 没被置 false），说明拓扑序唯一，可以确定； 0：能排完但不唯一，信息不足，继续加关系。 1234567...

二分答案这两道题可以带学带练，思路几乎是一样的。学完二分你会发现，精髓其实在于思考如何借助二分写函数体 check：我们有了查找的思路，难点在于把求最优解的问题，转化为给定一个值 Mid，判定是否存在一个可行方案达到 Mid。 P1873 砍树P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 我们要找一个合适的高度去切，刚好用二分来确定最后的 H。 易错点： 右边界 r 可以直接赋成 400000，也可以赋成数组里的最大值。 check 里算到 ans >= m 就提前返回，不用等全部算完，超过即符合题意。 123456789101112131415161718192021222324252627282930313233#include<bits/stdc++.h>using namespace std;using ll = long long;ll n, m;vector<ll> a;bool check(int h) { ll ans = 0; for (int i = 1; i <=...

记忆化搜索记忆化递归 = 用搜索的方式写 DP。递归天然表达「状态转移」，再加上一个 dp 数组记录算过的答案，避免重复计算，就是记忆化。 它比递推 DP 好在不用纠结拓扑序，状态怎么想得顺就怎么写；坏处是有递归栈开销，某些题目会被卡。 P1044 栈P1044 [NOIP 2003 普及组] 栈 - 洛谷 这道题还有一个变种，是我一开始学栈的时候就出现的，同源但不同做法。看到 dfs 的时候我惊讶于这道题还能用这么简洁的方式，着实震惊。 状态设计：x 是已经入过栈的数字个数，y 是当前栈里有多少个。 123456789101112int n;ll dp[20][20];ll dfs(int x, int y) { if (x == n && y == 0) return 1; // 所有数字已输出，找到一种合法方案 if (dp[x][y] != -1) return dp[x][y]; ll ans = 0; if (x < n) ans += dfs(x + 1, y + 1); // 还有数字没进栈 ...

分治分治的核心一句话：把大问题拆成形式完全一致的小问题，直到问题足够简单。 听起来简单，但「怎么拆」往往才是难点。 CF 1385D a-Good StringProblem - D - Codeforces 每次折半：左边一半全部改成 c，右边一半递归下去变成 c+1 开头的 good string；再和反过来的方案取 min。原题「折半」表达得很明显，不往分治想确实不应该。 1234567891011121314151617181920212223242526272829#include<bits/stdc++.h>using namespace std;int solve(string& s, int l, int r, char c) { if (l == r) return (s[l] != c); // 一个字符：不是 c 就改 1 次，是 c 就不用改 int mid = (l + r) / 2; int cnt1 = 0; // 方案1：左半全变 c，右半递归 fo...

差分与前缀和差分是前缀和的逆运算：对差分数组求一遍前缀和，就还原回原数组。它最大的用处是把「区间加」的修改从 O(n) 变成 O(1)——只需要在两端打上标记。 一维差分：P3406 海底高铁P3406 海底高铁 - 洛谷 题目要翻译一下：乘客按顺序经过若干段铁路，每一段可以「买票」也可以「买 IC 卡」。判断每一段到底买什么更划算，就是简单贪心；而「每一段被经过多少次」用差分统计。 易错点：处理 diff 左右端点时，右端点不需要 r++。因为我们要的是区间被覆盖的次数，diff[start]++、diff[end]-- 即可。 123456789101112131415161718192021222324252627282930313233343536#include<bits/stdc++.h>using namespace std;using ll = long long;struct Pay { ll a, b, c; };int main() { ios::sync_with_stdio(false); cin.tie(...

这学期离散数学属实上的比线代舒爽太多因为很多知识点可以切实应用到代码实现，几乎是立即反馈。本篇可能比较杂乱，会慢慢整理，先挖好坑再说（）

主要做ai解答的记录 哈希模板cf大佬博客) 1. 标准 unordered_map 安全增强版这是在比赛中最通用的写法，兼容所有现代 C++ 编译器。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include <iostream>#include <unordered_map>#include <chrono> // 必须引用，用于获取随机时间using namespace std;// --- 第一部分：把图片里的 custom_hash 结构体抄下来 ---struct custom_hash { static uint64_t splitmix64(uint64_t x) { // 这是一个高品质的扰动函数，把输入的位彻底打乱 x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf5...

这篇文章主要收录一些不算奇淫技巧的小tips,这种比较散乱的小知识点记起来还是需要系统化 蔡勒公式（时间转换到星期几）学校oj有很多时间转换的题目但是这个可以说知道公式就秒了，如果自己思考实现还是要费一点时间。更巧的是算法期中考完试在楼道还捡到了一张小纸条，就赫然写着这个公式。有种低山臭水遇知音感英雄所见略同感。蔡勒（Zeller）公式是一个非常有名的数学公式，可以直接根据日期（年、月、日）算出那天是星期几。 公式W = (d + 2m + 3(m+1)/5 + y + y/4 - y/100 + y/400 + 1) \bmod 7 $y$：年份 $m$：月份 $d$：日期 $W$：结果。0代表周日，1代表周一，2代表周二…以此类推，6代表周六。 潜规则蔡勒公式有一个非常特殊的规定，如果你忘了这一步，算出来全是错的： 如果月份是 1月 或 2月，必须把它们看作是前一年的 13月 和 14月。 比如：2024年 1月 20日 $\rightarrow$ 看作 2023年 13月 20日。 比如：2024年 2月 10日 $\rightarrow$ 看作 2023年 14月 1...