k个代表

74 阅读 0 评论 49 点赞

我是靠谱客的博主热心小笼包，最近开发中收集的这篇文章主要介绍k个代表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

k个代表是一个我原创的黑科技(其实说不定其他人也有类似做法) 取这个名字是为了【政治敏感】

我感觉k个代表的含义更贴近于“面向数据动态分类，答案一定在某类中”

1 入门

我们来看一个最简单的例子

（强行被称为k个代表）

有n个正整数 a₁-a_n你要求出对a_i(1<=i<=n)最大的 a_k 使得 a_k!=a_i没有输出-1 n=1e6

我们可以顺着扫一遍维护2个数分别是x,y x表示当前最大的数 y表示当前不同于x的最大的数初始x=y=-1

若a_i==x 输出y 否则输出x

 1 using namespace std;
 2 int n,a[1000005],x=-1,y=-1;
 3 int main(){
 4     scanf("%d",&n);
 5     for(int i=1;i<=n;++i){
 6         scanf("%d",a+i); 
 7         if(a[i]>x)y=x,x=a[i];
 8         else if(a[i]>y)y=a[i];
 9         if(a[i]==x)printf("%dn",y);
10         else printf("%dn",x);
11     }
12     return 0;
13 }

View Code

下面我们看一些正常一点的例子

2 静态k个代表

我称对每种代表只有一次写入没有修改的k个代表为静态k个代表

我们来看一个优秀的静态k个代表的例子

题目：http://acm.nflsoj.com/problem/72

给出一个只包含大写字母B，C，S的字符串，请找到最长的子串，要求这个子串满足以下两个条件中的一个：

该子串中B的出现次数不等于C的出现次数，C的出现次数不等于S的出现次数，S的出现次数不等于B的出现次数。
该子串只包含一种字符。

数据范围 1<=n<=1e6

std写的是树状数组 O(nlogn) 这种做法的题解：http://acm.nflsoj.com/blog/youyl/blog/100

我用了一种O(n)的做法：10个代表

全相等那种情况略

对于S(i,0)-S(i,1)=x_i,S(i,1)-S(i,2)=y_i,S(i,2)-S(i,0)=z_i

我们有：(j,i]可行<==>x_i!=x_j,y_i!=y_j,z_i!=z_j

所以我们对每个i,找到最小的j，0<=j< i, x_i!=x_j, y_i!=y_j, z_i!=z_j, 然后用i-j更新答案即可

对于x_i!=0,y_i!=0,z_i!=0,j=0

对于x_iy_iz_i恰好2个等于0，不可能，因为x+y+z=0

对于x_iy_iz_i恰好1个等于0

考虑x=0的情况

我们需要维护3个代表即可：

第一个:最小的p使x_p!=0

对于y_p=y的情况，我们知道了这组为(0,y_p,-y_p),对这一组找一个最小代表即可

对于z_p=z的情况，我们知道了这组为(0,-z_p,z_p),对这一组找一个最小代表即可

y=0,z=0情况同x=0

对x=0,y=0,z=0 找一个代表即可

