C++博客-Willing's Blog

SGU-340 Tex2HTML

Willing — Wed, 19 May 2010 09:12:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=340

将tex格式转为HTML格式,这道题主要就是考逻辑清不清晰还有栈的应用.

#include <cstdio>
#include <stack>
#include <cctype>

using namespace std;

int main(void) {
    char ch;
    stack<char> sym;
    while ((ch = getchar()) != EOF) {
        while ((ch = getchar()) != '$') {
            if (ch == ' ') {
                continue;
            }
            if (isalpha(ch)) {
                if (sym.empty() || sym.top() == '{') {
                    printf ("%c", ch);
                    sym.push('c');
                } else if (sym.top() == '^' || sym.top() == '_'){
                    printf ("%c%s", ch, (sym.top() == '^') ? "" : "");
                    sym.pop();
                } else {
                    putchar(ch);
                }
            } else {
                if (!sym.empty() && sym.top() == 'c') {
                    printf ("");
                    sym.pop();
                }
                if (ch == '^' || ch == '_') {
                    sym.push(ch);
                    printf ("%s", ch == '^' ? "" : "");
                } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                    printf (" %c ", ch);
                } else if (ch == '{') {
                    sym.push('{');
                } else if (ch == '}') {
                    sym.pop();
                    printf ("%s", sym.top() == '^' ? "" : "");
                    sym.pop();
                } else if (isdigit(ch)) {
                    putchar(ch);
                    if (!sym.empty() && (sym.top() == '^' || sym.top() == '_')) {
                        printf ("%s", (sym.top() == '^') ? "" : "");
                        sym.pop();
                    }
                } else {
                    putchar(ch);
                }
            }
        }
        if (!sym.empty()) {
            printf ("");
            sym.pop();
        }
        putchar('\n');
        getchar();
    }
    return 0;
}

Willing 2010-05-19 17:12 发表评论

SGU-397 Text Editor

Willing — Sun, 16 May 2010 06:52:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=397

模拟编辑器的操作，给出一个字符串，字符如果是'L'代表光标向左移动，'R'代表向右移动，如果到了最左或最右则不再移动，如果是其他字符则直接在光标处插入。
用链表处理就比较好了。因为如果用数组或连续分配的内存的话那么每次在中间或开头插入都要将后面的字符向右移动，操作起来会比较慢。文本编辑器的实现一般也是用类似链表的这种结构。

#include <cstdio>
#include <cstring>
#include <list>

using namespace std;

char org[1000001];

int main(void) {
    list<char> word;
    scanf ("%s", org);
    int i;
    int len = strlen(org);
    list<char>::iterator it = word.begin();
    for (i = 0; i < len; ++i) {
        if (org[i] == 'L') {
            if (it != word.begin()) {
                --it;
            }
        } else if (org[i] == 'R') {
            if (it != word.end()) {
                ++it;
            }
        } else {
            word.insert(it, org[i]);
        }
    }
    for (it = word.begin(); it != word.end(); ++it) {
        printf ("%c", *it);
    }
    printf ("\n");
    return 0;
}

Willing 2010-05-16 14:52 发表评论

SGU-207 Robbers

Willing — Sat, 15 May 2010 03:24:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=207

大致翻译：n个强盗去抢劫银行得到m个金币，抢劫前他们先确定好了分配方案，每个人按比例Xi/Y分配，X1+X2+..Xn = Y，m可能不能被Y整除，所以实际分配可能会有不公平，假设第i个强盗分配到Ki个金币，定义不公平度为|Xi/Y-Ki/m|，给出了n,m,Y,Xi，求出Ki，使得不公平度的总和最小
首先不公平度乘以Y*m不会影响结果，得到Xi*m - Y*Ki。则Ki必定取值[Xi*m/Y]或[Xi*m/Y]+1（怎样证明我也不知道。。感觉是这样。）
那么可以先让每个强盗先分到[Xi*m/Y]个金币，然后再按不公平度的大小排序（最大的排前面），让排在前面的强盗分别得到1个金币（直到金币分完）
其实就是贪心了，每次让强盗再得到1个金币都让不公平度最大程度地减小。

#include <stdio.h>
#include <stdlib.h>

typedef struct tagNode {
    int k;
    int b;
    int i;
} node;

