Stanford's ACM Training Course—Chapter#03 Data Structure

Training Course—Chapter#03 Data Structure"/>

Stanford's ACM Training Course—Chapter#03 Data Structure

由于这几天各种忙，于是拖到现在才解决Chapter#03.

这里是课件: Data Structure

下面是这次的作业。。。

Assignment 3: Data Structures

·2418 Hardwood Species (1)

统计相同字符串的个数，用BST或者排序都可以解决，我是用BST做的，第一次用指针打数据结构，打的真是头痛...

View Code

#include <stdio.h>
#include <string.h>
#include <stdlib.h>struct node
{char name[32];int count;node *left,*right;
}*head,*tmp;char s[32];
int n;void initialize(node *&p)
{gets(s);p=new node;p->left=p->right=NULL;strcpy(p->name,s);p->count=1;
}void print(node *p)
{if (p->left!=NULL) print(p->left);printf("%s %.4lf\n",p->name,p->count*100.0/n);if (p->right!=NULL) print(p->right);
}void insert(char s[32])
{tmp=head;while (1){if (strcmp(tmp->name,s)==0){tmp->count++;break;}elseif (strcmp(tmp->name,s)>0){if (tmp->left==NULL){tmp->left=new node;tmp->left->left=tmp->left->right=NULL;strcpy(tmp->left->name,s);tmp->left->count=1;break;}tmp=tmp->left;}else{if (tmp->right==NULL){tmp->right=new node;tmp->right->left=tmp->right->right=NULL;strcpy(tmp->right->name,s);tmp->right->count=1;break;}tmp=tmp->right;}}
}int main()
{initialize(head);  n=1;while (gets(s)){n++;insert(s);}print(head);return 0;
}

·1330 Nearest Common Ancestors (3)

最裸的LCA问题，用LCA倍增算法无压力。。。由于很久没有打LCA问题了，有点生疏...

View Code

#include <iostream>
#include <cstdio>
#include <memory.h>
#define MAXN 10010int head[MAXN],next[MAXN],link[MAXN];
int dep[MAXN],f[MAXN][16];
int n,root;
int u,v;void dfs(int u)
{int now;now=head[u];while (now>0){f[link[now]][0]=u;dep[link[now]]=dep[u]+1;dfs(link[now]);now=next[now];}
}void build()
{int i,j;for (j=1;1<<j<=n;j++)for (i=1;i<=n;i++)if (f[i][j-1]>0)f[i][j]=f[f[i][j-1]][j-1];
}int lca(int u,int v)
{int i, log;if (dep[u]<dep[v])i=u, u=v, v=i;for (log=1;1<<log<=n;log++);for (i=log;i>=0;i--)if (dep[u]-(1<<i)>=dep[v]){u=f[u][i];if (u==v) return u;}for (i=log;i>=0;i--)if (f[u][i]!=-1&&f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];return f[u][0];
}int main()
{int test,i;scanf("%d",&test);while (test--){scanf("%d",&n);root=n*(n+1)/2;memset(head,-1,sizeof(head));memset(next,-1,sizeof(next));memset(f,-1,sizeof(f));for (i=1;i<n;i++){scanf("%d%d",&u,&v);next[i]=head[u];head[u]=i;link[i]=v;root-=v;}scanf("%d%d",&u,&v);dep[root]=0;dfs(root);build();printf("%d\n",lca(u,v));}return 0;
}

·3367 Expressions (3)

题目有一点坑，就是根据后缀表达式构造出表达式树，然后层次遍历一下，倒序输出即可。输出的时候记住在字符串末尾加结束符\0(坑爹的东西，怀念P啊)

View Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define MAXN 10010using namespace std;int lch[MAXN],rch[MAXN];
char s[MAXN],ans[MAXN];
int len,n;void build()
{int now=n;if (isupper(s[now])){rch[now]=--n;build();lch[now]=n;build();}else lch[now]=rch[now]=-1, n--;
}void construct()
{int head,tail,now;int queue[MAXN];head=tail=0;ans[len]=0;queue[0]=len-1;while (head<=tail){now=queue[head]; head++;ans[--len]=s[now];if (lch[now]>=0) tail++,queue[tail]=lch[now];if (rch[now]>=0) tail++,queue[tail]=rch[now];}
}int main()
{int test;scanf("%d ",&test);while (test--){gets(s);len=strlen(s);n=len-1;build();construct();puts(ans);}return 0;
}

·1984 Navigation Nightmare (5)

