题意：

N头牛，一共K种特色。每头牛有多种特色。[i,j]段被称为balanced当且仅当K种特色在[i,j]内拥有次数相同。求最大的[i,j]段长度。n≤100000，k≤30。

题解：

得到式子：a[i][l]-a[j][l]=a[i][l-1]-a[j][l-1],l在2..k之间，移项得a[i][l]-a[i][l-1]=a[j][l]-a[j][l-1],l在2..k之间，故可以定义一个结构体，里面包含所有的a[i][l]-a[i][l-1],l在2..k之间，然后用set查找满足所有元素相等的最小j即可。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 100010 7 using namespace std; 8  9 inline int read(){10     char ch=getchar(); int f=1,x=0;11     while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1; ch=getchar();}12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();13     return f*x;14 }15 int sum[maxn][50],n,k,ans;16 struct nd{17     int id; int num[50];18     bool operator < (const nd &a)const{inc(i,1,k-1)if(num[i]!=a.num[i])return num[i]
         
          st; nd a;21 int main(){22     n=read(); k=read();23     inc(i,1,n){24         int x=read(); inc(j,1,k)sum[i][j]=sum[i-1][j]; for(int j=k-1;j>=0;j--)if(x&(1<
          
           ::iterator sti=st.find(a); if(sti==st.end())st.insert(a);else{30 ans=max(ans,i-sti->id);31 }32 }33 printf("%d",ans); return 0;34 }
          
         
        
       
      
     

 

20160929