题解p9669 jinan order

$m\le 20$，状压 DP。 首先可以根据每个人的 $k$ 从小到大排序。 定义 $f_{i,j}$ 表示考虑到第 $i$ 个人，完成了 $j$ 状态的题目，不考虑显示器所需的最小价格。 转移显然为 $f_{i,j|s_i}=\min(f_{i-1,j}+x_i)$。 最终答案为 $ans=\m ......

贪心+DP。 先从小到大排序。 定义 $f_i$ 表示序列 $[1,i]$ 能否分组。 转移为 $f_i|=f_j[a_i-a_j\le d,j\le i-k+1]$。 右区间可以直接算出来，左区间可以二分或根据单调性弄个指针。 定义 $sum_i=\sum\limits_{t=1}^{i}f_t$ ......

题解太高深，自己整理一份。 **阶的定义：** 若 $\gcd(a,m)=1$，则使 $a^l\equiv1\pmod{m}$ 的最小的 $l$ 称为 $a$ 关于模 $m$ 的阶，记为 $\operatorname{ord}_m a$。 **阶的性质：** 根据欧拉定理，$a^{\varphi(m ......

恶心题。 每次操作，相当与把第 $i$ 个数置换到 $p_i$，于是可以连边。 因为 $i$ 和 $p_i$ 互不相同，所以对于每一个点，有且仅有一条出边和一条入边，即若干个简单环。 那么最少操作 $\operatorname{lcm}(a_1,a_2,a_3...a_{x-2},a_{x-1},a ......

这是一篇简洁易懂的良心题解，提供了多种做法。 对于两个数 $x,y$，定义 $x=n^2 \cdot tx,y=m^2 \cdot ty$。如果 $x\cdot y$ 为平方数，则说明 $tx=ty$。所以我们可以将每个数除去其平方因子，比较相邻两数是否相等即可。 ## F1： 定义 $f_{i,j ......

感觉题解区不是写的太高深，就是写的太高深。所以给初中、小学和幼儿园的萌新准备一篇简单易懂的良心题解~ ### 前置知识 一、多项式的系数表示法和点值表示法。$A(x)=\sum\limits_{i=0}^{n-1}a_i\cdot x^i$ 系数：$(a_0,a_1,a_2...a_{n-2},a_ ......

有意思的题，927ms 拿下最优解。 点数最多 $10^{10}$ 个，没法暴力拼接，考虑简化大树。 每次拼接，我们记录 $x$，$to$ 和 $to$ 所在大树的根节点 $rt$。然后连两条边： $(rt,to)$ 和 $(to,x)$。本质上相当于把每次接上来的子树缩成一个点。 这样大树的点数最 ......

[Score of a Tree](https://www.luogu.com.cn/problem/CF1777D) 思维题。 我们考虑一个点 $u$ 在所有时刻内的点权为多少。 可以发现，假如 $u$ 的深度为 $0$，那么 $t$ 时刻时它的权值为其子树内所有深度为 $t$ 的点的初始权值异或 ......

组合容斥问题。 定义 $\operatorname{sum}(i)$ 为至少有 $i$ 组人会讨论的方案数。 那么最终答案就为 $\sum\limits_{i=0}(-1)^i\times \operatorname{sum}(i)$。 在 $n$ 个人中选 $m$ 组人讨论的方案数为 $\dbin ......

[Bracket Insertion](https://www.luogu.com.cn/problem/CF1781F) 神仙 DP 题，不愧是 tourist。 容易发现，括号序列一共有 $1\cdot 3\cdot 5...\cdot (2n-1)$ 种生成方式。 假如 `(` 为 $1$，` ......

[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) 本篇题解为此题~~最~~较**简单做法**及~~最~~**较少码量**， 并且码风 ......