洛谷 P1627 分析（别看）

科技起源的小号1

2026-08-27 10:10:47

发布于：天津

10阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个具体值

1.2 题目背景、允许、禁止与限制

背景：
有一个 $1,2,...,n$ 的排列 $a$
允许：
要求记录排列中有多少长度为奇数的子序列中位数是 $b$

1.3 题目数据范围与猜测

$n \le 100000~~~~~~~~~~~~~~~1\le b \le n$

1.4 一句话概括题意

有一个排列，统计其中长度为奇数的子序列的中位数为 $b$ 的个数

2 题目破题推导

2.1 第一步：正向思维转逆向思维

我们记一个数列 $p$ ：

若 $a_i < b$ 则 $p_i\leftarrow -1$
若 $a_i > b$ 则 $p_i\leftarrow 1$
若 $a_i =b$ 则 $p_i\leftarrow 0$

那么只有奇数长度的序列和为 $0$ 时才能确保“长度为奇数的子序列中位数为 $b$ ”
接下来可能有些人会有疑问：

中位数的定义是中位数是指把所有元素从小到大排列后，位于中间的数。
万一这个子序列和是 $0$ 但是中间没有元素 $b$ 呢？
不会存在！
因为如果这个和是 $0$ 且长度为奇数，当且仅当含有一个 $0$ 和若干组 $1,-1$
其他情况要想让和是 $0$ ，只有可能含有若干组 $1,-1$ ，而这样 $2\times 任意数$ 一定是偶数，不满足题目中提到的“奇数长度子序列”

2.2 第二步：数学性质

如果从 $p_j(p[b]=j)$ 开始从左往右连续的序列总和为 $sum$ ，则为了让整个子序列总和为 $0$ 的同时满足“中位数”的要求，需要在左边选出一个序列，总和为 $-sum$
同时，右边可能有多个序列总和都为 $sum$ ，因此需要统计所有个数

3 模型匹配

用 $p$ 的时候要注意一下，不能有负数，加一个 $n$ 的偏移量

4 最终代码（禁止抄袭，仅用于参考）

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

int n, b;// b一定存在，且一定只存在一个
const int N = 111111;
int a[N];
int f[N * 2];

int main(){

    cin >> n >> b;
    int mid = -1;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
        if (a[i] < b){
            a[i] = -1;
        } else if (a[i] > b){
            a[i] = 1;
        } else {
            mid = i;
            a[i] = 0;
        }
    }
    int ans = 0;
    int sum = 0;
    for (int i = mid;i <= n;i++){
        sum += a[i];
        f[n + sum]++;
    }
    sum = 0;
    for (int i = mid;i >= 1;i--){
        sum += a[i];
        ans += f[n - sum];
    }
    cout << ans;
    
    return 0;
}