ZuesHans's little bag

图论与搜索 DFS 深度优先搜索 用途：枚举、路径搜索、连通性。 常见坑：注意回溯还原（如标记数组清零），加剪枝防超时。 小猫爬山 1234567891011121314151617181920212223242526int n, w, ans = 20;vector<int> lcs(20);void dfs(int stepnum, int lcnum, const vector<int> &cats) { if (lcnum >= ans) return; if (stepnum == n) { ans = lcnum; return; } for (int j = 1; j <= lcnum; j++) if (lcs[j] + cats[stepnum] <= w) { lcs[j] += cats[stepnum]; dfs(stepnum + 1, lcnum, ...

贪心 如上P2887 [USACO07NOV] Sunscreen就是典型的贪心，重点是如何去通过我们固定左端点的大胆尝试去实现 反悔贪心 P2949 [USACO09OPEN] Work Scheduling G (全局贪心) 我一开始的错误思路 人人都能想得到去走时间，然后将最紧急的任务先做了然后再紧急的任务里面贪心 最大的问题是:你的贪心是占用时间的，是有后效性的，万一后面有价值更高的任务他就不是期望值了 DP？时间跨度巨大：Di≤109D_i \le 10^9Di​≤109。任务数量（N）较大：N≤105N \le 10^5N≤105。离散化时间之后依然n方 正确思路以及为什么: 以后你在做题时，如果满足以下特征，请立刻想到反悔贪心： 选择带有顺序性（或者可以排序）。 当前的选择会影响后续的资源（比如占用了时间、金钱）。 我们在乎的是“数量”或者“总价值”。 如果发生冲突，我们可以通过“撤销”之前的某个劣质选择，来接纳当前的优质选择，且这种交换一定是不亏的（甚至更赚） AC代码 12345678910111213141516171819202...

基础算法 二分搜索 用途：答案单调时逼近最优解。 常见坑： 最小值模板：if(check) r=mid else l=mid+1。 最大值模板：if(check) l=mid else r=mid-1。 注意边界（left 初始化为最大单元素）。 货运难题 1234567891011121314151617181920212223242526272829int n, k;bool check(int pans, const vector<int> &nums) { int hsh = 0, cnt = 0; for (int i = 0; i < n; i++) { if (hsh + nums[i] > pans) { cnt++; hsh = nums[i]; } else hsh += nums[i]; } return cnt <= k-1;}voi...

[toc] 遗老 数组构造 C_Meximum_Array_2.cpp 杂 欧拉筛和最大公约数 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121#include <iostream>#include <vector>#include <numeric> // 用于 std::gcd (C++17), 但手写gcd更通用using namespace std;// ================= 配置区域 =================const int MAXN = 100...

这里是计算几何 使用建议 精度：定义dcmp来判断所有double 向量化 调试：cout << fixed << setprecision(10); 前置头 123456789const double EPS = 1e-9;const double PI = acos(-1.0);inline int dcmp(double x) { if (x < -EPS) return -1; if (x > EPS) return 1; return 0;}//这个函数可以做到：1，提取数字的符号 2，比较两个数的大小:调用的时候:dcmp(a-b)inline double sqr(double x) { return x * x; }//取平方 struct 点(包含重载运算符) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950struc...

二进制常见trick 快速判断奇偶：n & 1 乘除2n >> 1 n << 1 x>>k是指x右移k格就是把最右边顶掉就是除以二 正数是向下取整负数是向下（比如-5>>1=-3） 关于2的次方：必须注意的两个“坑”坑一：优先级问题位运算的优先级低于加减法！错误：1 << k - 1 (会被解析为 1 << (k - 1))错误：a + 1 << k (会被解析为 (a + 1) << k)正确：总是加括号！(1 << k)坑二：不要用 pow(2, k)pow() 函数是浮点运算，返回值是 double。缺点：慢：比位运算慢得多。精度问题：当 kkk 很大时，转回 int 或 long long 可能会出现精度丢失（比如算出 31.99999 转成 31）。结论：整数运算永远只用 <<。 是不是2的整数次幂 作用：log2 n; n & (n - 1) lowbit:用于树状数组update 和 query 操作b...

单调栈模板 运用场景 下一个/上一个更大/更小值的位置 去除重复子串 精妙之处 在栈里面存下标，只在更新的时候“取下标”。 AC代码 123456789101112131415161718192021222324int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } stack<int> stk; vector<int> ans(n); for (int i = 0; i < n; i++) { while (!stk.empty() && a[stk.top()] < a[i]) { ans[stk.top()] = i + 1; stk.pop(); } stk.push(i); &...

unique O(N) 去重 (只去相邻重复) 离散化 (Sort + Unique + Erase) 必须先 Sort！ m = unique(a, a+n) - a; 返回去重后末尾指针。 next_permutation O(N) 下一个全排列 暴力枚举全排列 生成字典序 do { ... } while(next_permutation(all(s))); lower_boundO(logN) 找 ≥\ge≥ val 的第一个位置 LIS (最长上升子序列) 查找排名/前驱后继返回迭代器。 idx = lower_bound(all(v), val) - v.begin(); __gcd O(logV) 最大公约数 数论、化简分数 lcm(a,b) = a/gcd(a,b)*b fill O(N) 赋值 初始化数组/容器 fill(a, a+n, val);比 memset 安全，支持任意值 (memset 只能 0/-1/0x3f)。 vector 我的最爱 支持可变大小，不支持开出来的大小清空 O(1) p...

Dijkstra最短路算法 Dijkstra模板 P4779 【模板】单源最短路径（标准版） 题号: P4799 链接: 题目链接 算法类型:最短路 AC 代码: 123456789101112131415161718192021222324252627282930313233343536373839void solve(){ ll n,m,s; cin>>n>>m>>s; //前面是点,后面是距离 vector<vector<pair<int,ll>>> mp(n+1); rep(i,0,m-1) { int u,v,w; cin>>u>>v>>w; mp[u].push_back({v,w}); // mp[v].push_back({u,w});这道题是有向边所以不要入两次！！ } pri...

2026年1月12日 烂完了 复健 无所谓了 人最重要的就是战胜自己的心魔 2026年1月5日 1 2 3 4 5 不想言 我好难受 相似 2025年12月6日 通宵之后打了个cacc，主要是更新博客有点麻烦，实在是很情绪化或者很日常的就发推特了 现在头晕 新生赛很顺利，也是拿到和计算机学院入门票了 我还是很喜欢unk，他是最好的宝宝，感觉越来越好了… 情绪就是这样过山车吧，不重要，我知道的是 我现在真的在想和他有以后 能够永远在一起，能够有两个人的幸福世界 我爱你，，我爱你，，我爱你 2025年11月15日 摆烂一天。。恋爱真是伤人的东西。。 昨晚的div2似乎unrated了，那也好，因为c也不完全是我自己想出来的。 应该已经emo有个几天了，上周末也是这样子。我怎么总是这样。这简直就是我大脑里面巨大的BUG，什么时候维护能删掉啊？我会去期待她的消息。我都不想给他设特别关注了，死人，水群也不回我消息。特别关注弹出来让我白高兴一场。 感觉快要分手了，我操，想到这个就难受 我本来以为是我在这一次恋爱里面发挥有问题，顺着我的性子发了点消息给他，ok，验证了真的不是我的问题...