专栏文章

no.9

NNTT__int128
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingrc8h
此快照首次捕获于
2025/12/02 02:09
3 个月前
此快照最后确认于
2025/12/02 02:09
3 个月前
查看原文

no.9 总结

T1 matrix

题意简述

给两个 n×nn\times n 的方阵 A,BA,B，每行每列都是 1∼n1\sim n 的排列。每次交换 AA 的两行或两列，求 A→BA\to B 的最小交换次数。

暴力

无。

正解思路

神秘题，考场上想出来了。
根据样例，发现一个性质：交换顺序对于结果无影响（证明要用群论，此处略）。
于是枚举 AA 的哪一行到了 BB 的第一行，再确定列之间的交换，从而确定行之间的交换。
不难做到 Θ(n3)\Theta(n^3)。

T2 net

题意简述

nn 个节点的一棵树。定义一次操作为选择一条路径或选择一个点周围的边覆盖，求每条边恰覆盖 11 次的最少操作次数。

暴力

无。

正解思路

树形 DP。
定义 dpu,0/1/2dp_{u,0/1/2} 为以 uu 为根的子树内，对 uu 使用脉冲术/路径术覆盖完/路径术可以向上连的最小操作次数。
转移：
dpu,0=∑dpv,2+1dpu,1=min⁡(dpu,1+dpv,0,dpu,2+1+min⁡(dpv,1,dpv,2))dpu,2=min⁡(dpu,2+dpv,0,dpu,1+min⁡(dpv,1,dpv,2))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

题意简述

nn 个数，每次删除一个数（破成两段），求 min⁡∣∑t=ijat−k∣\min\left|\sum\limits_{t=i}^ja_t-k\right|，其中，i,ji,j 属于同一段。

暴力

3030 pts

时光倒流。
考虑加进来一个数会发生什么。
枚举包含这个数的区间，计算答案即可。

正解思路

启发式合并。
每次加入一个数，就把它和其左边/右边合并，每次把小的合并到大的，二分求出答案最小值，更新即可。

T4 perm

有一个长度为 nn 的排列 aa，每次可以选择两个数 i,ji,j，满足 1≤i<j≤n1\le i<j\le n 且 ai>aja_i>a_j，交换 ai,aja_i,a_j。求最终能得到多少种排列。

暴力

3030 pts

DFS+哈希。

正解思路

发现只有 0101 是好做的，因为 11 只能往右走，所以预处理状压即可。
考虑怎么把排列转化为 0101 串。显然，枚举每个数，把大于等于它的视为 11，小于它的视为 00 即可。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...