并查集的应用，在father[]上再加两个值x和y，表示当前点距父亲的距离. 在Union和Find的过程中维护这两个值即可. 需要注意的是询问的输入不一定按时间来排序，我们需要对它进行排序.

View Code

#include <iostream>
#include <functional>
#include <algorithm>
#include <cstdio>
#define MAXN 40010
#define MAXM 40010
#define MAXK 10010struct message
{int a,b,l;char dir;
};
struct query
{int a,b,t;
};
struct element
{int f,x,y;
};query q[MAXK];
message msg[MAXN];
element set[MAXN];
int id[MAXN];
int ans[MAXK];
int n,m,k;int cmp(int a,int b)
{return (q[a].t<q[b].t);
}void initialize()
{int i;for (i=1;i<=n;i++){set[i].f=i;set[i].x=set[i].y=0;}
}int find(int x)
{int tmp;if (x!=set[x].f){tmp=set[x].f;set[x].f=find(set[x].f);set[x].x+=set[tmp].x;set[x].y+=set[tmp].y;}return set[x].f;
}void Union(int a,int b,int l,char dir)
{int dx=0,dy=0;int fa,fb;switch (dir){case 'E': dx=l; break;case 'W': dx=-l; break;case 'N': dy=-l; break;case 'S': dy=l; break;}fa=find(a); fb=find(b);if (fa==fb) return;set[fa].f=fb;set[fa].x=set[b].x-set[a].x+dx;set[fa].y=set[b].y-set[a].y+dy;
}int check(int a,int b)
{int fa,fb;fa=find(a); fb=find(b);if (fa!=fb) return -1;return (abs(set[a].x-set[b].x)+abs(set[a].y-set[b].y));
}int main()
{int i,j;scanf("%d%d",&n,&m);for (i=1;i<=m;i++)scanf("%d %d %d %c\n",&msg[i].a,&msg[i].b,&msg[i].l,&msg[i].dir);scanf("%d",&k);for (i=1;i<=k;i++){scanf("%d%d%d",&q[i].a,&q[i].b,&q[i].t);id[i]=i;}std::sort(id+1,id+k+1,cmp);initialize();j=1;for (i=1;i<=m;i++){Union(msg[i].a,msg[i].b,msg[i].l,msg[i].dir);while (q[id[j]].t==i){ans[id[j]]=check(q[id[j]].a,q[id[j]].b);j++;}}for (i=1;i<=k;i++)printf("%d\n",ans[i]);return 0;
}

·1785 Binary Search Heap Construction (5)

一开始百度了一下，尼玛笛卡尔树、Treap，各种不会...但是想了一下之后，发现完全不需要用这些高级的东西，只需RMQ和分治即可. 每次我们用RMQ找到树根，然后将序列分成左右两部分继续构建. 需要注意的是输入数据中lable是乱序的，我们首先要按照lable升序排序.在这题中学了一下scanf的高级用法 %*[]表示忽略[]内的字符, %[a-z]表示读入字符串直到遇到不是a-z中的字符为止，%[^a]表示读入字符串直到遇到字符a为止，但a并没有被读入.

View Code

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define MAXN 50010struct node
{char l[100];int p;
}a[MAXN];
int f[MAXN][16];
int n;int cmp(node a,node b)
{return (strcmp(a.l,b.l)<0);
}int get_root(int l,int r)
{int k;k=floor(log(1.0*(r-l+1))/log(2.0));if (a[f[l][k]].p>a[f[r-(1<<k)+1][k]].p) return f[l][k];else return f[r-(1<<k)+1][k];
}void construct(int l,int r)
{int root;if (l>r) return;root=get_root(l,r);printf("(");construct(l,root-1);printf("%s/%d",a[root].l,a[root].p);construct(root+1,r);printf(")");
}int main()
{int i,j;while (scanf("%d",&n)!=EOF&&n){for (i=1;i<=n;i++)scanf("%*[ ]%[a-z]/%d",a[i].l,&a[i].p);std::sort(a+1,a+n+1,cmp);for (i=1;i<=n;i++) f[i][0]=i;for (j=1;(1<<j)<=n;j++)for (i=1;i<=n-(1<<j)+1;i++)if (a[f[i][j-1]].p>a[f[i+(1<<j-1)][j-1]].p) f[i][j]=f[i][j-1];else f[i][j]=f[i+(1<<j-1)][j-1];construct(1,n);printf("\n");}
}

·1988 Cube Stacking (6)

