集训队 线段 题解p10009

Link UVA1658 Admiral Question 给出一个图，找出 \(1 \sim n\) 的两条，使得路径和最小 Solution 可以把点拆开，把除了 \(1\) 和 \(n\) 的点 \(i\) ，拆成 \(i\) 和 \(i'\) ，\(i\) 到 \(i'\) 连一条费用为 \ ......

Link P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G Question 牛栏中有 \(N\) 头奶牛，和一些 \(M\) 对爱慕关系，A->B 表示 A 爱慕 B。每个奶牛都喜欢自己，被所有奶牛喜欢就是一头明星奶牛，求明星奶牛的数量 Solution 考虑一个强连通 ......

https://qoj.ac/contest/506/problem/1359 problem 给定一张大小为 的有向图 。现在告诉你敌军大本营在节点 \(s\) 和友军基地在节点 \(t\)。你需要在每个点上放置一定数量的APERS bounding mine来杀伤敌方步兵。 为了达成战术效果，你 ......

https://qoj.ac/contest/537/problem/1173 problem 给定 \(n\leq 10^6\) 个区间，你需要求出能够最多选出多少对区间，使得两个区间不交（区间为闭区间）。要求一个区间最多属于一对选出的区间。 solution 这是一般图匹配问题的特殊情况，所以放 ......

题意 给定 \(n\) 个数，有 \(m\) 个询问，每个询问给定 \(l\) 和 \(r\)，求出区间 \(l\) 到 \(r\) 中的最小众数出现次数，强制在线。 数据范围：\(n\le 500000\)，空间限制：\(62.5MB\)。 思路 这道题的弱化版是 蒲公英，这道题加强的地方在于数据 ......

