在讨论《萌新刚学 OI 1ms，求调线段树合并模板》回复：

队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了 队爷，进队了…

在文章《回忆录》发表评论：

同样的竞赛经历，但是我却没有竞赛之前的那一段/ll

在文章《题解：P13957 [ICPC 2023 Nanjing R] 背包》发表评论：

为啥 如果有免费拿的宝石的价格比任何一个用钱买的宝石的价格要低，交换二者显然更优？ 如果一个价值小，重量大，一个价值大，重量小，那我肯定是免费拿前者，付费拿后者啊。 这样的话，如果交换，免费拿后者，前者背包里放不下了，那不就不对了吗

这题硬 DP 可做。 设 $f_{i,0/1}$ 表示考虑完了前 $i$ 个位置，第 $i$ 个位置放右边还是左边的方案数。状态非常简单。 如果答案不为 $0$，相邻 $a_i$ 的差都小于等于 $1$，所以考虑转移的时候枚举 $a_i-a_{i-1}$ 的值，有三种情况 $-1,0,1$。讨论一下就行了。 1. $a…

### 题意 构造一个 $n\times n$ 的网格，每个点有往上、下、左、右走四种情况。使得恰好有 $k$ 个点能走到网格之外。 ### 思路 主要就是两条： 1. 在网格最外围还往外指的点能出去。 2. 如果一个点指向的点能出去，那么这个点就能出去。 根据这两条可以轻松构造出 $k$ 个能出去的点。因为一定存在一…

### 题意 在一个 $n\times m$ 的网格中，有一些点能走一些点不能走，每一步可以向左、向右或向上（一个格子不能重复经过）。问从最下面一行的任意一格走到最上面一行的任意一格有多少种方案。 ### 思路 暴力 DP 的状态需要明确一下：$f_{i,j}$ 表示到 $i,j$ 这一格，并且上一步是往上走的方案数。…

首先，$\sum_{i=1}^{l}a_i$ 需要是 $m$ 的倍数。 当 $\sum_{i=1}^{l}a_i$ 与 $\sum_{i=2}^{l+1}a_i$ 两者之差 $a_{l+1}-a_1$ 是 $m$ 的倍数时，$\sum_{i=2}^{l+1}a_i$ 也是 $m$ 的倍数。这时，有 $a_{l+1}\e…

这题真是诈骗到我了。一开始我还以为是很难的计算几何... 平面版本不太直观，先考虑一维版本。 一条直线上有 $n$ 个点，每个点每次可以向左或右移动一格，问所有点会合时的最小时间。容易发现这个就是最左边的点与最右边的点的坐标差，再除以二向上取整。 接着我们参考运动的分解，发现一个平面上的点的运动可以拆成横坐标的运动和纵…

记录：https://www.luogu.com.cn/record/231854989 思路：随机两个数，给两个数的差分解质因数，将这个质因数作为 $m$ 去计算。 因为随机一个数在最优集合里的概率大于等于 0.5，所以每次随机有约 0.25 的概率使两数都在最优集合里，用了卡时使随机次数尽量多。 调出来的大佬给 2…

### T1 这个题是神秘小贪心。 首先分类讨论一下，如果 $n$ 是奇数，那么肯定是那种数多那种数放到奇数位置。如果 $n$ 是偶数，那么就两种都试一下取最优。 先按上面的方式得到一个序列，然后考虑调整到字典序最小。 有一些段是往左调的，记为集合 $P$，有一些点是往右调的，记为集合 $Q$。 $P$ 集合里的点内部…

### T1 这个题我的赛时做法是对于每个联通块维护一个大小为 k 的 set。 缩点完跑拓扑的时候合并 set 即可。 但是这个做法被老师出的数据卡了。 发现其实没有这么复杂。先把点按从大到小的顺序，建反图。每个点被前 $k$ 个点访问的时候就一定是前 $k$ 大的点。 如果一个点被经过 $k$ 次，那么就不用再走了…

随机化算法 ### P2312 [NOIP 2014 提高组] 解方程 枚举解从 $1$ 到 $m$，$O(n)$ 判断。 但是 $a_i$ 是大整数，所以可以去模一个大质数之后去判断。 ** ### P10102 [GDKOI2023 提高组] 矩阵 这个题很聪明。 一个矩阵乘一个向量 $(n\times1)$ 的时…

# 正难则反题目 ## CF559C 统计经过至少一个黑色点打的方案数，最后用总数减去。 先把黑点排序，设 $f_i$ 表示经过第 $i$ 黑点的方案数。 枚举 $j$ 从 $1$ 到 $i-1$，从 $j$ 走到 $i$ 的方案数为 $C_{x_i+y_i-x_j-y_j}^{x_i-x_j}$。 状态转移方程就是…

### 题意 给定两个长度为 $n$ 的序列 $A_i$ 和 $B_i$，求给 $A$ 序列任意重排后 $\displaystyle \sum_{i=1}^n ((A_i+B_i) \bmod M)$ 的最小值。 ### 思路 简单贪心，先观察数据范围，发现一条： $0\le A_i,B_i #define int l…

