代码源div2每日一题

1001：数数（codeforces 1550c）题解

题目描述

对于平面上的两个点 P(x0,y0)，Q(x1,y1)，两点之间的曼哈顿距离为 d(P,Q)=|x0−x1|+|y0−y1|。

定义一组点 p,q,r 为坏的当且仅当 d(p,r)=d(p,q)+d(q,r)。

定义一个序列 a 是好的，当且仅当从 a 中无法选出一组互不相同的数 i,j,k，使得 (ai,i),(aj,j),(ak,k) 是坏的。

给定了一个长度为 n 的序列 a，请问 a 中有多少个子段是好的。

输入描述

第一行给出一个 T (1≤T≤5000)，表示有 T 组数据

接下来对于每一组数据：

第一行给出一个数 n (1≤n≤2∗105)，表示 a 的长度

第二行给出序列 a1，a2，… an (0≤ai≤109)

输出描述

输出一个数表示 a 中好子段的个数
样例输入
3
4
2 4 1 3
5
6 9 1 9 6
2
13 37
样例输出
10
12
3

输出解释

第一个样例没有一个子段是坏的，所以 ans=4+3+2+1=10 第二个样例中，1,2,4 是坏的，因为

d((a1,1),(a4,4))=|6−9|+|1−4|=6 d((a1,1),(a2,2))=|6−9|+|1−2|=4
d((a2,2),(a4,4))=|9−9|+|2−4|=2 所以
d((a1,1),(a4,4))=d((a1,1),(a2,2))+d((a2,2),(a4,4))

题目原链

代码源链接: link (目前代码源貌似寄了）
codeforces链接:[https://codeforces.com/contest/1550/problem/C]

下面作出（ai,i),(aj,j),(ak,k)的位置图，这里为方便观看，是以常规x轴方向表示下标，y轴方向表示a(下标)

很显然，i,j,k下标所构成的点要是坏的必须要满足以下条件，即满足i，j，k单调，同时，ai,aj,ak保持单调。

知道了这点就很简单了，题目所求的是好的子段（子串）的个数,
这里我们可以知道，如果一个子段包含了一个能构成坏段的i,j,k，
那么这个段不是好段，也就是说，只要我们找到哪些下标所构成的点会形成上述的单调关系，把它排除掉就好，但是怎么找到这种坏段呢？
答案很简单，其实，单调的这种情况在子段长度为5时必定会出现。
这里我们举个例子,a[] = 9 8 12 11 x，我们只看这5个值的前4个，很明显，9 8 12 11这四个数并不能选出3个下标，在下标是单调的情况还要使得其a值单调，但是当我们选择第5个数时，因为从4个数中选两个数，肯定也是可以选出可以构成单调或不完全单调的，这是很显然的，当第5个选择时，要么前面4个就已经可以构成坏段了，要么就是第5个和前面四个中的两个构成坏段，因为前面四个不构成坏段只有两个一组的时候是单调减（增），每组之间又是单调增（减），这样你下标倒着选或者正着选，总会有选3个数能构成单调，故当子段长度为5时，必定不可能为好段。
而长度为1或者2的子段在题目中被定义为是满足条件的好段，故也不需要讨论
也就是说我们仅仅需要讨论长度为3或者4的子段的好坏情况即可，把所有好段枚举起来求和，便可以得到我们需要的答案，复杂度O(n),满足条件。这里给出代码：

void solve(){       
    ans=0;
    n=rd();vector<int>a(n+1);
    rep(i,1,n) a[i]=rd();
    ans+=n+n-1;//长度为1、2的子段个数
    auto check=[&](int i,int j,int k){
        if(a[i]>=a[j]&&a[j]>=a[k]) return 0;
        if(a[i]<=a[j]&&a[j]<=a[k]) return 0;
        return 1;
    };
    rep(i,1,n-2){
        if(check(i,i+1,i+2)){
            ans++;
        }
    }
    rep(i,1,n-3){
        if(check(i,i+1,i+2)&&check(i,i+1,i+3)&&check(i,i+2,i+3)&&check(i+1,i+2,i+3)) ans++;
    }
    printf("%lld\n",ans);
}

一个还不错的题，考验了做题人的题目转化和对数据的分析能力，以上

最后，感谢浏览！觉得不错可以点个赞！