题解at_abc 321 abc

来一篇简单易懂的良心题解。  由于数值不是 $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$， ......

## T1：[Order Something Else](https://atcoder.jp/contests/abc310/tasks/abc310_a) 模拟 代码实现 ``` n, p, q = map(int, input().split()) d = list(map(int, inpu ......

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

python抽象类的介绍 python的abc模块提供了对抽象类的支持，通过继承ABC类，可以实现定义一个抽象父类，这个父类可以提前定义好一些抽象接口，可以通过继承抽象父类并实现这些接口方法来定义不同的类 比如我们定义一个图形类 from abc import ABC, abstractmethod ......

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

Problem Statement If we add edges between every pair of sets that have shared elements, there will be O(N^2) edges to traverse. Instead, we can add N ......

### 题目 [F - Make 10 Again](https://atcoder.jp/contests/abc310/tasks/abc310_f) ### 思路 [参考](https://www.cnblogs.com/legendstane/p/freee-programming-cont ......

### 题目 [E - NAND repeatedly](https://atcoder.jp/contests/abc310/tasks/abc310_e) ### 思路 ![image](https://img2023.cnblogs.com/blog/3165412/202307/316541 ......

### 题目 [D - Peaceful Teams](https://atcoder.jp/contests/abc310/tasks/abc310_d) **参考:** https://www.cnblogs.com/legendstane/p/freee-programming-contest ......

计数好题。 首先对于每个连通块独立考虑，最后合并答案。 发现 点数超过 1 的强连通分量一定删不掉。 - 若连通块中存在 点数超过 1 的强连通分量 - tarjan 缩点之后，称这些点数超过 1 的强连通分量为关键点； - 那么两关键点之间的点也不能删； - 于是对于剩下的点直接 dp 即可，由于 ......

写在前面：本题蒟蒻给出两种做法，一种乱搞贪心（只是目前能过，若能被 Heck 请和我说），一种正解二分。 ## 正文 1 **最坏时间复杂度：$\mathcal{O}(n+\log V)(V=10^9)$** 这个做法是很简单的，在此不多讲。只需要二分超频电压 `mid` 即可，若当前 `mid` ......