随笔-68  评论-10  文章-0  trackbacks-0
 
UVa 112 - Tree Summing
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=48
注意：1、有负数；2、空树答案为no.
版本一：
#include <iostream>
using namespace std;

bool proc_tree(int sum, int des, bool &chld)
{
    char c;
    int t;
    bool lchld, rchld;
    cin >> c;
    if(cin >> t)
    {
        sum += t;
        chld = true;
        bool flag = proc_tree(sum, des, lchld) | proc_tree(sum, des, rchld); //此处若用||，可能会因为第一个操作数为真而不执行第二个操作数。
        cin >> c;
        if(!lchld && !rchld) return sum == des;  //如果是叶子节点。
        else return flag;
    }
    else
    {
        chld = false;
        cin.clear();
        cin >> c;
        return false;
    }
}

int main()
{
    int des;
    while(cin >> des)
    {
        bool chld;
        cout << (proc_tree(0, des, chld) ? "yes" : "no") << endl;
    }
    return 0;
}



版本二：递归建树 + 搜索
#include <iostream>
using namespace std;
struct Node
{
    int val;
    int left, right;
    Node(): left(-1), right(-1) {}
};
int cnt, des;
Node tree[10000];

int buildTree()
{
    char c;
    int t;
    cin >> c;
    if(cin >> t)
    {
        int tmp = ++cnt;
        tree[tmp].val = t;
        tree[tmp].left = buildTree();
        tree[tmp].right = buildTree();
        cin >> c;
        return tmp;
    }
    cin.clear();
    cin >> c;
    return -1;
}

bool dfs(int idx, int sum)
{
    if(idx == -1) return false;
    sum += tree[idx].val;
    if(tree[idx].left == -1 && tree[idx].right == -1)
    {
        return sum == des;
    }
    return dfs(tree[idx].left, sum) || dfs(tree[idx].right, sum);
}

void reset()
{
    for(int i = 0; i <= cnt; ++ i)
    {
        tree[i].left = -1;
        tree[i].right = -1;
    }
}

int main()
{
    while(cin >> des)
    {
        cnt = -1;
        int head = buildTree();
        cout << (dfs(head, 0) ? "yes" : "no") << endl;
        reset();
    }
    return 0;
}
posted @ 2011-11-24 21:50 wuxu 阅读(536) | 评论 (0) | 编辑 收藏
UVa 540 - Team Queue
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=481
这道题主要是理解题意。假设有A、B两个班的人到售票处买火车票需要排队，那么每去一个人就站在队列中该班的最后一个人的后面；如果某人是班上第一个去的，则站在队列末尾。相应的每个班对应team, 每个人对应team中的元素，那个排队队列就是题目中的queue.
#include <iostream>
#include <cstdio>
#include <list>
#include <iterator>
#include <list>
using namespace std;

int t;
int ele[1000000];   //记录元素(element)所在的team.
list<int> lst;  //排队队列
list<int>::iterator team[1001]; //指向每个team在lst中排最后一个的元素的位置。若lst中没有team中的元素，则指向lst.end().

int main()
{
    int ca = 0;
    while(cin >> t && t)
    {
        lst.clear();
        int num, tmp;
        for(int i = 1; i <= t; ++i)
        {
            team[i] = lst.end();
            cin >> num;
            for(int j = 0; j < num; ++j)
            {
                cin >> tmp;
                ele[tmp] = i;
            }
        }
        cout << "Scenario #" << ++ca << endl;
        string s;
        while(cin >> s && s != "STOP")
        {
            if(s == "ENQUEUE")
            {
                cin >> tmp;
                if(team[ele[tmp]] != lst.end())
                {
                    ++team[ele[tmp]];
                    team[ele[tmp]] = lst.insert(team[ele[tmp]], tmp);
                }
                else
                {
                    team[ele[tmp]] = lst.insert(team[ele[tmp]], tmp);
                }
            }
            else if(s == "DEQUEUE")
            {
                int top = lst.front();
                if(team[ele[top]] == lst.begin())
                {
                    team[ele[top]] = lst.end();
                }
                lst.pop_front();
                cout << top << endl;
            }
        }
        cout << endl;
    }
    return 0;
}

