7.15天梯赛训练2

天梯赛训练2"/>

7.15天梯赛训练2

目录

• 总结
• 1.比较大小
• 2.N个数求和
• 3.A-B
• 4.计算指数
• 5. 计算阶乘和
• 6. 简单题
• 7. 跟奥巴马一起画方块
• 8. 查验身份证
• 9. 集合相似度
• 10.树的遍历
• 11. 家庭房产
• 12. 最长对称子串
• 13. 垃圾箱分布（未补题）
• 14. 迎风一刀斩（未补题）
• 15. 特殊堆栈

总结

1. 没做也没补的题目：
   1. （题10）树的遍历：二叉树这个就没怎么学，所以也没管这个题目到底难易程度如何，都先搁置了。要尽早地补二叉树的知识。
   2. （题13）垃圾箱分布：一个最短路问题呗，但是没信心在短时间内做出来，以最近的状态不看题解可能还解决不了自己的bug，所以先搁置。
   3. （题14）迎风一刀斩：题目都没看，主要是看了没人做出来，也是时间有限，所以战略性放弃。
2. 训练时部分正确的题目：
   1. （题9）集合相似度：靠啊，STL忘干净了啊。必须补一下STL的知识。
   2. （题15）特殊堆栈：还是STL。
3. 训练时做出来的题目：
   1. （题1）比较大小
   2. （题2）N个数求和
   3. （题3） A-B
   4. （题4） 计算指数
   5. （题5） 计算阶乘和
   6. （题6） 简单题
   7. （题7） 跟奥巴马一起画方块
   8. （题8） 查验身份证
   9. （题9） 最长对称子串

1.比较大小

2.N个数求和

传送门
有理数的相加，要提取出整数部分，还要将分子分母最简化，利用好最大公因数就能做。

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;int n, ans, ans_zi, ans_fen;
int zi[105], fen[105];
int dfs(int a, int b){if(b==0)    return a;return dfs(b, a % b);
}
int main(){scanf("%d", &n);for (int i = 0; i < n; i++)    scanf("%d/%d", zi + i, fen + i);ans_zi = zi[0], ans_fen = fen[0];for (int i = 1; i < n; i++){int mod = dfs(ans_fen, fen[i]);ans_zi = (ans_zi * fen[i] + zi[i] * ans_fen)/mod;ans_fen = ans_fen * fen[i] / mod;}ans = ans_zi / ans_fen;ans_zi %= ans_fen;int mod = dfs(ans_zi, ans_fen);ans_zi /= mod;ans_fen /= mod;if(ans && !ans_zi)    printf("%d\n", ans);else if(!ans && ans_zi)  printf("%d/%d\n", ans_zi, ans_fen);else if(!ans&&!ans_zi)    printf("0\n");else    printf("%d %d/%d\n", ans, ans_zi, ans_fen);return 0;
}

3.A-B

传送门
字符串相减，注意是B中出现过的字符，A中要全部删除。

#include<stdio.h>
#include<string.h>
int main(){char a[10005], b[10005];int flag[200];gets(a);gets(b);for (int i = 0; b[i]; i++)    flag[b[i]]++;for (int i = 0; a[i]; i++)    if(!flag[a[i]])    printf("%c", a[i]);return 0;
}

4.计算指数

5. 计算阶乘和

6. 简单题

7. 跟奥巴马一起画方块

8. 查验身份证

9. 集合相似度

传送门
！！！该好好巩固STL了！就是set的简单应用，不记得set当时真的磕了一段时间，而且只是部分正确。

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;int n, m, x, k, a, b;
int c1, c2, cnt;
set<int> s[55];
int main(){scanf("%d", &n);for (int i = 1; i <= n; i++){scanf("%d", &m);while(m--){scanf("%d", &x);s[i].insert(x);}}scanf("%d", &k);while(k--){scanf("%d%d", &a, &b);cnt = 0, c1 = s[a].size(), c2 = s[b].size();set<int>::iterator it;for (it = s[a].begin(); it != s[a].end(); it++){if(s[b].find(*it) != s[b].end())cnt++;}printf("%.2lf%\n", (double)cnt / (c1 + c2 - cnt) * 100);}return 0;
}

10.树的遍历

传送门

#include <iostream>
#include<queue>
using namespace std;int mid[70], post[70];
struct node{int lson,rson;
}f[70];int build(int lmid,int rmid,int lpost,int rpost){if(lmid>rmid) return 0;int root = post[rpost];int fa = lmid;while(mid[fa]!=root)    fa++;int len = fa - lmid;f[root].lson = build(lmid, fa - 1, lpost, lpost + len - 1);f[root].rson = build(fa + 1, rmid, lpost + len, rpost - 1);return root;
}void bfs(int x){queue <int> q;vector <int> v;q.push(x);while(!q.empty()){int w = q.front();q.pop();if(!w) break;v.push_back(w);if(f[w].lson) q.push(f[w].lson);if(f[w].rson) q.push(f[w].rson);}int len=v.size();printf("%d", v[0]);for (int i = 1; i < len; i++)printf(" %d", v[i]);return;
}int main(){int n;scanf("%d", &n);for (int i = 0; i < n; i++)scanf("%d", &post[i]);for (int i = 0; i < n; i++)scanf("%d", &mid[i]);int root = post[n - 1];build(0, n - 1, 0, n - 1);bfs(root);return 0;
}