一共是10个代表

 1 #define X  first
 2 #define Y  second
 3 using namespace std;
 4 int s[1000005][3],n,ans=1,l[3];
 5 int f[10],X[10],Y[10],Z[10];
 6 void upd(int k){if(k>ans)ans=k;}
 7 int main(){
 8     scanf("%d",&n),getchar();
 9     for(int i=1;i<=n;++i){
10         char c=getchar();
11         s[i][0]=s[i-1][0],s[i][1]=s[i-1][1],s[i][2]=s[i-1][2];
12         int k=(c>'C')+(c>'B');
13         ++s[i][k];
14         if(l[k])upd(i-l[k]+1);
15         else l[0]=l[1]=l[2]=0,l[k]=i;
16     }
17     for(int i=1;i<=n;++i){
18         int x=s[i][0]-s[i][1],y=s[i][1]-s[i][2],z=s[i][2]-s[i][0];
19         int k=0;
20         if(x){
21             k^=1;
22             if(!f[1])f[1]=i,X[1]=x,Y[1]=y,Z[1]=z;
23             else{
24                 if(!f[2]&&Y[1]!=y&&-Y[1]!=z)f[2]=i,X[2]=x,Y[2]=y,Z[2]=z;
25                 if(!f[3]&&-Z[1]!=y&&Z[1]!=z)f[3]=i,X[3]=x,Y[3]=y,Z[3]=z;
26             }
27         }
28         if(y){
29             k^=2;
30             if(!f[4])f[4]=i,X[4]=x,Y[4]=y,Z[4]=z;
31             else{
32                 if(!f[5]&&X[4]!=x&&-X[4]!=z)f[5]=i,X[5]=x,Y[5]=y,Z[5]=z;
33                 if(!f[6]&&-Z[4]!=x&&Z[4]!=z)f[6]=i,X[6]=x,Y[6]=y,Z[6]=z;
34             }
35         }
36         if(z){
37             k^=4;
38             if(!f[7])f[7]=i,X[7]=x,Y[7]=y,Z[7]=z;
39             else{
40                 if(!f[8]&&X[7]!=x&&-X[7]!=y)f[8]=i,X[8]=x,Y[8]=y,Z[8]=z;
41                 if(!f[9]&&-Y[7]!=x&&Y[7]!=y)f[9]=i,X[9]=x,Y[9]=y,Z[9]=z;
42             }
43         }
44         if(!k){
45             if(f[0])upd(i-f[0]);
46             continue;
47         }
48         if(k==7){
49             if(!f[0])f[0]=i;
50             upd(i);
51             continue;
52         }
53         if(!x){
54             if(!f[1]) continue;
55             if(Y[1]==y){if(f[2])upd(i-f[2]);}
56             else if(Z[1]==z){if(f[3])upd(i-f[3]);}
57             else upd(i-f[1]);
58             continue;
59         } 
60         if(!y){
61             if(!f[4]) continue;
62             if(X[4]==x){if(f[5])upd(i-f[5]);}
63             else if(Z[4]==z){if(f[6])upd(i-f[6]);}
64             else upd(i-f[4]);
65             continue;
66         } 
67         if(!z){
68             if(!f[7]) continue;
69             if(X[7]==x){if(f[8])upd(i-f[8]);}
70             else if(Y[7]==y){if(f[9])upd(i-f[9]);}
71             else upd(i-f[7]);
72         }    
73     }
74     printf("%dn",ans);
75     return 0;
76 }

View Code

用时是std的10分之一而且非常好写（你要学会复制粘贴）

再看一个例子

线性基其实也是一种静态k个代表（真不要脸）

这里不介绍自行搜索

当然下文会给出功能更加强大的线性基

3 动态k个代表

我们来看一个例子

(这里假设你已经会了线性基)

题目来源whzzt模拟赛

蒜头是一位优秀的 OI 选手。
自古以来，迷人的星空总是吸引着许多天文学的爱好者。顺着星星的指引，明天的蒜头将会遇到一道
有趣的题，和蒜头曾经出过的一道题一样有趣。
给一个长度为 n 的序列 a，q 次询问在 a[l...r] 中选择若干个数 (可以不选) 和 d 异或所能得到的最
大值。

数据范围1<=n,q<=1e6,1<=a_i<2^30

我们发现线性基是静态的太浪费了

于是想到可以动态改变那30个代表我们尽量找比较新的

我们插入数的时候到某一位时若比原代表更新就把它替换掉拿原代表向下插

类似冒泡排序

因为只有老数被新数异或所以正确性显然

这题std和我做法一样所以再贴一下whzzt的题解

“时间复杂度瓶颈在于我们要表示出 O(loga) 个线性基。

考虑我们之前维护端点的过程，那么后 i 个端点实际上就是一个

大小为 i 的线性无关组。

容易发现，我们将位置在前面的数异或位置在后面的数，并不会

对我们的答案产生影响。所以实际上我们仍然可以维护线性基，

并且只需维护 1 个。

实现上来说，只要同时存在两个最高位相同的数时，用前面的异

或后面的即可。