posted @ 2011-11-24 15:38 wuxu 阅读(862) | 评论 (0) | 编辑 收藏
UVa 11234 - Expressions
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2175
#include <iostream>
#include <string>
#include <stack>
#include <queue>
#include <cctype>
#include <algorithm>
using namespace std;

struct Node
{
    char c;
    int num, left, right;
    Node():left(-1), right(-1) {}
};

int main()
{
    int T;
    string s;
    cin >> T;
    while(T--)
    {
        cin >> s;
        Node tree[10005];
        stack<Node> st;
        for(int i = 0; i < s.size(); ++i) //建树
        {
            if(islower(s[i]))
            {
                tree[i].c = s[i];
                tree[i].num = i;
                st.push(tree[i]);
            }
            else
            {
                Node a, b, d;
                a = st.top();
                st.pop();
                b = st.top();
                st.pop();
                tree[i].c = s[i];
                tree[i].num = i;
                tree[i].left = b.num;
                tree[i].right = a.num;
                st.push(tree[i]);
            }
        }

        string ans;
        queue<Node> q;
        q.push(tree[s.size() - 1]);
        while(!q.empty())                 //层次遍历
        {
            Node tmp = q.front();
            ans += tmp.c;
            q.pop();
            Node x;
            if(tmp.left != -1)
            {
                x = tree[tmp.left];
                q.push(x);
            }
            if(tmp.right != -1)
            {
                x = tree[tmp.right];
                q.push(x);
            }
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    }
    return 0;
}
posted @ 2011-11-23 16:16 wuxu 阅读(256) | 评论 (0) | 编辑 收藏
UVa 11111 - Generalized Matrioshkas
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2052
#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <cmath>
#include <cstring>
using namespace std;

struct toy
{
    int x;
    int c;
    toy(int i = 0, int j = 0): x(i), c(j) {}
};
int n;
int a[500000];

bool isMatKa()
{
    stack<toy> st;
    for(int i = 0; i < n; ++i)
    {
        if(a[i] < 0)
            st.push(toy(a[i], a[i]));
        else
        {
            if(st.size() && st.top().x + a[i] == 0)
            {
                st.pop();
                if(st.size())
                {
                    toy t = st.top();
                    st.pop();
                    t.c += a[i];
                    if(t.c >= 0) return false;
                    st.push(t);
                }
                else if(i + 1 < n)
                    return false;
            }
            else return false;
        }
    }
    return st.empty();
}

int main()
{
    string s;
    while(getline(cin, s))
    {
        n = 0;
        stringstream str(s);
        while(str >> a[n]) ++n;
        bool isMK = true;
        isMK = isMatKa();
        if(!isMK)
            cout << ":-( Try again." << endl;
        else
            cout << ":-) Matrioshka!" << endl;
    }
    return 0;
}
posted @ 2011-11-23 13:27 wuxu 阅读(528) | 评论 (0) | 编辑 收藏
UVa 10152 - ShellSort
    题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=1093
    首先找到需要移动的字符串，方法如下：以初始序列为准，设初始序列下标为i, 目的序列下标为j, 从n-1开始，如果两下标对应的字符串相等，下标同时减一，否则仅初始序列下标减一。那么目的序列中还未被成功匹配的字符串就是需要移动的字符串。要使移动次数最少，显然应该按未被处理的目的序列中字符串逆序移动（输出）。   
#include <iostream>
#include <string>
using namespace std;

int k, n;
string org[210], des[210];

int main()
{
    int i, j;
    cin >> k;
    while(k--)
    {
        cin >> n;
        cin.ignore();
        for(i = 0; i < n; ++i)
        getline(cin, org[i]);
        for(i = 0; i < n; ++i)
        getline(cin, des[i]);
        for(i = j = n - 1; i >= 0; --i)
        {
            if(org[i] == des[j]) --j;
        }
        for( ; j >= 0; --j)
        cout << des[j] << endl;
        cout << endl;
    }
    return 0;
}
posted @ 2011-11-22 16:36 wuxu 阅读(851) | 评论 (0) | 编辑 收藏
UVa 133 - The Dole Queue
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=69
#include <iostream>
#include <list>
#include <iterator>
#include <iomanip>
using namespace std;

int N, k, m;
list<int> dole;

int main()
{
    while(cin >> N >> k >> m)
    {
        if(!(N || k || m)) break;
        dole.clear();
        for(int i = 1; i <= N; ++i)
        dole.push_back(i);
        list<int>::iterator is, ie;
        is = dole.begin();
        ie = dole.end();
        --ie;
        while(true)
        {
            for(int i = 1; i < k; ++i)
            {
                ++is;
                if(is == dole.end()) is = dole.begin();
            }
            for(int i = 1; i < m; ++i)
            {
                if(ie == dole.begin())
                {
                    ie = dole.end();
                }
                --ie;
            }
            if(is == ie)
            {
                cout << setw(3) << *is;
                if(dole.size() != 1)
                {
                    cout << ',';
                    is = dole.erase(is);

                    if(is == dole.begin())
                    {
                        ie = dole.end();
                        --ie;
                    }
                    else
                    {
                        ie = is;
                        --ie;
                    }
                    if(is == dole.end()) is = dole.begin();
                }
                else
                {
                    cout << endl;
                    break;
                }
            }
            else
            {
                cout << setw(3) << *is << setw(3) << *ie;
                list<int>::iterator it1 = is;
                list<int>::iterator it2 = ie;
                if(dole.size() != 2)
                {
                    cout << ',';
                    ++is;
                    while(is == it2) ++is;
                    ++ie;
                    while(ie == it1) ++ie;
                    dole.erase(it1);
                    dole.erase(it2);

                    if(is == dole.end()) is = dole.begin();
                    if(ie == dole.begin())
                    {
                        ie = dole.end();
                        --ie;
                    }
                    else --ie;
                }
                else
                {
                    cout << endl;
                    break;
                }
            }
        }
    }
    return 0;
}
posted @ 2011-11-19 22:12 wuxu 阅读(261) | 评论 (0) | 编辑 收藏
UVa 101 - The Blocks Problem
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=37
#include <iostream>
#include <sstream>
#include <vector>
#include <iterator>
#include <string>
#include <algorithm>
#include <cstddef>
using namespace std;

int n;
vector<int> block[30];

void move_onto(int ia, int a, int ib, int b)
{
    int tmp;
    tmp = block[ia].back();
    while(tmp != a)
    {
        block[ia].pop_back();
        block[tmp].push_back(tmp);
        tmp = block[ia].back();
    }
    tmp = block[ib].back();
    while(tmp != b)
    {
        block[ib].pop_back();
        block[tmp].push_back(tmp);
        tmp = block[ib].back();
    }
    block[ia].pop_back();
    block[ib].push_back(a);
}

void move_over(int ia, int a, int ib, int b)
{
    int tmp;
    tmp = block[ia].back();
    while(tmp != a)
    {
        block[ia].pop_back();
        block[tmp].push_back(tmp);
        tmp = block[ia].back();
    }
    block[ia].pop_back();
    block[ib].push_back(a);
}

void pile_onto(int ia, int a, int ib, int b)
{
    int tmp;
    tmp = block[ib].back();
    while(tmp != b)
    {
        block[ib].pop_back();
        block[tmp].push_back(tmp);
        tmp = block[ib].back();
    }
    vector<int>::iterator it;
    it = find(block[ia].begin(), block[ia].end(), a);
    block[ib].insert(block[ib].end(), it, block[ia].end());
    block[ia].erase(it, block[ia].end());
}

void pile_over(int ia, int a, int ib, int b)
{
    vector<int>::iterator it;
    it = find(block[ia].begin(), block[ia].end(), a);
    block[ib].insert(block[ib].end(), it, block[ia].end());
    block[ia].erase(it, block[ia].end());
}

void manipulate(const string &s)
{
    string s1, s2;
    int a, b, ia, ib;
    stringstream str(s);
    str >> s1 >> a >> s2 >> b;
    if(a == b) return;
    for(int i = 0; i < n; ++i)
    {
        for(size_t j = 0; j != block[i].size(); ++j)
        {
            if(block[i][j] == a) ia = i;
            if(block[i][j] == b) ib = i;
        }
    }
    if(ia == ib) return;
    if(s1 == "move" && s2 == "onto") move_onto(ia, a, ib, b);
    else if(s1 == "move" && s2 == "over") move_over(ia, a, ib, b);
    else if(s1 == "pile" && s2 == "onto") pile_onto(ia, a, ib, b);
    else pile_over(ia, a, ib, b);
}

int main()
{
    string s;
    cin >> n;
    for(int i = 0; i < n; ++i)
    block[i].push_back(i);
    cin.ignore();
    while(getline(cin, s) && s != "quit")
    manipulate(s);
    for(int i = 0; i < n; ++i)
    {
        cout << i << ':';
        for(size_t j = 0; j != block[i].size(); ++j)
        cout << ' ' << block[i][j];
        cout << endl;
    }
    return 0;
}
posted @ 2011-11-19 00:04 wuxu 阅读(327) | 评论 (0) | 编辑 收藏
UVa127 - "Accordian" Patience
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=63
此题若按每发一张牌就处理一次会TLE.
#include <iostream>
#include <cstddef>
#include <string>
#include <vector>
#include <stack>
using namespace std;

inline bool Match(const string &s1, const string &s2)
{
    return s1[0] == s2[0] || s1[1] == s2[1];
}

int main()
{
    string s;
    vector< stack<string> > piles;
    while(cin >> s && s != "#")
    {
        stack<string> tmp;
        tmp.push(s);
        piles.push_back(tmp);
        if(piles.size() == 52)
        {
            while(true)
            {
                size_t i;
                for(i = 0; i != piles.size(); ++i)
                {
                    if(i >=3 && Match(piles[i].top(), piles[i - 3].top()))
                    {
                        piles[i - 3].push(piles[i].top());
                        piles[i].pop();
                        break;
                    }
                    if(i >= 1 && Match(piles[i].top(), piles[i - 1].top()))
                    {
                        piles[i - 1].push(piles[i].top());
                        piles[i].pop();
                        break;
                    }
                }
                if(i == piles.size()) break;
                else if(piles[i].empty())
                {
                    piles.erase(piles.begin() + i);
                }
            }
            cout << piles.size() << (piles.size() == 1 ? " pile remaining:" : " piles remaining:");
            for(size_t i = 0; i != piles.size(); ++i) cout << ' ' << piles[i].size();
            cout << endl;

            piles.clear();
        }
    }
    return 0;
}
posted @ 2011-11-15 00:03 wuxu 阅读(495) | 评论 (0) | 编辑 收藏
POJ 1220 NUMBER BASE CONVERSION（大数进制转换）
题目链接：http://poj.org/problem?id=1220
#include<iostream>
#include<string>
using namespace std;
string idx = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 

//将字符转换为对应的数字 
inline int getValue(char ch)
{
    if(ch >= '0' && ch <= '9') return ch - '0';
    else if(ch >= 'A' && ch <= 'Z') return ch - 'A' + 10;
    else return ch - 'a' + 36;
}

//将s由from进制转换为to进制 
string change(string s, int from, int to)
{
    string res;
    int sum, remainder;
    do
    {
        remainder = sum = 0;
        for(int i = 0; i < s.size(); ++i)
        {
            remainder = remainder * from + getValue(s[i]);
            s[i] = idx[remainder / to];
            sum += getValue(s[i]);
            remainder %= to;
        }
        res = idx[remainder] + res;
    }while(sum);
    return res;
}

int main()
{
    string s;
    int t, from, to;
    cin >> t;
    while(t--)
    {
        cin >> from >> to >> s;
        cout << from << ' ' << s << endl;
        cout << to << ' ' << change(s, from, to) << endl << endl;
    }
    return 0;
}
posted @ 2011-10-21 15:47 wuxu 阅读(265) | 评论 (0) | 编辑 收藏
UVa 10194 Football (aka Soccer)
     摘要: 题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=98&problem=1135&mosmsg=Submission+received+with+ID+9393629 Code highlighting ...  阅读全文
posted @ 2011-10-21 15:27 wuxu 阅读(244) | 评论 (0) | 编辑 收藏
仅列出标题
共7页: 1 2 3 4 5 6 7 
Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 wuxu