1,有一个连起来的项链，每个珠子都有一种颜色(所有颜色共有m种)，珠子共有n个，需要给出一个最小的长度l，从某个位置开始连续l个，包含了所有的m种颜色。
从任意位置断开后变成链，处理时最后求余在化为圆形。
最简单的方法枚举，但是需要O(n3)
因此考虑.
color[x],为地x个珠子的颜色。
若记s(j,i)为起点为j,长度为i的颜色集合。
ans[j][i]为从j长度为i的颜色个数。
idx=j+i-1>n ? i+j-1%n+1;i+j-1;
若color[idx] not in s(j,idx-1);
ans[j][idx]=ans[j][idx-1]+1;
s[j][idx]=s[j][idx-1]
s[j][idx] push color[j]
否则
ans[j][idx]=ans[j][idx-1];
s[j][idx]=s[j][idx-1]
此时复杂度接近时间O(n2)，空间O(n2),如果用set类则空间复杂度为O(n2longn),难以承受。
此时需要使用BitSet.
32位下无符号有32位可用，每一个数对应一个零一，此时可以用一个数来表示集合。
长度为n的全部元素集合为(1<<n)-1,注意<<预算符优先级低。
8就代表
00000000......1000这个集合。
如下为具体实现:
#include <iostream>
#include <cmath>
#define maxn 11
using namespace std;
class BitSet{
public:
BitSet(){
base = n = 1;
all = (base<<n) - 1;
set_null();
}
BitSet(int nx){
base = 1;
n = nx;
all = (base<<n) - 1;
set_null();
}
bool exsist(int i){
return (bitmap >> (i-1)) & base;
}
void print_bitmap(){
int i;
unsigned long long tmp = bitmap;
for(i=0;i<n;i++){
cout << (tmp & 1) ;
tmp = tmp >> 1 ;
}
cout << endl;
}
void set_all(){
bitmap = (base<<n) - 1;
}
void set_null(){
bitmap = 0;
}
void set_add(int i){
bitmap = (bitmap | (base<<(i-1)));
}
void set_del(int i){
bitmap = (bitmap) & (all- (base<<(i-1)));
}
void set_union(BitSet bs){
bitmap = ((bitmap) | (bs.get_bitmap()));
}
void set_join(BitSet bs){
bitmap = ((bitmap) & (bs.get_bitmap()));
}
unsigned long long get_bitmap(){
return bitmap;
}
private :
unsigned long long bitmap,base,all;
int n;
};
int ansmin=maxn+1;
int ans[maxn][maxn]={0};
BitSet bss[maxn][maxn];
int color[maxn*maxn+1];
int main(){
int i,j,n,m=10;
for(cin>>n ,i=1 ; i<=n; i++){
cin>> color[i];
}
BitSet bs = BitSet(10);
for(i=1;i<=n;i++){
bss[i][1]=BitSet(10);
bss[i][i].set_add(color[i]);
ans[i][i]=1;
}
for(i=2;i<=n;i++){
for(j=1;j<=n;j++){
int idx=j+i-1 > n ? (j+i-1)%n+1 : j+i-1;
bss[j][idx]= BitSet(10);
bss[j][idx]=bss[j][idx-1];
ans[j][idx]=ans[j][idx-1];
if(bss[j][idx].exsist(color[idx])==0){
bss[j][idx].set_add(color[idx]);
ans[j][idx]++;
if(ans[j][idx]==m){
ansmin = min(ansmin,i);
}
}
}
}
cout << ansmin << endl;
return 0;
}