3.1 基础数据结构回顾

例题1 uva11995 http://acm.hust.edu.cn/vjudge/problem/18700

猜测符合哪种数据结构 , 用stl模拟判断.

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e5+10;
11 int n;
12 int a[M];
13 int b[M];
14 char answer[8][32]={"stack","queue","priority queue","impossible","not sure"};
15 stack<int> s;
16 queue<int> q;
17 priority_queue<int> p;
18 bool checkStack(){
19     while(!s.empty()) s.pop();
20     for(int i=0;i<n;i++){
21         if(a[i]==1){
22             s.push(b[i]);
23             continue;
24         }
25         if(s.empty()) return false;
26         if(s.top()!=b[i]) return false;
27         s.pop();
28     }
29     return true;
30 }
31 bool checkQueue(){
32     while(!q.empty()) q.pop();
33     for(int i=0;i<n;i++){
34         if(a[i]==1){
35             q.push(b[i]);
36             continue;
37         }
38         if(q.empty()) return false;
39         if(q.front()!=b[i]) return false;
40         q.pop();
41     }
42     return true;
43 }
44 bool checkPriority(){
45     while(!p.empty()) p.pop();
46     for(int i=0;i<n;i++){
47         if(a[i]==1){
48             p.push(b[i]);
49             continue;
50         }
51         if(p.empty()) return false;
52         if(p.top()!=b[i]) return false;
53         p.pop();
54     }
55     return true;
56 }
57 int solve(){
58     bool isStack=checkStack();
59     bool isQueue=checkQueue();
60     bool isPriority=checkPriority();
61     if(isStack&&!isQueue&&!isPriority) return 0;
62     if(!isStack&&isQueue&&!isPriority) return 1;
63     if(!isStack&&!isQueue&&isPriority) return 2;
64     if(!isStack&&!isQueue&&!isPriority) return 3;
65     return 4;
66 }
67 int main(){
68     #ifdef txtout
69     freopen("in.txt","r",stdin);
70     freopen("out.txt","w",stdout);
71     #endif // txtout
72     while(~scanf("%d",&n)){
73         for(int i=0;i<n;i++){
74             scanf("%d%d",&a[i],&b[i]);
75         }
76         puts(answer[solve()]);
77     }
78     return 0;
79 }

View Code

例题2 uva 11991 http://acm.hust.edu.cn/vjudge/problem/18696