原题链接：P4081 题意 给定一颗 \(n\) 个点 \(m\) 条边的树，求这棵树的严格次小生成树。 严格次小生成树指：边权和大于最小生成树，且边权和最小的生成树。 思路 首先可以用克鲁斯卡尔求出这棵树的最小生成树，然后考虑用类似于反悔贪心的思路来做。 对于每一条不在最小生成树中的边 \(u \ ......

题意不多赘述。 思路 如果两个所选的三角形有重合部分的话，那么这种情况肯定是不会出现的。因为如果把这两个三角形合成一个大三角形的话，不仅覆盖面积会增大，而且花费的代价还不会多。 于是我们可以想到用 dp 来解决，设 \(dp_{i}\) 表示删完横坐标为 \(0\) 到 \(i\) 中的点的最小代价 ......

题意 给定一张有向图 \(G\)，有 \(n\) 个点和 \(m\) 条边，问是否存在一种拓扑序的排列 \(P\) 使得 \(l_{i} \le p_{i} \le r_{i}\)。 思路 首先对于一条边 \(u \to v\)，如果限制满足 \(r_{v}\le r_{u}\) 或者 \(l_{v ......

传送门：https://atcoder.jp/contests/abc332/tasks/abc332_f 容易发现，对于一个位置 $i$，$A_i$ 的最终值是由对 $i$ 的最后一次赋值操作决定的；因此，将所有操作按时间顺序倒过来考虑，则由第 $j$ 次操作决定 $A_i$ 最终值的概率为"在第 ......

传送门：https://atcoder.jp/contests/abc332/tasks/abc332_g 看完题，第一眼反应为最大流。 建模方式为：以颜色为左部点，盒子为右部点，源点 $S$ 向颜色 $i$ 连一条容量为 $A_i$ 的边，盒子 $j$ 向汇点 $T$ 连一条容量为 $B_j$ 的 ......

2023HFOI小学组 题解 存钱(saving) 题目传送门 前置芝士：数学 很明显，数据范围过大，考虑用周期性来解决。 周一至周日节省的钱数相同，很明显是一个周期。 算出来所有周期，再把剩下来的天数节省的钱累加。 /*Written by smx*/ #include<bits/stdc++.h ......

原题链接：CF848C。 题意：给定一个序列 \(a\)，维护两个操作。 操作一：将 \(a_x\) 修改为 \(y\) 操作二：对于区间 \(l,r\) 中出现的每一种数 \(x\)，求出 \(\sum f(x)\)。 \(f(x)\) 表示区间 \(l\) 到 \(r\) 内 \(x\) 最后一 ......

题意：求出一个序列 \(q\) 的最长二维不上升子序列，以及求出每个数出现在这个最长二维不上升子序列中的概率。 很显然，三维偏序问题可以用 cdq 分治来优化 dp。 对于第一问，直接把这道题的 \(n^{2}\) dp 优化到 \(\log^{2}\) 即可。具体来讲，设 \(l_{i}\) 表示 ......

是一道树剖好题，之前听 lsl 讲过一点，于是很快就做出来了。 题意：有一个 \(n\) 个节点的树，最开始的时候所有边都是轻边，维护两个操作： 操作一：将 \(u\) 到 \(v\) 的路径中经过的所有点的邻边变为轻边，再将这条路径上的边变为重边。 操作二：求出 \(u\) 到 \(v\) 这条路 ......

题意：给定一颗 \(n\) 个点的树，点 \(i\) 有权值 \(a_{i}\)，边有边权。现在有另外一个完全图，两点之间的边权为树上两点之间的距离加上树上两点的点权，求这张完全图的最小生成树。 首先有一个很显然的暴力，把完全图中每两点之间的边权算出来，然后跑一边最小生成树，时间复杂度 \(O(n^ ......

其他 线段树详解与实现 - 知乎⁤ (zhihu.com) 线段树 - OI Wiki (oi-wiki.org) 线段树 学习笔记 - xujindong 的博客 - 洛谷博客 (luogu.com.cn) 简介 线段树(segment tree)是一种二叉搜索树，也是平衡二叉树，它的每一个结点对 ......

可能算是日记性质的东西，主要是想也得记一下讲的东西，放闲话里的话似乎有点不道德 . 随时更新，想起什么就写点什么吧 . 目录Dec. 9Dec. 10 Dec. 9 可能是 Day 0 这样的内容 . 登上 QQ 发现 Alpha1022 还给我发消息了，还是关于我的闲话的，害怕 /fad 火车上整 ......

Link ARC169 B Subsegments with Small Sums Question \(x\) 是一个序列，定义 \(f(x)\) 为把序列 \(x\) 切成几段，每段的和不能超过 \(S\) 的最小段数 给出序列 \(A=(A_1,A_2,\cdots,A_N)\) 求： \[\ ......

\(\text{By DaiRuiChen 007}\) Contest Link A. Cultivation Problem Link 题目大意 在一个 \(r\times c\) 的网格上有 \(n\) 个格子是黑色的。 每次操作可以把所有黑色格子向上下左右的某个方向扩展一格，即把所有黑色格子 ......

给定 n 个整数构成的序列 a，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。 题目一开始的离散化复杂度为\(O(n\log n)\)，构建基础主席树复杂度为\(O(n\log n)\)，统计并插入的复杂度是\(O(n\log n + n\log n)=O(n\log n)\)，询问的 ......

更好的阅读 这是一道找规律的题目。 因为我个人习惯，以下部分使用从 \(1\) 开始的下标讲述。 首先我们以 \(1\) 来说：发现在第 \(x\) 行 \(y\) 列的连通块是可以直接连到第 \(1\) 列的，所以很容易可以得出 \(1\) 到 \(y\) 列的连通块数量是 \(2^y-1\)。 ......

const int N = 1e5 + 10; int n, m; int a[N]; struct Tree{ int l,r; ll sum,add; }tr[4*N]; void build(int u,int l,int r){ // l=tr[u].l;r=tr[u].r; //注释掉的部 ......

CTT 结束后发现自己胡策题都没咋补，这下尴尬了。主要原本胡策就打着玩的（ 怎么 CTT 平均难度比胡策还要简单啊.jpg。 还是随便写几篇题解吧。 先来个补全进度表，根据胡策 OJ 或 qoj 通过情况来评判： 测试赛（10.22） A + B Problem 奥林匹克五子棋 元旦激光炮 Day ......

【题解】CQOI2017 - 小 Q 的表格 https://www.luogu.com.cn/problem/P3700 首先考虑题面给的两个式子。由式二可以得到： \[\dfrac{f(a,a+b)}{a(a+b)}=\dfrac{f(a,b)}{ab} \]发现这个很像辗转相除，可得 \[\d ......

题意： 思路： 当 $ k \ge n $ 时，一定无法构造。 证明： $ n $ 个点的无向图，每个点的度数 $ d ∈ [1，n - 1] $ ，度数的种数一定不会超过 $ n - 1 $ 。 当 $ k \le n - 1 $ 时，构造方案如下： 首先，选取前 $ k + 1 $ 个点，构造成 ......

题意： 思路： 由于需要维护极差，因此将 $ a $ 排序；由于相同的数对因子的种类和极差的贡献重复，因此将 $ a $ 去重。 设满足条件且极差最小的方案为： $ a_1 $ ， $ a_3 $ ， $ a_4 $ ， $ a_7 $ ， $ a_9 $ ，该方案等价于区间 $ [1，9] $ 。 ......

Contest Link A. Construction of Highway Problem Link 题目大意 给 \(n\) 个点，初始每个点有权值 \(w_i\)，\(n-1\) 次操作连一条边 \(u\gets v\)，其中 \(u\) 与 \(1\) 连通，\(v\) 与 \(1\) 不 ......

题意： 思路： 构造： $ n $ 行 $ m $ 列，先填奇数行，每行填 $ m $ 个，第 $ 2i - 1 $ 行依次填入 $ (i - 1) \cdot m + 1 $ ， $ (i - 1) \cdot m + 2 $ ， $ ... $ ， $ i \cdot m - 1 $ ， $ i ......

题意： 思路： 树形 $ dp $ ： 设 $ cnt_u $ 表示以 $ u $ 为根的子树中叶子节点的数量，那么状态转移方程有： 当 $ u $ 为叶子节点时， $ cnt_u = 1 $ ； 当 $ u $ 不为叶子节点时， $ cnt_u = \sum_{i ∈ Son_u} cnt_{v_ ......

Contest Link \(\text{By DaiRuiChen007}\) A. Examination Problem Link 题目大意 有 \(n\) 个二元组 \((a,b)\) 和 \(q\) 个询问 \((x,y,z)\)，每个询问求满足 \(a\ge x\)，\(b\ge y\) ......