时间复杂度 O((n + q)loga) 。”

 1 #define pb   push_back
 2 using namespace std;
 3 int n,q,a[1000005],f[31],l[1000005],r[1000005],d[1000005];
 4 vector<int> v[1000005];
 5 int main(){
 6     scanf("%d",&n);
 7     for(int i=1;i<=n;++i)scanf("%d",a+i);
 8     scanf("%d",&q);
 9     for(int i=1;i<=q;++i)scanf("%d%d%d",l+i,r+i,d+i),v[r[i]].pb(i);
10     for(int i=1;i<=n;++i){
11         int k=i;
12         for(int j=29;j>=0;--j){
13             if((a[k]&(1<<j))){
14                 if(k>f[j])a[f[j]]^=a[k],swap(f[j],k);
15                 else a[k]^=a[f[j]];
16             }
17         }
18         for(int j=0;j<v[i].size();++j){
19             int o=v[i][j];
20             for(int k=29;k>=0;--k)if(l[o]<=f[k]&&!(d[o]&(1<<k)))d[o]^=a[f[k]];
21         }
22     }
23     for(int i=1;i<=q;++i)printf("%dn",d[i]);  
24     return 0;
25 }

View Code

4 一种代替做法

有的时候我们实在想不出怎么划分k个代表这时有一个多一个log但是好想好实现的划分方法可以解决部分问题

（通常来说这类问题其实都有O(1)划分方法）

我们发现x!=y <==>存在k使得(x&(1<<k))!=(y&(1<<k))

于是划分方法为：第2k+1个代表是(x&(1<<k))==0集合中选出的代表第2k+2个代表是(x&(1<<k))==(1<<k)集合中选出的代表

5 拓展

其实某个代表不一定是一个数可能是一个集合或者别的什么东西

暂时没有好的例子所以没有写在这里

===upd

加了一道我出的非常难的k个代表题目

https://acm.nflsoj.com/problem/379

（idea和solution来自我，题面及时空范围来自lqs2015）

如果因为权限看不到题面可以看这个：

（markdown格式，懒得改了）

2000ms 256MiB

###题目描述

众所周知，蒟蒻总是崇拜神犇。在 NFLS 里，有 $n$ 个蒟蒻，编号为 $1,2,cdots,n$。lqs 是其中的一员。他们每个人都有**一个**崇拜的神犇，每个人崇拜的神犇都是**FizzyDavid, Ohweonfire, diamond_duke**中的一个。编号为 $i$ 个蒟蒻对他崇拜的神犇的崇拜度为 $A_i$。

wzy 是 NFLS 的另外一位神犇，他也希望有蒟蒻来崇拜他。现在 wzy 想要选择编号为一个区间的蒟蒻，使得他们崇拜他。对于编号为 $[l,r]$ 的蒟蒻来说，如果存在两个神犇，崇拜他们的蒟蒻个数相同（可能为 $0$），那么这个区间的不平衡度为 $0$。否则这个区间的不平衡度为这个区间中所有蒟蒻对他们崇拜的神犇的崇拜度的异或和，即 $A_l oplus A_{l+1} oplus cdots oplus A_r$，其中 $oplus$ 是异或操作。

现在 wzy 想知道对于所有的 $x(1 le x le n)$，以 $x$ 为右端点的区间的不平衡度的最大值，因为不平衡度越大，wzy 越好下手。神犇总是日理万机，所以他没时间做这个。因为你是 wzy 的粉丝，所以他把这个任务交给了你。

由于一些原因，你可能需要顺序回答问题，具体请见输入格式。

###输入格式

第一行两个整数 $n,opt$，表示蒟蒻的个数，若 $opt=0$，则不强制在线，否则表示强制在线。如果 $opt=2$ 则表示一种特殊的部分分，请见“约束”。

第二行有 $n$ 个数字，第 $i$ 个数字是 $0,1,2$。表示第 $i$ 个蒟蒻崇拜的神犇，$0$ 表示 **FizzyDavid**，$1$ 表示**Ohweonfire**，$2$ 表示**diamond_duke**.

