一些数题解

Piggy343288 · 2023-06-23 11:18:28 · 题解

首先我们考察 LIS 长度为 n-1 的数列的性质。可以发现，这必定是 1,2,3,\cdots,n 中拎出一个不听话的元素甩到其他地方去，剩下的元素依次补齐所构成的。这意味着，最多只有一个元素满足 a_i-i\ge2，更具体的，不考虑只对邻项交换的排列（即形如 1,2,3,\cdots,i,i-1,\cdots,n），每个满足要求的排列都有且仅有一个元素满足 a_i-i\ge 2。

接下来对所有钦定了值的元素进行考察。这意味着下文中我们已经默认了 a_i\not=-1。

所有 a_i=i。那么我们只能对下标的空隙部分做操作。也就是假设相邻的两个下标分别为 i,j，那么这一段对答案的贡献是 (j-i-2)^2。不难写出如下的代码：
```
int cur = 0;
for(int i = 1; i <= n; i++){
if(!~a[i]) cur++;
else if(cur){
    ans += pow(cur - 1, 2);
    cur = 0;
}
}
if(cur) ans += pow(cur - 1, 2);
```

存在 |a_i-i|\ge 2。因为这样的 i 只能有一个，所以如果找到多个这样的下标直接 cout<<0<<"\n" 走人。即使仅有一个这样的 i，合法的也最多只能有一个排列。因此判断一下是否合法即可。不难写出下面的代码：

int p = -1;
for(int i = 1; i <= n; i++){
if(!~a[i]) continue;
if(abs(a[i] - i) >= 2){
    if(~p) return false;
    else p = i;
}
}
if(~p){
//found one abs(a[i] - i) >= 2
if(a[p] > p){
    int l = p, r = a[p];
    for(int i = 1; i <= n; i++){
        if(!~a[i]) continue;
        if((i < l || i > r) && a[i] != i) return false;
        if((i > l && i <= r) && a[i] != i - 1) return false;
    }           
}else{
    // just a reversion of a[p] > p...
    int l = a[p], r = p;
    for(int i = 1; i <= n; i++){
        if(!~a[i]) continue;
        if((i < l || i > r) && a[i] != i) return false;
        if((i >= l && i < r) && a[i] != i + 1) return false;
    }
}
}

存在 a_i=i+1,a_{i+1}=i。这种比较好判断，而且也最多只能存在一个这样的 i。
```
int cnt = 0;
for(int i = 1; i <= n; i++){
if(a[i] != i && ~a[i]){
    if(a[i] == i + 1 && a[i + 1] == i) i++, cnt++;
    else return false;              
}
}
if(!cnt) return false;
```
在写代码的时候，我把上述两个情况合并在一起了。因为它和下面的情况相差较大，但这两个本质是一个情况，即指定了开头所提到的“不听话的元素”。

存在一段 a_i=i+1 或一段 a_i=i-1。注意判断仅能存在一个这样的段！因此我们不难写出下面的代码，其中 flag 标志了目前在什么阶段（进入段前，段中，第一段后）。

int flag = 0;
p = 0;
for(int i = 1; i <= n; i++){
if(!~a[i]) continue;
if(a[i] == i){
    if(flag == 1) flag = 2;// signal if i is out of the offset area.
}else{
    // a[i] != i
    r = i;
    if(flag == 0){
        //no offset currently
        p = a[i] - i;
        l = i, flag = 1;// into the offset area;
    }else{
        if(flag == 1){
            if(a[i] - i != p) return false;
        }else{
            assert(flag == 2); return false;// out of the offset area and found another section,
            // which is impossible to generate any valid solution in this occasion.
        }
    }
}
}
return true;

int lcnt = 0, rcnt = 0;
for(int i = l - 1; i && !~a[i]; i--) lcnt++;
for(int i = r + 1; i <= n && !~a[i]; i++) rcnt++;
ans = 1ll * lcnt * rcnt;
ans += (~p ? rcnt : lcnt);

把几段代码融合一下，就得到了此题的代码。完整代码不给！

一些数 题解

一些数题解