题记ynoi

## 1.1 前言 > 在太阳西斜的这个世界里，置身天上之森，等这场战争结束之后，等这场战争结束之后，人人本着正义之名，长存不灭的过去，逐渐消逝的未来，我回来了，纵使日薄西山，即使看不到未来，此时此刻的光辉，盼君勿忘，世界上最幸福的女孩 珂朵莉要永远幸福的呀~ [题目链接](https://www. ......

# 我的出题记录 ## NOIP 2021 T3 链接：https://www.luogu.com.cn/problem/P7962 在写这一段之前，我诚挚地向因为本题的数据受到影响的所有选手道歉。 出好此题并提交题面之后，我突然发现此题的数据十分难造，难以卡掉所有错误的算法。于是我向负责命题的 y ......

[$\text{link}$](https://www.luogu.com.cn/problem/P9337)，这题太毒瘤啦！难写难调还略微卡常。 >谁爱卡常谁卡吧。反正我先贺为敬了。——引用自洛谷别人的提交记录 本人写了两天（两个 $case$ 各一天），调崩溃了才调出来，太毒瘤了！ 看到颜色相同 ......

Problem - C - Codeforces 找最大的简单环 题解：首先就是如果有一条链的左右起点相同，那么起点链就要强制更换 然后就是一直递归的去跑，不断判断这个链可不可以当起点链，就是当它比前面跑的环都大的时候，那我们就把这个链当做新的起点链，否则一直跑环就可以了，最后一条链一般都直接加上即 ......

题意：就是给你一个数列，让你找出可以组成等差数列的最多元素有多少个 正解： 题解：直接暴力，枚举d，然后二分查找，注意这里要枝剪，减去已经有的最大值就行了 #include <bits/stdc++.h> #include <iostream> #include <cstdio> #include ......

### [题目传送门](https://www.luogu.com.cn/problem/P6105) ## solution 妙妙题。 分成 $a+b\geq C$ 和 $a+b using namespace std; const int N = 5e5+7; multiset num,ans; ......

### [题目传送门](https://www.luogu.com.cn/problem/P4689) ## soltion 简单题 换根显然可以拆成 $O(1)$ 个区间，这里先不管。 直接做法是莫队，把双子树拆成 $dfs$ 序上的双前缀，可以直接莫队，但是常数比较大。 另一种做法是根分，对颜色 ......

### [题目传送门](https://www.luogu.com.cn/problem/P5524) ## solution 简单题。 我们正着做扫描线。 设 $t_i$ 表示位置 $i$ 最后一次进行二操作的时间，那么一操作就是交换 $t_x,t_y$ ，二操作就是区间复制。 对于三操作，开一个 ......

## 题目描述 由于你不会设计哥德尔机，所以你决定先做一道数据结构题： 给定一个长度为 $n$ 的序列 $a_1\cdots a_n$。你需要回答 $m$ 个询问，第 $i$ 个询问给定一个区间 $[l_i,r_i]$，请你求出这个区间中所有非空子集的最大公约数的乘积。由于答案可能很大，每次询问请你 ......

### [题目传送门](https://www.luogu.com.cn/problem/P8512) ## solution 简单题，考虑正着做扫描线，维护最后一次覆盖每个位置的修改时间，这个可以用 $set$ 维护颜色段数均摊。 那么显然对于一个以当前位置为右端点的询问，其答案就是所有最后修改时 ......

## 数据结构 #### [Ice-cream Tycoon](https://vjudge.net/contest/567668#problem) 平衡树 / 线段树二分。 对于平衡树而言， 构造一个函数， 求出拿到最便宜的所需数量的 ice-cream 的价格（利用类似于树上查排名的操作即可）， ......

## 动态规划 ## 字符串 ## 杂题 #### [A:Animals and Puzzle](https://www.luogu.com.cn/problem/CF713D) #### [B:Vanya and Treasure](https://www.luogu.com.cn/problem ......

Problem - C - Codeforces 思路：一道dp，首先明确vis含义，vis[i-1][0]代表的是上一步是一个1的柱子地最优解，vis[i-1][1]代表的是上一个是一个2的柱子的最优解，然后就初始状态第一个题目是一定是0开始所以vis[0][1]="非常大的数" vis[0][0 ......

题解：主要是对于炸弹时间的处理，直接让时间赋值给数组，进行判断即可，跑一遍bfs的板子就可以了。 #include <bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm ......

[更好的阅读体验。](https://www.cnblogs.com/Ender32k/p/17125914.html) 假设值域为 $v$ 即 $10^5$，显然每个质因数 $p$ 独立，考虑计算每个 $p$ 对答案的贡献。 $p$ 对答案的贡献次数为 $\sum\limits_{S\subset ......

这东西在线不太能做，考虑离线扫描。扫描右端点 $r$，我们对每个位置 $l$ 维护一个 $p_l$ 表示最小的 $p$ 使得 $[l,p]$ 是 $[l,r]$ 的合法子区间。 考虑如何维护 $p_l$。考虑新加入的右端点 $r$，加入一个数 $a_r$，上一次出现的位置为 $lst_{a_r}=c ......

| | $\quad\mathcal{Problem\ \ ID}\quad$ | $\quad\quad\mathcal{Name}\quad\quad$ | $\quad\quad\mathcal{Time}\quad\quad$ | | : : | : : | : : | : : | | $\ ......

题目意思就是：有n个任务，每一个任务都有K个小任务每一个小任务都有指定时间，之后做完一个大任务额外加一分，然后给你M分钟，问在M分钟里，你需要得到最多分是多少。 题解：首先对K个小任务排个序，对n个大任务进行遍历，就是你做完一个大任务，其他的时间全部搞小任务，然后一个个n进行比较，看看做几个大任务最 ......

# Luogu P6109 [Ynoi2009] rprmq1 [Luogu P6109](https://www.luogu.com.cn/problem/P6109) ## 题目背景 我谔谔 本题读入量约 13 MB，输出量约 7 MB，请选择合适的输入输出方法 ## 题目描述 有一个 $n \ ......

首先将修改操作差分为 $l_1$ 时刻给 $[l_2,r_2]$ 中的值 $+v$，$r_1+1$ 时刻给 $[l_2,r_2]$ 中的值 $-v$。这样第 $i$ 行的状态相当于执行 $1\sim i$ 时刻的操作后的状态。 猫树分治，把一个询问挂在线段树上满足 $l\le l_1\le mid\ ......

[Problem Link](https://www.luogu.com.cn/problem/P9062) 给定平面上 $n$ 个点，$Q$ 次询问编号在 $[l,r]$ 内的点的最近点对。$n,Q\le 2.5\times 10^5$。 技巧：平面网格化 乱搞都是错的。看见欧几里德距离，想到平面 ......

大家可以猜猜看为什么有两个标题，因为这个原因本文就不设密码了。 5 月模拟赛，6 月补题，7 月补 sol，不愧是我。 ## 题目描述 [link](https://www.luogu.com.cn/problem/P5065)。 赛时得分：0/0。 完全不会，暴力都没打。 首先，有个经典结论：前缀 ......

[洛谷传送门](https://www.luogu.com.cn/problem/P7722 "洛谷传送门") 被踩爆了好神的题啊！ 转化一下题意，给出三个数组 $a, b, c$，每次可以单点修改 $a, b, c$，询问即求 $b_i = a_j = c_k, 1 \l ......

## [P3146 [USACO16OPEN] 248 G](https://www.luogu.com.cn/problem/P3146) 我们可以想到用区间DP来做 $f_{l,r}$ 表示 $[l,r]$ 的区间内其中合并能获得的最大分值 我们要枚举区间断点 $k$ ，然后我们来看一下在如何的 ......

Ynoi 4血！我永远喜欢珂朵莉！ 原题链接 珂朵莉给了你一个序列，每次查询一个区间 [l,r][l,r] 中所有子序列分别去重后的和\pmod p(modp)。 首先这是一个静态问题，还不强制在线，而且是 Ynoi 的黑题。 于是们就可以想到大概是一个离线算法，并要求解序列问题。 莫队算法 首先我 ......

[题目 Link](https://www.luogu.com.cn/problem/P8264) 我们不妨来考虑所有询问都是 $l=1,r=n$ 的情形，这种情况下需要对每个值处理出他经过一系列变换后变成了什么数。 考虑用 $\text{solve}(p,l,r)$ 表示我们现在要计算 $x\in ......

> 二阶堂真红给了你一个长为 $n$ 的序列 $a$，有 $m$ 次操作 > > 1. 把区间 $[l,r]$ 中大于 $x$ 的数减去 $x$。 > 2. 查询区间 $[l,r]$ 中 $x$ 的出现次数。 > > 对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le m\l ......

分块。我们先来考虑修改对整块的影响。记值域为 $V=10^5$。 考虑对每一块维护 $V$ 个集合 $S_1,S_2,\cdots,S_V$，第 $i$ 个集合 $S_i$ 维护了区间中所有 $=i$ 的元素的一些信息，并维护区间的最大值 $m$，对于一次操作 $x$： - 若 $m\le 2x$， ......

[题目 Link](https://www.luogu.com.cn/problem/P5046) 分块，首先预处理所有整块之间的答案，这部分用类似莫队二离的手法可以改成 $O(n)$ 次插入和 $O(n\sqrt{n})$ 查询，然后根号平衡一手做到 $O(n\sqrt{n})$；空间自然也是能线 ......

对于这类问题，我们有一种比较通用的解法是设定一个贡献的充要条件。我们通常会在若干个都能产生某一贡献 $p$ 的元素 $a_1\dots a_k$ 上定义一种小于关系 $R$，每次只让这些元素中的极小值进行贡献。具体来讲我们可以对每个元素求出它上/下一个比它“小”的元素 $pre_x,suf_x$，那 ......