并查集的应用，题解写过好几次了，具体分析可以参考并查集习题集那部分的分析.

View Code

#include <stdio.h>
#define MAXN 30010int f[MAXN],sum[MAXN], upon[MAXN];
int p;void UFsets()
{int i;for (i=1;i<=MAXN;i++){f[i]=i;sum[i]=1;upon[i]=0;}
}int find(int x)
{int tmp;if (x!=f[x]){tmp=f[x];f[x]=find(f[x]);upon[x]+=upon[tmp];}return f[x];
}void move()
{int x,y,fx,fy;scanf(" %d %d",&x,&y);fx=find(x); fy=find(y);f[fy]=fx;upon[fy]=sum[fx];sum[fx]+=sum[fy];
}void count()
{int x,fx;scanf(" %d",&x);fx=find(x);printf("%d\n",sum[fx]-upon[x]-1);
}int main()
{char opt;scanf("%d",&p);UFsets();while (p){scanf("\n%c",&opt);if (opt=='M') move();else if (opt='C') count();p--;}return 0;
}

·1703 Find them, Catch them (6)

种类并查集，跟1984类似. 设p[i]表示i的性质，如果p[i]=0则，i和father(i)在同一团伙，否则i和father(i)
在不同团伙. 在Union和find时维护p[].对于A操作，如果father(a)和father(b)不同，那么不能确定a和b的关系，否则如果p[a]=p[b]则a和b在同一团伙，反之a和b不在同一团伙.

View Code

#include <cstdio>
#include <cstdlib>
#define MAXN 100010int f[MAXN],p[MAXN];
int n,m;void initialize()
{int i;for (i=1;i<=n;i++){f[i]=i;p[i]=0;}
}int find(int x)
{int tmp;if (x!=f[x]){tmp=f[x];f[x]=find(f[x]);p[x]=(p[x]+p[tmp])%2;}return f[x];
}int main()
{int test;char opt;int a,b;int fa,fb;scanf("%d",&test);while (test--){scanf("%d%d",&n,&m);initialize();while (m--){scanf("%*[\n]%c%d%d",&opt,&a,&b);if (opt=='A'){fa=find(a); fb=find(b);if (fa!=fb) printf("Not sure yet.\n");elseif (p[a]==p[b]) printf("In the same gang.\n");else printf("In different gangs.\n");}else{fa=find(a); fb=find(b);if (fa!=fb){f[fa]=fb;p[fa]=(p[b]+p[a]+1)%2;}}}}return 0;
}

·2274 The Race (6)

堆的应用，比较难。。这道题目在刘汝佳《算法艺术与信息学竞赛》中有讲解，但我觉得这本书里面讲解的不是十分详细，我现在来讲一下我的做法.
对于第一问显然就是经典求逆序对的个数，求逆序对有许多的方法，像直接模拟法、线段树、归并排序、树状数组之类的，反正有许多.
由于这道题目Vi∈(0,100)，我们完全可以用模拟的方法来解决.设count[i]表示速度i出现的次数，我们顺序枚举每一辆赛车V，然后累计count[]数组中i大于V的和tmp，inc(ans,tmp)，然后inc(count[V]).这样ans就是你逆序对的数目,时间复杂度就是O(NV).
其实上述过程可以用树状数组优化，我们用树状数组就可以在O(logV)时间内做好求和的工作，时间复杂度可以优化为O(NlogV).这样的优化对于这道题目来说并不明显，所以完全没有必要这样做.
当然最后别忘记ans mod 1000000；

对于第二问，就相对第一问难上许多.第二问显然是要我们输出第一问求出的所有的逆序对中，逆序发生时间(即超车时间)最小的前10000个.这一问我们可以使用堆的扩展形式来解决(本质上就是堆中元素的大小比较多了限制).
我们构建一个小根堆Heap[]表示元素的编号(我们只需要知道编号就可以计算出超车时间和超车位置)，当然heap需要根据超车时间和超车位置这两个键值进行维护，设front[i]表示赛车i前面最近的那辆车的编号(没有就设为n+1)，back[i]表示赛车i后面最近的那辆车的编号(没有就设为0)，home[i]表示赛车i在堆中的位置.
在堆的维护方面绝对没有任何困难，第二问的难点就在与超车发生后如何跟新front[i]和back[i]并且保持堆的性质，下面我就来讲一下如何解决这个操作.
设i表示当前要超车的赛车的编号，j=frint[i](显然i要超过j)，k=back[i].
由于i超过了j(显然我们需要输出i j),那么：
我们先考虑i要怎样变化，j前面的赛车变为i的前面车，i后面的车(即k)变为j的后面车，j就变为i后面的车，即front[i]=front[j]; back[i]=j; back[j]=k;
接下来我们考虑j前面车的变化，显然back[front[j]]:=i; front[j]:=i;
最后我们考虑k的变化，同样front[k]=j;(前提k>0);
以上每次这样调整以后我们需要从堆中相应元素开始向下和向上维护一遍，这样这道题目就完美解决了.
第二问的时间复杂度约为O(MlogN)其中M表示操作的次数,因此总的时间复杂度为O(MlogN+NlogV).
需要注意的是N=1的情况，这个需要特判...

View Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 250010
#define MAXV 110
#define MOD 1000000
#define Limit 10000int x[MAXN],v[MAXN];
int front[MAXN],back[MAXN];
int heap[MAXN],home[MAXN];
int c[MAXV];
int n,ans;void add(int k)
{while (k<=MAXV){c[k]++;k+=k&-k;}
}int sum(int k)
{int s=0;while (k>0){s=(s+c[k])%MOD;k-=k&-k;}return s;
}int cmp(int i,int j)
{int dvi,dvj;int dxi,dxj;long long posi,posj;if (front[j]>n) return 1;if (front[i]>n) return 0;if (v[i]<v[front[i]]) return 0;if (v[j]<v[front[j]]) return 1;dxi=x[front[i]]-x[i];dxj=x[front[j]]-x[j];dvi=v[i]-v[front[i]];dvj=v[j]-v[front[j]];posi=dvi*(x[i]-x[j]);posj=dxi*(v[j]-v[i]);if (dxi*dvj<dxj*dvi||(dxi*dvj==dxj*dvi&&posi<posj)) return 1;else return 0;
}void swap(int *a,int *b)
{int t;t=*a; *a=*b; *b=t;
}void shift(int i)
{while (i>>1){if (cmp(heap[i],heap[i>>1])){swap(&heap[i],&heap[i>>1]);home[heap[i]]=i;home[heap[i>>1]]=i>>1;}else break;i>>=1;}
}void sink(int i)
{while ((i<<1)<=n){i<<=1;if (i<n&&cmp(heap[i+1],heap[i])) i++;if (cmp(heap[i],heap[i>>1])){swap(&heap[i],&heap[i>>1]);home[heap[i]]=i;home[heap[i>>1]]=i>>1;}else break;}
}int main()
{int i,j,k,tmp;scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d%d",&x[i],&v[i]);front[i]=i+1;back[i]=i-1;home[i]=heap[i]=i;}ans=0;memset(c,0,sizeof(c));for (i=n;i>0;i--){ans=(ans+sum(v[i]-1))%MOD;add(v[i]);}printf("%d\n",ans);if (n==1) return 0;for (i=1;i<=n;i++)shift(i);ans=0;while (ans++<Limit&&v[heap[1]]>v[front[heap[1]]]){i=heap[1]; j=front[i]; k=back[i];printf("%d %d\n",i,j);front[i]=front[j];back[i]=j;back[front[j]]=i;sink(1);front[j]=i;back[j]=k;tmp=home[j];sink(tmp); shift(tmp);if (k>0){front[k]=j;tmp=home[k];sink(tmp); shift(tmp);}}return 0;
}

·3321 Apple Tree (6)

先DFS一遍构造出DFS序列，然后就可以用树状数组来解决了。。。

View Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 100010int head[MAXN],next[MAXN*2],link[MAXN*2];
int vis[MAXN],begin[MAXN],end[MAXN];
int a[MAXN*2];
int n,m,cnt;void addedge(int u,int v)
{next[++cnt]=head[u];link[cnt]=v;head[u]=cnt;
}void dfs(int u)
{int now,v;begin[u]=++cnt;now=head[u];while (now>0){v=link[now];if (!vis[v]){vis[v]=1;dfs(v);}now=next[now];}end[u]=cnt;
}int lowbit(int k)
{return (k & -k);
}void add(int k,int delta)
{while (k<=n){a[k]+=delta;k+=lowbit(k);}
}int sum(int k)
{int s=0;while (k>0){s+=a[k];k-=lowbit(k);}return s;
}void updata(int x)
{int tmp;tmp=sum(begin[x])-sum(begin[x]-1);if (tmp==0) add(begin[x],1);else add(begin[x],-1);
}int main()
{int i,x,u,v;char cmd;scanf("%d",&n);cnt=0;memset(head,-1,sizeof(head));memset(next,-1,sizeof(next));memset(vis,0,sizeof(vis));for (i=1;i<n;i++){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}memset(vis,0,sizeof(vis));vis[1]=1; cnt=0;dfs(1);for (i=1;i<=n;i++)add(i,1);scanf("%d",&m);while (m--){scanf("\n%c%d",&cmd,&x);if (cmd=='Q') printf("%d\n",sum(end[x])-sum(begin[x]-1));else updata(x);}return 0;
}

