### CF1994E Wooden Game 神金诈骗题。 最难的是想到只用分一个个的，因为如果把子树分开，和不分是等价的。 问题就转化成了一个数可以把它变小，问最大的或。 注意到 $\sum s_i\le10^6$，所以直接枚举每棵树留几个节点即可。 ### P3619 魔法 负收益的情况： 考虑一对(i,j) i…

我的评价是**这场太难了**，我太菜了，看了题解还是一道题都补不出来。ε=(´ο｀*)))唉。 ### T1 Increase 签到题，贪心发现肯定是 $a_n=a_{n-1}+1,a_{n-1}=a_{n-2}+2,\dots$ 这样下去最优。 然后用小学二年级就学过的等差数列求和公式就能算出，如果 $\displa…

## T1 Gcd 签到题。像 CF2063A 的诈骗题。 题面不用管，直接面向样例编程，发现输出 $1$ 和 $x-1$ 即可。 ## T2 Code Village ### 题意 给定一个长度为 $n$ 的区间，$m$ 次询问，每次询问求区间 $[l,r]$ 中大于等于 $k$ 的数有多少个。 ### 思路 一眼莫…

### 题意 有两个长度为 $n$ 的序列 $u_i$ 和 $d_i$，每次操作可以把一个正数减一，问最少经过次操作使得： 1. 存在 $H$ 使所有 $u_i+d_i=H$。 2. 序列中相邻两个数的差小于等于 $x$。 ### 思路 这道题可以二分答案去做。 只需要确定 $H$，答案就是所有数字的总和减去 $H\t…

### 题意 给定一个有向图，可以花 $x$ 的代价把边反转，花 $1$ 的代价走一条边。 问从 $1$ 到 $n$ 的最小代价。 ### 思路 分层图最短路练手题。 一共两层图，一层正图，一层反图。在两层之间连一条权值为 $x$ 的双向边。然后跑 dijkstra 即可。 有可能是到反转层的终点最短，也有可能是到原层…

### 题意 求出序列中相隔最近的两个相同数字的距离。 ### 思路 发现值域非常小，$A_i\le10^6$。所以可以直接开桶。 开一个数组 $pre_t$，表示 $t$ 这个数上一次出现的位置。如果当前数字出现过，就统计答案。$ans=\min(i-pre_{a_i}+1)$。 ### AC Code ```cpp…

### 题意 给定一个序列，每次可以将整个序列加一或减一，问若干次操作后序列中绝对值最大的数最小是多少。 ### 思路 这个题有坑点。 首先考虑序列中既有正数又有负数的情况，记一个最大值和最小值。 如果最小值绝对值大就加，直到加到最小值与最大值绝对值相等。否则最大值绝对值大就减，减到与最小值绝对值相等。设最大值为 $m…

### 题意 一个由 $0,1,2$ 组成的长度为 $n$ 序列 $a$，$0$ 表示向后指，$1$ 表示向前指，$2$ 表示哪都不指。问位置 $k$ 有没有被指。 ### 思路 如果一个位置的前面是 $0$ 或后面是 $1$ 就说明被指到了，所以只需要判断 $a_{k-1}=0$ 或 $a_{k+1}=1$ 即可。…

在讨论《【MX-X9/J11】 黄瓜赛 & GROI R3 赛时答疑帖》回复：

请问如何反应T1数据过水的问题。 一个手搓了好几组样例都错了的代码过了。

### 题意 给定一个长度为 $n$ 的序列 $a$。 有 $q$ 次询问，每次询问 $r$ 和 $x$ 求前 $r$ 个数中每个数都小于等于 $x$ 的最长上升子序列的长度。 ### 思路 把询问按 $r$ 从小到大排序，这样只需要逐渐向后拓展即可。 设 $f_i$ 表示以长度为 $i$ 的上升子序列结尾的最小值。答…

### 题意 给定一个长度为 $n$ 的序列 $a$ 和一个整数 $k$，对于每个 $i$，求出必须选 $a_i$ 的情况下选 $k$ 的数的最大 $\gcd$。 ### 思路 首先思考原始问题，在长度为 $n$ 的序列中选 $k$ 个数的最大 $\gcd$。这是有原题的。[P1414 又是毕业季II](https:/…

