第一题 培训
题目描述
某培训机构的学员有如下信息：
姓名（字符串）
年龄（周岁，整数）
去年 NOIP 成绩（整数，且保证是 5的倍数）
经过为期一年的培训，所有同学的成绩都有所提高，提升了 20 %（当然 NOIP 满分是 600 分，不能超过这个得分）。
输入学员信息，请设计一个结构体储存这些学生信息，并设计一个函数模拟培训过程，其参数是这样的结构体类型，返回同样的结构体类型，并输出学员信息。
输入格式
第一行输入一个正整数 n，表示学员个数。
第二行开始往下 n 行。每行首先是一个字符串表示学员姓名，再是一个整数表示学员年龄，再是一个整数为去年 NOIP 成绩。
输出格式
输出 n 行，每行首先输出一个字符串表示学生姓名，再往后两个整数，表示经过一年的培训后学员的年龄和他们今年的 NOIP 成绩。以空格隔开。
样例 #1
样例输入 #1
3 kkksc03 24 0 chen_zhe 14 400 nzhtl1477 18 590
样例输出 #1
kkksc03 25 0 chen_zhe 15 480 nzhtl1477 19 600
提示
数据保证，1 ≤ n ≤ 5 。年龄为 0 ∼ 100 （含 0 与 100 ）的整数。成绩为 0 ∼ 600 （含 0 00 与 600）的 5的整倍数。
解题思路
1）非常简单的输入和判断。
2）今年的成绩如果没超过600，那就输出去年成绩的120% ，否则就输出600 。
参考代码
#include<bits/stdc++.h> using namespace std; int main() { string s; int n,a,b; cin>>n; for(int i=0;i<n;i++) { cin>>s>>a>>b; if((b+b/5)<=600) cout<<s<<" "<<a+1<<" "<<b+(b/5)<<endl; else cout<<s<<" "<<a+1<<" "<<600<<endl; } return 0; }
第二题 高精度减法
题目描述
高精度减法。
输入格式
两个整数 a , b（第二个可能比第一个大）。
输出格式
结果（是负数要输出负号）。
样例 #1
样例输入 #1
2 1
样例输出 #1
1
提示
20 % 数据 a , b在 long long 范围内；
100 % 数据 0 < a , b ≤
。
解题思路
1）用数组分别存储高精度数的每一位。
2）计算同一位的结果
3）继续计算下一位，直到运算结束
参考代码
#include<bits/stdc++.h> using namespace std; int compare(string s1,string s2); int main() { string str1,str2; int a[250],b[250],len1,len2; int i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); cin>>str1>>str2; len1=str1.length(); for(i=1;i<=len1;i++) a[i]=str1[len1-i]-'0'; len2=str2.length(); for(i=1;i<=len2;i++) b[i]=str2[len2-i]-'0'; if((compare(str1,str2))==0) { for(i=1;i<=len1;i++) { a[i]-=b[i]; if (a[i]<0) { a[i+1]--; a[i]+=10; } } len1++; while((a[len1]==0)&&(len1>1)) len1--; for(i=len1;i>=1;i--) cout<<a[i]; cout<<endl; } else { cout<<'-'; for(i=1;i<=len2;i++) { b[i]-=a[i]; if (b[i]<0) { b[i+1]--; b[i]+=10; } } b[0]++; while((b[len2]==0)&&(len2>1)) len2--; for(i=len2;i>=1;i--) cout<<b[i]; cout<<endl; } return 0; } int compare(string s1,string s2) { if(s1.length()>s2.length()) return 0; if(s1.length()<s2.length()) return 1; for(int i=0;i<=s1.length();i++) { if(s1[i]>s2[i]) return 0; if(s1[i]<s2[i]) return 1; } return 0; }
第三题 【模板】并查集
题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。
输入格式
第一行包含两个整数 N , M ,表示共有 N 个元素和 M 个操作。
接下来 M行，每行包含三个整数 Z i , X i , Y i 。
当 Z i = 1 时，将 X i 与 Y i所在的集合合并。
当 Z i = 2 时，输出 X i 与 Y i 是否在同一集合内，是的输出
Y ；否则输出 N 。
输出格式
对于每一个 Z i = 2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
样例 #1
样例输入 #1
4 7 2 1 2 1 1 2 2 1 2 1 3 4 2 1 4 1 2 3 2 1 4
样例输出 #1
N Y N Y
提示
对于 30 % 的数据，N ≤ 10，M ≤ 20。
对于 70 % 的数据，N ≤ 100 ，M ≤ 
。
对于 100 %的数据，1 ≤ N ≤ 
，1 ≤ M ≤ 2 × 
，1 ≤ X i , Y i ≤ N ，Z i ∈ { 1 , 2 }。
解题思路
1）并查集通过一个一维数组来实现，其本质是维护一个森林。
2）刚开始的时候，森林的每一个点都是孤立的，通过一些条件，合并成一颗树。
参考代码
#include<bits/stdc++.h> using namespace std; int f[10010]; int find(int x) { if(f[x]==x) return x; else return f[x]=find(f[x]); } void join(int x,int y) { f[find(x)]=find(y); return; } int main() { int n,m,a,b,c; cin>>n>>m; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++){ cin>>a>>b>>c; if(a==1) join(b,c); else if(find(b)==find(c)) cout<<"Y"<<endl; else cout<<"N"<<endl; } return 0; }
第四题 亲戚
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x和 y 是亲戚，y 和 z 是亲戚，那么 x和 z也是亲戚。如果 x，y 是亲戚，那么 x的亲戚都是 y的亲戚，y 的亲戚也都是 x 的亲戚。
输入格式
第一行：三个整数 n , m , p ，（n , m , p ≤ 5000 ），分别表示有 n个人，m个亲戚关系，询问 p对亲戚关系。
以下 m行：每行两个数 M i，M j ，1 ≤ M i , M j ≤ N , M j≤N，表示 M i 和 M j具有亲戚关系。
接下来 p 行：每行两个数 P i , P j ，询问 P i 和 P j是否具有亲戚关系。
输出格式
p 行，每行一个 Yes 或 No。表示第 i个询问的答案为“具有”或“不具有”亲戚关系。
样例 #1
样例输入 #1
6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6
样例输出 #1
Yes Yes No
解题思路
1）简单的并查集的应用，和上面没太大的变化。
参考代码
#include<bits/stdc++.h> using namespace std; int f[10010]; int fd(int x) { if(f[x]==x) return x; else return f[x]=fd(f[x]); } void hb(int x,int y) { f[fd(y)]=fd(x); return ; } int main() { int n,m,q,a,b,c,d; cin>>n>>m>>q; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { cin>>c>>d; hb(c,d); } for(int i=1;i<=q;i++) { cin>>a>>b; if(fd(a)==fd(b)) printf("Yes\n"); else printf("No\n"); } return 0; }
