1. 字符串的反码
大水不解释
//2011年吉林大学计算机研究生机试题 字符串的反码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main() {
int n, t, p;
while(scanf("%d", &n), n) {
t = n; p = 0;
while(t > 0) {
p += t % 10;
t /= 10;
}
printf("%d ", p);
t = n * n; p = 0;
while(t > 0) {
p += t % 10;
t /= 10;
}
printf("%d\n", p);
}
return 0;
}
2. 数字之和
大水不解释
//2011年吉林大学计算机研究生机试题 数字之和
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main() {
int n, t, p;
while(scanf("%d", &n), n) {
t = n; p = 0;
while(t > 0) {
p += t % 10;
t /= 10;
}
printf("%d ", p);
t = n * n; p = 0;
while(t > 0) {
p += t % 10;
t /= 10;
}
printf("%d\n", p);
}
return 0;
}
3. 搬水果
贪心，每次取数目最少的两堆水果合并
无聊花了茫茫长时间回忆priority_queue。。。长久不用，重载运算符都不会写了。。有空复习C++去。。
//2011年吉林大学计算机研究生机试题 搬水果
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
struct Node {
int a;
bool operator<(const Node &b) const {
return a > b.a;
}
};
int main() {
int n, a, b, ans;
Node tp;
while(scanf("%d", &n), n) {
priority_queue<Node> que;
while(n--) {
scanf("%d", &a);
tp.a = a;
que.push(tp);
}
ans = 0;
while(que.size() > 1) {
a = que.top().a; que.pop();
b = que.top().a; que.pop();
ans += a + b;
tp.a = a + b;
que.push(tp);
}
printf("%d\n", ans);
}
return 0;
}
4. 堆栈的使用
STL stack水过
//2011年吉林大学计算机研究生机试题 堆栈的使用
#include<stack>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
int main() {
int q, a;
char ch[5];
while(scanf("%d", &q), q) {
stack<int> stk;
while(q--) {
scanf("%s", ch);
if(ch[0] == 'A') {
if(stk.empty()) puts("E");
else
printf("%d\n", stk.top());
}
else if(ch[0] == 'O') {
if(!stk.empty()) stk.pop();
}
else if(ch[0] == 'P') {
scanf("%d", &a);
stk.push(a);
}
}
puts("");
}
return 0;
}
5. 连通图
裸搜。。无聊回忆了下前向星~
//2011年吉林大学计算机研究生机试题 连通图
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 5010
#define M 5010
int n, m, e, ev[M], vis[N], q[N], head[N], nxt[M];
void addedge(int x, int y) {
ev[e] = y; nxt[e] = head[x];
head[x] = e++;
}
void BFS() {
int l = 0, r = 1, i;
q[0] = 1;
while(l < r) {
for(i = head[q[l]]; ~i; i = nxt[i]) {
if(!vis[ev[i]]) {
vis[ev[i]] = 1;
q[r++] = ev[i];
}
}
++l;
}
}
int main() {
int i, j;
while(scanf("%d %d", &n, &m), n | m) {
e = 0;
memset(head, -1, sizeof(head));
while(m--) {
scanf("%d %d", &i, &j);
addedge(i, j);
addedge(j, i);
}
memset(vis, 0, sizeof(vis));
BFS();
for(i = 1; i <= n; ++i) {
if(!vis[i]) break;
}
if(i <= n) puts("NO");
else
puts("YES");
}
return 0;
}