NYOJ 2 括号配对问题
栈的简单应用。可使用STL。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int maxn=+; char ch[maxn];
stack<char> s; bool deal()
{
while(!s.empty())
s.pop();
int len=strlen(ch);
for(int i=;i<len;i++)
{
if(ch[i]=='('||ch[i]=='[')
s.push(ch[i]);
else if(!s.empty()&&ch[i]==')')
{
if(s.top()=='(')
s.pop();
else
return ;
}
else if(!s.empty()&&ch[i]==']')
{
if(s.top()=='[')
s.pop();
else
return ;
}
else
return ;
}
return s.empty();
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",ch);
if(deal())
printf("Yes\n");
else
printf("No\n");
}
return ;
}
NYOJ 5 Binary String Matching
简单模拟
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=+; char a[maxn],b[maxn]; int deal()
{
int num=,j,len1,len2;
len1=strlen(a);
len2=strlen(b);
for(int i=;i<len2;i++)
{
j=;
while(a[i]==a[j])
{
i++;
j++;
}
if(j==len1)
{
num++;
j=;
}
i-=j;
}
return num;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s%s",&a,&b);
printf("%d\n", deal());
}
return ;
}
NYOJ 63 小猴子下落
有规律
观察可知，每一层小猴子经过节点往下都是左右轮流。
并且，猴子I为奇数时在二叉树左半部分，偶数时在右半部分，到子结点的猴子数目逐层减半。
所以，我们只需根据I的大小，判断每一层猴子会去左右哪一边。
这里用到一个性质：左子结点编号=父节点*2，右结点编号=父节点*2+1.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int main()
{
int d,n,ans;
while(scanf("%d%d",&d,&n)&&(d+n))
{
ans=;
while(--d)
{
if(n%==)
{
n/=;
ans=ans*+;
}
else
{
n=(n+)/;
ans=ans*;
}
}
printf("%d\n",ans);
}
return ;
}
NYOJ 93 汉诺塔（三）
简单模拟
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=; struct node
{
int len;
int s[maxn];
}h[]; int n,p; void init()
{
h[].len=h[].len=h[].len=-;
for(int i=n;i>=;i--)
h[].s[++h[].len]=i;
} int deal()
{
int x,y,xx,yy,f=;
for(int i=;i<p;i++)
{
scanf("%d%d",&x,&y);
if(f)
continue ;
if(h[x].len!=-)
{
xx=h[x].len;yy=h[y].len;
if(yy!=-&&h[y].s[yy]<h[x].s[xx])
f=;
else
{
h[x].len--;
h[y].len++;
h[y].s[yy+]=h[x].s[xx];
}
}
else
f=;
}
return !f;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&p);
init();
if(deal())
printf("legal\n");
else
printf("illegal\n");
}
return ;
}