Educational Codeforces Round 111 (Rated for Div. 2) C. Manhattan Subarrays
若想有三点满足这条公式 ,假设
已知两点的坐标,若想使
点坐标 满足上述公式这一点
需要落在 以
为对角线的矩形上
因为题目的限制,所以一个序列是否是好序列,相当于取寻找这个序列的最长(不降 / 不升)子序列是否大于等于3,如果大于等于3,那么就是坏序列,还存在这样一个性质这个好序列的长度最长只有4.
证明:我们构造一个组长度为4的好序列,首先这个数不能比(最大的大 比 最小的小 ) 这点显而易见,对于在除最大最小的两个数,剩下的数的其中 一个数 ,我们所构造的这个数那么比他大要么比他小 比他大 它和最小值就组成不降序列,同样比他小 它和最大值就组成 不升序列, 那么题目的答案就是 以序列中每个元素开头,看他先后能形成最长的连续序列有多长,那么加上它的贡献,就是最后的答案
#include<cstdio> #include<cstdlib> #include<algorithm> #define NUM 200010 #define LL long long using namespace std; int n,arr[NUM]; LL ans =0; bool check(int *p ,int l,int r){ int le = r-l+1; if (le <=2) return true; for (int i =l;i<=r;i++){ for (int j =i+1;j<=r;j++){ for (int k=j+1;k<=r;k++){ if ((p[i]<=p[j] && p[j] <= p[k]) || (p[i]>=p[j] && p[j]>=p[k]) ) return false; } } } return true; } void sovle () { ans = 0; scanf("%d",&n); for (int i =0;i<n;i++){ scanf("%d",&arr[i]); } for (int i=0;i<n;i++){ int tq =1; for (int q=0,j =i-1;j>=max(0,i-3);j--){ if (check(arr,j,i)) tq++; else break; } // int tp = 1; // for (int p=0, j =i-1;j>=0;j--){ // if (arr[j]<=arr[j+1]) p++; // //else break; // if (p>=2) break; // tp++; // } ans += tq; } printf("%lld\n",ans); return ; } int main () { int t; scanf("%d",&t); while (t--){ sovle(); } return 0; }