题解p9858 2008 cold

[The Human Equation](https://www.luogu.com.cn/problem/CF1775E) 思维题。 我们考虑每次 $a$ 数组加一减一对于其前缀和 $sum$ 的影响。 可以发现，假设相邻两次加一和减一的位置分别为 $l$ 和 $r$，那么 $sum$ 在 $[l ......

[[ARC153B] Grid Rotations](https://www.luogu.com.cn/problem/AT_arc153_a) 有思维含量的一题。 我们横纵坐标分开考虑，对于每一个矩形，每次操作会使其内部元素的横坐标上下对调。 纵坐标也同理，左右对调。 而这种反转操作我们显然可以直 ......

[Yet Another Minimization Problem](https://www.luogu.com.cn/problem/CF868F) 神仙题。 第一眼看上去就是 DP。 定义 $f_{i,j}$ 表示当前点 $i$，分 $j$ 段的最小费用。 $f_{i,j}= \min(f_{i ......

[P4322 [JSOI2016]最佳团体](https://www.luogu.com.cn/problem/P4322) 分数规划+树形背包。 可以根据推荐关系建出一颗树，然后如果选了一点，则该点到根上的所有点都必须选。 二分 $mid$，定义每个结点的权值，然后判断选 $k+1$ 个节点的最大 ......

[Friendly Spiders](https://www.luogu.com.cn/problem/CF1775D) 带有技巧的最短路。 如果 $u$ 能到 $v$，说明 $\gcd(u,v)>1$，也就是有相同因子。 所以我们考虑对于每个数 $u$，向他的所有质因子连一条长度为 $1$ 的边， ......

很容易想到分类。 我们可以把 $1$ 到 $i-1$ 的球分为两类，一类是权值小于 $val_i$，另一类是权值大于 $val_i$。 对于第一类，$sum$ 加上小于 $val_i$ 的球的个数乘以 $val_i$。 对于第二类，$sum$ 加上所有大于 $val_i$ 的球的权值。 这显然可以用 ......

看题目限制，可以发现如果将机器人作为点，指控和保护关系作为边，可以建出一个森林，就下来就是传统的树形背包了。 设 $f_{i,j,0/1}$ 表示当前点为 $i$，子树内有 $j$ 个狼人，当前点是否为狼人的方案数。 初始化：$f_{u,0,0} = f_{u,1,1} = 1$ 当前点为狼： - ......

### 题面描述 给定一颗树，求分成三部分后的最小差异值。 ### 题解 暴力：每次枚举两个点，将其父边断掉，如果存在祖先关系则特判一下，复杂度 $O(n^2)$，预计 50pts。 正解：dfs 搜索每个结点，砍掉它的父边，剩下的尽量等分（易证）。 这一步可以用 multiset 维护。 对于一个 ......

来一篇简单易懂的良心题解。  由于数值不是 $0$ 就是 $1$，我们可以考虑将逆序对的统计方式化简。 以左区间为例，设 $x$ 为 $1$ 的个数，$p_i$ 为第 $i$ ......

## T1 辣椒树 ### 题面描述 给定一颗树，求分成三部分后的最小差异值。 - 子任务一，$20$分，保证 $N ≤ 200$； - 子任务二，$30$分，保证 $N ≤ 2000$； - 子任务三，$50$分，$N ≤ 2 × 10^5$。 ### 题解 暴力：每次枚举两个点，将其父边断掉，如 ......

一道推式子的数学题。 $$ \begin{aligned} \sum\limits_{i=l}^{r}\sum\limits_{j=1}^{i}\left\{\dfrac{j}{i}\right\} &=\sum\limits_{i=l}^{r}\sum\limits_{j=1}^{i}\left( ......

暴力1：按照题意模拟即可，复杂度 $O(32n^2)$，预计 30pts。 暴力2：将 IP 地址用 `unsigned int` 存下来，比较 $a$，$b$ 是否匹配就只需要用位运算 $O(1)$ 判断即可，复杂度 $O(n^2)$，预计 50pts。 正解：考虑将当前插入的所有 IP 地址建成 ......

暴力1：直接 dfs 枚举每个位置状态，复杂度 $O(2^n)$，预计 10pts。 暴力2：考虑贪心，如果一个左括号有多个合法的右括号匹配，则一定选最靠右的，而一对括号匹配当且仅当字符相同且中间部分可以完全匹配。 怎么判断能否一段连续区间可以完全匹配呢？我们可以用栈模拟！ 假设该区间为 $[l, ......

显然，答案不好直接求，我们考虑用总数减去不合法的方案数。 为了不算重，我们每次只考虑当前点与圆心连线交圆周于一点所形成的半圆内的不合法情况，然后用组合数算出剩下两个点的选择方案数。 ![](https://cdn.luogu.com.cn/upload/image_hosting/9cugwrpj. ......

通过观察，可以发现此题和最小生成树十分相似（两个地点之间途经的最小值最大）。 于是可以考虑这么做： 1. 通过 bfs 将每一个块预处理出来，并记录其编号、高度、类型（是否为高地）以及边缘的点。 2. 将每一个块按高度从大到小排序。 3. 依次枚举每个块： - 对于当前要处理的块，枚举其边界的所有点 ......

首先可以观察到一个非常重要的性质：对于一次前进的操作，如果前面有奇数次转向，则走上下，否则走左右。（当然如果一开始就前进就只能走右） 于是我们可以将其拆成许多的“块”，并分成两类，即前进方向为左右还是上下。 ![](https://cdn.luogu.com.cn/upload/image_host ......

首先我们定义“圈”为与原点距离相等的点集。 ``` . . . 3 . . . . . 3 2 3 . . . 3 2 1 2 3 . 3 2 1 0 1 2 3 . 3 2 1 2 3 . . . 3 2 3 . . . . . 3 . . . ``` ### 暴力： 把圈放到堆里，然后每次取出代 ......

首先可以观察出一颗 $n$ 个节点的二叉树，当其字典序最小的时候，其形态为一条向右偏的链，当其字典序最大的时候，是一条向左偏的链。 由于每一种编码对应唯一的一颗二叉树，我们可以先建树。 然后考虑树上分治，尝试以下三种方式： 1. 变大右子树的字典序 2. 变大左子树的字典序，并将右子树变成一条链 3 ......

# 第五次作业题解 ## [P3156 【深基15.例1】询问学号 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P3156) $vector$**的输入** - **for (auto &i : a) cin ......

[原题链接](https://www.luogu.com.cn/problem/SP12304) | [题解链接](https://www.luogu.com.cn/problem/solution/SP12304) 本篇题解为此题~~最~~较**简单做法**及~~最~~**较少码量**， 并且码风 ......

可以证明答案是 $l$ 或 $r$ 的一段前缀，拼上后面全部相同的一段字符 $d$，证明方式类似数位 dp。能够自由填的数字一定是相等的，这样不会影响幸运值。前面那些不能自由填写的，就是 $l$ 或 $r$ 的一段前缀。假如不是 $l$ 或 $r$ 的一段前缀，必然填写相等的更好，而这种情况已经被考 ......

## 前言 [传送门](https://www.luogu.com.cn/problem/P7809) [blog](https://www.luogu.com.cn/blog/JJL0610666/solution-p7809) # 思路 ## Problem 1 问题一问的是最长不下降子序列的长 ......

## 前言 [传送门](https://www.luogu.com.cn/problem/P7333) [blog](https://www.luogu.com.cn/blog/JJL0610666/solution-p7333) # 思路 首先看数据范围 $10^5$，$O(n \log_2 n) ......

## 前言 [传送门](https://www.luogu.com.cn/problem/P8708) [blog](https://www.luogu.com.cn/blog/JJL0610666/solution-p8708) # 思路 这种选出两个数拼接在一起的题，一看就可以使用 two-po ......

### 前言 长沙市一中8机房0714模拟测1。 [传送门](https://www.luogu.com.cn/problem/UVA10791) [blog](https://www.luogu.com.cn/blog/JJL0610666/solution-uva10791) # 思路 本题思路 ......

### 前言 为了纪念 **长沙市一中** 第一次思维训练，我写下这篇题解。 [传送门](https://www.luogu.com.cn/problem/P2714) ## 题目描述 有 $n$ 个正整数 $a_i$，你要统计有多少个四元组满足 $\gcd(a_i,a_j,a_k,a_l) = 1 ......

T3： 考虑对每个人分开处理，f[i][j][0/1]表示已经做了A本语文作业，B本数学作业，目前在做语文/数学，需要的最小时间。 转移形如：$f[i][j][s]=min{f[i-l][j][1-s]+K\times{l^2}+B}$ 非常典的斜优或者决策单调性。决策单调性需要使用二分队列，复杂度 ......

# Descirption 给定一个 01 序列，每次随机交换两个不同位置的数，求交换 $k$ 次后序列排序好的概率。答案对 $998244353$ 取模。 # Solution 定义 $\text{cnt}$ 是序列中 $0$ 的个数，发现排序好的序列是前面 $\text{cnt}$ 个 $0$， ......

## _Description_ 在此题中，对于一个数 $x$，若 $\texttt{popcount}(x)\geq3$（即 $x$ 在二进制下 $\texttt{1}$ 的个数大于等于三时），那它是非法的，否则其为合法的。 给定 $T$ 个数，如果当前的数 $x$ 是非法的，则输出 ```N... ......

每组 $(a_i,b_i)$ 之间相互独立，于是我们只需要考虑一对数 $(a,b)$。 首先 $(0,0)$ 的情况是平凡的。考虑我们需要的状态 $(0,b)$，它的变化过程是这样的：$(0,b)\to(b,b)\to(b,0)\to(0,b)$，所以是三轮一个循环，且除了 $(0,b)$ 之外另外 ......