3274.cpp

acm pku 3274题目算法 有源代码

#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct Node { int s[30]; };
 
const int N = 100010;
int n, K;
Node a[N];
map<Node, int> mym;
vector<int> l[N];
 
 bool operator<(const Node& a, const Node& b) {
  int i;
  for(i = 0; i < K; ++i) 
   if(a.s[i] != b.s[i])
    return a.s[i] < b.s[i];
 return false;
 }
 
 int main() {
  scanf("%d %d", &n, &K);
  int i, t, j, k;
  for(j = 0; j < K; ++j)
   a[0].s[j] = 0;
  for(i = 1; i <= n; ++i) 
  {
   scanf("%d", &t);
   for(j = 0; j < K; ++j, t >>= 1)
    a[i].s[j] = a[i-1].s[j] + (t % 2);
   for(j = 1; j < K; ++j)
    a[i].s[j] -= a[i].s[0];
   a[i].s[0] = 0;
 }
 
   j = 0;
  for(i = 0; i <= n; ++i)
  {
   if(mym.find(a[i]) == mym.end()) 
    mym[a[i]] = j++;
  l[mym[a[i]]].push_back(i);
  }

  int res = 0;
  for(i = 0; i < j; ++i) 
  {
   int min = 123456789, max = -1;
   for(k = 0; k < l[i].size(); ++k) {
   if(l[i][k] > max) max = l[i][k];
   if(l[i][k] < min) min = l[i][k];
   }
  if(max - min > res) res = max - min;
 }
 
printf("%d\n", res);
 
  return 0;
 }