loj专题

loj 最小生成树（模板）

最小生成树模板如下 kruskal算法 #include<stdio.h>#include<string.h>#include<algorithm>using namespace std;const int maxn=2e5+10;typedef long long ll;ll ans=0;int f[maxn],n,m;struct node{int x,y,z;}s[m

【loj P4570】: 元素线性基

传送门分析首先我们需要知道一个性质，线性基内的元素数量是唯一的，也就是说我们能够插入的数的个数是确定的，如果有一个数不能插入线性基，我们只需要更改插入顺序就可以了所以，我们可以贪心的去想，按照魔力值从大到小的顺序把元素需要插入线性基，能够插入就加上这个矿石的魔力值代码 #pragma GCC optimize(3)#include <bits/stdc++.h>#define

【LOJ】白雪皑皑并查集

传送⻔分析因为区间会被后面的区间覆盖，所以考虑从后往前处理我们用 f [ i ] f[i] f[i]表示 i i i节点前第一个没有被染色的节点，然后用并查集进行维护即可代码 #include <bits/stdc++.h>#define debug(x) cout<<#x<<":"<<x<<endl;#define dl(x) printf("%lld\n",x);#def

LOJ#2473. 「九省联考 2018」秘密袭击（线段树合并+拉格朗日插值）

一个非常强的题。也许比较套路但是都比较生疏。主要使用两个思想。首先是把求第k大的权转化成枚举i 从1 - W 计算最终的第k大大于等于 i 的和。然后就可以转化成一个DP。 f[i][j][k] represents the subtree of the node i and we are considering the value of the kth node is not le

Loj#139 树链剖分

题目链接问题分析一道比较标准的模板题。唯一需要考虑的是换根操作。发现换根对链上的操作并没有影响，考虑对树上以$u$为根子树的影响。设原树上以$u$为根的子树是$T$。如果新的根在$T$的外部，那么以$u$为根的子树不变。如果新根就是$u$，那么子树就是整棵树。否则，取原树中$u$的一个儿子$v$，$v$包含新的根，那么新的以$u$为根的子树就是整棵树

LOJ #2483 [CEOI2017]Building Bridges CDQ分治+斜率优化

