天天看点
返回

HPUACM2014级第三周练习赛解题报告 C++中关于strtok()函数的用法

1001：HDU1072 ACboy needs your help again!

解题思路：最基本的栈和队列的问题，用数组模拟即可

#include <stdio.h>
#include <string.h>


int main (){
    int t,i;
    scanf("%d",&t);
    while(t--){
        int n,x;
        char str[10];
        char mark[10];
        int a[100000];
        scanf("%d",&n);
        scanf("%s",&str);
        if(strcmp(str,"FIFO")==0){//队列
            int j,j1;
            j=j1=0;//j为进队列数，j1为出队列数
            while(n--){
                scanf("%s",mark);
                if(strcmp(mark,"IN")==0){
                    scanf("%d",&x);
                    a[j++]=x;//进队列
                }
                else{
                    if(j1>=j)//判断队列是否为空
                        printf("None\n");
                    else
                        printf("%d\n",a[j1++]);//出队列
                }
            }
        }
        else {//栈
            int j;
            j=0;
            while(n--){
                scanf("%s",mark);
                if(strcmp(mark,"IN")==0){
                    scanf("%d",&x);
                    a[j++]=x;//进栈
                }
                else{
                    if(j<1)
                        printf("None\n");、、判断栈是否为空
                    else
                        printf("%d\n",a[--j]);//出栈
                }
            }
        }
    }
    return 0;
}

下面的是用C++中的STL写的，有余力的同学可以学习一下

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;


int main (){
    int t,i;
    cin>>t;
    while(t--){
        int n,x;
        string str;
        string mark;
        cin>>n>>str;
        if(str.compare("FIFO")==0){
            queue<int>q1;//创建一个队列
            while(n--){
                cin>>mark;
                if(mark.compare("IN")==0){
                    cin>>x;
                    q1.push(x);//x进入队列
                }
                else if(mark.compare("OUT")==0){
                    if(q1.empty())//判断队列是否为空
                        cout<<"None"<<endl;
                    else{
                        cout<<q1.front()<<endl;//输出队列的队首元素
                        q1.pop();//队首元素出队
                    }
                }
            }
        }
        else if(str.compare("FILO")==0){
            stack<int>q2;//创建一个栈
            while(n--){
                cin>>mark;
                if(mark.compare("IN")==0){
                    cin>>x;
                    q2.push(x);//x入栈
                }
                else if(mark.compare("OUT")==0){
                    if(q2.empty())//判断栈是否为空
                        cout<<"None"<<endl;
                    else{
                        cout<<q2.top()<<endl;//输出栈顶元素
                        q2.pop();//栈顶元素出栈
                    }
                }
            }
        }
    }
    return 0;
}

1002：HDU1022  Train Problem I 

题目大概意思：有N辆火车，以序列1方式进站，判断是否能以序列2方式出栈。进站不一定是一次性进入，也就是说中途可以出站。

直接数组模拟，有兴趣的可以尝试一下用STL写

#include<stdio.h>
#include<string.h>
int p[100];
char l[100],s1[100],s2[100];
int main ()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%s",s1);
        scanf("%s",s2);
        memset(p,0,sizeof(p));
        int i,j,k,ans;
        i=ans=k=-1;
        j=0;
        l[++i]=s1[++ans];
        p[++k]=1;//用数组p标记进栈还是出栈
        while(i<n&&j<n)    //保持i和j的数值一致，i和j都要进行<n的判定，如果只进栈的话，不执行j，需要i判断；如果出栈的话 ，执行j，如果进栈的的全部出栈的话 ，靠j判定跳出循环
        {
            while(i>=0&&l[i]==s2[j])  //出栈
            {
                p[++k]=0;
                --i;
                ++j;
            }
            p[++k]=1;                //进栈
            l[++i]=s1[++ans];
        }
        if(ans==n&&j==n)
        {
            printf("Yes.\n");
            for(i=0;i<k;i++)
            {
                if(p[i]==1)
                    printf("in\n");
                else
                    printf("out\n");
            }
            printf("FINISH\n");
        }
        else
            printf("No.\nFINISH\n");
    }

    return 0;
}

1003 HDU1870 愚人节的礼物

如果前两题会，看这一题很水吧，直接上代码

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    char s[1200];
    char l[1200];
    while(scanf("%s",s)!=EOF)
    {
        int i,j,con;
        i=0;
        j=-1;
        con=0;
        while(i<strlen(s))
        {
            if(s[i]=='(')
                {
                    l[++j]='(';
                    con++;
                    i++;
                }
            else if(s[i]==')')
            {
                --j;
                con--;
                i++;
            }
            else
                break;
        }
        if(j==-1)
            printf("0\n");
        else
            printf("%d\n",con);

    }
    return 0;
}

1004 HDU1003 Max Sum

求最大连续子序和。没啥好讲的，大家写写画画，好好想想。

