yLOI

题目链接: [yLOI2022] 长安幻世绘 比较不错的综合题。考虑下处理极差的绝对值我们应该怎么做，很显然排序是有必要的，我们需要带着下标排序。 考虑几个核心点： 1.假如没有其他限制考虑极差与序列长度有啥关系，很显然长度越长，极差单调不降，具备单调性。 2.考虑对于一个长度为 \(L\) 的连续 ......

这个小丑看了好久题目才发现保证 \(t\) 不降。 好像与其他题解做法稍有不同。 思路 其他题解的标记做法非常复杂，怎么办。 我们可以使用适用性可加强大的矩阵乘法。 我们考虑维护： \[\begin{bmatrix} \sum v&\sum a\times b&\sum a&\sum b&len\\ ......

P5522 [yLOI2019] 棠梨煎雪 题解 题目链接 分析1 抛开时间复杂度不谈，先来看看对于每次询问，如何计算合法的字符串个数。 对于每次询问的 \([l,r]\)，我们可以对字符串的每一位按以下种情况讨论（设讨论的这一位为第 \(i\) 位）： \(str[l..r][i]\) 既有 0 ......

思路 看到条件 \(2\)，我们得知：这个节点对应的最长链，一定在这个节点到根节点的简单路径上。 所以我们记录 \(1\) 到 \(i\) 之间的权值和，记为 \(sum_i\)。因为权值是正整数，所以满足单调性，可以二分。 如何二分路径上的点呢？我们维护一个与当前 dfs 同步的栈，记录从根节点到 ......

题目意思： 需要在元素互不相同的数列 \(a\) 中选出一个长度为 \(m\) 的元素互不相邻的子列，使得子列的极差最小。 做法 我们知道，对于一组数列，我们只需知道它的最大值和最小值，就可以得到它的极差。那么我们可以将数字从小到大排序，固定最小值，寻找最优的最大值，当最小值和最大值的位置固定了，那 ......

P8201 简单题。 题中求的是 \(dis_{a, t} \oplus dis_{t, b} = k\) 是否存在，显然不好直接维护，考虑转化。 令 \(dist = dis_{a, t} \oplus dis_{t, b}\)，\(val = \bigoplus\limits_{x\in \te ......

原题 被降智了，刚学了stirling数，以为是\(O(n \log n)\)用卷积求stirling数，但是我不会啊/kk，于是看了一眼题解，才想起来这是个黄题 把樱花树当作隔板插到\(n-m+1\)个空里即可 ......

[原题](https://www.luogu.com.cn/problem/P9472) 因为数列字典序是从第一项开始看的，样例输入了每个数列的第一项，所以如果数列的第一项就不相同，那么第一项小的字典序一定是小的。 接着如果两个数列的第一项相同，由题得第二项是第一项与这个数列的编号的乘积。如果这两个 ......

# 题目大意 在元素互不相同的数列 $a$ 中选出一个长度为 $m$ 的元素互不相邻的子列，使得子列的极差最小。 # 思路 爆搜、$dp$ 肯定是过不了的，所以我们考虑固定某个值，赛时想到了固定最大或者最小值，然后找到另一个值，但是除了 $dp$ 没想到好做法，比赛结束了才知道正解居然是同时固定最大 ......

# 思路 我们可以先找出所有的可以被删除的点，然后取点权前 $k$ 大的点就好了。 因为图可能存在环，所以我们需要先缩点，考虑缩点后的 DAG，我们可以按照拓扑序倒序删点就好。 再来考虑每个 SCC 如何取点。 我们先把 SCC 分为三种情况： 1. 该 SCC 没有入度，且无自环。 2. 该 SC ......

~~因为比赛的时候数据比较水，暴力原本能拿满的，但是后面怕T掉，改了个线性筛的，结果有个地方写错了，导致T了，悲痛啊。~~ # 分析 首先我们想到了暴力分别求出 $gcd,lcm$ 和乘积，然后判断是否相等，但是当数列中的数足够大的时候，求 $gcd$ 的时候会超时，而且乘积就算是 ```unsig ......

~~因为自己太憨了，所以交了好几次都没过~~，谢谢审核大大！！！ # 思路 因为这是一棵树，所以每个节点只有一个父亲，那么选定一个结点，它到根节点的路径唯一。 所以第一个思路就是暴力，对于每一个节点，直接暴力向上枚举，找到第一个满足条件的节点，然后输出长度即可。 但是显然，第一种方法很容易 TLE， ......

题目链接：[P5522 [yLOI2019] 棠梨煎雪](https://www.luogu.com.cn/problem/P5522) 听着>写棠梨煎雪，太美妙了！ ## 题意： 对于一些给定的字符串，每个字符串只包含$0,1$以及?号。对于一个字符串$s_1$，如果另一个不包含?号的串$s_2$ ......

Upd：2023/8/5补 ## T1 普及组的题，而且T1，而且叫签到题。所以非常简单，入门难度。没什么好说的。 就是统计大写，小写和字母个数。 ```cpp #include #define ll long long using namespace std; const int N=100+5; ......

原题：[P9474 [yLOI2022] 长安幻世绘](https://www.luogu.com.cn/problem/P9474 "P9474 [yLOI2022] 长安幻世绘") 看到很多大佬的题解直接讲了做法，本蒟蒻看得不是很懂，调了很久才把这题做出来，于是写了这篇比较详细的题解谈一下我做这 ......

看到极差，不难想到双指针。 显然，如果 $[l,r]$ 的位置都被覆盖，那么其中最多可以选 $\lceil\frac{r-l+1}{2}\rceil$ 个数。 我们先将所有数离散化，排序，双指针卡取值范围。 `set` 里面存 `pair` 类型变量，表示覆盖的区间。 每次将值为 $r$ 的数的位置 ......

# Description 给定一个长为 $n$ 的序列 $\{a_n\}$，判断他们的最大公约数与最小公倍数的乘积是否等于序列中所有数的乘积。 对于所有数据，$1\leq n\leq5\times10^5$，$1\leq a_i\leq10^8$。 # Solution 设 $\displayst ......

给定序列，选取一个恰好为给定长度的元素在原序列中不相邻的子序列，使得该子序列极差最小。排序后双指针，用 set 维护区间解决。 ......

~~谨以此题解纪念我的20次提交~~。 题目大意 给一个整数 $x$ 和 进位次数 $k$，求一个数 $y$ 使得列竖式计算 $x+y$ 时正好产生 $k$ 次进位。 思路 ~~（最开始是想正着搞的，但是怎么也调不出来）~~提供一种倒着做的做法。 首先有几个结论： 产生进位 $=$ 给前一位 $+1 ......

题目分析 分析发现，如果要让 $p_i$ 均为奇数，那么这个数必须是奇数，否则分到最后一定会分到2，所以我们只需要判断此数是否是偶数就行了 如果你就这样提交上去，那么一定会，稻花香里说丰年 听取WA一片！ 俗话说得好，不开long long见祖宗，由于n$<=$ $10^{18}$，所以输入的数字要 ......