n个正整数, m 次查询都是10^5, 每次查询第k 个值为v的下标. 开10的6次方vector,每个值的下表到对应vector, o1查询. on预处理

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e5+10;
11 int n,m;
12 int a[M];
13 int k[M];
14 int v[M];
15 int answer[M];
16 vector<int> id[M*10];
17 void solve(){
18     for(int i=0;i<n;i++){
19         id[a[i]].clear();
20     }
21     for(int i=0;i<n;i++){
22         id[a[i]].push_back(i+1);
23     }
24     for(int i=0;i<m;i++){
25         int value=v[i];
26         if(id[value].size()<k[i]){
27             answer[i]=0;
28         }
29         else{
30             answer[i]=id[value][k[i]-1];
31         }
32     }
33 }
34 int main(){
35     #ifdef txtout
36     freopen("in.txt","r",stdin);
37     freopen("out.txt","w",stdout);
38     #endif // txtout
39     while(~scanf("%d%d",&n,&m)){
40         for(int i=0;i<n;i++){
41             scanf("%d",&a[i]);
42         }
43         for(int i=0;i<m;i++){
44             scanf("%d%d",&k[i],&v[i]);
45         }
46         solve();
47         for(int i=0;i<m;i++){
48             printf("%d
",answer[i]);
49         }
50     }
51     return 0;
52 }

View Code

白书用 map <int, vector<int> > ,也是一种写法 nlogn

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e5+10;
11 int n,m;
12 map<int, vector<int> > a;
13 int main(){
14     #ifdef txtout
15     freopen("in.txt","r",stdin);
16     freopen("out.txt","w",stdout);
17     #endif // txtout
18     while(~scanf("%d%d",&n,&m)){
19         a.clear();
20         int x,y;
21         for(int i=0;i<n;i++){
22             scanf("%d",&x);
23             if(!a.count(x)) a[x]=vector<int>();
24             a[x].push_back(i+1);
25         }
26         for(int i=0;i<m;i++){
27             scanf("%d%d",&x,&y);
28             if(!a.count(y)||a[y].size()<x){
29                 puts("0");
30                 continue;
31             }
32             printf("%d
",a[y][x-1]);
33         }
34     }
35     return 0;
36 }

View Code

例题3 la3135 http://acm.hust.edu.cn/vjudge/problem/18684

输入 A B, 表示每B秒产生A编号, 输出前k个编号，同时产生的优先选编号小的。

优先队列，规则时间小的靠前，时间相同编号小的考前。优先队列大的在堆顶。

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e5+10;
11 int n;
12 char a[M];
13 struct Q{
14     int id,now,add;
15     bool operator <(const Q &b) const {
16         return now>b.now||(now==b.now&&id>b.id);
17     }
18 }now,pre;
19 priority_queue<Q> q;
20 int main(){
21     #ifdef txtout
22     freopen("in.txt","r",stdin);
23     freopen("out.txt","w",stdout);
24     #endif // txtout
25     while(!q.empty()) q.pop();
26     while(~scanf("%s",a)){
27         if(!strcmp(a,"#")){
28             scanf("%d",&n);
29             while(n--){
30                 pre=q.top();
31                 q.pop();
32                 printf("%d
",pre.id);
33                 now.id=pre.id;
34                 now.add=pre.add;
35                 now.now=pre.now+pre.add;
36                 q.push(now);
37             }
38             while(!q.empty()) q.pop();
39             continue;
40         }
41         int id,t;
42         scanf("%d%d",&id,&t);
43         now.id=id;
44         now.now=now.add=t;
45         q.push(now);
46     }
47     return 0;
48 }

View Code

例题4 uva11997 http://acm.hust.edu.cn/vjudge/problem/18702

给k*k矩阵每行选一个, 求和, 那么一共有 k的k次方种和, 输出前k大的和

做法, 两行两行的做, 当k只有两行的时候 k^2暴力 ,然后取前k个是可以接受的. 当有3行或以上时 , 可以看出之前两行的前k个小的才有用 , 所以用这前k个与下一行 k^2枚举然后得到的和再取前k个.

实现的时候,用优先队列维护,保持队列里最多有k个就可以,因为大于k的最终也会被淘汰,所以没必要存,并且可以通过当前最大的值剪枝. 不算剪枝是k^3logk的实际上挺快 300ms

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e3+10;
11 int n;
12 int a[M][M];
13 vector<int> answer;
14 priority_queue<int> q;
15 void solve(){
16     for(int i=0;i<n;i++){
17         sort(a[i],a[i]+n);
18     }
19     answer.clear();
20     while(!q.empty()) q.pop();
21     for(int i=0;i<n;i++){
22         for(int j=0;j<n;j++){
23             q.push(a[0][i]+a[1][j]);
24             if(q.size()>n) q.pop();
25         }
26     }
27     while(!q.empty()){
28         answer.push_back(q.top());
29         q.pop();
30     }
31     for(int i=2;i<n;i++){
32         while(!q.empty()) q.pop();
33         for(int j=0;j<n;j++){
34             for(int k=0;k<n;k++){
35                 int sum=answer[j]+a[i][k];
36                 if(q.size()==n&&q.top()<=sum) break;
37                 q.push(sum);
38                 if(q.size()>n) q.pop();
39             }
40         }
41         answer.clear();
42         while(!q.empty()){
43             answer.push_back(q.top());
44             q.pop();
45         }
46     }
47     sort(answer.begin(),answer.end());
48 }
49 int main(){
50     #ifdef txtout
51     freopen("in.txt","r",stdin);
52     freopen("out.txt","w",stdout);
53     #endif // txtout
54     while(~scanf("%d",&n)){
55         for(int i=0;i<n;i++){
56             for(int j=0;j<n;j++){
57                 scanf("%d",&a[i][j]);
58             }
59         }
60         solve();
61         for(int i=0;i<answer.size();i++){
62             if(i) putchar(' ');
63             printf("%d",answer[i]);
64         }
65         puts("");
66     }
67     return 0;
68 }

View Code

白书写法100ms, 在合并的时候不是k^2的,合并AB两个数组时,先把AB排序, 会有 k^2的情况, 但是 A1 和B1-Bn 的和是单调增的 , 所以相当于k个有序的一维数组,

A1 B1 --- A1 Bn

AnB1 --- An Bn

每一行都是递增的, 现在要从这k*k个数中取前k大, 那么先考虑把第一列都放进优先队列, 然后优先队列每次弹出最小的, 弹出后, 再压入下一个比如弹出 AiB1 那么下一个就是AiB2. 这样合并就是klogk的

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e3+10;
11 
12 struct G{
13     int s,b;
14     G(int s,int b):s(s),b(b){}
15     bool operator <(const G &b) const {
16         return s>b.s;
17     }
18 };
19 
20 void Merge(int* A,int* B,int* C,int n){
21     priority_queue<G> q;
22     for(int i=0;i<n;i++){
23         q.push(G(A[i]+B[0],0));
24     }
25     for(int i=0;i<n;i++){
26         G g=q.top(); q.pop();
27         C[i]=g.s;
28         int b=g.b;
29         if(b+1<n) q.push(G(g.s-B[b]+B[b+1],b+1));
30     }
31 }
32 
33 int A[M][M];
34 
35 int main(){
36     #ifdef txtout
37     freopen("in.txt","r",stdin);
38     freopen("out.txt","w",stdout);
39     #endif // txtout
40     int n;
41     while(~scanf("%d",&n)){
42         for(int i=0;i<n;i++){
43             for(int j=0;j<n;j++){
44                 scanf("%d",&A[i][j]);
45             }
46             sort(A[i],A[i]+n);
47         }
48         for(int i=1;i<n;i++){
49             Merge(A[0],A[i],A[0],n);
50         }
51         for(int i=0;i<n;i++){
52             if(i) putchar(' ');
53             printf("%d",A[0][i]);
54         }
55         puts("");
56     }
57     return 0;
58 }

View Code

整体复杂度k^2logk 比我好k ,但实际好了3倍,说明剪枝能减去很多.

例题5 la3644 http://acm.hust.edu.cn/vjudge/problem/12648

按顺序加边,无向图,如果出现环则这条边不能加,问最后有几条边不能加.

用并查集,如果本来是一个集合 ,说明不能加.

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e5+10;
11 class UnionFindSet { ///并查集
12     static const int MV=1e5+10; ///点的个数
13     int par[MV],num[MV];
14     void add(int son,int fa) {
15         par[fa]+=par[son];
16         par[son]=fa;
17         num[fa]+=num[son];
18     }
19 public:
20     void init(int n) {
21         for(int i=0; i<=n; i++) {
22             num[i]=1;
23             par[i]=-1;
24         }
25     }
26     int getroot(int x) {
27         int i=x,j=x,temp;
28         while(par[i]>=0) i=par[i];
29         while(j!=i) {
30             temp=par[j];
31             par[j]=i;
32             j=temp;
33         }
34         return i;
35     }
36     bool unite(int x,int y) {
37         int p=getroot(x);
38         int q=getroot(y);
39         if(p==q) return false;
40         if(par[p]>par[q]) {
41             add(p,q);
42         }
43         else {
44             add(q,p);
45         }
46         return true;
47     }
48     int getnum(int id) { ///返回该点所在集合包含的点数
49         return num[getroot(id)];
50     }
51 } gx;
52 int main() {
53 #ifdef txtout
54     freopen("in.txt","r",stdin);
55     freopen("out.txt","w",stdout);
56 #endif // txtout
57     gx.init(1e5+5);
58     int answer=0;
59     int a,b;
60     while(~scanf("%d",&a)) {
61         if(a==-1){
62             printf("%d
",answer);
63             gx.init(1e5+5);
64             answer=0;
65             continue;
66         }
67         scanf("%d",&b);
68         if(!gx.unite(a,b)) answer++;
69     }
70     return 0;
71 }

View Code

简洁一点的白书的实现方式.

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e5+10;
11 class UnionFindSet { ///并查集
12     static const int MV=1e5+10; ///点的个数
13     int par[MV];
14 public:
15     void init(int n) {
16         for(int i=0; i<=n; i++) {
17             par[i]=i;
18         }
19     }
20     int getroot(int x) {
21         return x==par[x]?x:par[x]=getroot(par[x]);
22     }
23     bool unite(int x,int y) {
24         int p=getroot(x);
25         int q=getroot(y);
26         if(p==q) return false;
27         par[p]=q;
28         return true;
29     }
30 } gx;
31 int main() {
32 #ifdef txtout
33     freopen("in.txt","r",stdin);
34     freopen("out.txt","w",stdout);
35 #endif // txtout
36     gx.init(1e5+5);
37     int answer=0;
38     int a,b;
39     while(~scanf("%d",&a)) {
40         if(a==-1){
41             printf("%d
",answer);
42             gx.init(1e5+5);
43             answer=0;
44             continue;
45         }
46         scanf("%d",&b);
47         if(!gx.unite(a,b)) answer++;
48     }
49     return 0;
50 }

View Code

例题6 la3027 http://acm.hust.edu.cn/vjudge/problem/33982

操作把A的父亲设置为B, 距离 w, 查询 A距离根的距离.

白书带权并查集模板

 1 //#define txtout
 2 //#define debug
 3 #include<bits/stdc++.h>
 4 #define mt(a,b) memset(a,b,sizeof(a))
 5 using namespace std;
 6 typedef long long LL;
 7 const double pi=acos(-1.0);
 8 const double eps=1e-8;
 9 const int inf=0x3f3f3f3f;
10 const int M=1e5+10;
11 class WeightedUnionFindSet { ///带权并查集
12     static const int MV=2e4+10; ///点的个数
13     int par[MV];
14     int dist[MV];
15 public:
16     void init(int n) {
17         for(int i=0; i<=n; i++) {
18             par[i]=i;
19             dist[i]=0;
20         }
21     }
22     int getdist(int x){
23         getroot(x);
24         return dist[x];
25     }
26     int getroot(int x) {
27         if(x==par[x]) return x;
28         int root=getroot(par[x]);
29         dist[x]+=dist[par[x]];
30         return par[x]=root;
31     }
32     void unite(int x,int y,int w) {
33         par[x]=y;
34         dist[x]=w;
35     }
36 } gx;
37 int main() {
38 #ifdef txtout
39     freopen("in.txt","r",stdin);
40     freopen("out.txt","w",stdout);
41 #endif // txtout
42     int t,n,x,y;
43     char op[4];
44     while(~scanf("%d",&t)) {
45         while(t--){
46             scanf("%d",&n);
47             gx.init(n);
48             while(true){
49                 scanf("%s",op);
50                 if(op[0]=='O') break;
51                 if(op[0]=='E'){
52                     scanf("%d",&x);
53                     printf("%d
",gx.getdist(x));
54                     continue;
55                 }
56                 scanf("%d%d",&x,&y);
57                 gx.unite(x,y,abs(x-y)%1000);
58             }
59         }
60     }
61     return 0;
62 }

View Code

end