Cfz Round 3 E / 洛谷 P10033 题解

前言

我场切了，看来这场题目顺序很诈骗，明明 C 和 D 都没写出来。

等等，这道题竟然评绿了？

好激动，第一次场切绿，所以来写篇题解。

题意

给定一个 $1\sim n$ 的排列 $p$ 。你需要构造一个长度为 $n$ 的序列 $a$ ，满足：

序列 $a$ 中的每个元素均为不大于 $n$ 的正整数；
不存在有序整数二元组 $(l,r)$ ，满足 $1 \le l \le r \le n$ 且 $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$ ；或报告无解。

其中， $1\sim n$ 的排列指满足所有不大于 $n$ 的正整数恰好出现一次的序列。

数据范围

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有数据， $1 \le T \le 5000$ ， $2 \le n \le 10^6$ ， $\sum n \le 10^6$ ，保证 $p$ 是 $1\sim n$ 的排列。

思路

我们可以尝试考虑最终答案序列 $a$ 的形式。

$a$ 和原序列 $p$ 一样都由从 $1$ 到 $n$ 的整数构成，但不同点在于 $a$ 并不是 $1\sim n$ 的排列， $a$ 中的数字出现多少次都可以。

而题目里要求 ${\forall}l,r \in [1,n]$ ， $\sum\limits_{i=l}^r a_i≠\sum\limits_{i=l}^r p_i$ ，直觉告诉我让 $p$ 中的全部数字都大于 $a$ 就能很轻松地满足这个条件了；

但 $p_i$ 的取值最大只能为 $n$ ，且序列 $a$ 里必定有一个 $n$ ，所以一个全部为 $n$ 的 $p$ 序列已经可以满足除了 $l=r=i(a_i=n)$ 的所有情况了，因为不管怎么取 $l$ 和 $r$ ， $\sum\limits_{i=l}^r p_i$ 都一定是大于 $\sum\limits_{i=l}^r a_i$ 的。

那么 $a_i=n$ 的这一位 $p_i$ 该怎么改呢？我们顺着刚刚的思路，也给 $i$ 这一位放一个除了 $n$ 以外尽量大的数，设这个数 $p_i=n-k (1\leq k<n )$ 。

那么在取 $l,r$ 时，如果 $l>i$ 或 $r<i$ ，则 $\sum p$ 的值仍为 $(r-l+1)\times n$ 不受影响，一定满足要求；

但如果 $l\leq i\leq r$ ， $\sum p$ 就不一定能够大于 $\sum a$ 了。

于是我们换个思路，尝试让 $p_i$ 的值能够取到一个临界值 $[l_S,r_S]$ ，正好使这时在 $[l_S,r_S]$ 内的 $\sum p<\sum a$ ，但凡 $l$ 再比 $l_S$ 小 $1$ 或 $r$ 比 $r_S$ 大 $1$ ， $\sum p$ 就会超过 $\sum a$ 。

上述的这个过程我们可以通过从大到小枚举 $p_i$ （也就是 $n-k$ ），同时枚举 $l$ 和 $r$ 完成，看起来枚举了三个数很吓人，实际上复杂度并不高，因为临界值很快就会被取到，不信的话可以尝试构造一个能够尽量增加枚举次数的序列 $a$ ，它大概长成这个样子：

$\cdots n-2,n,n-1,n-3,\cdots$

可以看到，上面的这个序列已经很努力地在卡掉了 $p_i(a_i=n)$ 在 $[n-3,n-1]$ 中的值，但这已经是它能做到的极限了，不太优雅的证明如下：

当序列 $a$ 能卡掉 $p_i=n-1$ 、 $n-2$ 时， $n-1$ 与 $n-2$ 一定正好在 $n$ 的两侧，此时 $n-3$ 自然也被卡掉了；

想卡掉 $n-4$ 就只能在 $n-1$ 的同一侧放一个 $n-3$ ，但这样做你就永远卡不掉 $n-5$ 了，因为 $n-3$ 与 $n-1$ 在同侧，与 $n-2$ 在异侧；

反之亦然，如果想卡掉 $n-5$ 那 $n-4$ 就一定没法被卡掉。

所以我们不太优雅地证明了在 $[n-5,n-1]$ 里一定能取到 $p_i$ 。

到这里我们几乎已经解决了本题，接下来考虑序列 $a$ 的长度 $n$ 太小，导致 $n-5<1$ 的情况，下面是一个例子：

1
2

4
2 4 3 1

显然我们取遍了 $p_i$ 也没能取到一个值不会被特定的 $[l,r]$ 给卡掉，但有了前面的经验，我们只要反过来构造就好了：

把除了 $a_i=1$ 对应的 $p_i$ 以外的 $p$ 值都设成 $1$ ，让 $\sum p$ 尽量小于 $\sum a$ ，然后再枚举 $p_i$ 即可。

用上面的方法就能构造出序列 1 1 1 2，满足条件。

如果上面两种方法都构造不出来序列 $p$ ，那就是因为序列长度 $n$ 过短（也就是 $n=2$ ），可以证明这个时候一定无解，输出 -1 即可。

代码

int a[1000005],ans[1000005],pf[1000005];
inline int ques(int l,int r){return pf[r]-pf[l-1];}
void solve() {
    int t;read(t);
    pf[0] = 0;
    while(t--){
        int n;read(n);
        for(int i=1;i<=n;i++)   read(a[i]);
        for(int i=1;i<=n;i++)   pf[i] = pf[i-1]+a[i];   //前缀和处理一下方便查询
        a[0] = 0;a[n+1] = 0;
        bool get = 0;
        for(int i=1;i<=n;i++){
            if(a[i]!=n) ans[i] = n;
            else{
                for(int j=n-1;j>=1;j--){    //枚举这个位置该填的值
                    get = 1;
                    int sum = n,fsum = j;   //原数列a在该区间的和与构造出的数列的和
                    for(int l=0;i-l>=1;l++){
                        for(int r=0;i+r<=n;r++){
                            sum = n+(l?ques(i-l,i-1):0)+(r?ques(i+1,i+r):0);    //枚举区间[n-l,n+r]
                            fsum = j+(l+r)*n;
                            if(fsum>=sum){  //到了临界值
                                if(fsum==sum)   get = 0;    //这个值j不可用
                                break;
                            }
                        }
                    }
                    if(get){
                        ans[i] = j; //取到了符合条件的j
                        break;
                    }
                }
            }
        }
        if(get){
            for(int i=1;i<=n;i++)   cout<<ans[i]<<" ";
        }
        else{
            for(int i=1;i<=n;i++){  //再次尝试用n-1个1构造序列p
                if(a[i]!=1) ans[i] = 1;
                else{
                    for(int j=2;j<=n;j++){
                        get = 1;
                        int sum = 1,fsum = j;
                        for(int l=0;i-l>=1;l++){
                            for(int r=0;i+r<=n;r++){
                                sum = n+(l?ques(i-l,i-1):0)+(r?ques(i+1,i+r):0);
                                fsum = j+(l+r)*n;
                                if(fsum<=sum){
                                    if(fsum==sum)   get = 0;
                                    break;
                                }
                            }
                        }
                        if(get){
                            ans[i] = j;
                            break;
                        }
                    }
                }
            }
            if(get){
                for(int i=1;i<=n;i++)   cout<<ans[i]<<" ";
            }
            else    cout<<-1;   //这都构造不出来就是真无解了
        }
        cout<<"\n";
    }
}