no.9
NTT__int128
·
·
个人记录
no.9 总结
T1 matrix
题意简述
给两个 n\times n 的方阵 A,B，每行每列都是 1\sim n 的排列。每次交换 A 的两行或两列，求 A\to B 的最小交换次数。
暴力
无。
正解思路
神秘题，考场上想出来了。
根据样例，发现一个性质：交换顺序对于结果无影响（证明要用群论，此处略）。
于是枚举 A 的哪一行到了 B 的第一行，再确定列之间的交换，从而确定行之间的交换。
不难做到 \Theta(n^3)。
T2 net
题意简述
### 暴力
无。
### 正解思路
树形 DP。
定义 $dp_{u,0/1/2}$ 为以 $u$ 为根的子树内，对 $u$ 使用脉冲术/路径术覆盖完/路径术可以向上连的最小操作次数。
转移：
$$
dp_{u,0}=\sum dp_{v,2}+1\\
dp_{u,1}=\min(dp_{u,1}+dp_{v,0},dp_{u,2}+1+\min(dp_{v,1},dp_{v,2}))\\
dp_{u,2}=\min(dp_{u,2}+dp_{v,0},dp_{u,1}+\min(dp_{v,1},dp_{v,2}))
$$
## T3 [balance](https://www.luogu.com.cn/problem/T686177)
### 题意简述
$n$ 个数，每次删除一个数（破成两段），求 $\min\left|\sum\limits_{t=i}^ja_t-k\right|$，其中，$i,j$ 属于同一段。
### 暴力
#### $30$ pts
时光倒流。
考虑加进来一个数会发生什么。
枚举包含这个数的区间，计算答案即可。
### 正解思路
启发式合并。
每次加入一个数，就把它和其左边/右边合并，每次把小的合并到大的，二分求出答案最小值，更新即可。
## T4 [perm](https://www.luogu.com.cn/problem/T686189)
有一个长度为 $n$ 的排列 $a$，每次可以选择两个数 $i,j$，满足 $1\le i<j\le n$ 且 $a_i>a_j$，交换 $a_i,a_j$。求最终能得到多少种排列。
### 暴力
#### $30$ pts
DFS+哈希。
### 正解思路
发现只有 $01$ 是好做的，因为 $1$ 只能往右走，所以预处理状压即可。
考虑怎么把排列转化为 $01$ 串。显然，枚举每个数，把大于等于它的视为 $1$，小于它的视为 $0$ 即可。