如果 $opt neq 0$，记上面这 $n$ 个数的序列为 $p_1,p_2,cdots,p_n$，那么真实的数字 $=(lastans oplus p_i) mod 3$，否则输入的 $p_i$ 就是真实的数字。

第三行为 $n$ 个数 $A_1,A_2,cdots,A_n$。其意义如题。

如果 $opt neq 0$，那么真实的数字 $=lastans oplus A_i$，否则输入的 $A_i$ 就是真实的数字，其中，$lastans$ 是上一次计算的结果，初始时为 $0$。

###输出格式

输出共一行，有 $n$ 个数，第 $i$ 个数表示以 $i$ 为右端点的区间的不平衡度的最大值。

###样例输入 1

```

8 0

0 1 2 2 1 1 0 0

2 3 7 1 4 5 3 2

```

###样例输出 1

```

0 0 0 5 2 6 7 4

```

###样例解释 1

下面是每个位置为右端点取到的最大值区间：

$[1,1]$（此时由于膜另外两位神犇的都是0人，因此答案为0）,

$[2,2]$（原因同上）,

$[3,3]$（原因同上）,

$[2,4]$,

$[3,5]$,

$[1,6]$,

$[2,7]$,

$[6,8]$.

###样例输入 2

```

10 0

0 0 0 0 0 0 0 0 0 0

1 2 4 8 16 32 64 128 256 512

```

###样例输出 2

```

0 0 0 0 0 0 0 0 0 0

```

###样例解释 2

**FizzyDavid**粉丝群，由于一直没人膜另外两个神犇，因此答案都为 $0$。

###数据范围与约定

对于 $100%$ 的数据 $n le 300000,A_i le 10^9$。

* $subtask1(20pts)：n le 2000$

* $subtask2(20pts)：$保证解密之后，所有人只膜 **FizzyDavid** 和 **Ohweonfire**，为了方便选手判断这一档部分分，$subtask2$ 的所有数据中 $opt=2$。

* $subtask3(20pts)：opt=0$

* $subtask4(20pts)：n le 10 ^ 5$

* $subtask5(20pts)：$无特殊限制

