2010年5月19日
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 ("<i>%c", ch);
sym.push('c');
} else if (sym.top() == '^' || sym.top() == '_'){
printf ("<i>%c</i>%s", ch, (sym.top() == '^') ? "</sup>" : "</sub>");
sym.pop();
} else {
putchar(ch);
}
} else {
if (!sym.empty() && sym.top() == 'c') {
printf ("</i>");
sym.pop();
}
if (ch == '^' || ch == '_') {
sym.push(ch);
printf ("%s", ch == '^' ? "<sup>" : "<sub>");
} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
printf (" %c ", ch);
} else if (ch == '{') {
sym.push('{');
} else if (ch == '}') {
sym.pop();
printf ("%s", sym.top() == '^' ? "</sup>" : "</sub>");
sym.pop();
} else if (isdigit(ch)) {
putchar(ch);
if (!sym.empty() && (sym.top() == '^' || sym.top() == '_')) {
printf ("%s", (sym.top() == '^') ? "</sup>" : "</sub>");
sym.pop();
}
} else {
putchar(ch);
}
}
}
if (!sym.empty()) {
printf ("</i>");
sym.pop();
}
putchar('\n');
getchar();
}
return 0;
}
2010年5月16日
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;
}
2010年5月15日
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;
}
2010年5月13日
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;
}
2010年5月12日
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;
}
2010年5月11日
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;
}
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;
}
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;
}
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;
}
2010年5月7日
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;
}