搜索结果
查询Tags标签： MAXM，共有 15条记录-
CF292D Connected Components 题解
这道题给各位一种与之前不一样的做法。 首先显然可以使用并查集维护连通块个数，但是我们知道并查集 不支持删除，而题目是 区间询问，所以： 不支持删除+区间询问=回滚莫队！ 所以这道题可以用回滚莫队通过，没学过的可以看看 这篇博文。 那么对于这题，取块长 \(block =…
2022/4/14 23:16:18 人评论 次浏览 -
3.30省选模拟
开局\(MTT\)优化\(dp,\)跳,\(dp\)计数,跳,虚树\(dp,QAQ,\)昨天是数学场,今天搁这\(dp\)场呢看题解都能看自闭... \(T1\) 考场上很容易转化到取石子,转化成阶梯博弈就好了,然后至于优化\(dp,\)使用\(MTT\)就好了 于是乎,我前几天看的一个博客,讲了除了阶梯博弈的所有博弈,看…
2022/3/30 23:19:45 人评论 次浏览 -
第62期：图论-最小生成树-Boruvka算法
参考： Boruvka算法 - lher - 博客园 Boruvka算法_weixin_30527323的博客-CSDN博客 最小生成树的Boruvka算法__shivering_的博客-CSDN博客_boruvka算法 【模板】最小生成树题解 - 洛谷 1.【模板】最小生成树 - 洛谷#include<bits/stdc++.h> using namespace std; co…
2022/3/18 20:28:08 人评论 次浏览 -
Luogu P5897 [IOI2013]wombats
Luogu P5897 [IOI2013]wombats 为了统一记号，下文设矩形的行数为 \(n(\le 5000)\)，列数为 \(m(\le 200)\)，更新次数为 \(U(\le 500)\)，查询次数为 \(Q(\le 2\times 10^5)\)。 最暴力的想法是每一次查询时直接DP，时间复杂度为 \(\mathcal O(Qnm^2)\)。这显然过…
2022/3/9 6:17:33 人评论 次浏览 -
CF2800 722F Cyclic Cipher 题解
令当前时间为 \(t\)，则序列 \(i\) 取的到 \(j\) 需满足的条件为：\(t\equiv j \pmod {len_i}\)。 多个同余方程要一起考虑，不难想到 excrt（扩展中国剩余定理）。 考虑枚举具体的数字（\(1\sim m\)），遍历 \(1\sim n\)，肯定不可能把 excrt 跑完。（这样优化空间很小）…
2021/8/22 6:38:53 人评论 次浏览 -
CF2800 722F Cyclic Cipher 题解
令当前时间为 \(t\)，则序列 \(i\) 取的到 \(j\) 需满足的条件为：\(t\equiv j \pmod {len_i}\)。 多个同余方程要一起考虑，不难想到 excrt（扩展中国剩余定理）。 考虑枚举具体的数字（\(1\sim m\)），遍历 \(1\sim n\)，肯定不可能把 excrt 跑完。（这样优化空间很小）…
2021/8/22 6:38:53 人评论 次浏览 -
【缩点 动态规划】JZOJ_4253. 【五校联考7day2】QYQ在艾泽拉斯
题意 给出一个图，上面有若干连通块。 对于每个连通块，为有向边组成的图，每个点上有点权。 最多在\(K+1\)个连通块操作，使得遍历这个连通块获得的点权之和最大。 思路 将每个连通块上的环缩点，变成一个DAG然后dp即可。 代码 #include <queue> #include <stac…
2021/8/9 23:07:09 人评论 次浏览 -
【缩点 动态规划】JZOJ_4253. 【五校联考7day2】QYQ在艾泽拉斯
题意 给出一个图，上面有若干连通块。 对于每个连通块，为有向边组成的图，每个点上有点权。 最多在\(K+1\)个连通块操作，使得遍历这个连通块获得的点权之和最大。 思路 将每个连通块上的环缩点，变成一个DAG然后dp即可。 代码 #include <queue> #include <stac…
2021/8/9 23:07:09 人评论 次浏览 -
noip模拟32
\(\color{white}{\mathbb{山高而青云冷，池深而蛟穴昏，行以慎步，援以轻身，名之以：落石}}\)开题发现 \(t1\) 80分特别好写，于是先写了 但是这个做法没有任何扩展性，导致一直没有往正解的方向想 \(t3\) 看见有点的坐标，以为是计算几何，于是写完 \(t1\) 打了个暴力就…
2021/8/7 23:09:44 人评论 次浏览 -
noip模拟32
\(\color{white}{\mathbb{山高而青云冷，池深而蛟穴昏，行以慎步，援以轻身，名之以：落石}}\)开题发现 \(t1\) 80分特别好写，于是先写了 但是这个做法没有任何扩展性，导致一直没有往正解的方向想 \(t3\) 看见有点的坐标，以为是计算几何，于是写完 \(t1\) 打了个暴力就…
2021/8/7 23:09:44 人评论 次浏览 -
HH去散步
题目link：https://www.luogu.com.cn/problem/P2151Part0： 注意题目有重边。Part1： 首先这道题的题目限制为走过一条边不能按原边返回，这就导致了这个图的有向性，从而得出需要拆边的结论。Part2： 拆完边后，容易看出如果要想满足题目限制，那么相当于走过第 $i$ 条边…
2021/7/28 23:35:51 人评论 次浏览 -
HH去散步
题目link：https://www.luogu.com.cn/problem/P2151Part0： 注意题目有重边。Part1： 首先这道题的题目限制为走过一条边不能按原边返回，这就导致了这个图的有向性，从而得出需要拆边的结论。Part2： 拆完边后，容易看出如果要想满足题目限制，那么相当于走过第 $i$ 条边…
2021/7/28 23:35:51 人评论 次浏览 -
AtCoder Beginner Contest 210
A-Cabbages# include "iostream" # include "cstdio"using namespace std;int N,A,X,Y;int main(){scanf("%d%d%d%d",&N,&A,&X,&Y);printf("%d",N>=A?A*X+(N-A)*Y:N*X);return 0; }B-Bouzu Mekuri# include …
2021/7/21 6:10:06 人评论 次浏览 -
AtCoder Beginner Contest 210
A-Cabbages# include "iostream" # include "cstdio"using namespace std;int N,A,X,Y;int main(){scanf("%d%d%d%d",&N,&A,&X,&Y);printf("%d",N>=A?A*X+(N-A)*Y:N*X);return 0; }B-Bouzu Mekuri# include …
2021/7/21 6:10:06 人评论 次浏览 -
二分图匹配，匈牙利算法原理与实现
以下场景太过真实，但都是虚构，为了讲清楚理论的过程。如有雷同，纯属我瞎编，还望勿对号入座。1 婚恋市场，明码实价中国如今男女比例严重失衡，2021年预计将有9200万单身贵族。为了帮助解决这个社会性问题，提升整体人民的幸福感，小K打算投身到这份伟大的事业中。“几…
2021/4/29 12:27:44 人评论 次浏览