我有时间了放上解答但是先提供std

  1 //Relive your past life.
  2 //Face your demons.
  3 //The past is never dead,it is not even past.
  4 //The memories are not only the key to the past but...also to the future.
  5 //coded in Rusty Lake
  6 #include<cmath>
  7 #include<math.h>
  8 #include<ctype.h>
  9 #include<algorithm>
 10 #include<bitset>
 11 #include<cassert>
 12 #include<cctype>
 13 #include<cerrno>
 14 #include<cfloat>
 15 #include<ciso646>
 16 #include<climits>
 17 #include<clocale>
 18 #include<complex>
 19 #include<csetjmp>
 20 #include<csignal>
 21 #include<cstdarg>
 22 #include<cstddef>
 23 #include<cstdio>
 24 #include<cstdlib>
 25 #include<cstring>
 26 #include<ctime>
 27 #include<cwchar>
 28 #include<cwctype>
 29 #include<deque>
 30 #include<exception>
 31 #include<fstream>
 32 #include<functional>
 33 #include<iomanip>
 34 #include<ios>
 35 #include<iosfwd>
 36 #include<iostream>
 37 #include<istream>
 38 #include<iterator>
 39 #include<limits>
 40 #include<list>
 41 #include<locale>
 42 #include<map>
 43 #include<memory>
 44 #include<new>
 45 #include<numeric>
 46 #include<ostream>
 47 #include<queue>
 48 #include<set>
 49 #include<sstream>
 50 #include<stack>
 51 #include<stdexcept>
 52 #include<streambuf>
 53 #include<string>
 54 #include<typeinfo>
 55 #include<utility>
 56 #include<valarray>
 57 #include<vector>
 58 #include<string.h>
 59 #include<stdlib.h>
 60 #include<stdio.h>
 61 #define ll   long long
 62 #define pb   push_back
 63 #define mp   make_pair
 64 #define orz  1000000007
 65 using namespace std;
 66 int n,opt,x,y,z,a,ans,T[300005],A[300005];
 67 int l[4000005],r[4000005],f[4000005][9],cnt;
 68 bool b[4000005][9],__=1;
 69 bool chk(int k){
 70     if(x!=f[k][0]&&y!=f[k][1]&&z!=f[k][2]) return 1;
 71     if(x==f[k][0]){
 72         if(!b[k][0]) return 0;
 73         if(y!=f[k][3]&&z!=f[k][4]) return 1;
 74         return y==f[k][3]?b[k][1]:b[k][2];
 75     }
 76     if(y==f[k][1]){
 77         if(!b[k][3]) return 0;
 78         if(x!=f[k][5]&&z!=f[k][6]) return 1;
 79         return x==f[k][5]?b[k][4]:b[k][5];
 80     }
 81     if(!b[k][6]) return 0;
 82     if(x!=f[k][7]&&y!=f[k][8]) return 1;
 83     return x==f[k][7]?b[k][7]:b[k][8];
 84 }
 85 void upd(int k){
 86     if(__){
 87         f[k][0]=x,f[k][1]=y,f[k][2]=z;
 88         __=0;
 89         return;
 90     }
 91     if(x!=f[k][0]){
 92         if(!b[k][0])b[k][0]=1,f[k][3]=y,f[k][4]=z;
 93         else{
 94             if(!b[k][1]&&y!=f[k][3]&&z!=-f[k][0]-f[k][3])b[k][1]=1;
 95             if(!b[k][2]&&y!=-f[k][0]-f[k][4]&&z!=f[k][4])b[k][2]=1;
 96         }
 97     }
 98     if(y!=f[k][1]){
 99         if(!b[k][3])b[k][3]=1,f[k][5]=x,f[k][6]=z;
100         else{
101             if(!b[k][4]&&x!=f[k][5]&&z!=-f[k][1]-f[k][5])b[k][4]=1;
102             if(!b[k][5]&&x!=-f[k][1]-f[k][6]&&z!=f[k][6])b[k][5]=1;
103         }
104     }
105     if(z!=f[k][2]){
106         if(!b[k][6])b[k][6]=1,f[k][7]=x,f[k][8]=y;
107         else{
108             if(!b[k][7]&&x!=f[k][7]&&y!=-f[k][2]-f[k][7])b[k][7]=1;
109             if(!b[k][8]&&x!=-f[k][2]-f[k][8]&&y!=f[k][8])b[k][8]=1;
110         }
111     }
112 }
113 void ins(){
114     int _=0;
115     upd(0);
116     for(int i=29;i>=0;--i){
117         if(a&(1<<i)){
118             if(!r[_])r[_]=++cnt,__=1;
119             _=r[_];
120         }
121         else{
122             if(!l[_])l[_]=++cnt,__=1;
123             _=l[_];
124         }
125         upd(_);
126     }
127 }
128 int get(){
129     int x=0;
130     char c=getchar();
131     while(c<48)c=getchar();
132     while(c>47)x=x*10+c-48,c=getchar();
133     return x;
134 }
135 int main(){
136     n=get();
137     opt=get();
138     if(opt)opt=1;
139     for(int i=1;i<=n;++i)T[i]=get();
140     for(int i=1;i<=n;++i)A[i]=get();
141     ins();
142     for(int i=1;i<=n;++i){
143         int t,_;
144         t=(T[i]^(ans*opt))%3;
145         _=A[i]^(ans*opt);
146         a^=_;
147         if(t==0)++x,--z;
148         else if(t==1)++y,--x;
149         else ++z,--y;
150         ans=0;
151         int o=0;
152         if(chk(0)){
153             for(int j=29;j>=0;--j){
154                 if(a&(1<<j)){
155                     if(l[o]&&chk(l[o]))o=l[o],ans^=(1<<j);
156                     else o=r[o];
157                 }
158                 else{
159                     if(r[o]&&chk(r[o]))o=r[o],ans^=(1<<j);
160                     else o=l[o];
161                 }
162             }
163         }
164         printf("%d",ans);
165         if(i<n)printf(" ");
166         else printf("n");
167         ins();
168     }
169     //system("pause");
170     return 0;
171 }