·1177 Picture (7, challenge problem)

扫描线，我们考虑最终图形的边界线段有什么特性. 容易得出从左往右(或从下往上)扫描，边界线总是第一个(或最后一个)被扫到的. 我们给每个点设置一个level[]表示这个点被覆盖了几次(初值为0),在扫描的过程中，如果某个点的level从0变为1，那么这个点在边界线上，同理如果某一个点的level从1变为0，那么这个点也在边界线上.于是根据这个性质 我们将n个矩形离散化为2n条横边和2n条竖边. 这里我们一横边为例，解释一下算法，将所有横边按照纵坐标的大小从小到大排序，如果坐标相同那么把入边放在前面（所谓入边就是一个矩形有两条横边，纵坐标较小的就是入边）。
这个题在统计是可以用线段树优化，目前我还是不会做....以后线段树专题再补上...

View Code

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#define size 10000
#define MAXN 5010typedef struct
{int a,b,c,key;
}node;node col[MAXN*2],row[MAXN*2];
int level[size*2+1];
int n,ans;int cmp(node a,node b)
{return (a.key<b.key||(a.key==b.key&&a.key==0));
}int main()
{int x1,x2,y1,y2;int i,j;scanf("%d",&n);for (i=1;i<=n;i++){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1+=size; y1+=size; x2+=size; y2+=size;col[i].a=y1; col[i].b=y2; col[i].c=0; col[i].key=x1;col[i+n].a=y1; col[i+n].b=y2; col[i+n].c=1; col[i+n].key=x2;row[i].a=x1; row[i].b=x2; row[i].c=0; row[i].key=y1;row[i+n].a=x1; row[i+n].b=x2; row[i+n].c=1; row[i+n].key=y2;}ans=0;std::sort(col+1,col+2*n+1,cmp);memset(level,0,sizeof(level));for (i=1;i<=2*n;i++)if (col[i].c==0){for (j=col[i].a+1;j<=col[i].b;j++){level[j]++;if (level[j]==1) ans++;}}else{for (j=col[i].a+1;j<=col[i].b;j++){level[j]--;if (level[j]==0) ans++;}}std::sort(row+1,row+2*n+1,cmp);memset(level,0,sizeof(level));for (i=1;i<=2*n;i++)if (row[i].c==0){for (j=row[i].a+1;j<=row[i].b;j++){level[j]++;if (level[j]==1) ans++;}}else{for (j=row[i].a+1;j<=row[i].b;j++){level[j]--;if (level[j]==0) ans++;}}printf("%d\n",ans);return 0;
}

·1195 Mobile phones (8, challenge problem)

二维树状数组，十分简单，不知道为什么将其设为Challenge Problem。。注意将读入的坐标值都加1（因为树状数组的下标从1开始）.

View Code

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define SIZE 1025int a[SIZE][SIZE];
int s;void initialize()
{scanf("%d",&s);memset(a,0,sizeof(a));
}int lowbit(int k)
{return (k & -k);
}void add(int x,int y,int delta)
{int y0;y0=y;while (x<=s){y=y0;while (y<=s){a[x][y]+=delta;y+=lowbit(y);}x+=lowbit(x);}
}int sum(int x,int y)
{int y0,Sum=0;y0=y;while (x>0){y=y0;while (y>0){Sum+=a[x][y];y-=lowbit(y);}x-=lowbit(x);}return Sum;
}void updata()
{int x,y,delta;scanf("%d%d%d",&x,&y,&delta);x++; y++;add(x,y,delta);
}void get()
{int x1,x2,y1,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++; y1++; x2++; y2++;printf("%d\n",sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1));
}int main()
{int cmd;while (scanf("%d",&cmd)!=EOF&&cmd!=3){switch (cmd){case 0:initialize(); break;case 1:updata(); break;case 2:get(); break;}}return 0;
}

·2750 Potted Flower (9, challenge problem)

线段树的应用，先放着。。。

转载于:.html