不明白的这题的讨论区上有个讲的不错的，可以看看：http://acm.hdu.edu.cn/discuss/problem/post/reply.php?postid=20808&messageid=1&deep=0

#include<cstdio>
#include<cstring>

int a[100005];

int main ()
{
    int T,con=1;
    scanf("%d",&T);
    while(T--){
        int st,ed,x,y,sum,newsum;
        st=ed=x=y=1;
        int n,i;
        scanf("%d",&n);
        for(i=1;i<=n;++i)
            scanf("%d",&a[i]);
        sum=newsum=a[1];
        for(i=2;i<=n;++i){
            if(sum>=0){
            sum+=a[i]; y=i;
            }
            else{
                sum=a[i];x=y=i;
            }
            if(sum>newsum){
                newsum=sum;st=x;ed=y;
            }
        }
        printf("Case %d:\n",con++);
        printf("%d %d %d\n",newsum,st,ed);
        if(T) printf("\n");
    }
    return 0;
}

1005 HDU2040 亲合数

水题，看大家都写出来了，直接上代码

#include <cstdio>
#include <cstring>

int main (){
    int n,suma,sumb,i,a,b;
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&a,&b);
        suma=sumb=0;
        for(i=1;i<=a/2;++i)
            if(a%i==0)
            suma+=i;
        for(i=1;i<=b/2;++i)
            if(b%i==0)
            sumb+=i;
        if(suma==b && sumb==a)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

1006 HDU2041 超级楼梯

递推：

