C/C++教程

codeforces1473C

本文主要是介绍codeforces1473C,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

https://codeforces.com/problemset/problem/1473/C

题意:

给定一个序列a,是1,2,3,4,...k,k-1,k-2,...,k-(k-n)一共n个,现在要找到一个k的排列使得构造一个新序列b,b[i]=p[a[i]]并且要求b的字典序最大,且逆序对不能超过a序列

思路:

先看一个简单证明

\[1,2,3,4,5,6,7,6,5,4, \]

可以发现,他的逆序对的贡献只有在3,4,5,6,7,6,5,4中
可以将其总结成一个公式:

\[(1+2+3+...+(n-k-1))*2+n-k=(n-k)*(n-k-1)+(n-k)=(n-k)^{2} \]

这其实是一个回文串,在这个里面,假设一共有s个数字,编号为i,依次次从小到大,两个最小的一共可以对于每个数字一共可以提供(k-1)2次,以此类推,可以得出结果依旧是上式,假如对称的从大到小看,那么和最大的能够构成的逆序对也是(k-1)2次,可以看出来,在一个数字都不同的回文串里面,他的逆序对是一个定值,也就是一半长度的平方

#include <bits/stdc++.h>
#define eb emplace_back
#define divUp(a,b) (a+b-1)/b
#define mkp(x,y) make_pair(x,y)
#define all(v) begin(v),end(v)
#define int long long
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> pii;
bool checkP2(int n) {return n > 0 and (n & (n - 1)) == 0;};
const int N=100010;
int a[N];
void solve() {
    int n,k;
    cin>>n>>k;
    int tem=k-(n-k);
    for(int i=1;i<tem;i++) cout<<i<<' ';
    for(int i=k;i>=tem;i--) cout<<i<<' ';
    cout<<endl;
}
signed main() {
    ios::sync_with_stdio(false);cin.tie(0);
    int _; cin >> _; while (_--) 
    solve();
    return 0;
}
这篇关于codeforces1473C的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!