LuoguP2765 魔术球问题 首先,很难看出来这是一道网络流题.但是因为在网络流24题中，所以还是用网络流的思路 首先考虑完全平方数的限制。 如果\(i,j\)满足\(i < j\) 且 $i + j \(为完全平方数我们就在\)i - j $连一条有向边 练完之后我们会得到这样一个图(图来自luogu题解)  发现这是一个DAG，而且我们将柱子的限制转化为路径条数。问题就转化成了 LuoguP2764 最小路径覆盖问题 然后，我们就一直加球，加到需要的路径条数大于给定的柱子数为止 #include<cstdio> #include<cctype> #incl...

LuoguP1402 酒店之王 最大流题目。带有一定的思维技(tao)巧(lu) 依旧分析题目。如果只有房间或者菜一种限制。那么就是一道裸的最大流了 可是两种条件都应当满足， 这貌似也可以做。 因为每个菜和房间都只能选择一次。我们很容易建出这样一个模型  上图中矩形表示房间，圆表示顾客，三角表示菜 但是很不幸，是错的 因为我们忽略了人的限制，每个菜和房间都只能选择一次，每个人也只能被选择一次,即上图中圆圈的点流量不超过\(1\)。 所以应该将每个圆圈拆成两个点,中间连一条容量为\(1\)的边，表示人数限制。 #include<cstdio> #include<cctype&g...

luoguP4313 文理分科 复习完之后做了道典型题目。 这道题条件有点多 我们逐个分析 如果没有\(sameart\)或者\(samescience\)的限制,就是一个裸的最大权闭合子图的问题了 但是再考虑有的话（其实还是一个最大权闭合子图） 很明显我们还是可以按照套路分成两个集合. 然后先按照权值分别划分\(S\),\(T\)集合 然后再向他要求的学生连一条\(\infty\) 放一张奇丑无比的图  感性理解一下就好了 #include<cstdio> #include<cstring> #include<iostream> #include<c...

网络流复习笔记 主要用来复习一下自己之前学过的网络流。 因为当时都是直接抄的题解,莫得印象。所以写篇博客加强记忆。 最大流 LuoguP3254 圆桌问题 先分析题目。 比较明显，如果我们用网络流的思路去分析这个问题。将会将每个单位和每个餐桌都看做点。然后由于每个单位的人理论上可以坐在任意餐桌,同时对于一个餐桌一个单位只能有一个人。所以每个单位向每个餐桌连一条容量为\(1\)的边。 第\(i\)个单位最多有\(r_i\)人，所以从原点向它连容量为\(r_i\)的边。 餐桌同样考虑。 如果最大流等于总人数.说明有可行方案。 #include<cstdio> #include<c...

3.31考试题解及总结 Noip难度的题目还翻车，真的是菜出了天际。自己最近思维出现问题.静不下心来 T1 很明显的套路题，转化为差分数组.我们可以花费\(1\)的代价来对一个一个位置\(+1\)另一个位置\(-1\).最后统计一下大于\(k\)的之和与小于\(-k\)的差值之和取个\(max\)就好了 #include<cstdio> #include<iostream> #include<cctype> #include<cstring> #include<algorithm> #define LL long long using...

简单概率期望题目总汇 由于自己初学概率期望,学的都是简单题，就不分开写博客了. 51Nod 1639绑鞋带 非常入门的概率期望题目。但因为题目意思比较恶心. 一共有\(2 * n\)个鞋头，第\(i\)次操作前还有\(2 * n - (i - 1) * 2\)个鞋头，由于我们选出一个后,它不能和自己绑,也不能和和它在同一条链上的绑。 所以 \(f_{i + 1}= f_i * \frac{2 * n - (i - 2) * 2 - 2}{2 * n - (i - 1) * 2 - 1}\) #include<cstdio> #include<cstring> #incl...

FFT NTT错误总结 1 处理\(r\)数组时忘记赋值 r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1)); 2 负数重载运算符 point operator * (point a,point b){ return point(a.x * b.x - a.y * b.y,a.x * b.y + a.y * b.x); } 3 欧拉公式记不清楚 point Wn = point(cos(Pi / mid),type * sin(Pi / mid)); 4 蝴蝶操作忘记*w point x = A[j + k]...

P4173 残缺的字符串 FFT在字符串匹配中的应用. 能解决大概这种问题: 给定长度为\(m\)的A串,长度为\(n\)的B串。问A串在B串中的匹配数 我们设一个函数(下标从\(0\)开始) \(C(x,y) =A(x)- B(y)\)，若为0,表示B串中以第\(y\)个字符结尾的字符可以与A串中以\(x\)节为结尾的字符可以匹配 \(P(x) = \sum_{i = 0}^{m - 1}C(i,x - m + i + 1)\) 但是很遗憾当\(P(x)\),等于零时,只能够说明上述子串的字符集相同. 为什么？因为负数的存在！ 我们考虑怎么去掉负数,平方！ \(P(x) = \sum_{i ...

首先,我们需要知道第二类斯特林数组的组合意义(即容斥) \(S^m_n = \frac{1}{m!} \sum_{k = 0}^{m}(-1)^k*C^k_m*(m - k)^n\) 然后,题目中让我们求 \(f(n) = \sum_{i = 0}^n\sum_{j = i}^nS^j_i*2^j*j!\) 我们直接将\(S^j_i\)展开成上述的组合意义,同时\(j\)从\(0\)开始枚举（因为当\(m > n\)时,\(S^m_n = 0\)） 则有: \(f(n) = \sum_{i = 0}^n\sum_{j = 0}^n\frac{1}{j!}\sum_{k = 0}^j(-1...