题解：P16534 [THUPC 2026 决赛] 年鉴整理

lailai0916 · 2026-08-31 04:08:00 · 题解

题意简述

每次可把相邻的后一本年鉴移到前面，并令它的破损度增加 1。要求在至多 n^2-n 次操作内，使破损度严格递增；若无法做到，则输出 -1。

解题思路

一次操作会把相邻两项 (x,y) 变为 (y+1,x)。先构造两个保持相对顺序的加值操作。

在同一位置连续操作 4 次，变化过程为：

因此，4 次操作可将相邻两项同时增加 2。

对连续三项依次操作右、左位置，并重复 3 次，最终有：

这个过程使用 6 次操作。任意长度至少为 2 的连续段，都能拆成若干二元组，必要时再加入一个三元组。整段每项都增加 2，相对顺序不变。操作数恰为区间长度的两倍。

下面从左到右固定答案。设当前尚未固定的后缀为 [l,n]，且长度至少为 5。给位置 i 定义关键量：

选择使 b_p 最小的最靠左位置 p。再用 p-l 次操作把该项移到位置 l。每向左移动一格，它都会增加 1，所以固定后的值为：

接下来，需要保证后缀中无论哪一项被选作下一个固定项，其最终值都严格大于 v。

先考虑原位置 j<p 的项。第 p 项移走后，它向右移动一格。若下一轮把它移到 l+1，所得值为：

由于 p 是最靠左的最小位置，j<p 时必有 b_j>b_p，故该值严格大于 v。

再考虑原位置 j>p 的项。将这些项全部增加 2，且不改变它们的顺序。若下一轮把其中一项移到 l+1，所得值为：

由 b_j\ge b_p，这个值同样严格大于 v。

当 p\le n-2 时，原来位于 p 右侧的区间长度至少为 2。可直接用前述二元组和三元组完成加值。

当 p=n-1 时，对当前最后两项连续操作 4 次。这个过程会额外增加一项，但不会破坏严格不等式。当 p=n 时，右侧没有元素，无须处理。

因此，每固定一项后，下一项一定可以取得更大的值。重复这一过程，直到只剩最后 4 项。

还需证明操作数不超过限制。设当前后缀长度为 m。当 p\le n-2 时，本轮操作数为：

当 p=n-1 时，操作数为 m+2；当 p=n 时，操作数为 m-1。由于此时 m\ge5，两者也都不超过 2m-2。从长度 n 处理到长度 5，总操作数至多为：

最后 4 项可以在 12 次内完成。先逐位选择使「当前值加当前位置」最小的最靠后项，并把它移到当前首位。

若两项关键量相等，则让靠后的项先被选中。其余项经过位置变化后，下一轮的最小关键量至少增加 1。因此，至多使用 3+2+1=6 次操作，就能得到非严格递增序列 (w,x,y,z)。

随后对这四项的相对位置依次操作：

序列会变为 (w,x+1,y+2,z+3)，从而严格递增。代码不必实现这套固定构造，而是对最后至多 4 项进行迭代加深搜索。上述结论保证搜索深度不会超过 12。

当原序列长度不超过 4 时，某些数据确实无解。此时搜索所有不超过 n(n-1) 次的操作序列，即可准确判断是否存在合法方案。

每组数据的时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。其中操作序列本身可能达到二次规模。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=505;
const int M=250005;
int n,cnt;
int a[N],op[M];
void apply(int p)
{
    a[p+1]++;
    swap(a[p],a[p+1]);
    op[++cnt]=p;
}
void rollback(int p)
{
    cnt--;
    swap(a[p],a[p+1]);
    a[p+1]--;
}
bool sorted(int l)
{
    for(int i=l+1;i<=n;i++)if(a[i-1]>=a[i])return 0;
    return 1;
}
bool search(int l,int dep)
{
    if(sorted(l))return 1;
    if(!dep)return 0;
    for(int i=l;i<n;i++)
    {
        apply(i);
        if(search(l,dep-1))return 1;
        rollback(i);
    }
    return 0;
}
void finish(int l)
{
    int len=n-l+1;
    for(int i=0;i<=len*(len-1);i++)if(search(l,i))return;
    cnt=-1;
}
void add2(int p)
{
    for(int i=1;i<=4;i++)apply(p);
}
void add3(int p)
{
    for(int i=1;i<=3;i++)
    {
        apply(p+1);
        apply(p);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        cnt=0;
        if(n<=4)finish(1);
        else
        {
            for(int i=1;i<=n-4;i++)
            {
                int p=i;
                for(int j=i+1;j<=n;j++)if(a[j]+j<a[p]+p)p=j;
                for(int j=p-1;j>=i;j--)apply(j);
                if(p<n)
                {
                    if(p==n-1)add2(p);
                    else
                    {
                        int j=p+1;
                        while(n-j+1>3)
                        {
                            add2(j);
                            j+=2;
                        }
                        if(n-j+1==2)add2(j);
                        else if(n-j+1==3)add3(j);
                    }
                }
            }
            finish(n-3);
        }
        if(cnt==-1)
        {
            cout<<-1<<'\n';
            continue;
        }
        cout<<cnt<<'\n';
        for(int i=1;i<=cnt;i++)cout<<op[i]<<(i==cnt?'\n':' ');
        if(!cnt)cout<<'\n';
    }
    return 0;
}