### 题意 给定 $n$ 个字符串，任意选取 $m$ 个字符串（一个字符串可选多次）拼接起来。问在所有 $n^m$ 个拼接方案中字符串字典序第 $x$ 小的。 ### 思路 首先要观察数据。 - $1\leq n \leq 10$ - $1\leq m \leq 5$ - $|S_i|\le10$ 发现 $n^m\l…

发现题解区全是二分写法，但是这个题也可以不用二分做。 先把人数表示成 $a\times 2^b$ 的形式，也就是打了 $b$ 轮淘汰赛和一轮有 $a$ 个人的循环赛。 总场次就是 $a\times (2^b-1)+\dfrac{a(a-1)}{2}$。 得到方程 $a\times (2^b-1)+\dfrac{a(a-…

### 题意 定义 $k$ 阶斐波那契数列为： 1. 第 $0$ 项到第 $k-1$ 项都为 $1$。 2. 从第 $k$ 项开始，每一项等于其前面 $k$ 项的和。 ### 思路 像这种累加的题肯定能想到前缀和。 记 $a_i$ 表示第 $i$ 项的值，$sum_i$ 表示前 $i$ 项的和。 容易推出 $a_i=s…

先随机抽取键盘上某个按键，然后根据我键盘的颜色来决定做什么颜色的题，特别的，如果抽到 ←键、↓键，→键，按绿题记。 >概率： >- 红题 $18.39\%$ >- 橙题 $19.54\%$ >- 黄题 $19.54\%$ >- 绿题 $18.39\%$ >- 蓝题 $14.94\%$ >- 紫题 $9.2\%$ >罚时…

在讨论《扣 1 复活讨论区》回复：

不同意！ 过去一段时间，我们注意到部分讨论内容逐渐偏离社区初心——「机房惨案」等低质灌水泛滥、无意义内容挤占优质交流空间、个别用户发表辱骂及不友善言论等问题，已严重影响用户体验。尽管我们持续优化管理措施，但仍难以在现有框架下平衡自由交流与规范管理。

### 题意 给定一个长度为 $n$ 的序列，将其分为 $2$ 段，每一段的权值为不同数字的个数，问两段最大的权值和。 ### 思路 暴力模拟即可。枚举 $i$ 从 $1$ 到 $n-1$，表示从第 $i$ 个点之后断开。 如果枚举断点后遍历每个区间是 $n^2$ 的，会爆掉。考虑开两个桶 $t1_i$ 和 $t2_i…

在文章《题解：P11854 [CSP-J2022 山东] 宴会》发表评论：

2022年，小时候的代码

### 题意 有 $n$ 个区间 $[l_i,r_i]$，每次给区间中的数加一，问最后序列的最大值。 ### 思路 我还以为得加个离散化，结果一看数据范围 $a_i,b_i\le10^6$，又是差分板子。 先差分，每次操作就是单点加，最后把差分数组前缀和一遍就是最终数组，统计最大值即可。 有一个坑点，就是差分数组的值域…

### 题意 给定长度为 $n$ 的序列 $x$ 和 $t$，求出一个最小的 $x_0$，使得 $\max(t_i+|x_0-x_i|)$ 最小。 ### 思路 这个题是大原题，[CF1730B](https://www.luogu.com.cn/problem/CF1730B)，连样例都一样。 发现无论 $x_0$…

在讨论《话说扩B及之外的字是不是发不出来》回复：

扩G的biang打不出来 ???

在讨论《话说扩B及之外的字是不是发不出来》回复：

?

### 题意 有一个 $n\times n$ 的网格，网格有的位置有数。一个人要从左上角走到右下角，每一步只能向下或向右走。他要两次从左上角走到右下角，重复的点权值只算一次，要使两次路径上的数字之和最大，求出这个最大值。 ### 思路 典型动态规划题。 如果设 $f_{i,j}$ 为走到点 $(i,j)$ 的最大值，先…

### 题意 有 $7$ 组数，$(a_1,b_1)$ 到 $(a_7,b_7)$。 如果 $a_i+b_i>8$，那么津津会不高兴。如果 $a_i+b_i>8$，则 $a_i+b_i$ 的值越大他就越不高兴。 问津津最不高兴的是哪一天，如果有相同的，输出最靠前的。 ### 思路 这个题的题意是求 $a_i+b_i>8…

### 题意 给定一棵树，删掉两个节点，问最多变成几棵树。 ### 思路 因为是一棵树，所以删掉的点 $x$ 度数为 $d_x$，那么 $x$ 所在的这棵树就会从 $1$ 棵树变成 $d_x$ 棵树。相当于增加了 $d_x-1$ 棵树。 所以可以想到一个很简单的贪心做法，先删度最大的点 $id$，答案加上 $d_{id…

### 题意 有一个长度为 $n$ 的序列，给定区间 $[l,r]$。可以在序列上进行一次操作，选中一个子序列然后将它翻转。问操作后区间 $[l,r]$ 和的最小值。 ### 思路 翻转子序列一定是有 $[l,r]$ 之间的元素的，不然就对原序列没什么影响。 如果又包含区间左边的元素，又包含区间右边的元素，那么可以考虑…

在讨论《关于我们逆天的作业量》回复：

@[AstaSunch_](luogu://user/764773)我们学校也很难受啊，1.18号才放假，有两本假期作业，语数英加起来将近40页，物化两科就20多页，每天还要体育锻炼。。。