CF2145D 题解
2025-10-07 01:07:44
发布于：广东
42阅读
0回复
0点赞
赛后 4min 切，有点可惜。不过能让我学到知识的题就是好题。
题意解析：
定义一个排列的逆序值为所有满足 且区间 存在至少一个逆序对的 的数量。
给定两个正整数 ，请你构造一个长度为 的排列，使得该排列的逆序值为 。
看似是构造题，实则不然。
首先考虑如何求一个排列的逆序值。
我们可以分别计算 对于逆序值的贡献，然后加起来。
例如 。
- ：区间就一个元素，显然没有贡献逆序值。
- ：显然也没有贡献逆序值。
- ：注意到 构成了一对逆序对，所以贡献出 ，，共 组。
- ：还是 构成逆序对，贡献出 ，，共 组。
- ： 构成逆序对，贡献出 ，，，，共 组。
- ：贡献出 ，，，，共 组。
注意到，如果 ，则 对逆序值的贡献与 对逆序值的贡献相同；如果 ，则 对逆序值的贡献为 。这个结论不难证明。
那这个对正解有什么帮助吗？
我们可以考虑 DP，求出一种合法的方案，使得区间对逆序值的贡献符合上面的规则。
记录是否存在第 个数， 对逆序值的贡献为 ，总逆序值为 的情况，如果存在，则 对逆序值的贡献可能是多少。
然后进行 dfs，枚举这种情况的每一个 是否满足 。
接下来就是构造环节了。首先令 ，然后对于连续的需要满足 的数，对这一块进行翻转即可。对，构造部分就是这么简单。
代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
int a[35];
int dp[35][35][440];
vector <bool> ans;
void dfs(int x, int y, int z){
if(!x) return;
dfs(x - 1, dp[x][y][z], z - y);
if(x == y) ans.push_back(1);
else ans.push_back(0);
}
void solve(){
int n, m;
cin >> n >> m;
ans.clear();
for(int i = 0; i < n; i++){
if(dp[n - 1][i][m] != -1){
dfs(n - 1, i, m);
for(int i = 1; i <= n; i++){
a[i] = i;
}
int l = -1;
for(int i = 1; i <= n; i++){
if(!ans[i - 1]){
if(l != -1){
reverse(a + l, a + i + 1);
l = -1;
}
}else{
if(l == -1) l = i;
}
}
if(l != -1){
reverse(a + l, a + n + 1);
}
for(int i = 1; i <= n; i++){
cout << a[i] << ' ';
}
for(int i = 1; i <= n; i++){
a[i] = 0;
}
cout << '\n';
return;
}
}
cout << "0\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
memset(dp, -1, sizeof(dp));
dp[0][0][0] = 0;
for(int i = 1; i <= 30; i++){
for(int j = 0; j < i; j++){
for(int k = j; k <= 435; k++){
if(dp[i - 1][j][k - j] != -1) dp[i][j][k] = j;
}
}
for(int j = i; j <= 435; j++){
for(int k = 0; k < i; k++){
if(dp[i - 1][k][j - i] != -1){
dp[i][i][j] = k;
}
}
}
}
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度：。
有帮助，赞一个