SCUT校赛129：笔芯值（数学）

93 阅读 0 评论 62 点赞

我是靠谱客的博主苗条大象，最近开发中收集的这篇文章主要介绍SCUT校赛129：笔芯值（数学），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

对于一个 $n$ 个数的序列 $a_1,a_2,cdots,a_n$ ，从小到大排序之后为 $a_{p_1},a_{p_2},cdots,a_{p_n}$ ，定义它的 $b x$ 值为满足 $a_{p_i} neq a_{p_{i-1}}+1, 1 < i leq n$ 的 $i$ 的个数。

给定 $n$ 个数的一个排列，你需要计算它所有连续子序列的 $b x$ 值之和。

输入格式

输入第一行包括一个正整数 $T$ ，表示数据组数。
对于每组数据，第一行一个整数 $n$ ，第二行 $n$ 个整数，表示 $n$ 个数的一个排列。
$1 \leq T \leq 20$
$1 \leq n \leq 100000$
$a_i leq n$

输出格式

对每组数据输出一个整数表示答案。

样例数据

输入

输出

0
5

思路：先计算n个数总的bx值，连续子序列长度为x对答案做出的贡献为(n-(x-1))*(x-1)，再减去非法的个数。具体做法就是对这n个数的下标排序，连在一起的下标就是非法的，比如a[3] = 7，a[6] = 8，那么包含下标3和6的连续子序列都需要减去1，那么这样的序列有3*(n-6+1)个。

# include <bits/stdc++.h>
# define ll long long

using namespace std;
const int maxn = 1e5;
ll a[maxn+3];
int c[maxn+3];
int main()
{
    int t, n;
    scanf("%d",&t);
    while(t--)
    {
        ll ans = 0;
        scanf("%d",&n);
        for(int i=1; i<=n; ++i)
        {
            scanf("%d",&a[i]);
            c[a[i]] = i;
            ans += (ll)(n-i+1)*(i-1);
        }
        for(int i=1; i<n; ++i)
        {
            int l = c[i], r = c[i+1];
            if(l > r) swap(l, r);
            ans -= (ll)l*(n-r+1);
        }
        printf("%lldn",ans);
    }
    return 0;
}