洛谷 P1627 [CQOI2009]中位数 解题报告

P1627 [CQOI2009]中位数

题目描述

给出1~n的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后,位于中间的数。

输入输出格式

输入格式:

第一行为两个正整数n和b,第二行为1~n的排列。

【数据规模】

对于30%的数据中,满足n≤100;

对于60%的数据中,满足n≤1000;

对于100%的数据中,满足n≤100000,1≤b≤n。

输出格式:

输出一个整数,即中位数为b的连续子序列个数。


这个题其实并不是很难想。

转换一下模型,我们发现对于中位数,我们只关心某个数比b大还是小,并不关心它具体是几,所以我们可以这样描述这串序列。

把比b大的数置为1,比b小的数置为-1,把b置为0。

用前缀和数组\(f[i]\)存储

则满足

  1. \(f[i]==f[j]\)
  2. \(i,j\)奇偶性不同
  3. 区间\(i+1,j\)存在值\(b=0\)

    时,区间\([i+i,j]\)是满足条件的。

因为题目说是一个排列,所以只可能有一个b。

我们通过分奇偶存储值为\(f[k]\)的数的个数来描述。令\(cnt[0/1][i]\)代表位置为偶数(0)或奇数(1)的数\(i\)在\(b=0\)的左边的出现次数,则答案为\(\sum cnt[k\&1xor1][f[k]]\) ,\(k\)在\(b=0\)右边。

不过需要注意的是,因为\(f[i]\)可能为负,所以我们对每个\(f[i]\)加上\(n\)。我最开始没注意到居然还有90分


#include <cstdio>
const int N=100010;
int n,a,b,ans=0,f[N],cnt[2][N],flag=1;//1µ¥Î»0˫λ
int main()
{
scanf("%d%d",&n,&b);
cnt[0][n]=1;
f[0]=n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
if(a>b)
{
f[i]=f[i-1]+1;
if(flag) cnt[i&1][f[i]]++;
else ans+=cnt[(i&1)^1][f[i]];
}
else if(a<b)
{
f[i]=f[i-1]-1;
if(flag) cnt[i&1][f[i]]++;
else ans+=cnt[(i&1)^1][f[i]];
}
else
{
f[i]=f[i-1];
ans+=cnt[(i&1)^1][f[i]];
flag=0;
}
}
printf("%d\n",ans);
return 0;
}

2018.6.12

上一篇:洛谷 P2505 [HAOI2012]道路 解题报告


下一篇:洛谷 P2617 Dynamic Rankings 解题报告