bzoj 1303: [CQOI2009]中位数图 数学
1303: 中位数图Time Limit: 20 Sec Memory Limit: 256 MB题目连接
http://www.lydsy.com/JudgeOnline/problem.php?id=1303
Description
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
Input
第一行为两个正整数n和b ，第二行为1~n 的排列。
Output
输出一个整数，即中位数为b的连续子序列个数。
Sample Input
7 4
5 7 2 4 3 1 6
Sample Output
4
HINT
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000
题意
题解：
把大于b的置为1，把小于b的置为-1
然后左右都扫一遍，l表示左边和为i的个数，r表示右边和为i的个数
if(i+j==0)ans+=l*r
代码：
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 1000001
#define mod 10007
#define eps 1e-9
int Num;
char CH;
//const int inf=0x7fffffff; //нчоч╢С
const int inf=0x3f3f3f3f;
/*
inline void P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH+48);
puts("");
}
*/
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH+48);
puts("");
}
//**************************************************************************************
int num;
int sum;
int l,r;
int point;
int main()
{
int n,b;
scanf("%d%d",&n,&b);
for(int i=1;i<=n;i++)
{
scanf("%d",&num);
if(num==b)
point=i;
if(num>b)
num=1;
else if(num<b)
num=-1;
else
num=0;
}
l=1,r=1;
for(int i=point-1;i>=1;i--)
{
sum=sum+num;
l+n]++;
}
for(int i=point+1;i<=n;i++)
{
sum=sum+num;
r+n]++;
}
int ans=0;
for(int i=0;i<=2*n;i++)
{
ans+=l*r;
}
cout<<ans<<endl;
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15303184/3111132
页:
[1]