20200403 Shortest Path 下载pdf，获得更好的阅读体验。 提取码：f1ji  题意翻译 有一棵有 个结点的树（ 为偶数）将其划分为 对点对，使得点对间距离综合最小，求该最小值。 多测， 组测试数据。  题解 为了值最小，显然尽量不选重的。 对于一棵子树，如果它的大小是偶数，则可以在这个子树内完成配对。 如果它是奇数，则有一个点要继续向上配对。无论是和根结点还是和其他子树，这个点额外的贡献都是父节点往这个子树的连边。 只要 dfs 一遍就可以得出答案。  Code #include<bits/stdc++.h> using namespace std; type...

20200402 月月查华华的手机 下载pdf，获得更好的阅读体验。 提取码：06ez  问题简述 给出字符串 ，查询 是否为 的子串，询问 次。 查询 是否为 的子串可以用序列自动机完成。  序列自动机 在 JSOI2019SC 听过这个科技，现在又查了几个博客复习了一下。 序列自动机的构建 序列自动机的核心在于 数组（由于其他一些字符串算法，常习惯写为 。  代表位置 后字符 第一次出现的位置。   当从位置 移动到位置 时，显然只有一个字符的 值发生变化。 代码： void Build(void) { n = strlen(s + 1); for(int i = n; i >= 1...

下载pdf，获得更好阅读体验。提取码：ke7w。 upd：这好像是 08 年哪个省省选题原题 题意转化 毒瘤出题人把 放在最后，害得眼睛不好的选手一开始没看到想了好长时间...   为一棵树 那这样就是一棵根为 的树上删除若干条边，使得所有叶子结点都与根不连通。  树形 DP 画一棵树，假设 有 个子树   根据 DP 子问题的思想，我们已经知道了下面 个子树，使得其叶子结点不能到 的最小代价。 此时，对于子树 ，有两种方案：一种是采取子树决策的方案，一种是删掉 的边，显然取最小更优。 对于叶子结点，子树决策为 即可。   #include<bits/stdc++.h> using...

单调队列模板题 每次先把已经超过范围的扔掉。 然后把范围内不可能成为最优解的扔掉。 然后入队。 很久以前写的代码： #include<iostream> #include<cstdio> using namespace std; #define maxn 10000007 int x,q[maxn],a[maxn],n,m,f,r; inline void Init() { scanf("%d%d",&n,&m); for(register int i=1;i<=n;i++) scanf("%d",&a[i]); } inline void...

首先有暴力枚举左端点和右端点的做法，加上前缀和优化，时间复杂度为  发现时间复杂度瓶颈在于枚举左右端点，考虑从这里着手优化。 发现枚举左端点后右端点最优解确定，所以可以只枚举左端点，时间复杂度  答案为 。

设 代表字符串 中 至 个字符，字符串 中 至 个字符是否能构成回文串。 然后区间DP套路转移。 时间复杂度  #include <bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 50 + 7; char s[maxn], p[maxn]; int dp[maxn][maxn][maxn][maxn], T; int main() { cin >> T; while (T--) { cin >> (s + 1) >> (p + 1); int n...

Prologue 菜的真实，普及都 AK 不掉.. Score: 100 + 100 + 100 + 0 = 300 rank: 16  A String 看来 PJ T1 考字符串读入成铁上钉钉了？ 考虑开桶 ，记录 ASCII 为 的字符是否出现即可。 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 100000 + 7; const int maxm = 200000 + 7; int n, m; #ifdef Graph_Define int Head[m...

考虑枚举 ，显然有贪心做法：取超过 武力值最大的 个人。 发现从小到大枚举 ，每次要把 不符合条件的删掉，再筛选 个，不太容易。 考虑倒序枚举 ，这样不符合条件的 只用筛选一次，用堆维护即可。

问题描述 LG3803  题解 点我  \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; const int maxn=1350000; const double Pi=acos(-1); int n,m; struct CP{ CP(double X=0,double Y=0) {x=X,y=Y;} double x,y; CP operator + (CP const &a) const {return CP(x+a.x,y+a.y);} CP operator - (CP const &amp...

问题描述 [BZOJ5339](https://www.lydsy.com/JudgeOnline/problem.php?id=5339） LG4593  题解 打出暴力之后，发现就是 \(F(x)=\sum\limits_{i=1}^{x}{i^{m+1}}\) 的时间复杂度比较高 暴力拉格朗日插值一下就好了  \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; #define int long long const int maxm=57; const int mod=1000000007; int T...

问题描述 LG4781  题解 多项式点值转系数的方法。 时间复杂度 \(O(n^2)\)，要线性求逆。 求 \(n+1\) 次多项式的拉格朗日插值式子： \[F(k)=\sum\limits_{i=0}^{n}{y_i \times \prod\limits_{i \neq j}{\frac{k-x_j}{x_i-x_j}}}\]  \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; const int mod=998244353; const int maxn=2007; #define int long...

问题描述 $ n $ 个点，$ m $ 条边，每条边 $ e $ 有一个流量下界 $ \text{lower}(e) $ 和流量上界 $ \text{upper}(e) $，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。  https://www.luogu.com.cn/blog/duyi/qian-tan-you-shang-xia-jie-di-wang-lao-liu  \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; const int maxn=220; const i...

问题描述 BZOJ2820 LG2257  题解 求 \(\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{m}{[gcd(i,j)==p]}}\) ，其中 \(p\)为质数，\(n<m\) 。 考虑不要求 \(gcd(i,j)\) 为质数时的做法： 可以转化为 \[\sum\limits_{g=1}^{n}{g \times \sum\limits_{i=1}^{\lfloor \frac{n}{g} \rfloor}{\sum\limits_{j=1}^{\lfloor \frac{m}{g} \rfloor}{[gcd(i,j)==1]}}}\] 根...

问题描述 BZOJ2127 LG1646  题解 和文理分科差不多 收益最大 -> 损失最小 -> 最小割 分别新建点表示互相关系就行了  \(\mathrm{Code}\) #include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f3f; int n,m,S,T; int Head[100*100*6+100],to[5000007],Next[5000007],w[5000007],tot=1; int d[100*100*6+100]; void addedge(int x,int y,i...