题解：P12600 连号子序列数

cff_0102 · 2025-05-25 02:28:52 · 题解

成功加入愚人节比赛出题组后，发现好像没有那种诈骗题，于是就出了一道。

考虑每个 1 到 N 之间的连续区间对答案产生多少贡献，不难发现对于每个连续区间，都可以在排列中找到唯一一个子序列与之对应，即贡献为 1。因此答案就是连续区间的数量，即 \frac{N(N+1)}2。

C++ 要开 long long。下面代码 AC 记录。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    long long n;cin>>n;
    cout<<n*(n+1)/2;
    return 0.102;
}

其实原本题目背景还有“，建议大家先做原题后再来挑战加强版”的，后来为了防止产生过多的误导删掉了。

btw，等题目上传到主题库之后才发现，很巧的是，本题题号和“原题”（P8600）题号刚好相差 4000。