CQCPC F

Ptzyc · 2026-06-15 15:34:57 · 题解

题解

发现题目中给了单调不减的性质，考虑这个性质的作用。

发现无解的情况是好判的，只需判断是否存在 a_i > i 的点即可。

考虑如何构造，发现对于点 x 我们钦定 x+1 到 n 都已经在 x+1 到 n 中出现完了，考虑 x 所在的位置。

发现对于点 a_x 我们可以通过修改 a_x 使得 a_x 到 x 之间的所有值都被修改为 a_x 到 x 之间的值。

具体的，因为单调不减的性质，a_x 到 x 之间的值都是 \le a_x 的，这启发我们可以考虑将 a_x 中的值修改为 x，a_x - 1 中的值修改为 x-1 以此类推，这样每个点总和下来最多修改 \frac {n (n-1)} {2} 次，符合题目要求。

（实在不行就自己手摸几个样例吧）。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e3+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,a[N];
vector<ll> num;
inline void solve () {
    n=read();
    for (ll i=1;i<=n;i++) {
        a[i]=read();
    }
    for (ll i=1;i<=n;i++) {
        if (a[i]>i) {
            puts("NO");
            return ;
        }
    }
    num.clear();
    ll pos;
    for (ll i=n;i;i=pos-1) {
        pos=a[i];
        while (a[pos]<pos) {
            num.push_back(i);
            a[pos]++;
        }
        for (ll j=pos+1;j<=i;j++) {
            num.push_back(i);
            while (a[j]<i-(j-pos)) {
                num.push_back(pos);
                a[j]++;
            }
        }
    }
    puts("YES");
    print(num.size());
    puts("");
    for (auto it : num) {
        print(it);
        putchar(' ');
    }
    puts("");
}
int main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    T=read();
    while (T--) {
        solve();
    }
    return 0;
}