题解1545b cf
8.22 [CSP-S 2021] 交通规划 题解
```cpp #include using namespace std; using pii = pair; constexpr int N = 3e5 + 5, S = 2e3 + 5, K = 1e2 + 5, INF = 0x3f3f3f3f; int n, m, T, poi[N]; int ......
CF1840G2
[原题](https://codeforces.com/contest/1840/problem/G2) [翻译](https://www.luogu.com.cn/problem/CF1840G2) 观察G1操作貌似不能再优化了,但我们可以用一些随机化算法 我们发现对于我们已经查询过的所有数中最大 ......
CF1176C Lose it!
## 思路 定义一个数组能分为若干份,每一份都是 $4,8,15,16,23,42$ 的前缀的数组是 **半优秀** 的。 容易发现只有满足以下性质的数组才是 **半优秀**: 令 $j$ 在数组的 $[1,i]$ 中出现的次数为 $num_{i,j}$,对于每一个 $i(1\leq i\leq n ......
CF1840G1
[原题](https://codeforces.com/contest/1840/problem/G1) [翻译](https://www.luogu.com.cn/problem/CF1840G1) 先查询$[1,m]$的位置,再查询$m,2m,3m,...,$的位置,然后再判断这些位置是否和之前 ......
CF1840F
[原题](https://codeforces.com/contest/1840/problem/F) [翻译](https://www.luogu.com.cn/problem/CF1840F) 首先先说一个我想的错误的做法 因为从$(0,0) \rightarrow (i,j)$肯定是时间越短越 ......
CF1485C Floor and Mod 题解
## 题面 给定 $x, y$,求 $$\sum\limits_{a = 1}^{x} \sum\limits_{b = 1}^{y} \left[\left\lfloor\dfrac{a}{b}\right\rfloor = a \bmod b\right]$$ ($1 \le x, y \le ......
P3089 题解
### [P3089](https://www.luogu.com.cn/problem/P3089) 令 $f_1[i][j]$ 表示向右跳,从 $j$ 跳到 $i$ 的最大总得分,有状态转移方程: $$ f_1[i][j]=\displaystyle\max_{k1&&x[j]-x[k-1] u ......
P3165 排序机械臂 题解
[link](https://www.luogu.com.cn/problem/P3165)。 #### 题意 对序列进行 $n$ 次 reverse 操作,第 $i$ 次操作的左端点为 $i$,问如果最终要使序列有序,每次操作选择的右端点是什么。 #### 解法 由于每次左端点为 $i$,很容易想 ......
YC2023:英才专题测试-数据结构1 题解
### 题目颜色为洛谷难度 # [$\color{#F39C11}{A}$](https://vjudge.csgrandeur.cn/contest/576896#problem/A) [洛谷上](https://www.luogu.com.cn/problem/P2952) ## 思路 容易发现 ......
YC2023:英才专题测试-数据结构1 题解
### 题目颜色大致对标洛谷难度 # [$\color{#F39C11}{A}$](https://vjudge.csgrandeur.cn/contest/576896#problem/A) ## 思路 容易发现这是一道双端队列的模板题,所以直接模拟就好。 我使用的是手工队列(忘了 STL 的双端 ......
P2572 序列操作 题解
[link](https://www.luogu.com.cn/problem/P2572)。 对平衡树的懒标记的应用题,其实和线段树也差不多。 如果不考虑取反操作,那维护操作 $5$ 就需要知道当前区间答案,当前区间前缀和后缀,因为在 push_up 时我们当前区间的答案肯定等于左区间的答案,右区 ......
AGC032 A-D题解
A 最后一次插入的数的值与位置一定相同 考虑倒着做 每次从左往右扫一遍 当遇到 a[i]==i 时将此数删除并跳出 B 当 n 为 5 时 构造出的图如下 (图形编辑器 (csacademy.com)) 那么我们猜想当 n 为奇数时将 n 与其他点连边 i 与除了 n-i 的其他点连边 证明: n ......
[国家集训队\] 等差子序列 题解
# P2757 [国家集训队\] 等差子序列 题解 首先简化题目之后,发现如果序列之中存在一个长度 $\ge 3$ 的子序列,一定存在一个子序列的子序列长度为 $3$,所以只需要统计有没有长度为 $3$ 的子序列即可。 对于这种长度为 $3$ 的统计问题,第一想法就是从中间的那个点入手,由于排列的性 ......
题解:【AT Xmas H】 Stamps 3
[题目链接](https://www.luogu.com.cn/problem/AT_xmascon19_h) 经典一个系列四道题,其他三道都是 trash。给定一个有一些位置初始被染色的矩阵,每次可以选择一行将一个公差为**奇素数**的等差序列位置染色,求最少操作多少次使得整个矩阵被染上色。 首先 ......
P7486 「Stoi2031」彩虹 题解
## 题意 给定 $l, r$,求 $$\prod\limits_{i = l}^{r} \prod\limits_{j = l}^{r} \operatorname{lcm}\left(i, j\right)^{\operatorname{lcm}\left(i, j\right)} \bmod ......
[CSP-J 2021] 网络连接 题解
[传送门](https://luogu.com.cn/problem/p7911) 早期题解,转自博客 QwQ 本蒟蒻为数不多过了的黄题,祝贺!!! ![](https://bu.dusays.com/2023/01/20/63ca134dbb0be.webp) # 题面 # [CSP-J 2021 ......
「NOIP2010」机器翻译 题解
## 前言 *~~附加任务~~* 这道题也是一个简单模拟题。 [传送门](https://luogu.com.cn/problem/p1540) ## 解析 这道题就是一个简单的模拟题,简单来说就是如果内存里面没有这个单词(其实是一个数)的话就从外存入队,如果内存容量不够,出队即可。 对了,每次查询 ......
「JLOI2014」松鼠的新家 题解
## 「JLOI2014」松鼠的新家 ### 前言 这道题倒也不是很难,只是有一些小坑需要避一下,可以看作半个 LCA 树上差分裸题。 ### 解析 考虑维护一个树,点 $u$ 表示每个房间需要的糖果数 $s_u$,而维尼在参观房间时从 $a$ 到 $b$ 就需要在 $(a,\to b)$ 的路径上 ......
「CSP-J2019」交通换乘 题解
转自博客。 [传送门](https://luogu.com.cn/problem/p5661) 一道`橙题`,但是会T。 # 题面 # [CSP-J2019] 公交换乘 ## 题目描述 著名旅游城市 B 市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交车的优惠方案: 1. 在搭乘一次地铁后 ......
「NOIP2008 普及组」ISBN 号码 题解
# 前言 转自博客,早期黑历史作品。 这是本蒟蒻の第一篇题解qwq,发在博客上,还请多多关照. 这道题是一道橙题,难度没有太大的问题,对于大犇们来说自然是一遍过的,本蒟就只能调调再交了. # 题面 [传送门](https://www.luogu.com.cn/problem/P1055) ## 题目 ......
[ABC098D] Xor Sum 2 题解
### 题解 [传送门](https://luogu.com.cn/problem/at_abc176_d) #### 题目大意 给出一个序列 $A$ ,求 $A_l \oplus A_{l+1} \oplus \dots \oplus A_r = A_l + A_{l + 1} +\dots+ A ......
「NOIP2003 普及组」乒乓球 题解
## 前言 [传送门](https://www.luogu.com.cn/problem/P1042) 远古TJ!!! *~~这道题题解是老师喊我写的!!!~~* ## 题面 ### 题目背景 国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及。其中 $11$ 分 ......
P3168 [CQOI2015\] 任务查询系统 题解
# P3168 [CQOI2015\] 任务查询系统 题解 因为题目给定的是若干区间,所以考虑差分一下,把区间左端点挂上一个标记,表示到这里的时候多了一个任务,把区间右端点加一挂上一个标记,表示到这里的时候任务消除了。 接着看到第 $k$ 大,考虑主席树,可以用一排在序列上的主席树维护优先级的前缀和 ......
[ABC254Ex] Multiply or Divide by 2 题解
### 前言 [传送门](https://www.luogu.com.cn/problem/AT_abc254_h) 仅次于文本编辑器的紫水题(草 ### 题意 给你两个集合 $A$ 和 $B$ ,你可以把集合 $A$ 的任意一项变为原来的 $\left \lfloor\frac{1}{2}\rig ......
P3825 [NOI2017] 游戏 题解
# P3825 [NOI2017] 游戏 题解 首先解决没有 `x` 的情况,这种情况下 每个事件有两种选择,例如 `a` 可以选择 `b, c`,所以这就是一个 `2-SAT` 问题,但是这题比较特殊,除了题目中给的命题,还需要建立原命题的逆否命题所对应的边,最后跑一遍 $\text{Tarjan ......
【八月ex】CF选做
## 86D 莫队。 移动指针的贡献:$cnt_i\times cnt_i\times i$。 ## 600E Dsu on Tree 的板子之一。 对于轻儿子暴力统计并且每次统计之后删除贡献,重儿子统计后向上不断合并。 对于这个题而言,你需要统计的信息是对于一个点,它的孩子中占主导地位的颜色是哪个 ......
Interval GCD 题解 || WHK废物快乐题
### 题意 给定一个序列,需要对其进行区间加和和查询 $\gcd$ 操作。 ### 思路 首先看到了区间加和,自然想到是直接打懒标记,但是呢。。。 $\gcd$ 具有一些特殊性,我们并不能通过向下传递标记的方式维护 $\gcd$ 。 于是想到昨天 Tad 讲树状数组区间修改的差分数组方案。 我们创 ......
2023 年山东省大学生程序设计竞赛 个人题解
### 比赛链接 - [现场赛榜单](https://board.xcpcio.com/provincial-contest/2023/shandong) - [洛谷重现赛](https://www.luogu.com.cn/contest/126525) 重现赛个人下饭操作太多,后程直接开摆,分数 ......
「SCOI2012」滑雪与时间胶囊 题解 && 卡题记录
### 前言 [传送门](https://www.luogu.com.cn/problem/P2573) 调了一个下午终于弄出来了!!! ### 卡题的事情 上图: ![](https://cdn.fzoi.top/upload/user/st20250310/23072704416058.jpeg ......
「NOIP2013」货车运输 题解
## 「NOIP2013」货车运输 ### 前言 这道题算是一个稍有思维难度的 MST+LCA 题目了。 稍微卡了一会(0-88-88-88-100(打表)-100(打表)-100(正解)),开始是打了表过了,后面在 DCZ 的帮助下正解通过(下面注释提到的一个坑)。 ### 题目大意 给出一张无向 ......