BalticOI

[BalticOI 2004] Sequence 数字序列 Luogu P4331 题目描述 给定一个整数序列 \(a_1, a_2, \cdots , a_n\)，求出一个递增序列 \(b_1 < b_2 < ··· < b_n\)，使得序列 \(a_i\) 和 \(b_i\) 的各项之差的绝对值 ......

[BalticOI 2019 Day2] 汤姆的餐厅 题目背景 译自 BalticOI 2019 Day2 T1. Tom's Kitchen 题目描述 Tom's Kitchen 是一家非常受欢迎的餐厅，其受欢迎的原因之一是每份菜都由至少 $ K $ 名厨师进行准备。今天有 $ N $ 份菜需要准 ......

BalticOI 2009 Day1 - 甲虫 https://www.luogu.com.cn/problem/P4870 首先看到题面就能想到排序后区间 dp。 设 \(f_{i,j,0/1}\) 表示区间 \([i,j]\)，收集完毕后在哪个端点时能收集到最多的露水，但是发现转移过程中还需要这 ......

P4678 [BalticOI 2005] Bus Trip 题解(RE:题解再改造!!) 贴码 #include<bits/stdc++.h>#define MAXN 500010using namespace std;//ifstream is("trip.in",ios::in); //ofs ......

题解 P6767 Roses 题目传送门 \(a,c\) 为每束花的朵数，\(b,d\) 为每束花需要的钱 首先简单了解一下题意，大概就是现在给你 \(n\) 朵花，每 \(a\) 朵花 \(b\) 元，每 \(c\) 朵花 \(d\) 元，求最少需要多少钱？ 注意： 这里 \(n\) 的范围是 \ ......

整体二分。 有个小技巧，就是可以把存边的数组往后复制一遍，然后删去区间 $[l,r]$ 就相当于保留区间 $[r+1,l+m-1]$ 的边。于是只需要解决这么个问题： > 给定一张 $n$ 个点 $m$ 条边的无向图，$q$ 次询问，每次只保留区间 $[l,r]$ 的边，问是否是二分图。 乍一看有点 ......

## 题目大意 给定 $N$ 对数据，每对数据包含两个整数 $A_i$ 和 $B_i$，表示这一对数据的 $v_i$ 的范围：$A_i \leq v_i \leq B_i$。又将这 $N$ 对数据分为 $P$ 组，其中 $K_i$ 表示第 $i$ 组数据中有多少对数据。 我们设第 $i$ 组数据中将 ......

翻了一下已有的题解，似乎没有针对此题本质即线性规划做的题解，故作分享。 可以由此题抽象出一类问题的模型，做训练的效果还是非常好的。 ## 题意简述 要选择 $N$ 个物品，有两种方案，每花费 $C$ 元可以买 $A$ 个，每花费 $D$ 元可以买 $B$ 个。 ## 分析 对于这一题，题目有明确提示 ......

### [原题链接](https://www.luogu.com.cn/problem/P6227) ## 题目大意： 一颗 $N$ 个节点的以 $E$ 为根的树，每条边有权值 $W_i$，有 $S$ 个特殊点和 $Q$ 次询问。 每次询问第 $I$ 条边不能经过，并给定一个起点 $R$。 1.若能 ......

### [原题链接](https://www.luogu.com.cn/problem/P6227) ## 题目大意： 一颗 $N$ 个节点的以 $E$ 为根的树，每条边有权值 $W_i$，有 $S$ 个特殊点和 $Q$ 次询问。 每次询问第 $I$ 条边不能经过，并给定一个起点 $R$。 1.若能 ......

题目传送门：[Click](https://www.luogu.com.cn/problem/P4795)。 蒟蒻看见这道题，想了足足一个小时，过后顿有所悟，故作此篇。 首先，看到题目，光是数据就已经达到了 $\operatorname{O}(nm)$ 的级别，再看一看数据范围：$3 \leq n, ......

# [BalticOI 2014 Day1] Sequence ## 题意 现在有 $K$ 个连续整数，每个整数你只能看见其中一位数字，求最开始的数 $N$ 的最小值。 ## 题解 考试的时候一眼原，但是没补题，很痛苦。 注意到答案肯定不会超过 $102345678900000$。 观察这个东西会发 ......

### P6227 [BalticOI 2019 Day1] 山谷 ### Description 给一棵树，一个根，一些特殊补给点，一些询问。求解如下问题：断掉一条边 $u\to v$，这样以后你能否从给定的 $R_i$ 走到根，若能输出 `escaped`。不能到达根且不能到达任何一个特殊补给点 ......

通过观察，可以发现此题和最小生成树十分相似（两个地点之间途经的最小值最大）。 于是可以考虑这么做： 1. 通过 bfs 将每一个块预处理出来，并记录其编号、高度、类型（是否为高地）以及边缘的点。 2. 将每一个块按高度从大到小排序。 3. 依次枚举每个块： - 对于当前要处理的块，枚举其边界的所有点 ......

首先我们定义“圈”为与原点距离相等的点集。 ``` . . . 3 . . . . . 3 2 3 . . . 3 2 1 2 3 . 3 2 1 0 1 2 3 . 3 2 1 2 3 . . . 3 2 3 . . . . . 3 . . . ``` ### 暴力： 把圈放到堆里，然后每次取出代 ......

# [BalticOI 2015] Tug of War ## 题意 拔河（*Tug of War*）在 Byteland 是十分受欢迎的运动。规则十分简单：两队以相反方向拉绳子。一年一度的 Byteland 拔河比赛将要进行，并且许多选手都报名参加了。作为公平竞赛专员，你的工作是把选手们划分为两个 ......

本文网址：https://www.cnblogs.com/zsc985246/p/17539182.html ，转载请注明出处。 ## 题目大意 现在有一棵树 $T$，复制一个完全相同的 $T'$，并将这两棵树的叶子节点全部对应合并在一起，形成一个图，我们称这种图为**对称图**。 给定一个图，判断 ......

首先发现 $a_i$ 只会与 $a_{2\times i}$ 和 $a_{2\times i+1}$ 两个数交换，所以可以联想到线段树的结构。 考虑按照线段树的方法递归，然后分类讨论。 如果当前递归到 $i$，令 $a$ 表示 $val_i$，$b$ 表示 $val_{2\times i}$，$c$ ......

左偏树维护动态区间中位数。 [传送门 P4331 BalticOI 2004 Sequence 数字序列](https://www.luogu.com.cn/problem/P4331)。 ## Solution ### 1 我的思路和题解前半部分完全重合了（（ 如果按照单调不增去分割 $a$ 序列 ......

题意： 有一只甲虫处于一根水平的树枝。因为他沉迷数学无法自拔，所以他觉得很像是在 $x$ 轴上。 在同一根树枝上，还有 $n$ 滴露水。每滴露水占用 $m$ 个单位的水分。相对于甲虫的位置，他们的坐标分别是 $x_1,x_2,\dots,x_n$。 显然，这一天将会骄阳似火。每过一个时间单位，就会有 ......