给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
第一行为两个正整数n和b，第二行为1~n的排列。
【数据规模】
对于30%的数据中，满足n≤100；
对于60%的数据中，满足n≤1000；
对于100%的数据中，满足n≤100000,1≤b≤n。
输出一个整数，即中位数为b的连续子序列个数。
7 4 5 7 2 4 3 1 6
4
因为这道题不关心数据具体为多少，只关心每个数比b大或小， 所以首先在读入的时候就忽视数据绝对大小，只存相对b的大小 （小于b存-1 等于b存0 大于b存1
O(n^2)： 枚举区间长度L和左端点i 利用前缀和可以O(1)得到区间和 易知区间和为0的话在这个区间内b为中位数 （证明：因为区间和为0 所以在这个区间内的-1数量和1的数量相等 也就是比b小的和比b大的数一样多）
期望60，却因为数据巨水搞到90(喵喵喵？)
本来打算卡一波常A掉然后发n方题解哈哈哈哈
90分代码：
#include<iostream> #include<cstdio> #include<cmath> using namespace std; inline int read() { char ch=getchar(); int x=0;bool s=1; while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return s?x:-x; } int a[100007]; int s[100007]; int main() { //scan int n,mid,p; n=read(),mid=read(); unsigned long long ans=0; for(int i=1;i<=n;++i) { int x=read(); if(x<mid)a[i]=-1; else if(x>mid)a[i]=1; else p=i; } for(int i=1;i<=n;++i) s[i]=s[i-1]+a[i]; //run for(int l=1;l<=n;l+=2) { int k=min(p,n-l+1); for(int i=max(1,p-l+1);i<=k;++i) { int j=i+l-1; if(s[j]-s[i-1]==0)ans++; } } cout<<ans<<endl; return 0; }AC做法：（先懵着脑袋看 后有讲解）
读入的同时记录b出现的坐标为p。从p-1到1扫一遍，从p+1到n扫一遍，用类计数排序的方式记录 ↓
int s=0; for(int i=p-1;i;--i){ s+=a[i]; L[s+c]++;//c=100001 避免负坐标 } s=0; for(int i=p+1;i<=n;++i){ s+=a[i]; R[s+c]++; }L[ s + c ]表所有左端点为1到p-1，右端点为p-1的区间中，区间和为s的情况数 同理R[ s + c ]表所有左端点为p+1，右端点为p+1到n的区间中，区间和为s的情况数
而对于一个区间< l , r >，如果< l , p-1 >的区间和 + < p+1 , r >的区间和==0的话，就是一个符合条件的区间。 所以根据乘法原理，L[ s + c ] × R[ ( - s ) + c ] == p左边的区间和为s时的所有可能情况（此时右边区间和为-s）所以
ans+=L[ s + c ] × R[ ( - s ) + c ] ( s = - n to n ) ;最后因为以上只计算了 l < p 且 r > p 的区间，所以还要
ans+=L[ 0 + c ] (l<p r==p) +R[0+c] (l==p r>p) +1(l==p r==p);AC代码：
#include<iostream> #include<cstdio> using namespace std; #define R register inline int read() { char ch=getchar(); int x=0;bool s=1; while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} return s?x:-x; } int a[100007],l[200007],r[200007]; int main() { //scan int n=read(),b=read(),p; for(R int i=1;i<=n;++i) { int x=read(); if(x<b)a[i]=-1; else if(x>b)a[i]=1; else p=i; } //predo int s=0,c=100001; for(R int i=p-1;i;--i) { s+=a[i]; l[s+c]++; } s=0; for(R int i=p+1;i<=n;++i) { s+=a[i]; r[s+c]++; } //run int ans=0; for(R int i=-n;i<=n;++i) { ans+=l[i+c]*r[-i+c]; } ans+=l[0+c]+r[0+c]+1; cout<<ans<<endl; return 0; }转载于:https://www.cnblogs.com/qwerta/p/9379754.html
相关资源：JAVA上百实例源码以及开源项目