题目链接：传送门洛咕传送门令 s u m w sumw sumw表示 w w w的前缀和。显然的 d p dp dp方程： d p [ i ] = m i n ( d p [ j ] + ( h [ i ] − h [ j ] ) 2 + s u m w [ i − 1 ] − s u m w [ j ] ) dp[i]=min(dp[j]+(h[i]-h[j])^2+sumw[i-1]-

$[LOJ 5516]无聊的数对$

[LOJ 5516]无聊的数对

无聊的数对题解好水的题呀，为什么还是这句话？？？额，首先，我们知道要使得的__builtin_parityll(即它在二进制下1的个数是否为奇，一下简称parityll为奇的话，a与b的parityll一定是不同的。这，还是证一下吧。我们设有个1，有个1，它们共有的1的个数为，那么它们异或后的1的个数为，它的奇偶性与是相同的，所以要使得的1个数为奇，必定为奇，于是与的奇偶性不同

LOJ#6032. 「雅礼集训 2017 Day2」水箱【笛卡尔树】

题目描述：题目分析：如果想象水慢慢往上涨，高的隔板会将不同的区域分隔开，导致两边的水位高低可能不一样。而水位如果超过了隔板，那么这个隔板两边就等价了。于是我们想到用最大值将区间划分，然后答案就可以这么求（设当前隔板的高度为h，最近的比当前隔板高的隔板的高度为h’）：如果水位没有达到当前隔板，可以满足的条件为h到h’中无水的条件加上当前隔板两边水位任意时最多满足的条件。如果水位

LOJ #2542 [PKUWC2018]随机游走 (概率期望、组合数学、子集和变换、Min-Max容斥)

很好很有趣很神仙的题！题目链接: https://loj.ac/problem/2542 题意: 请自行阅读题解首先我们显然要求的是几个随机变量的最大值的期望(不是期望的最大值)，然后这玩意很难求，根据Min-Max容斥化成最小值的期望来求。 Minn-max容斥是指\(\max(x_1,x_2,...,x_n)=\sum_{S\in \{1,2,...,n\} } (-1)^{|S|-1}

LOJ #2731 [JOI2016春季合宿]Solitaire (DP、组合计数)

题目链接 https://loj.ac/problem/2731 题解首先一个很自然的思路是，设$dp[i][j]$表示选了前$i$列，第$2$行第$i$列的格子是第$j$个被填上的。还要加个第三维$0/1$，表示第$2$行第$i$列不是/是这一列最后一个被填上的（这决定了它是被上下填上还是被左右填上）。转移: 若第$2$行第$i$列是棋子，则所有的

LOJ #2733 [JOI2016春季合宿]Sandwiches (DP)

题目链接 https://loj.ac/problem/2733 题解神仙题…… 首先可以观察到一个结论: 目标块的两块小三明治一定分别是最后和倒数第二个被吃的。由此我们可以考虑这两块谁先被吃。这样的好处就是，起初我们一个块被吃的依赖条件是某两个块中有一个被吃就行，现在两个块中的某一个已经钦定了比它更晚，另一个就一定要比它早，这样依赖关系就形成了一张图。那么有一个$O(n^4)$的做法

#trie#loj 10056 poj 3764 The XOR Largest Path

题目在n个数中找两个数 x , y x,y x,y，使x到y的路径异或和最大分析可以用一种类似于差分的东西，用一个深搜求出点到根节点的异或值，然后就像The XOR Largest Pair就好了代码 #include <cstdio>#include <bitset>#include <cstring>struct node{int y,w,next;}e[200

【洛谷P2146】【LOJ#2130】【BZOJ4196】软件包管理器【树链剖分】

题目大意：题目链接：https://www.luogu.org/problem/P2146 Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/C

【LOJ#2236】【洛谷P3258】松鼠的新家【LCA】【树上差分】

题目大意：题目链接：洛谷：https://www.luogu.org/problem/P3258 LOJ：https://loj.ac/problem/2236 给出一棵树以及 n n n个点走的顺序，求每一个点会被经过几次。规定到达最后一个点的那一次不算。思路：这是一道在「省选斗兽场 − - −树链剖分」的一道题目。本着背树剖板子心态来刷的。看完题后这不是一道树上差分sb题

【Trie】【费用流】管道监控（loj 3026）

正题 loj 3026 题目大意给你一棵树，和若干匹配串，如果一个节点向下的某条链构成了匹配串i，则可以花费这w_i匹配这条链，问你匹配完所有点的最小代价解题思路这题可以理解为树上树上的线性规划先对于每个匹配串倒着建trie，然后每个点向父亲跑trie，当跑到一个匹配串时，就连接头和尾，费用为 w i w_i wi，流量inf 然后每个点向子节点连流量inf费用0的

LOJ 「美团 CodeM 初赛 Round A」二分图染色（组合数学）

Description 给定一个完全二分图，图的左右两边的顶点数目相同。我们要把图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。计算所有满足条件的染色的方案数，并对10^9+7取模。 Input 二分图单边的顶点数目 n Output 输出一个整数，即所求的答案。 Sample Input 2 Sample Output 35

LOJ #6279 数列分块入门3 题解

Part # -1. 前言 \text{Part \# -1. 前言} Part # -1. 前言重要的事情说三遍先初始化，后输入！先初始化，后输入！先初始化，后输入！蒟蒻就是这样错的（ Part # 0.题目 \text{Part \# 0.} 题目 Part # 0.题目给出一个长为 n n n 的数列，以及 n n n 个操作，操作涉及区间加法，询问区间内小于某

LOJ #6278 数列分块2题解 2024年第一篇题解

Part #0 . 前言 \text{Part \#0 . 前言} Part #0 . 前言数列分块1 分块是一种优雅的暴力。 Part #1 . 数列分块入门2 \text{Part \#1 . 数列分块入门2} Part #1 . 数列分块入门2 传送门观察题目，我们可以发现题目是一个区间查询，区间修改。首先，题目要求查询的是小于 c 2 c^2 c2 的数的个数

LOJ #6277 数列分块1题解 2023年最后一篇题解

Part #0 . 前言 \text{Part \#0 . 前言} Part #0 . 前言分块是一种优雅的暴力。 Part #1 . 数列分块入门1 \text{Part \#1 . 数列分块入门1} Part #1 . 数列分块入门1 传送门这题是一个基础的分块，块外的暴力，块内做标记，块长 n \sqrt{n} n ，块数 n \sqrt{n} n ，注意

Loj #3085. 「GXOI / GZOI2019」特技飞行

Loj #3085. 「GXOI / GZOI2019」特技飞行题目描述公元 $9012$ 年，Z 市的航空基地计划举行一场特技飞行表演。表演的场地可以看作一个二维平面直角坐标系，其中横坐标代表着水平位置，纵坐标代表着飞行高度。在最初的计划中，这 $n$ 架飞机首先会飞行到起点 $x = x_{st}$ 处，其中第 $i$ 架飞机在起点处的高度为 $y_{i,0}$。它

Loj#3320-「CCO 2020」旅行商问题

正题题目链接:https://loj.ac/p/3320 题目大意有一张 n n n个点的无向完全图，每一条边是红色或者蓝色，对于每个点 s s s求从这个点出发的一条尽量短的经过所有点的路径。 1 ≤ n ≤ 2000 1\leq n\leq 2000 1≤n≤2000 解题思路显然地猜测一下最短的长度肯定是 n n n，说是找一条路径，实际上我们是能够找到一个颜色交

[loj#2868][线段树][笛卡尔树][DP]会议

Description 传送门题解不想写了所以下面没有代码看题解发现我第一步就自闭了…感觉我在这种题从来都不会想DP的事情… 设一个 f [ i ] [ j ] f[i][j] f[i][j]表示 [ i , j ] [i,j] [i,j]的答案是什么如果我们找到了这个区间的最大值位置 p p p，那么显然要不你就是让人们全部走到最大值的左边，要不就是走到最大值的右边那么转

「LOJ#10056」「一本通 2.3 练习 5」The XOR-longest Path （Trie

#10056. 「一本通 2.3 练习 5」The XOR-longest Path 题目描述原题来自：POJ 3764 给定一棵 nnn 个点的带权树，求树上最长的异或和路径。输入格式第一行一个整数 nnn，接下来 n−1n-1n−1 行每行三个整数 u,v,wu,v,wu,v,w，表示 u,vu,vu,v 之间有一条长度为 www 的边。输出格式