
$\text{Std Code:}$
#include<bits/stdc++.h>
using namespace std;
int V , len , now , cnt[27] , sum[27];
int get_max(int len){
return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
bool check(int x , int n){
memset(cnt , 0 , sizeof(cnt));
int add1 = 0 , add2 = 0;
for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];
sum[x] ++ ;
for(int L = 1 ; L <= n ; L ++){
int ma = -1 , pos = 0 , num = 0;
for(int j = 26 ; j >= 1 ; j --){
if(L - 1 - cnt[j] + num > ma){
ma = L - 1 - cnt[j] + num;
pos = j;
}
num += sum[j];
}
add2 += ma , cnt[pos] ++;
}
if(now + add1 + add2 >= V) {
now += add1;
return true;
}
else {
sum[x] -- ;
return false;
}
}
signed main()
{
string ans = "";
cin >> V;
for(int i = 1 ; ; i ++) {
if(get_max(i) >= V){
len = i;
break ;
}
}
for(int i = 1 ; i <= len ; i ++){
for(int j = 1 ; j <= 26 ; j ++){
if(check(j , len - i)){
ans += char(j + 'a' - 1);
break ;
}
}
}
cout << ans << '\n';
return 0;
}
$\text{My Code:}$
//耗费了整整一晚上,我大抵是凭借着我的反编译技术理解了。。。
//本题是推理+构造题,先推出当长度一定时,最大交换次数是多少,需要观察到 每个字符的交换次数贡献*2 = 总字符数-该种字符的数量(这也代码中L-1-cnt[j]的原因)
//因此贪心一下,每种字符的数量要尽可能平均,总的逆序对数量才会最大
//构造时从小到大枚举,可以找到字典序最小的第一个可行解
//由于字典序越小,逆序对也越少,当找到第一个可行解时,最终的逆序对数一定是恰好等于V的
//理解之后可以发现check中j正着循环也是正确的
#include<bits/stdc++.h>
using namespace std;
int V , len , now , cnt[27] , sum[27];
int get_max(int len){
return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
bool check(int x , int n){
memset(cnt , 0 , sizeof(cnt));
int add1 = 0 , add2 = 0;
for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];
sum[x] ++ ;
for(int L = 1 ; L <= n ; L ++){
int ma = -1 , pos = 0 , num = 0;
for (int j = 1; j <= 26; ++j) num += sum[j];
//for(int j = 26 ; j >= 1 ; j --){
for (int j = 1; j <= 26; ++j) {
num -= sum[j];
if (L - 1 - cnt[j] + num > ma) { //注意,这里插入的时候不是按照顺序插入的,而是插入到最合适的位置使得逆序对最大
ma = L - 1 - cnt[j] + num;
pos = j;
}
//num += sum[j];
}
add2 += ma , cnt[pos] ++;
}
if(now + add1 + add2 >= V) {
now += add1;
return true;
}
else {
sum[x] -- ;
return false;
}
}
signed main()
{
string ans = "";
cin >> V;
for(int i = 1 ; ; i ++) {
if(get_max(i) >= V){
len = i;
break ;
}
}
for(int i = 1 ; i <= len ; i ++){
for(int j = 1 ; j <= 26 ; j ++){
if(check(j , len - i)){
ans += char(j + 'a' - 1);
break ;
}
}
}
cout << ans << '\n';
return 0;
}
Comments | NOTHING