NYOJ 简单数据结构

NYOJ 2 括号配对问题

栈的简单应用。可使用STL。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <stack>
 5 using namespace std;
 6 const int maxn=10000+5;
 7 
 8 char ch[maxn];
 9 stack<char> s;
10 
11 bool deal()
12 {
13     while(!s.empty())
14         s.pop();
15     int len=strlen(ch);
16     for(int i=0;i<len;i++)
17     {
18         if(ch[i]=='('||ch[i]=='[')
19             s.push(ch[i]);
20         else if(!s.empty()&&ch[i]==')')
21         {
22             if(s.top()=='(')
23                 s.pop();
24             else
25                 return 0;
26         }
27         else if(!s.empty()&&ch[i]==']')
28         {
29             if(s.top()=='[')
30                 s.pop();
31             else
32                 return 0;
33         }
34         else
35             return 0;
36     }
37     return s.empty();
38 }
39 
40 int main()
41 {
42     int t;
43     scanf("%d",&t);
44     while(t--)
45     {
46         scanf("%s",ch);
47         if(deal())
48             printf("Yes
");
49         else
50             printf("No
");
51     }
52     return 0;
53 }

View Code

NYOJ 5 Binary String Matching

简单模拟

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn=1000+5;
 6 
 7 char a[maxn],b[maxn];
 8 
 9 int deal()
10 {
11     int num=0,j,len1,len2;
12     len1=strlen(a);
13     len2=strlen(b);
14     for(int i=0;i<len2;i++)
15     {
16         j=0;
17         while(a[i]==a[j])
18         {
19             i++;
20             j++;
21         }
22         if(j==len1)
23         {
24             num++;
25             j=1;
26         }    
27         i-=j;
28     }
29     return num;
30 }
31 
32 int main()
33 {
34     int t;
35     scanf("%d",&t);
36     while(t--)
37     {
38         scanf("%s%s",&a,&b);
39         printf("%d
", deal());  
40     }
41     return 0;
42 }

View Code

NYOJ 63 小猴子下落

有规律

观察可知，每一层小猴子经过节点往下都是左右轮流。

并且，猴子I为奇数时在二叉树左半部分，偶数时在右半部分，到子结点的猴子数目逐层减半。

所以，我们只需根据I的大小，判断每一层猴子会去左右哪一边。

这里用到一个性质：左子结点编号=父节点*2，右结点编号=父节点*2+1.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int d,n,ans;
 9     while(scanf("%d%d",&d,&n)&&(d+n))
10     {
11         ans=1;
12         while(--d)
13         {
14             if(n%2==0)
15             {
16                 n/=2;
17                 ans=ans*2+1;
18             }
19             else
20             {
21                 n=(n+1)/2;
22                 ans=ans*2;
23             }
24         }
25         printf("%d
",ans);
26     }
27     return 0;
28 }

View Code

NYOJ 93 汉诺塔（三）

简单模拟

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn=70;
 6 
 7 struct node
 8 {
 9     int len;
10     int s[maxn];
11 }h[5];
12 
13 int n,p;
14 
15 void init()
16 {
17     h[1].len=h[2].len=h[3].len=-1;
18     for(int i=n;i>=1;i--)
19         h[1].s[++h[1].len]=i;
20 }
21 
22 int deal()
23 {
24     int x,y,xx,yy,f=0;
25     for(int i=0;i<p;i++)
26     {
27         scanf("%d%d",&x,&y);
28         if(f)
29             continue ;
30         if(h[x].len!=-1)
31         {
32             xx=h[x].len;yy=h[y].len;
33             if(yy!=-1&&h[y].s[yy]<h[x].s[xx])
34                 f=1;
35             else
36             {
37                 h[x].len--;
38                 h[y].len++;
39                 h[y].s[yy+1]=h[x].s[xx];
40             }
41         }
42         else
43             f=1;    
44     }
45     return !f;
46 }
47 
48 int main()
49 {
50     int t;
51     scanf("%d",&t);
52     while(t--)
53     {
54         scanf("%d%d",&n,&p);
55         init();
56         if(deal())
57             printf("legal
");
58         else
59             printf("illegal
");
60     }
61     return 0;
62 }

View Code