### 题意 给定一个长度为 $n$ 的 01 串，每次可以交换两个相邻的位置，问至少多少次交换可以让所有的 $1$ 都在一起。 ### 思路 容易发现最中间的 $1$ 不动，把两边的向中间靠是最优的。 如何确定最中间的？考虑 $1$ 的个数 $cnt$，如果是奇数，那肯定就是第 $\frac{cnt+1}{2}$ 个…

### 题意 给你一张无向图，问最少删几条边能使它变成一张简单图。 ### 思路 简单图指的是没有重边和自环的图，所以在输入 $m$ 条边的时候，判断一下当前边是否为重边或者自环。 自环非常简单，即 $u=v$ 的情况。重边的话用一个 map 记录，因为是无向边，所以当有 $u$ 到 $v$ 的边时也要标记从 $v$…

今天洛谷讨论区没了 但是 zhhhh 还可以发 吓我一跳 那还行 ### [P9650 [SNCPC2019] Escape Plan](https://www.luogu.com.cn/problem/P9650) 多源最短路，从所有终点开始跑，给每条边建反边，dijk 初始时把所有终点都放到堆里开始 bfs。 一个…

### [P2044 [NOI2012] 随机数生成器](https://www.luogu.com.cn/problem/P2044) 推出 $\begin{bmatrix}a & 1 \\0 & 1\end{bmatrix}\times\begin{bmatrix}x_0 \\c \end{bmatrix}=\be…

### [P4155 [SCOI2015] 国旗计划](https://www.luogu.com.cn/problem/P4155) 因为没有包含，所以左端点靠右的右端点一定靠右。把环断开，复制一份在后面，问题是选多少个区间能覆盖 $i$ 到 $i+n$。每次选区间能覆盖到的左端点最靠右的。 ### [CF208E…

在文章《题解：P1073 [NOIP2009 提高组] 最优贸易》发表评论：

%%%

# ~~线段树进进进进进接~~ ### [P6327 区间加区间 sin 和](https://www.luogu.com.cn/problem/P6327) 和角公式，维护 $\sin$ 值和 $\cos$ 值。 ### [P4198 楼房重建](https://www.luogu.com.cn/problem/P4…

## 莫队 ### [P3245 [HNOI2016] 大数](https://www.luogu.com.cn/problem/P3245) $suf_i$ 是算出来的后缀 $i$ 位 $\mod p$ 的值。 后缀差分，查区间 $[l,r]$ 有多少个 $(i,j)$ 满足 $suf_r-suf_l=0$，类似小…

## 根号分治 设一个阈值 $B$，如果查询数值 $m\le B$ 就用一种方法处理（时间复杂度通常是约 $O( n\times m)$），如果 $m>B$ 就用另一种方法处理（时间复杂度通常是 $\displaystyle O(\frac{n^2}{m})$），发现 $B$ 取 $\sqrt n$ 时最优，总体复杂度…

## 高斯消元 系数矩阵做三种变化： 1. 将某一行乘上 $k$。 2. 将某一行加到另一行。 3. 交换两行。 最后消成主对角线是 $1$，最后一列是答案，剩下的是 $0$。 结果： 1. 如果仅最后一列非 $0$，则方程无解。 2. 如果某一行全都是 $0$。 3. 否则有唯一的解。 例子看蓝书。 一开始尽可能选最…

在文章《个人纪录》发表评论：

?wokanbudong

在讨论《bug or futune?》回复：

@[crz_qwq](luogu://user/795344)什么意思

在讨论《熊出没。。。》回复：

@[meimu75](luogu://user/812561)逆转时空的时间线是在前9部之后的

在讨论《熊出没。。。》回复：

@[meimu75](luogu://user/812561)重返地球里说到牛大亨与牛夫人失败后决定回去开面馆，所以逆转时空里的面馆是重返地球之后的

它说评分小于 1600 的都是 rated，而且我在比赛之前报名了。报名的时候没有显示是否 rated 选项，只有一个报名，但是比赛完他说我是 unrated。

在讨论《洛谷日爆》回复：

@[dg114514](luogu://user/1373205)卡死我了，我打比赛呢，只能去梦熊交了。

听同机房大佬说的，不知道是不是。

在讨论《florr滚出中国》回复：

@[cjz5418](luogu://user/1209945) 你可以加入团队：47444

比如说之前叫他脱发缩合。 因为脱去一分子头发，形成一个肽键（太贱）。 但是这个太明显了，会被他发现。遂求助万能的谷民。