Find the original array for the inverse logarithm

Find the original array for the positive order logarithm

hypothesis The positive order logarithm is $01212$
solve :

1. Let's take care of those with small positive order logarithms , From small to large
2. When the positive order logarithm is the same , From right to left

$00000$
$10000$
$13020$
$13524$

Example
This problem needs to be based on the incomplete array , Complement the original array

#include<bits/stdc++.h>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
#define SIZE (1000000+10)
int a[SIZE];
int b[SIZE];
int flag[SIZE];
vector<int>pot[SIZE];
int main() {
    
    int i,j,n,k,p,x;
    scanf("%d%d",&n,&k);
    for(i=0;i<k;i++){
    
        scanf("%d%d",&p,&x);
        b[p]=x;
    }
    int maxn=0;
    for(i=1;i<=n;i++){
    
        if(b[i]==0)b[i]=b[i-1]+1;
        else {
    
            if(b[i]>maxn+1){
    
                cout<<-1<<endl;
                return 0;
            }
        }
        maxn=max(maxn,b[i]);
        pot[b[i]].push_back(i);     
    }
    int ans=1;
    for(i=1;i<=n;i++){
    
        for(j=pot[i].size()-1;j>=0;j--){
    
            a[pot[i][j]]=ans++;
        }
    }
    //for(i=1;i<=n;i++)printf("%d ",b[i]);cout<<endl;
    for(i=1;i<=n;i++)printf("%d ",a[i]);cout<<endl;
   
    return 0;
}

Find the original array for the inverse logarithm （ The original numbers are different

Sort
The key to this problem is to get the original array

1. Put in $0012...x-1xx+1...n-2$
2. The extra number is added from the second position , You can get the inverse logarithm $012...xxx+1...n-2$
3. Then deduct the number from the current position , We can get the positive order logarithm $0011...10...0$
4. First put 0 , Put again 1, From right to left

#include<bits/stdc++.h>
using namespace std;
const int Size = 1e5 + 10;
#define ll long long
#define debug(x) {
      cout<<#x<<" = "<<x<<" ";}
#define debug1(a) {
      debug(a);cout<<endl;}
#define debug2(a,b) {
      debug(a);debug1(b);}
#define debug3(a,b,c) {
      debug(a);debug2(b,c);}
#define debugvec(x,n) {
      cout<<#x<<": ";for(int asd=0;asd<n;asd++)cout<<x[asd]<<" ";cout<<endl;}
#define debugvector(x) {
      cout<<#x<<": ";for(int asd=0;asd<x.size();asd++)cout<<x[asd]<<" ";cout<<endl;}
#define debugvectorstring(x) {
      cout<<#x<<": ";for (auto& s : x) printf("%s", s.c_str());;cout<<endl;}
int n, k = 100;
string s, ans;
vector<int>v;
void ini() {
    
    int i, t;
    n = 1;
    while (n * (n - 1) / 2 < k) n++;
    v.push_back(0);
    for (i = 0; i < n - 1; i++)v.push_back(i);
    t = k - (n - 2) * (n - 1) / 2;
    //debug3(k, (n - 2) * (n - 1) / 2, t);
    for (i = n - 1; t; t--, i--)v[i]++;
    for (i = 0; i < n; i++)v[i] = i - v[i];
    //debugvec(v, n);
}
void sovle() {
    
    int i;
    char ch = 'a';
    s.resize(n);
    for (i = n - 1; i >= 0; i--)if (!v[i]) s[i] = ch++;
    for (i = n - 1; i >= 0; i--)if (v[i]) s[i] = ch++;
    cout << s << endl;
}
int main() {
    
    //freopen("C:\\Users\\31531\\Desktop\\input.txt", "r", stdin);
    ini();
    sovle();
    return 0;
}

Find the original array for the inverse logarithm （ The original number can be the same

String sort

When $k\le \frac{26(26-1)}{2}=325when$

1. Put in $0012...x-1xx+1...n-2$
2. Start from the bottom two $v[i]++$, Move forward two spaces at a time $i-=2$
3. Start with the positive two or three $v[i]++$, Move back two spaces at a time $i+=2$
4. It is already an increasing order , Put it directly from right to left

#include<bits/stdc++.h>
using namespace std;
const int Size = 3e3 + 10;
#define ll long long
#define debug(x) {
      cout<<#x<<" = "<<x<<" ";}
#define debug1(a) {
      debug(a);cout<<endl;}
#define debug2(a,b) {
      debug(a);debug1(b);}
#define debug3(a,b,c) {
      debug(a);debug2(b,c);}
#define debugvec(x,n) {
      cout<<#x<<": ";for(int asd=0;asd<n;asd++)cout<<x[asd]<<" ";cout<<endl;}
#define debugvector(x) {
      cout<<#x<<": ";for(int asd=0;asd<x.size();asd++)cout<<x[asd]<<" ";cout<<endl;}
#define debugvectorstring(x) {
      cout<<#x<<": ";for (auto& s : x) printf("%s", s.c_str());;cout<<endl;}
string s = "";
int n,k=100;
vector<int>v;
void debugs(string s) {
    
	for (auto ch : s) {
    
		printf("%3c", ch);
	}
	cout << endl;
	int p[2] = {
     0,0 };
	for (int i = 0; i < s.size(); i++) {
    
		int cnt = 0;
		for (int j = i - 1; j >= 0; j--) {
    
			if (s[j] > s[i]) {
    
				cnt++;
			}
		}
		p[1] += cnt;
		printf("%3d", cnt);
	}
	cout << endl;
	//debug2(p[0], p[1]);
}
void ini() {
    
	int i, t;
	n = 1;
	while (n * (n - 1) / 2 < k) n++;
	t = k - (n - 1) * (n - 2) / 2;
	v.push_back(0);
	for (i = 0; i < n - 1; i++)v.push_back(i);
	//debugvec(v, n);
	for (i = n - 2; i > 0 && t; i-=2, t--)v[i]++;
	//debugvec(v, n);
	for (i = 1 + (n % 2); t; t--, i += 2)v[i]++;
	//debugvec(v, n);
}
void solve() {
    
	s.resize(n);
	char ch = 'a';
	s[n - 1] = ch;
	for (int i = n - 2; i >= 0; i--) {
    
		if (v[i] == v[i + 1])s[i] = ch;
		else s[i] = ++ch;
	}
}
int flag = 26 * 25 / 2;
int main() {
    
	//freopen("C:\\Users\\31531\\Desktop\\input.txt", "r", stdin);
	//debugs("bbaa");
	//debugs("jihgfeeddccbbaa");
	cin >> k;
	if (k > flag)while (1);
	ini();
	solve();
	cout << s;
	return 0;
}

When $k>\frac{26(26-1)}{2}when$ To be continued

• 2237
• gzyyxxwwvvuuttssrrqqppoonnmmllkkkjjjiiihhhgggffffeeeeddddccccbbbbaaaa