[COGS]# 894. 追查坏牛奶 894. 追查坏牛奶 - COGS 前置知识 网络流最小割（本人习惯用Dinic） 问题拆解 这道题可以分为3问：求图的最小割容量求图的最小割集合大小输出最小的最小割集合问题1 这一问很好解决，只需要跑一遍Dinic求最大流即可（不会最大流的可以上网搜） 代码：…

LG P13280 「CZOI-R4」午夜巡游 不难发现除了 \(k\) 之外的其他数都是等价的，于是我们只需要计算 \(k\) 出现了几次即可。 考虑将所有 \(i\in[1,n]\) 连一条 \(i\to p_i\) 的有向边，这张图一定由若干个环组成。而最终答案为 \(k\) 等价于 \(k\) 所在的这个环的长度 \(x\mid m…

亲爱的 解题报告 简要题意 给定一个长度为 \(n\) 的字符串 \(s\)，字符集大小 \(62\)。询问有多少子序列满足：长度为 \(6\)。 形式如同 \(ABCDCD\)。（其中 \(ABCD\) 为四个互不相同的字符）数据范围：\(n \le 10^6\)。 分析 首先，我们注意到：第 \(3\) 个字符是特殊的。因为…

U606908 树 题目背景 现有一棵树，这棵树由以下代码生成。 int cnt=0; int solve(int n){if(n==0){cnt++;return cnt-1;}int ls=solve(n-1);int rs=solve(n-1);adde(ls,rs);return ls; }其中 adde(x,y) 表示加入一条连接 \(x,y\) 的边。 可以发现，如果运行 solve(n)，可以得到…

🌫️ 追忆 Recall中英文对照散文诗我常常追忆过去。 I often find myself lingering in the past. 生命瞬间定格在脑海。 Moments of life, caught in an instant, remain etched in my mind. 我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。 I fold and curl the ho…

目录等待事件持续等待周期间歇条件变量可能的死锁 等待事件 持续等待 当一个线程等待另一个线程完成任务时，持续的检查共享数据标志(用于做保护工作的互斥量)，直到另一线程完成工作时对这个标志进行重设。但这样一方面等待线程会一直被阻塞，浪费了资源；而被等待线程如果被打…

有点想不到的trick 题目有两个操作，分别是对 \([l,r]\) 区间进行升序和降序排序，在最后询问某个位置 \(q\) 上的值是多少。 真的去对一个序列做排序会让复杂度很难看，但如果是给一个 \(01\) 序列排序是比较轻松的，记录一下 \(1\) 的个数，每次1操作就可以用两次区间覆盖来代…

杜教筛和PN筛一类亚线性筛 亚线性筛是指能在小于线性的复杂度内完成一些筛法的一类筛。 狄利克雷卷积 对于数论函数 \(F\) 和 \(G\) ，定义其狄利克雷卷积为： \[(F*G)[n]=\sum_{d | n}F[d]\cdot G[n/d] \]几个性质：两个积性函数的迪利克雷卷积仍然是积性函数。 结合律：\(F*(…