/*
用dp[i]表示走到第i级的方法数，走到第i级的最后一步只可能有两种，走一级或者是两级，
所以：dp[i]=dp[i-1]+dp[i-2]。
*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int main (){
    int n,m,i;
    int dp[50];
    while(scanf("%d",&n)!=EOF){
        dp[1]=1,dp[2]=1,dp[3]=2;
        while(n--){
            scanf("%d",&m);
            for(i=4;i<=m;++i)
                dp[i]=dp[i-1]+dp[i-2];
            printf("%d\n",dp[m]);
        }

    }
    return 0;
}

1007 HDU2502 月之数

规律题

思路：N的全部二进制数总共有m=2^(N-1)个。第1竖列总共有m个1，之后的第2~N竖列中，1和0各占一半，总共有(N-1)*m/2个1。所以结果ans = m+ (N-1)*m/2。例如N=4:

N = 4：

1 000

1 001

1 010

1 011

1 100

1 101

1 110

1 111

#include <cstdio>
#include <cmath>

int main()
{
    int t,n,m;
    scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		m=pow(2,n-1);
		printf("%d\n",m+(n-1)*m/2);
	}
	return 0;
}

1008 HDU1020 Enconing

大家基本都做出来了，我也不费话了，直接上代码

#include<stdio.h>
#include<string.h>
char a[1000000];
int main ()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        scanf(" %s",a);
        int i,con=1,l;
        l=strlen(a);
        for(i=0;i<l;i++)
        {
            while(a[i]==a[i+1])
            {
                con++;
                i++;
            }
            if(con==1)
                printf("%c",a[i]);
            else 
                printf("%d%c",con,a[i]);
            con=1;
        }
        printf("\n");
    }
    return 0;
}

1009 2089 不要62

水题。

#include<stdio.h>
int d[1001000]={0};
void papapa()
{
    int i,t;
    for(i=1;i<=1001000;i++)
    {
        t=i;
        while(t)
        {
        if(t%10==4||t%100==62)
        d[i]=1;
        t/=10;
        }
    }
}

int main ()
{
    int a,b,i,sum;
        papapa();
    while(scanf("%d%d",&a,&b),a,b)
    {

        sum=0;
        for(i=a;i<=b;i++)
        sum=sum+d[i];
        printf("%d\n",b-a+1-sum);
    }
    return 0;
    
}

1010 HDU 1228 A+B

#include<stdio.h> 
#include<string.h>
#include<algorithm>
using namespace std;
char str[10][10]={"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
char s[100]; 
int replace(char *s)//注意传递的是地址
{
    int i;
    for(i=0;i<10;i++)
    {
    if(strcmp(s,str[i])==0)
    return i;
    }
}
int main()
{
    int a,b;
    while(scanf("%s",s)!=EOF)
    {
        a=replace(s);
        b=0;
        while(scanf("%s",s)&&strcmp(s,"+") != 0)
        {
        a=a*10+replace(s);
        }
        while(scanf("%s",s)&&strcmp(s,"=") != 0)
        {
        b=b*10+replace(s);
        }
        if(!a&&!b) break;
        printf("%d\n",a+b); 
    }
    return 0;
}

1011 HDU 2091 空心三角形

这题的格式比较坑，注意一行的最后一个没有空格

#include<stdio.h>
int main()
{    
    char a;
    int i,j,n,t=0;
    while(scanf("%c",&a)&&a!='@')
{
    t++;
    scanf("%d",&n);
    getchar();
    if(t>1)
    puts("");
    for(i=0;i<n-1;i++)
         {
         for(j=1;j<=n+i;j++)
         {
             if(j==n-i||j==n+i)
             printf("%c",a);
             else 
             printf(" ");
         }
            puts("");
        }
        for(i=1;i<=2*n-1;i++)
        printf("%c",a);
        puts("");
}
    return 0;    
}

1012 HDU4500

这是大二上周的周赛题，大一的好多同学也做出来了，加油，相信你们可以的

#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 100

int dir[][2]={0,1,0,-1,1,0,-1,0};//用数组记录上下左右四个方向
int map[maxn][maxn];

int check(int x,int y){// 判断两个数符号是否相同
	if(x>0 && y<0)
	return 1;
	else if(x<0 && y>0)
	return 1;
	else if(x>0 && y>0)
	return 0;
	else if(x<0 && y<0)
	return 0;
}
int main(){
	int n,m,i,j,k,num,sx,sy,sum;
	while(scanf("%d%d",&n,&m),n,m){
		for(i=1;i<=n;++i)
			for(j=1;j<=m;++j)
		scanf("%d",&map[i][j]);
		sum=-0x3f3f3f3f;
		for(i=1;i<=n;++i)
			for(j=1;j<=m;++j){
				num=0;
				for(k=0;k<4;++k){//检索一下相邻的四个位置
					int x=i+dir[k][0];
					int y=j+dir[k][1];
					if(x>=1 && x<=n && y>=1 && y<=m){//判断是否超边界
						if(check(map[i][j],map[x][y]))
							num+=fabs(map[x][y]);
						else
							num-=fabs(map[x][y]);
					}
				}
				if(num>sum){
					sum=num;
					sx=i;
					sy=j;
				}
			}
			printf("%d %d %d\n",sx,sy,sum);
	}
	return 0;
}

1013 HDU2391 Filthy Rich

数塔问题，简单的动态规划

题目大意；在一个矩阵里边，不同的位置有着不同量的黄金，只能向右，下，和右下走， 求从左上角到右下角最多能得到多少黄金。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define maxn 10000
int map[maxn][maxn];

int main (){
    int t,n,m,i,j,ans;
    scanf("%d",&t);
    ans=0;
    while(t--){
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j)
            scanf("%d",&map[i][j]);
        for(i=1;i<=n;++i)
            for(j=1;j<=m;++j){
                map[i][j]+=max(map[i-1][j],map[i][j-1]);
            }
            printf("Scenario #%d:\n",++ans);
            printf("%d\n\n",map[n][m]);
    }
    return 0;
}

1014 HDU 1106排序

大一第一次周赛的题目。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[2000];
int b[2000];
int main ()
{
    while(scanf("%s",a)!=EOF)
    {
        int len,i,k=0,sum=0;
        len=strlen(a);
        for(i=0;i<len;i++)
        {
            if(a[i]=='5')
                continue;
            while(a[i]!='5'&&a[i]!='\0')
                {
                sum=sum*10+(a[i]-'0');
                i=i+1;
                }
                b[k++]=sum;
                sum=0;
        }
        sort(b,b+k);
        for(i=0;i<k-1;i++)
        printf("%d ",b[i]);
        printf("%d\n",b[k-1]);
    }
        return 0;
}

第二种方法：用C++的strtok()函数，相对来说比较简单。

C++中关于strtok()函数的用法

函数原型：char *strtok(char *s, const char *delim);

Function：分解字符串为一组字符串。s为要分解的字符串，delim为分隔符字符串。

Description：strtok()用来将字符串分割成一个个片段。参数s指向欲分割的字符串，参数delim则为分割字符串，当strtok()在参数s的字符串中发现到参数delim的分割字符时   　　 则会将该字符改为\0 字符。在第一次调用时，strtok()必需给予参数s字符串，往后的调用则将参数s设置成NULL。每次调用成功则返回被分割出片段的指针。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main (){
    char str[11000];
    int a[11000];
    while(scanf("%s",str)!=EOF){
    int len=strlen(str),ans=0;
    for(int i=0;i<len;++i){
        if(str[i]=='5'){
            ans++;
        }
        if(ans==len){
            printf("0\n");
            continue;
        }
    }
    char *p=strtok(str,"5");
    int j=0;
    while(p!=NULL){
        a[j++]=atoi(p);
        p=strtok(NULL,"5");
    }
    sort(a,a+j);
    for(int i=0;i<j-1;++i)
        printf("%d ",a[i]);
    printf("%d\n",a[j-1]);
    }
    return 0;
}

解题报告写得比较简单，大家不要嫌弃。加油加油

HDOJ
上一篇: hdu1026题解
下一篇: 【hdoj_1003】Max Sum

继续阅读