C Manhattan Subarrays 思维

阳光穿透心脏的1/2处 2022-08-28 11:54 107阅读 0赞

题目地址:[C Manhattan Subarrays][]  
**题意**：定义一种操作， d ( p , q ) = a b s ( x p − x q ) + a b s ( y p − y q ) . d(p,q)=abs(x\_p-x\_q)+abs(y\_p-y\_q). d(p,q)=abs(xp−xq)\+abs(yp−yq).  
给你三个点，p,q,r如果 d ( p , r ) = d ( p , q ) + d ( q , r ) d(p,r)=d(p,q)+d(q,r) d(p,r)=d(p,q)\+d(q,r)那就说明这三个点是坏的。  
给你一个序列，每个点都是 ( b i , i ) (b\_i,i) (bi,i)，让你判断有这个序列有多少好的子序列。长度为1和长度为2的都是好序列。

**思路**：假设我们取得三个点是 ( a i , i ) , ( a j , j ) , ( a k , k ) (a\_i,i),(a\_j,j),(a\_k,k) (ai,i),(aj,j),(ak,k)假设他们满足d(k,i)=d(i,j)+d(j,k)，然后我们会得到两个公式  
 d ( k , i ) = ∣ a k − a i ∣ + ∣ k − i ∣ d(k,i)=|a\_k-a\_i|+|k-i| d(k,i)=∣ak−ai∣\+∣k−i∣  
 d ( i , j ) + d ( j , k ) = ∣ a i − a j ∣ + ∣ i − j ∣ + ∣ a j − a k ∣ + ∣ j − k ∣ d(i,j)+d(j,k)=|a\_i-a\_j|+|i-j|+|a\_j-a\_k|+|j-k| d(i,j)\+d(j,k)=∣ai−aj∣\+∣i−j∣\+∣aj−ak∣\+∣j−k∣  
仔细观察这两个公式，我们发现当i<j<k时，同时 a i ≤ a j ≤ a k a\_i\\leq a\_j\\leq a\_k ai≤aj≤ak或者是 a i ≥ a j ≥ a k a\_i\\geq a\_j\\geq a\_k ai≥aj≥ak的时候去掉绝对值后d(k,i)和d(i,j)+d(j,k)的值是一样的，也就是在这个时候包含这三个点的序列是一个坏序列。  
由此我们可以知道如果一个序列有5个元素一定能找到三个点满足上列条件，于是我们只需要遍历长度为3和长度为4的子串就可以了。  
AC代码：

/* **https://codeforces.com/contest/1550/problem/C */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 2e5+5;
    int a[N];
    bool judge(int x, int y,int z)
    { 
        if((x>=y&&y>=z)||(x<=y&&y<=z))
        { 
            return true;
        }
        else return false;
    }
    void solve()
    { 
        int n;
        scanf("%d",&n);
        ll ans = 2*n-1;
        for(int i = 0;i < n;i++)
        { 
            scanf("%d",&a[i]);
        }
        if(n >= 3)
        { 
            for(int i = 0;i < n-2;i++)
            { 
                if(judge(a[i],a[i+1],a[i+2]));
                else ans++;
            }
        }
        if(n >= 4)
        { 
            for(int i = 0;i < n-3;i++)
            { 
                if(judge(a[i],a[i+1],a[i+2])||judge(a[i],a[i+2],a[i+3])
                   ||judge(a[i],a[i+1],a[i+3])||judge(a[i+1],a[i+2],a[i+3]));
                else
                    ans++;
            }
        }
        printf("%d\n",ans);
    }
    
    int main()
    { 
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

[C Manhattan Subarrays]: https://codeforces.com/contest/1550/problem/D