2018.02.27(数据结构)

2018.02.27~28

数据结构入门

1.字符串排序(结构体，指针)

题目描述：有N个字符串，利用指针把它们按照字典序从大到小排序。

思路：定义一个二维数组$read[1001][1001]$用来储存字符串，定义一个指针数组$book[1001]$指向$read$的第一维，用$sort$排序时调用的是指针，换的也是指针，不必将整个字符串交换。

核心代码：

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 int n;
 8 char read[1001][1001];
 9 char* book[1001];
10 bool tmp(char* str1,char* str2){return strcmp(str1,str2)<0;}
11 int main(){
12     scanf("%d",&n);
13     int i,j;
14     for(i=1;i<=n;i++){
15         scanf("%s",read[i]);
16         book[i]=read[i];
17         getchar();
18     }
19     sort(book+1,book+1+n,tmp);
20     for(i=n;i>=1;i--)printf("%s
",book[i]);
21     return 0;
22 }

View Code

状态：AC

2.约瑟夫问题(指针，链表)

思路：用$now$表示当前的这个人，$next[now]$表示这个人的下一人是谁，在$while$里面每次循环，遇到该退出的时候就用以下代码将这个人退出。最后输出$next$数组中不是$-1$的。

int tmp=next[now];
next[now]=next[next[now]];
next[tmp]=-1;

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int next[10001];
 5 int main(){
 6     int n,m,k;
 7     scanf("%d%d",&n,&m);
 8     k=n;
 9     int i,j;
10     for(i=1;i<=n;i++){
11         if(i==n)next[i]=1;
12         else next[i]=i+1;
13     }
14     int now=1,bs=0;
15     while(k>1){
16         bs++;
17         if(bs==m-1){
18             k--;
19             bs=0;
20             int tmp=next[now];
21             next[now]=next[next[now]];
22             next[tmp]=-1;
23         }
24         now=next[now];
25     }
26     for(i=1;i<=n;i++)
27         if(next[i]!=-1)
28             printf("%d",i);
29     return 0;
30 }

View Code

状态：AC

3.括号序列(栈，指针)

思路：利用栈，遇到左括号就入栈，遇到右括号就看栈里面当前栈顶元素是否和当前右括号匹配。在最后，还要看栈是否清空。

核心代码(80分垃圾)：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 char word[2000001];
 5 char zhan[2000001];
 6 int top=0;
 7 int bz=0;
 8 int main(){
 9     int n;
10     scanf("%d",&n);
11     int i,j;
12     for(i=1;i<=n;i++){
13         getchar();
14         scanf("%s",word);
15         top=0;
16         bz=0;
17         zhan[0]='H';
18         for(j=0;j<=strlen(word)-1;j++){
19             if(word[j]=='['||word[j]=='<'||word[j]=='{'||word[j]=='('){
20                 top++;
21                 zhan[top]=word[j];
22             }
23             else if(word[j]==']'&&zhan[top]=='[')top--;
24             else if(word[j]=='}'&&zhan[top]=='{')top--;
25             else if(word[j]=='>'&&zhan[top]=='<')top--;
26             else if(word[j]==')'&&zhan[top]=='(')top--;
27             else bz=1;
28             if(top<0)bz=1;
29             if(bz==1)break;
30         }
31         if(top!=0)bz=1;
32         if(bz==0)printf("TRUE
");
33         else     printf("FALSE
");
34     }
35     return 0;
36 }

View Code

 1 #include<bits/stdc++.h>
 2 #define For(i,l,r) for(int i=(l);i<=(r);i++)
 3 using namespace std;
 4 char s[4000008];
 5 
 6 int main(){
 7     int n,len;
 8     bool ok;
 9     scanf("%d
",&n);
10     For(i,1,n){
11         scanf("%s",s);
12         stack<char> ST;
13         len=strlen(s);
14         ok=true;
15         For(j,0,len-1){
16             if (s[j]=='{' || s[j]=='('|| s[j]=='['|| s[j]=='<')
17                 ST.push(s[j]);
18             else 
19                 if (ST.empty() || abs(s[j]-ST.top())>2){
20                     ok=false;
21                     break;
22                 }
23                 else ST.pop();
24         }
25         if (ST.empty() && ok)
26             cout<<"TRUE"<<endl;
27         else
28             cout<<"FALSE"<<endl;
29     } 
30     return 0;
31 }

$STL代码$

 1 #include<bits/stdc++.h>
 2 #define For(i,l,r) for(int i=(l);i<=(r);i++)
 3 using namespace std;
 4 char s[4000008];
 5 char ST[5000000];
 6 int t;
 7 int main(){
 8     int n,len;
 9     bool ok;
10     scanf("%d
",&n);
11     For(i,1,n){
12         scanf("%s",s);
13         t=0;
14         len=strlen(s);
15         ok=true;
16         For(j,0,len-1){
17             if (s[j]=='{' || s[j]=='('|| s[j]=='['|| s[j]=='<')
18                 ST[++t]=s[j];
19             else 
20                 if (t==0 || abs(s[j]-ST[t])>2){
21                     ok=false;
22                     break;
23                 }
24                 else t--;
25         }
26         if (t==0 && ok)
27             cout<<"TRUE"<<endl;
28         else
29             cout<<"FALSE"<<endl;
30     } 
31     return 0;
32 }

$非STL代码$

状态：AC

4.表达式转换

思路：......................................

AC代码：

 1 #include<bits/stdc++.h>
 2 #define For(i,l,r) for(int i=(l);i<=(r);i++)
 3 using namespace std;   //+  -  *  /  ( )  ^
 4 const int prior[7][7]={{ 1, 1,-1,-1,-1,1,-1},          
 5 /*栈顶运算vs当前运算*/ { 1, 1,-1,-1,-1,1,-1},        
 6 /*栈顶运算优先算，置1*/{ 1, 1, 1, 1,-1,1,-1},
 7 /*当前运算先算，置-1*/ { 1, 1, 1, 1,-1,1,-1},
 8 /*对括号特殊处理，置0*/{-1,-1,-1,-1,-1,0,-1},        //左边为左括号，则右边什么运算都要先算，除了右括号 
 9                        { 0, 0, 0, 0, 0,0, 0},        //这一行其实没有意义可以随便赋初值，因为左括号不会出现在栈顶        
10                        { 1, 1, 1, 1,-1,1, 1}};        
11 char strh[2000]={0},strz[2000]={0};            //后缀表达式字符串，中缀表达式字符串 
12 char opst[10000],top=0;                        //运算符栈 
13 int numst[10000],t=0;                        //操作数栈 
14 int f(char op){        //将运算符对应到0-6的标号 
15     switch(op){
16         case '+': return 0;
17         case '-': return 1;
18         case '*': return 2;
19         case '/': return 3;
20         case '(': return 4;
21         case ')': return 5;
22         case '^': return 6;    
23     }
24 }
25 
26 void convert(char strz[],char strh[]){
27     int len=strlen(strz);
28     int j=0;
29     opst[++top]='('; //在最外层添加左括号 
30     
31     //以下部分，opst[top]是栈顶的上一个运算符，strz[i]是当前扫描到的运算符 
32     
33     For(i,0,len-1){                
34         if (isdigit(strz[i])) strh[j++]=strz[i];        //如果是操作数，直接输出到strh中 
35         else {
36             while (prior[f(opst[top])][f(strz[i])]>0)    //将所有优先于strz[i]的opst[top]都弹出 
37                 strh[j++]=opst[top--];
38             if (prior[f(opst[top])][f(strz[i])]==0)        //如果str[i]是右括号，将栈顶的左括号弹出 
39                 top--;
40             else
41                 opst[++top]=strz[i];                    //如果str[i]不是右括号，将strz[i]压入栈
42         }
43     }
44 }
45 
46 void print(char s[]){//给后缀表达式的剩余部分加上空格输出 
47     int len=strlen(s);
48     For(i,0,len-1){
49         printf("%c ",s[i]);    
50     }
51     printf("
");                
52 }
53 
54 void cal(char strh[]){        //后缀表达式的计算 
55     int len=strlen(strh);
56     print(strh);            //输出后缀表达式本身 
57     For(i,0,len-1)             //扫描后缀表达式 
58         if (isdigit(strh[i])) numst[++t]=strh[i]-'0';        //数字字符就入操作数栈 
59         else {
60             t--;                                            //否则根据strh[i]运算符对栈顶的两个元素进行计算 
61             switch(strh[i]){
62                 case '+':numst[t]=numst[t]+numst[t+1];break;
63                 case '-':numst[t]=numst[t]-numst[t+1];break;
64                 case '*':numst[t]=numst[t]*numst[t+1];break;
65                 case '/':numst[t]=numst[t]/numst[t+1];break;
66                 case '^':numst[t]=pow(numst[t],numst[t+1]);break;
67             }
68             For(j,1,t) printf("%d ",numst[j]);                //输出计算完这一步的后缀表达式中间过程 
69             print(strh+i+1);                                //分两段输出，前面一段对应操作数栈，后面一段对应未扫描的strh 
70         }
71 }
72 
73 int main(){
74     gets(strz);
75     int len=strlen(strz);
76     strz[len]=')';
77     strz[len+1]='';
78     //在最外层添加右括号 
79     convert(strz,strh);
80     cal(strh);
81     return 0;
82 }

View Code

状态：AC

5.抓住那头牛

思路：.......................................

核心代码(RE)：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int road[5000001][2],book[5000001];
 5 int main(){
 6     int farmer,cow;
 7     memset(book,0,sizeof(book));
 8     scanf("%d%d",&farmer,&cow);
 9     int i,j;
10     road[1][0]=farmer;
11     road[1][1]=0;
12     book[road[1][0]]=1;
13     i=0;j=2;
14     while(1){
15         i++;
16         if(i==500001)i=1;
17         if(road[i][0]*2<=500000&&book[road[i][0]*2]==0){
18             if(road[i][0]*2==cow){
19                 printf("%d
",road[i][1]+1);
20                 return 0;
21             }
22             book[road[1][0]*2]=1;
23             road[j][0]=road[i][0]*2;
24             road[j][1]=road[i][1]+1;
25             j++;
26         }
27         if(road[i][0]+1<=500000&&book[road[i][0]+1]==0){
28             if(road[i][0]+1==cow){
29                 printf("%d
",road[i][1]+1);
30                 return 0;
31             }
32             book[road[1][0]+1]=1;
33             road[j][0]=road[i][0]+1;
34             road[j][1]=road[i][1]+1;
35             j++;
36         }
37         if(road[i][0]-1>=0&&book[road[i][0]-1]==0){
38             if(road[i][0]-1==cow){
39                 printf("%d
",road[i][1]+1);
40                 return 0;
41             }
42             book[road[1][0]-1]=1;
43             road[j][0]=road[i][0]-1;
44             road[j][1]=road[i][1]+1;
45             j++;
46         }
47     }
48     return 0;
49 }

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring> 
 5 using namespace std;
 6 int a[100001],b[100001],c[100001];
 7 int tot=0;
 8 int print(int d){
 9     if(c[d]!=0) print(c[d]);
10     tot++;
11 }
12 int main(){
13     memset(b,0,sizeof(b));
14     memset(a,0,sizeof(a));
15     int n,k,x;
16     cin>>n>>k;
17     if(n==k){
18         cout<<0<<endl;
19         return 0;
20     }
21     a[1]=n;b[n]=1;
22     int head=0,tail=1;
23     while(head!=tail){
24         head++;
25         for(int i=1;i<=3;++i){
26             if(i==1) x=a[head]+1;
27             if(i==2) x=a[head]-1;
28             if(i==3) x=a[head]*2;
29             if(x>=0&&b[x]==0&&x<=100000){
30                 tail++;
31                 a[tail]=x;
32                 c[tail]=head;
33                 if(x==k){
34                     print(tail);
35                     cout<<tot-1<<endl;
36                     head=tail;
37                     break;
38                 }
39                 b[x]=1;
40             }
41         }
42     }
43     return 0;
44 }

$AC代码$

状态：AC

6.后缀表达式

思路：........................................

AC代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 char yhb;
 5 long long zhan[10001]={0},top=0;
 6 int main(){
 7     int i,j,ch=0;
 8     while((yhb=getchar())!='@'){
 9         if(yhb>='0'&&yhb<='9'){
10             ch=ch*10+yhb-'0';
11         }
12         else if(yhb=='.'){
13             zhan[++top]=ch;
14             ch=0;
15         }
16         else{
17             if(yhb=='+')zhan[top-1]+=zhan[top];
18             if(yhb=='-')zhan[top-1]-=zhan[top];
19             if(yhb=='*')zhan[top-1]*=zhan[top];
20             if(yhb=='/')zhan[top-1]/=zhan[top];
21             zhan[top]=0;
22             top--;
23         }
24     }
25     printf("%lld
",zhan[1]);
26     return 0;
27 }

View Code

状态：AC

7.接龙游戏

思路：........................................

核心代码：

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 int n,Top=0;
 8 long long _max=1;
 9 struct net{
10     char a[60];
11 }word[100001];
12 char*   p[100001];
13 int  zhan[100001];
14 bool tmp(char* str1,char* str2){return strcmp(str1,str2)<0;}
15 int main(){
16     int i,j;
17     scanf("%d",&n);
18     for(i=1;i<=n;i++){
19         scanf("%s",word[i].a);
20         p[i]=word[i].a;
21         getchar();
22     }
23     sort(p+1,p+1+n,tmp);
24     ////////////////////
25     zhan[++Top]=0;
26     for(i=1;i<=n;i++){
27         int flag=0;
28         while(Top!=0){
29             int tmp=zhan[Top];
30             int len1=strlen(word[tmp].a);
31             int len2=strlen(word[i].a);
32             if(len2>len1){
33                 flag=1;
34                 for(j=0;j<len1;j++){
35                     if(word[tmp].a[j]!=word[i].a[j]){
36                         flag=0;
37                         break;
38                     }
39                 }
40             }
41             if(flag)break;
42             Top--;
43         }
44         zhan[++Top]=i;
45         if(_max<Top)_max=Top;
46     }
47     ////////////////////
48     printf("%lld",_max+1);
49     return 0;
50 }

View Code

状态：UNAC

8.车厢调度

思路：........................................

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int stack[1010],a[1010];
 5 int top,n;
 6 int main(){
 7     int i;
 8     int cur;
 9     scanf("%d",&n);
10     for(i=1;i<=n;i++)
11         scanf("%d",&a[i]);
12     top=0;
13     for(i=1,cur=1;i<=n;i++){
14         while(cur<=a[i])
15             stack[++top]=cur++;//入栈？ 
16         if(stack[top]==a[i])
17             --top;//出栈？ 
18         else{
19             printf("NO
");
20             return 0;
21         }
22     }
23     printf("YES
");
24     return 0;
25 }

View Code

状态：AC

9.舞伴配对

思路：..........................................

核心代码：

1 #include <stdio.h>
2 #include <math.h>
3 #include <string.h>
4 int main(){
5     long long a,b,c;
6     scanf("%lld%lld%lld",&a,&b,&c);
7     printf("%lld %lld",a%c+1,b%c+1);
8     return 0;
9 }

View Code

状态：AC

10.Blah数集

思路：...........................................

核心代码：

 1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstring>
 4 #include <iostream>
 5 using namespace std;
 6 long long math[1000101];
 7 int _min(int x,int y){return x<y?x:y;}
 8 int main(){
 9     long long n;
10     int i,j;
11     int x2,x3;
12     while(cin>>math[1]>>n){
13         x2=1,x3=1,i=2;
14         while(i<=n){
15             long long t1,t2;
16             int t;
17             t1=math[x2]*2+1;
18             t2=math[x3]*3+1;
19             t=_min(t1,t2);
20             if(t1<t2)x2++;else x3++;
21             if(t==math[i-1])continue;//这里要注意！！！ 
22             math[i++]=t;
23         }
24         printf("%lld
",math[n]); 
25     }
26     return 0;
27 }

View Code

状态：AC