### 题目做法： 先按照题意模拟一遍，将球装进盒子中。 对于某种颜色的球需加入空盒子有两种情况（当前有空盒子）。 - 1.之前没有出现过该颜色的球。 - 2.之前出现过该颜色，但盒子已经被放满。 即球是当前颜色的第 $xk+1$ 个，球才可能被放入一个新盒子。 否则一定会放入最后一个相同颜色的盒子，直到放满为止，或是…

在讨论《原题？》回复：

没有条件吗？

### 前言： 对于该题的写法很多，有平衡树、集合、树状数组等写法，我场上先想到的是树状数组，就拿这个写了。 ### 题意： 给定两个数组 $a$，$b$。定义一次操作为按顺序将 $b$ 中数字放到 $a$ 中，并将位置 $\frac{n}{2}+1$ 上的数移出序列，求最后序列中的数之和。 ### 做法： 对于该题目…

### 题意： 你有一个序列，共 $q$ 次操作，每次操作会给 $i$ 位置上的数加上 $x$。你需要构造一个序列，使得每一个时刻该序列都满足单调递增。求出该序列的最小和。 ### 做法： 考虑贪心去给每个位置赋值，把位置 $1$ 上赋值为最小值 $1$，然后剩下的每个位置按照与上一个位置的历史最大差值来贪心赋值。 如…

## 前言： 没有场切，赛时假了。但赛后立马想到了正解。 ## 做法： 第一眼看过去，题目像是一道均分纸牌的题目，但均分纸牌只能相邻交换，而本题可以随便换。 我们需要构造出最小的交换方案。 我们易想到 $n-1$ 次交换方案的构造方法，即构造一条链，使得链上前半段都是大于平均值的，后半段小于平均值的。将前面多的传给下一…

### 做法： 题目需要构造一个长度为 $n$ 的集合，满足任意选两个值的和、积、异或和都没在集合中出现。 开始可能很难想，但数据给予了提示。对于每组数据都保证了 $(m-2\times n)^2 > m$。 那这个有什么用呢？ 对于第一个与第三个条件，我们发现构造出一个全奇数序列，能满足这两个条件。由于奇数的和为偶数…

### 前置知识：线段树 对于线段树的可以解决的区间查询问题，在某些时候会具有局限性，比如在线段树进行修改之后，新的值会覆盖在原来的值上面，如果想要知道原来的直接，就会很难解决。 故引申出可持久化线段树的概念。 可持久化线段树即在线段树的基础上，多记录了历史信息。 ### 例题1：[可持久化线段树1](https://…

在文章《题解：P2445 [SDOI2005] 动物园》发表评论：

%%%

## 前言： 把 D 放了先看 E，发现好做多了。 ## 做法： 题目求 $\sum_{i=1}^n\limits{\max(l,\min(r,a_i))}$。 由于没有保证 $l$，$r$ 的大小，故需注意 $l > r$ 的情况，值为 $n\times l$。 接下来是 $l\leq r$ 的情况，发现要求的实际上…

## 前言： 没有场切，赛时假了。但赛后立马想到了正解。 ## 做法： 第一眼看过去，题目像是一道均分纸牌的题目，但均分纸牌只能相邻交换，而本题可以随便换。 我们需要构造出最小的交换方案。 我们易想到 $n-1$ 次交换方案的构造方法，即构造一条链，使得链上前半段都是大于平均值的，后半段小于平均值的。将前面多的传给下一…

在讨论《求助：怎样提升水平》回复：

多写一些题，多找一些题单。

## 做法： 可以先看部分分，发现有 $b\leq 10^7$，易发现这部分可以使用枚举约数的调和级数来求解。 剩下的就是 $b > 10^7$ 的情况了。由于题目是约数与位数之间的关系，那我们可以对位数进行分类讨论： - $10^7 \leq b \leq 10^8$，即要求 $d(n)=8$。对于 $d(n)=\p…

在讨论《疑问》回复：

洛谷的机子性能不好，但你这个复杂度实在是太大了。开两秒都是卡着的

在讨论《HA CSPS 108 分能进吗》回复：

高中生应该有分就能进

在讨论《CSPS204分，SH，1=和7勾稳了吗》回复：

七勾不一定

在讨论《钩子评定是全国的还是按省的》回复：

全国

在讨论《S205有无7钩》回复：

差不多215+有希望吧

在讨论《S205有无7钩》回复：

不一定

## 做法： 题目需要找出一个字符串，使得其与剩下的 $n-1$ 个字符串恰有 $k$ 个字符不同。 对于最暴力的做法即 $O(n)$ 枚举一个字符串，然后与剩下 $n-1$ 个字符串进行每一位的比较，时间复杂度为 $O(n^2m)$。 那接下来就是优化了。枚举 $n$ 个字符串是不能优化的，那么能优化的就在比较上。…

## 基础： 对于一个满足全序关系且其中元素满足可加减性的序列 $x$，令下标为 $1-n$，则有： $$ \\ \begin{aligned} \max_{i\in S} x_i=\sum_{T\subseteq S}(-1)^{|T|-1} \min_{j\in T}x_j \\ \min_{i\in S} x_i…

## 前言： 挺好一道容斥题。 ## 做法： 根据题目，可以转化一下题目意思。即为选取三个互不相同的区间，使得和为 $0$，且能按第一关键字为左端点位置，第二关键字为右端点位置，满足三个区间的单调增关系。 我们易发现可以先不考虑区间的大小关系，进行任意枚举，对于满足区间和条件的三个区间的六种排列中只会有一种满足大小要求…

在文章《题解：P14306 【MX-J27-T3】旋律》发表评论：

因为当新加入a_i的时候极差会变大，极大值从a_i-1变到了a_i

在讨论《正解求助》回复：

坏了，好像跟题解一样？？？ 还是严肃学习 面向题解 编程！！！

在讨论《本题样例加强(暴力)》回复：

严肃学习。

## 前言： 赛事随便看了下，然后水了一发。 ## 做法： 考虑到题目中是选取子序列，且代价为极差值。则可以贪心发现在极小到极大区间取满时最优。 由此可以先排序。 然后进行 DP，定义 $dp_i$ 为选到第 $i$ 个，包含右端点的最大值。对于每一个新数，选上后会变为最大值。选上后会带来 $k$ 的价值，但极差会变大…

## Day -10 下午订正题目，意外发现超水数据，根本不用优化（虽然把优化也打了）。 傍晚写了篇题解。 晚上参加牛客比赛，差点被薄纱……，最终还是成功AK（虽然排名不高）。 ## Day -9 下午订正题目，看了半个小时，没有看到 inline 后没有加 int，可恶的 dev 本地不报错…… 晚上讲题，拓展思维……

# [P8253](https://www.luogu.com.cn/problem/P8253) ## 前言 作为一个菜狗，看到这种题目肯定不会做。故此题从部分分开始分析。 ## 做法概括 ### Subtask 1： 对于该点有 $n\leq 3000$，$m=4$。 对于该点，易发现直接 $n^2\times m…

在文章《题解：P11343 [KTSC 2023 R1] 出租车旅行》发表评论：

%%%

# [P3747](https://www.luogu.com.cn/problem/P3747) ### 做法概括 在做本题前建议先去完成 [P4139](https://www.luogu.com.cn/problem/P4139) 都是对于扩展欧拉定理的应用，对于本题具有启发意义。 对于扩展欧拉定理： $a^b…

在讨论《10分求调，必回关》回复：

@[Stary1105](luogu://user/1639066) flag要重新赋值为0