题目链接：hdu 4908 BestCoder Sequence

题目大意：给定N和M，N为序列的长度，由1~N组成，求有多少连续的子序列以M为中位数，长度为奇数。

解题思路：v[i]记录的是从1~i这些位置上有多少个数大于M，i-v[i]就是小于M的个数。pos为M在序列中的位置。如果有等式i?j=2?(v[i]?v[j?1]),i≥pos≥j

那么i和j既是一组满足的情况。将等式变形i?2?v[i]=j?2?v[j?1].

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 40000; int N, M, pos, v[maxn+5], c[2][maxn*2+5]; void init () { int a; v[0] = 0; for (int i = 1; i <= N; i++) { v[i] = v[i-1]; scanf("%d", &a); if (a > M) v[i]++; if (a == M) pos = i; } } int solve () { memset(c, 0, sizeof(c)); for (int i = 1; i <= pos; i++) { int tmp = i - 2 * v[i-1]; c[0][tmp + maxn]++; } for (int i = pos; i <= N; i++) { int tmp = i - 2 * v[i]; c[1][tmp + maxn]++; } int ans = 0; for (int i = 0; i <= maxn*2; i++) ans += c[0][i] * c[1][i]; return ans; } int main () { while (scanf("%d%d", &N, &M) == 2) { init(); printf("%d\n", solve()); } return 0; }