int cmp1(const void* a, const void* b) {
    node* pa = (node*)a;
    node* pb = (node*)b;
    return pb->b - pa->b;
}

int cmp2(const void* a, const void* b) {
    node* pa = (node*)a;
    node* pb = (node*)b;
    return pa->i - pb->i;
}

int main(void) {
    int n, m, y;
    scanf ("%d%d%d", &n, &m, &y);
    int x[1000];
    node h[1000];
    int i, total = m;
    for (i = 0; i < n; ++i) {
        scanf ("%d", x+i);
        h[i].k = m*x[i]/y;
        h[i].b = m*x[i]%y;
        h[i].i = i;
        total -= h[i].k;
    }
    qsort(h, n, sizeof(h[0]), cmp1);
    i = 0;
    while (total--) {
        h[i++].k++;
    }
    qsort(h, n, sizeof(h[0]), cmp2);
    printf ("%d", h[0].k);
    for (i = 1; i < n; ++i) {
        printf (" %d", h[i].k);
    }
    printf ("\n");
    return 0;
}

Willing 2010-05-15 11:24 发表评论

SGU-406 Goggle

Willing — Wed, 12 May 2010 17:00:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=406

判断所给的序列是否在数据库的序列中，-号表示排除，例如1,-2,3不在序列1，2，3，4中，因为-2排除了2，简单地判断即可。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

int main(void) {
    int n, m;
    scanf ("%d%d", &n, &m);
    int seq[10][11];
    int i, j;
    for (i = 0; i < n; ++i) {
        scanf ("%d", seq[i]);
        for (j = 1; j <= seq[i][0]; ++j) {
            scanf ("%d", seq[i]+j);
        }
    }
    int search[11];
    int k, p, q;
    bool can;
    for (i = 0; i < m; ++i) {
        scanf ("%d", search);
        for (j = 1; j <= search[0]; ++j) {
            scanf ("%d", search+j);
        }
        int count = 0;
        int record[10];
        for (k = 0; k < n; ++k) {
            can = false;
            for (p = 1; p <= search[0]; ++p) {
                can = false;
                for (q = 1; q <= seq[k][0]; ++q) {
                    if (abs(search[p]) == seq[k][q]) {
                        can = true;
                        break;
                    }
                }
                if ((!can && search[p] >= 0) || (can && search[p] < 0)) {
                    can = false;
                    break;
                }
                if (!can && search[p] < 0) {
                    can = true;
                }
            }
            if (can) {
                record[count++] = k;
            }
        }
        printf ("%d\n", count);
        for (k = 0; k < count; ++k) {
            printf ("%d", seq[record[k]][0]);
            for (p = 1; p <= seq[record[k]][0]; ++p) {
                printf (" %d", seq[record[k]][p]);
            }
            printf ("\n");
        }
    }
    return 0;
}

Willing 2010-05-13 01:00 发表评论

SGU-460 Plural Form of Nouns

Willing — Wed, 12 May 2010 15:29:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=460

将单数形式的单词变为复数然后输出

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

int main(void) {
    int n;
    scanf ("%d", &n);
    int i;
    char word[30];
    int len;
    for (i = 0; i < n; ++i) {
        bool es = true;
        scanf ("%s", word);
        len = strlen(word);
        if ((word[len-1] == 'h' && word[len-2] == 'c') ||
        word[len-1] == 'x' || word[len-1] == 's' || word[len-1] == 'o') {
            /*blank line*/
        } else if (word[len-1] == 'f') {
            word[len-1] = 'v';
        } else if (word[len-1] == 'e' && word[len-2] == 'f') {
            word[len-2] = 'v';
            word[len-1] = '\0';
        } else if (word[len-1] == 'y') {
            word[len-1] = 'i';
        } else {
            es = false;
        }
        printf ("%s", word);
        if (es) {
            printf ("es\n");
        } else {
            printf ("s\n");
        }
    }
    return 0;
}

Willing 2010-05-12 23:29 发表评论

SGU-404 Fortune-telling with camomile

Willing — Tue, 11 May 2010 08:11:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=404

就是拿一朵花不断地摘然后不停地数“Love", "Doesnt"...
取模就可以了

#include <stdio.h>

