首页 > ACM题库 > HDU-杭电 > HDU 3029-Scales-模拟-[解题报告]HOJ
2014
02-27

HDU 3029-Scales-模拟-[解题报告]HOJ

Scales

问题描述 :

Give you a scale, a goods weigts m kilograms. And then give you some stones weighting 1, 3, 9, 27, …, 3^k. Of course, the number of different weights’ is only ONE.

Now put the goods on the left of scale. And then you should put some stones on two sides of scale to make the scale balanced.

输入:

An integer m, stands for the weights of the goods (0 ≤ m ≤ 100 000 000)

输出:

An integer m, stands for the weights of the goods (0 ≤ m ≤ 100 000 000)

样例输入:

42
30

样例输出:

3 3 9 27
1 81
0
2 3 27

题目连接:http://acm.hit.edu.cn/hoj/problem/view?id=3029

题目是一个XML格式的文本,要筛选出相应缩进的词条。

可以用栈来模拟这个过程。type = 0表示内容,1表示起始,2表示结束,其中1和2是对应关系。cur记录当前的缩进变化。

如:范例中的XML格式的type分别是101021102102202

另外注意string不能用scanf()读入,用char[]吧。结构体初始化时再转换成string较好。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

struct Word
{
    string str;
    int type;
    int offset;

    Word(){};
    Word(string s)
    {
        if(s[0]!='<')
        {
            type = 0;
            str = s;
        }
        else if(s[1] == '/')
        {
            type = 2;
            str = s.substr(2,s.length()-3);
        }
        else
        {
            type = 1;
            str = s.substr(1,s.length() - 4);
            offset = s[s.length()-2] - '0';
        }
    }
};

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int n,q;
    char c[105];
    while(scanf(" %d %d",&n,&q)!=EOF)
    {
        stack<Word> s;
        queue<Word> result;
        int cur = 0;
        int count = 0;

        for(int i=0;i<n;i++)
        {
            scanf(" %[^\n]s",c);//别忘了前面加个空格
            Word a(c);
            if(a.type == 1)
            {
                s.push(a);
                cur += a.offset;
                if(cur == q)
                {
                    count ++;
                    result.push(a);
                }
            }
            else if(a.type == 2)
            {
                cur -= s.top().offset;//这里犯过错误,原来写成了cur-+a.offset;
                s.pop();
            }
            getchar();
        }
        printf("%d\n",count);
        while(!result.empty())
        {
            printf("%s\n",result.front().str.c_str());
            result.pop();
        }
    }
    return 0;
}

参考:http://blog.csdn.net/niuox/article/details/8623432


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。