AC修炼计划（ AtCoder Regular Contest 178）A~C

A - Good Permutation 2

传送门

我们想让排列字典序尽可能的小，就得把小的数尽可能的往前面放，也就是说，在考虑第i个点的时候，i后面的数字我们可以忽略不计，在符合条件的情况下把能放在i的最小的数放上去。

首先，第一位一定是要放1的，而后面的数只要符合条件就按照从小到大的顺序往里面放入依次放数。

当遇到题目限制条条件时我们要将限制条件分成一个个连续的段。每一段处理方法就是把该段的数字向左移动一位,最左端的数字移动到最右端+1的位置。比如限制条件是3，4，5。在n等于7时我们可以得到的最小序列为1 2 4 5 6 3 7.

当限制条件出现1或者n时则无法构建，代码如下：

#pragma GCC optimize(3)  //O2优化开启
#include
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair PII;
// const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f; 
//inline int read()                     //快读
//{
//    int xr=0,F=1; char cr;
//    while(cr=getchar(),cr'9') if(cr=='-') F=-1;
//    while(cr>='0'&&cr
//    if(x
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table
    ll num;
public:
    modint(ll num = 0) :num(num % mod){}
 
    ll val() const {
        return num;
    }
 
    modint pow(ll other) {
        modint res(1), temp = *this;
        while(other) {
            if(other & 1) res = res * temp;
            temp = temp * temp;
            other = 1;
        }
        return res;
    }
 
    constexpr ll norm(ll num) const {
        if (num > other.num; other.num %= mod; return is; }
    friend ostream& operator other.num = (other.num + mod) % mod; return os 
    cinn>m;
    bool f=0;
    int ff=0;
    for(int i=1;i
        cin>a[i];
        if(a[i]==n||a[i]==1){
            f=1;
        }
    }
    if(f)cout
        sort(a+1,a+1+m);
        int p=0;
        for(int i=1;i
            ans[a[i]]=a[i]+1;
            if(a[i]==a[i-1]+1){
                // ans[a[i]]=a[i]+1;
            }
            else{
                ans[a[i-1]+1]=p;
                p=a[i];
            }
        }
        ans[a[m]+1]=p;
        for(int i=1;i
            if(ans[i])cout
    ios::sync_with_stdio(false);          //int128不能用快读！！！！！！
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin_yq;
    while(_yq--){
        icealsoheat();
    }
}
//
//⠀⠀⠀             ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//

//    int xr=0,F=1; char cr;
//    while(cr=getchar(),cr
//    if(x
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(ll x) : x{norm(x % getMod())} {}
    static int Mod;
    constexpr static int getMod() {
        if (P  0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x