int main(void) {
    int n, m;
    char s[101][101];
    scanf ("%d%d", &n, &m);
    int i;
    for (i = 1; i <= m; ++i) {
        scanf ("%s", s[i]);
    }
    int love = (n%m == 0) ? m : n%m;
    printf("%s\n", s[love]);
    return 0;
}

Willing 2010-05-11 16:11 发表评论

SGU-403 Scientific Problem

Willing — Tue, 11 May 2010 06:10:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=403

给出一个数x,求出数n使得n是n之前所有数(包括n)的总和的1/x，由求和公式直接推出n=2*x+1

#include <stdio.h>

int main(void) {
    int x;
    scanf ("%d", &x);
    printf ("%d\n", 2*x+1);
    return 0;
}

Willing 2010-05-11 14:10 发表评论

SGU-302 BHTML 1.0

Willing — Tue, 11 May 2010 06:07:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=302

标签匹配的问题很多时候都用到栈。

#include <cstdio>
#include <cctype>
#include <stack>

using namespace std;

int main(void) {
    char s[1001];
    scanf ("%s", s);
    stack<bool> sta;
    char* t = s;
    while (*t) {
        if (*t == '<' && *(t+1) != '/') {
            if (*(t+1) == 'U') {
                sta.push(0);
                t += 4;
            } else {
                sta.push(1);
                t += 6;
            }
        } else if (*t == '<') {
            if (*(t+2) == 'U') {
                t += 5;
            } else {
                t += 7;
            }
            sta.pop();
        } else {
            if (sta.empty()) {
                putchar(*t++);
            } else if (sta.top()) {
                putchar(tolower(*t++));
            } else {
                putchar(toupper(*t++));
            }
        }
    }
    putchar('\n');
    return 0;
}

Willing 2010-05-11 14:07 发表评论

SGU-274 Spam-filter

Willing — Tue, 11 May 2010 06:05:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=274

判断一个所给字符串是不是有效的email地址，要注意的是题目给的邮箱地址可能中间含有空格。所以要用getline，我用getchar()不知道哪里错了总是TLE on test1。

#include <cctype>
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

bool word(char* s, int a, int b) {
    if (a > b) {
        return false;
    } else {
        int i;
        for (i = a; i <= b; ++i) {
            if (!isalnum(s[i]) && s[i] != '-' && s[i] != '_') {
                return false;
            }
        }
    }
    return true;
}

bool prefix(char* s, int a, int b) {
    if (a > b) {
        return false;
    }
    int i;
    for (i = b; i >= a; --i) {
        if (s[i] == '.') {
            break;
        }
    }
    return (i == a-1) ? word(s, a, b) : word(s, i+1, b) && prefix(s, a, i-1);
}

bool domain(char* s, int a, int b) {
    int i;
    for (i = a; i <= b; ++i) {
        if (!isalpha(s[i])) {
            return false;
        }
    }
    return (b-a)>=1 && (b-a)<=2;
}

bool suffix(char* s, int a, int b) {
    int i;
    for (i = b; i >= a; --i) {
        if (s[i] == '.') {
            break;
        }
    }
    return prefix(s, a, i-1) && domain(s, i+1, b);
}

bool address(char* s, int a, int b) {
    int i;
    for (i = a; i <= b; ++i) {
        if (s[i] == '@') {
            break;
        }
    }
    return prefix(s, a, i-1) && suffix(s, i+1, b);
}

int main(void) {
    char email[102];
    string s;
    int n;
    cin >> n;
    //scanf ("%d", &n);
    while (getchar() != '\n');
    while (n--) {
        getline(cin, s);
        strcpy(email, s.c_str());
        if (address(email, 0, strlen(email)-1)) {
            printf ("YES\n");
        } else {
            printf ("NO\n");
        }
    }
    return 0;
}

Willing 2010-05-11 14:05 发表评论

SGU-297 Fair-play

Willing — Fri, 07 May 2010 09:26:00 GMT

http://acm.sgu.ru/problem.php?contest=0&problem=297

什么也不说了，我专挑水题做的。

#include <stdio.h>

int main(void) {
    int n, m;
    scanf ("%d%d", &n, &m);
    int i, tmp, sum = 0;
    for (i = 0; i < m; ++i) {
        scanf ("%d", &tmp);
        sum += tmp;
    }
    printf ("%d\n", sum%n);
    return 0;
}

Willing 2010-05-07 17:26 发表评论