中位数题解

先看题

很明显，题目想让我们

求出n个数中中位数为b的连续子序列个数

比如

输入：
5 4
1 2 3 4 5
输出：
2

注:没看懂题的现在还有机会！

则中位数为b的连续子序列有

1. 4
2. 3 4 5

所以答案为 2

你，听懂了吗？

管你听没听懂，看====就完了！

好了，来让我们看看标程（标准程序）

注释我写的，请好好看！

#include <iostream>//引用头文件
#define N 100005//不建议使用
using namespace std;//申请命名空间
long long n,b,ans,c[2][2*N];//定义
int main () {//主函数
    cin>>n>>b; c[0][n]=1;//输入
    for (long long i=0,a,s=n,isRight=0;i<n;i++){
        cin>>a;//输入n个数
        if (a!=b) s+=a>b?1:-1;//这句=if(a>b) s+=1;else s+=-1;
        c[isRight|=a==b][s]++;//位运算
    }
    for (long long i=0;i<2*n;i++,ans+=c[0][i]*c[1][i]);//算出个数
    cout<<ans<<endl;//输出
    return 0;//愉快的结束！
}

我相信你一定没看注释！

算了，再仔细讲一遍

先讲讲s+=a>b?1:-1

其实s+=a>b?1:-1就等同于

if(a>b) s+=1;else s+=-1;

这里用到的是位运算

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

基本的位运算共 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。

为了方便叙述，下文中省略“按位”。

与、或、异或

这三者都是两数间的运算，因此在这里一起讲解。

它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

运算	运算符	数学符号表示	解释
与	&	、	只有两个对应位都为 时才为
或	`		、
异或	^	、	只有两个对应位不同时才为

注意区分逻辑与（对应的数学符号为 ）和按位与、逻辑或（）和按位或的区别。网络中的资料中使用的符号多有不规范之处，以上下文为准。

异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 。