1136 A Delayed Palindrome（20 分）
题意：给定字符串A，判断A是否是回文串。若不是，则将A反转得到B，A和B相加得C，若C是回文串，则A被称为a delayed palindrome；否则继续迭代。
分析：根据题意模拟。
1、C++写法。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const int MAXN = 1000 + 10;
string A;
bool judge(string x){
int len = x.size();
for(int i = 0; i < len / 2; ++i){
if(x[i] != x[len - 1 - i]) return false;
}
return true;
}
string add(string x, string y){
string ans;
int lenx = x.size();
int leny = y.size();
int tmp = 0;
int i, j;
for(i = lenx - 1, j = leny - 1; i >= 0 && j >= 0; --i, --j){
tmp += x[i] - '0' + y[j] - '0';
ans += (tmp % 10) + '0';
tmp /= 10;
}
while(i >= 0){
tmp += x[i] - '0';
ans += (tmp % 10) + '0';
tmp /= 10;
--i;
}
while(j >= 0){
tmp += y[j] - '0';
ans += (tmp % 10) + '0';
tmp /= 10;
--j;
}
if(tmp > 0) ans += tmp + '0';
reverse(ans.begin(), ans.end());
return ans;
}
int main(){
while(cin >> A){
if(judge(A)){
printf("%s is a palindromic number.\n", A.c_str());
continue;
}
int cnt = 0;
while(1){
string B = A;
reverse(B.begin(), B.end());
string C = add(A, B);
printf("%s + %s = %s\n", A.c_str(), B.c_str(), C.c_str());
if(judge(C)){
printf("%s is a palindromic number.\n", C.c_str());
break;
}
++cnt;
if(cnt == 10){
printf("Not found in 10 iterations.\n");
break;
}
A = C;
}
}
return 0;
}
2、python写法。
def judge(x):
y = x[::-1]
if x == y: return True
return False
A = input()
if judge(A):
print(A, "is a palindromic number.")
else:
cnt = 0
while(True):
B = A[::-1]
C = int(A) + int(B)
C = str(C)
print(A, "+", B, "=", C)
if judge(C):
print(C, "is a palindromic number.")
break
cnt += 1
if cnt == 10:
print("Not found in 10 iterations.")
break
A = C
1137 Final Grading（25 分）
题意：为得到证书，首先online programming assignments要不少于200分，其次final grade要不少于60分。其中，final grade的计算方法为：若Gmid−term>Gfinal，则G=(Gmid−term×40%+Gfinal×60%)；否则，G=Gfinal。
分析：根据题意模拟。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
using namespace std;
const int MAXN = 100000 + 10;
struct Node{
string name;
double Gp, Gmid, Gfinal, G;
Node(){
Gp = Gmid = Gfinal = -1;
}
bool operator < (const Node&rhs)const{
return G > rhs.G || G == rhs.G && name < rhs.name;
}
}num[MAXN];
int cnt;
map<string, int> mp;
int getId(string x){
if(mp.count(x)) return mp[x];
return mp[x] = ++cnt;
}
int main(){
int P, M, N;
scanf("%d%d%d", &P, &M, &N);
string name;
double score;
for(int i = 0; i < P; ++i){
cin >> name >> score;
int id = getId(name);
num[id].Gp = score;
num[id].name = name;
}
for(int i = 0; i < M; ++i){
cin >> name >> score;
int id = getId(name);
num[id].Gmid = score;
num[id].name = name;
}
for(int i = 0; i < N; ++i){
cin >> name >> score;
int id = getId(name);
num[id].Gfinal = score;
num[id].name = name;
}
for(int i = 1; i <= cnt; ++i){
if(num[i].Gmid > num[i].Gfinal){
num[i].G = num[i].Gmid * 0.4 + num[i].Gfinal * 0.6;
}
else{
num[i].G = num[i].Gfinal;
}
num[i].G = round(num[i].G);
}
sort(num + 1, num + 1 + cnt);
for(int i = 1; i <= cnt; ++i){
if((int)num[i].Gp >= 200 && (int)num[i].G >= 60){
printf("%s %.0lf %.0lf %.0lf %.0lf\n", num[i].name.c_str(), num[i].Gp, num[i].Gmid, num[i].Gfinal, num[i].G);
}
}
return 0;
}
1138 Postorder Traversal（25 分）
题意：给定前序遍历和中序遍历，求后序遍历的第一个点。
分析：根据前序遍历和中序遍历的性质，递归建树，并记录后序遍历的值。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
using namespace std;
const int MAXN = 50000 + 10;
int preorder[MAXN], inorder[MAXN];
vector<int> ans;
void build(int pL, int pR, int iL, int iR, int root){
if(pL > pR) return;
int id = iL;
while(inorder[id] != root) ++id;
int cnt = id - iL;
build(pL + 1, pL + cnt, iL, id - 1, preorder[pL + 1]);
build(pL + cnt + 1, pR, id + 1, iR, preorder[pL + cnt + 1]);
ans.push_back(root);
}
int main(){
int N;
while(scanf("%d", &N) == 1){
for(int i = 0; i < N; ++i) scanf("%d", preorder + i);
for(int i = 0; i < N; ++i) scanf("%d", inorder + i);
int root = preorder[0];
build(0, N - 1, 0, N - 1, root);
printf("%d\n", ans[0]);
}
return 0;
}
1139 First Contact（30 分）
题意：给定N个人和M条关系，若A想和B联系，首先A在自己的朋友中联系与其同性别的C，C在自己的朋友中联系与B同性别的D，而且D和B也是朋友，求能使A和B互相联系的C和D。
分析：
1、由于用4位数字的ID表示一个人，负数为女，正数为男，且同一个人只可能有一个性别，所以，在用atoi函数将读取的ID转化为数字并取绝对值后，可保证每个人的ID互不相同。
2、枚举A的同性朋友i和B的同性朋友j，若i和j是朋友，则满足输出条件。
3、用map<int, map<int, bool> > isfriend判断两人是否为朋友。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<map>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
using namespace std;
const int MAXN = 10000 + 10;
vector<int> G[MAXN];
map<int, map<int, bool> > isfriend;
int cnt;
char x[10], y[10];
struct Node{
int x, y;
bool operator < (const Node&rhs)const{
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
}num[MAXN];
int main(){
int N, M;
scanf("%d%d", &N, &M);
while(M--){
scanf("%s%s", x, y);
int id1 = abs(atoi(x));
int id2 = abs(atoi(y));
isfriend[id1][id2] = isfriend[id2][id1] = true;
if(strlen(x) == strlen(y)){
G[id1].push_back(id2);
G[id2].push_back(id1);
}
}
int K;
scanf("%d", &K);
while(K--){
cnt = 0;
scanf("%s%s", x, y);
int id1 = abs(atoi(x));
int id2 = abs(atoi(y));
int len1 = G[id1].size();
int len2 = G[id2].size();
for(int i = 0; i < len1; ++i){
for(int j = 0; j < len2; ++j){
int tmpx = G[id1][i];
int tmpy = G[id2][j];
if(tmpx != id1 && tmpx != id2 && tmpy != id1 && tmpy != id2 && isfriend[tmpx][tmpy]){
num[++cnt].x = tmpx;
num[cnt].y = tmpy;
}
}
}
sort(num + 1, num + 1 + cnt);
printf("%d\n", cnt);
for(int i = 1; i <= cnt; ++i){
printf("%04d %04d\n", num[i].x, num[i].y);
}
}
return 0;
}