11. 家庭房产

传送门
涉及结构体、并查集，归类起来比较麻烦。因为数据输入的时候有些编号可能重复出现，所以统计人数时要注意。然后就是个人状态的问题了吧，老是出现一些小错误，比如数组开的不够大，用到标记数组的时候直接越界；for循环的时候，范围的确定不严谨。甚至在数据输入部分都写不完整。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10005;int n, k, x;
int s[N];
int vis[N];
int flag[N];//vis和flag都是标记数组
struct node{int id, people;double num=0, area=0;//房子数量、面积
};
node per[N];//数据输入
node ans[N];//找到一个家庭中编号最小的，然后统计人数、房子总数量、总面积
node fam[N];//计算一个家庭的人均房子数量、人均面积。作为最后的数组用来输出int find(int a){    return s[a] == a ? a : s[a] = find(s[a]);}
int cmp(const node &a, const node &b){if(a.area==b.area)    return a.id < b.id;return a.area > b.area;
}void un(int a, int b){int fa = find(a), fb = find(b);if(fa > fb) s[fa] = fb;else        s[fb] = fa;
}//家人合并，找出家庭中编号最小的人员int main(){int id, ba, ma;scanf("%d", &n);for (int i = 0; i < N; i++)    s[i] = i;for (int i = 0; i < n; i++){scanf("%d %d %d", &id, &ba, &ma);per[i].id = id;vis[id] = 1;if(ba!=-1){ vis[ba] = 1;un(id, ba);}//注意-1代表父母去世，要先判断是否在世再合并if(ma!=-1){ vis[ma] = 1;un(id, ma);}scanf("%d", &k);for (int j = 0; j < k; j++){scanf("%d", &x);if(vis[x]!=-1){ vis[x] = 1;un(id, x);}//虽然样例中没有出现孩子去世的，但是为了谨慎起见也判断一下是否在世}double a, b;scanf("%lf%lf", &per[i].num, &per[i].area);}for (int i = 0; i < n; i++){int tem = find(per[i].id);ans[tem].id = tem;ans[tem].num += per[i].num;ans[tem].area += per[i].area;//统计房子总数和总面积}for (int i = 0; i < N; i++)if(vis[i])ans[find(i)].people++;int cnt = 0;for (int i = 0; i < N; i++){if(vis[i]){int tem = find(i);if(!flag[tem]){double people = (double)ans[tem].people;fam[cnt].id = tem;fam[cnt].people = ans[tem].people;fam[cnt].num = ans[tem].num / people;fam[cnt].area = ans[tem].area / people;cnt++;}flag[tem] = 1;   }}printf("%d\n", cnt);sort(fam, fam + cnt, cmp);for (int i = 0; i < cnt; i++)printf("%04d %d %.3lf %.3lf\n", fam[i].id, fam[i].people, fam[i].num, fam[i].area);return 0;
}

12. 最长对称子串

传送门
通过递归去求解呗，解法是知道的，但是在写的时候明显感觉到不知道怎么写代码，琢磨了好一阵子。并且最初的代码有一个测试点超时了，增加了这个if(j-i+1<ans) continue;

#include<stdio.h>
#include<string.h>
int ans;
char str[1005];
int jud(int i, int j, int len){if(i==j)        return len-1;else if(i+1==j)if(str[i]==str[j])      return len;else    return 0;else if(str[i]==str[j])    return jud(i + 1, j - 1, len + 2);return 0;
}
int main(){gets(str);int len = strlen(str);for (int i = 0; i < len; i++){for (int j = len - 1; j >= i; j--){if(j-i+1<ans)    continue;if(jud(i, j, 2)){if(ans < jud(i,j,2))ans = jud(i, j, 2);}}}printf("%d\n", ans);return 0;
}

13. 垃圾箱分布（未补题）

传送门
限制条件比较多的最短路问题，现在的水平应该能做，但是肯定要花比较长的时间去debug，因为时间有限也暂时搁置。

14. 迎风一刀斩（未补题）

传送门
看了题目直接逃跑好吧，也是先放着吧。

15. 特殊堆栈

传送门

又是STL的应用，真的需要去好好巩固一下。

#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<string>
using namespace std;stack<int>s;
vector<int>v;
int n, k;
string str;
int main(){scanf("%d", &n);while(n--){cin >> str;vector<int>::iterator it;if(str=="Push"){scanf("%d", &k);s.push(k);it = lower_bound(v.begin(), v.end(), k);v.insert(it, k);}else{if(v.empty()){printf("Invalid\n");}else{if(str=="Pop"){printf("%d\n", s.top());it = lower_bound(v.begin(), v.end(), s.top());v.erase(it);s.pop();}elseprintf("%d\n", v[(s.size() - 1) / 2]);}}}return 0;}