AtCoder Beginner Contest 282 G - Similar Permutation
2023-04-18 12:27:17 时间
套路题
题意
求有多少个 (1) 到 (n) 的排列满足恰有 (k) 对在排列中相邻的数满足前小于后
(2 leq n leq 500, 0 leq k leq (n - 1))
思路
f[i][j][k]
表示已经放置了前 i
个数, 放置的第i
个数是前i
个数中第j
大的($ 1leq(`j`)leq$i
),已放置的前i
个数形成的所有排列满足恰有 k
对在排列中相邻的数满足前小于后的排列数量。
放置第i+1
个数时,第i+1
个数是前i+1
个数中第j
大的,第i
个数是严格小于前i
个数中第j
大的,会为排列增加一对相邻的数满足前小于后,第i
个数是大于等于前i
个数中第j
大的,不会为排列增加一对相邻的数满足前小于后,转移方程为:
[f_{(i + 1) j k} = sum_{x = 1}^{j - 1}f_{i x (k-1)} + sum_{x=j}^{i}f_{ixk}
]
显然,后面的和式可以通过前缀和优化的。
时间复杂度为(O(n^2k))。
G - Similar Permutation
题意
求(1)到(n)的排列(A) 和 (B)的相似度为(k)的数量。
相似度计算:(k = sum_{i = 2}^{n}[(A_i - A_{i-1})(B_i - B_{i-1}) > 0]) (([X] = 1, X 为真,[X] = 0, X为假))。
(2 leq n leq 100, 0 leq k leq (n - 1))。
思路
与前一道题相比,这一题只是增加了一维状态。
f[i][a][b][k]
表示排列(A),(B)已经放置了前 i
个数, 排列(A)放置的第i
个数在排列(A)中是第a
大的,排列(B)放置的第i
个数在排列(B)中是第b
大的,此时相似度为(k)的排列数量。
转移方程为:
[f_{(i+1)abk} = sum_{x = 1}^{a - 1}sum_{y = 1}^{b - 1} f_{ixy(k-1)} +
sum_{x = a}^{i}sum_{y = b}^{i} f_{ixy(k-1)} +
sum_{x = 1}^{a - 1}sum_{y = b}^{i} f_{ixyk} +
sum_{x = a}^{i}sum_{y = 1}^{b - 1} f_{ixyk}
]
和式同样可以使用前缀和来优化。
时间复杂度为(O(n^4))。
代码
int pre[107][107][107], f[107][107][107];
void solve_problem() {
int n, m, P;
std::cin >> n >> m >> P;
auto add = [&](int a, int b) -> int {
a += b;
if ( a >= P ) a -= P;
return a;
};
auto sub = [&](int a, int b) -> int {
a -= b;
if ( a < 0 ) a += P;
return a;
};
auto sum = [&](int n, int x1, int y1, int x2, int y2) -> int {
if (n < 0) return 0;
return add(sub(sub(pre[n][x2][y2], pre[n][x2][y1 - 1]), pre[n][x1 - 1][y2]), pre[n][x1 - 1][y1 - 1]);
};
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int h = 0; h <= n; h++)
pre[i][j][h] = f[i][j][h] = 0;
f[0][1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int k = 0; k <= i + 1; k++) {
for (int a = 1; a <= i; a++) {
for (int b = 1; b <= i; b++) {
pre[k][a][b] = add(pre[k][a][b - 1], f[k][a][b]);
}
}
for (int b = 1; b <= i; b++) {
for (int a = 1; a <= i; a++) {
pre[k][a][b] = add(pre[k][a][b], pre[k][a - 1][b]);
}
}
}
for (int k = 0; k <= i + 1; k++) {
for (int a = 1; a <= i + 1; a++) {
for (int b = 1; b <= i + 1; b++) {
f[k][a][b] = add(
add(sum(k - 1, 1, 1, a - 1, b - 1), sum(k - 1, a, b, i, i)),
add(sum(k, 1, b, a - 1, i), sum(k, a, 1, i, b - 1))
);
}
}
}
}
std::cout << sum(m, 1, 1, n, n) << "
";
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击