搜索结果
查询Tags标签： maxn，共有 417条记录-
题解 treecnt
Description\(n\leq 500,k\leq 2000\) Solution 令 \(w(i,j)\) 表示同时含有 \(i,j\) 两个点的限制的数量 , 在 \(i,j\) 之间连一条权值为 \(w(i,j)\) 的边 . 那么可以观察到 , 每个限制最多对生成树总边权贡献 \(|S|-1\) , 同时必须贡献 \(|S|-1\) 才是一个合法的生成树 …
2022/4/1 23:23:40 人评论 次浏览 -
【Coel.学习笔记】【一个阶段的结束】01-Trie树（01字典树）求异或路径
题前闲语 是的，变成闲语了（别问我为什么要改） 今天考完了月考，虽然发挥得不是很好但终归是结束了，休息一下~ 刚好深进也到货了，开始新一轮学习吧！ 题目简介 题目描述 给定一棵 \(n\) 个点的带权树，结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点，求最长的异…
2022/3/31 23:22:00 人评论 次浏览 -
[WC2018] 通道
[WC2018] 通道 题目描述 给你三棵树，然后每条边有边权，求一个点对 \((x,y)\) ，最大化 \(dist1(x,y)+dist2(x,y)+dist3(x,y)\)，输出这个最大值。 \(n\le 10^5,w\le 10^{12}\)。 题解 这道题真的是道好题。就是有点难写。 我们首先考虑一棵树的时候，我们考虑枚举 \(lca…
2022/3/31 6:21:37 人评论 次浏览 -
[SDOI2019] 热闹的聚会与尴尬的聚会
前言 在洛谷题解逛了一圈，不是随机化乱搞就是带log的做法，这里来一个线性且正确性有保证的做法。 人傻常数大，打不过随机化/kk 题目 洛谷 LibreOJ 讲解 做法是每次删除度最小的点，贪心加入独立集。因为很多题解都证过了，这里就不证正确性了。 讲一下实现。 我们对每个…
2022/3/30 23:24:30 人评论 次浏览 -
P3143 钻石收藏家
传送门 题目需要求出两段不重合的序列使两段长度和最大。代码关键在于循环变量作为左指针，左右指针之间维护的是第二个序列，而第一个序列在左右指针向前推进的过程中其最大长度被保存下来了。#include<iostream> #include<algorithm> #define MAXN 50007 us…
2022/3/30 23:20:12 人评论 次浏览 -
P1950 长方形
传送门 以行为单位，统计以第k行为底边的矩形数量，而对于每一行，以每一格为基准计算左方案 li，右方案 ri，高方案 hi。同时为了防止重复计算，左方案 li 为这一列左边满足h值小于等于 hi 的列号（没有的话为0），右方案 ri 为这一列右边第一个满足h值小于hi的列号（如果…
2022/3/30 23:20:06 人评论 次浏览 -
3.30省选模拟
开局\(MTT\)优化\(dp,\)跳,\(dp\)计数,跳,虚树\(dp,QAQ,\)昨天是数学场,今天搁这\(dp\)场呢看题解都能看自闭... \(T1\) 考场上很容易转化到取石子,转化成阶梯博弈就好了,然后至于优化\(dp,\)使用\(MTT\)就好了 于是乎,我前几天看的一个博客,讲了除了阶梯博弈的所有博弈,看…
2022/3/30 23:19:45 人评论 次浏览 -
Floyd算法 解决多元汇最短路问题
接下来是图论问题求解最短路问题的最后一个，求解多元汇最短路问题 我们之前一般都是问1-n的最短路径，这里我们要能随便去问i到j的最短路径：这里介绍一下Floyd算法：我们只有一个d[maxn][maxn]数组直接存储从i到j的最短路径，我们先看代码： #include<bits/stdc++.h&…
2022/3/21 22:29:30 人评论 次浏览 -
【Algorithm】广度优先搜索（BFS）
前面介绍了深度优先搜索，可知 DFS 是以深度作为第一关键词的，即当碰到岔道口时总是先选择其中的一条岔路前进，而不管其他岔路，直到碰到死胡同时才返回岔道口并选择其他岔道口。 接下来介绍的广度优先搜索则是以广度为第一关键词，当碰到岔路口时，总是先依次访问从该岔…
2022/3/19 23:37:54 人评论 次浏览 -
Johnson 最短路算法
Johnson 算法 全源最短路径求解其实是单源最短路径的推广，求解单源最短路径的两种算法时间复杂度分别为：Dijkstra 单源最短路径算法：时间复杂度为 \(O(E + VlogV)\)，要求权值非负； Bellman-Ford 单源最短路径算法：时间复杂度为 \(O(VE)\)，适用于带负权值情况；如果…
2022/3/19 9:27:32 人评论 次浏览 -
第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 人评论 次浏览 -
[IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落(dp)
简单分析, 本题属于$2D/0D$问题,所以空间复杂度为$n^2$, 时间复杂度也是$n^2$ 这里我们定义$dp$方程$dp[i][j]$为i到j的子字符串变为回文字符串需要插入的字符的个数 初始化$dp[i][j]$为$inf$, $dp[i][i] = 0$ 显然$dp[i]j[j]$可以从$dp[i + 1][j - 1]$转移过来, 也可以从…
2022/3/10 6:14:52 人评论 次浏览 -
2016CCPC Final I. Mr. Panda and Crystal
题目大意 总共有魔力值 \(M\) ， \(N\) 种水晶， \(K\) 种合成公式，每种水晶还有一个基本信息： \(0\space p_{i}\) ：该种水晶不能够由魔力值直接生成，单价为 \(p_{i}\) 。 \(1\space c_{i} \space p_{i}\) ：该种水晶可以消耗 \(c_{i}\) 魔力值生成，单价为 \(p_{i}\)…
2022/3/9 23:19:55 人评论 次浏览 -
P7072 [CSP-J2020] 直播获奖 桶排序思想应用
P7072 [CSP-J2020] 直播获奖基本思想：求前几名是多少分。#include<algorithm> #include<iostream> using namespace std; const int maxn=100010; int a[maxn]; int t[610]; int main() {int ma,mi;ma=0x80000000;mi=0x7fffffff;int n,w,p;cin>>n>&…
2022/3/8 23:15:55 人评论 次浏览 -
【priority_queue】滑动窗口
题目链接 #10175. 「一本通 5.5 例 1」滑动窗口 - 题目 - LibreOJ (loj.ac) 前言 之前已经写过这道题的题解(2022GDUT寒假专题学习-1 B,F,I,J题 - blockche - 博客园 (cnblogs.com))，当时用的是 deque 模拟单调队列的方法来维护最大值，但后来突然发现其实可以直接用 pri…
2022/3/4 23:21:22 人评论 次浏览
