天梯赛训练赛（1.14-1.16）
1、L1-001 Hello World (5 分)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
printf("Hello World!");
return 0;
}
2、L1-002 打印沙漏 (20 分)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n;
char ch;
int main(){
scanf("%d %c",&n,&ch);
int p=pow((n+1)/2,1.0/2);//2*p-1为行数
for(int i=p;i>=1;i--)
{
for(int j=1;j<=p-i;j++) printf(" ");
for(int j=2*i-1;j>=1;j--){
printf("%c",ch);
}
printf("\n");
}
for(int i=2;i<=p;i++)
{
for(int j=1;j<=p-i;j++) printf(" ");
for(int j=2*i-1;j>=1;j--){
printf("%c",ch);
}
printf("\n");
}
int mod=n-(p*p*2-1);
printf("%d",mod);
return 0;
}
3、L1-003 个位数统计 (15 分)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstring>
using namespace std;
string s;
map<char,int> mp;
map<char,int>::iterator it;
int main(){
cin>>s;
for(int i=0;i<s.length();i++){
mp[s[i]]++;
}
for(it=mp.begin();it!=mp.end();it++){
cout<<it->first<<":"<<it->second<<endl;
}
return 0;
}
4、L1-004 计算摄氏温度 (5 分)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstring>
using namespace std;
int n;
int main(){
scanf("%d",&n);
printf("Celsius = %d",5*(n-32)/9);
return 0;
}
5、L1-005 考试座位号 (15 分)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#include<cstring>
using namespace std;
struct student{
string s;
int a;
int b;
}stu[1005];
map<int,student> mp;
int n,m,a;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>stu[i].s>>stu[i].a>>stu[i].b;
mp[stu[i].a]=stu[i];
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d",&a);
cout<<mp[a].s<<" "<<mp[a].b<<endl;
}
return 0;
}
6、L1-006 连续因子 (20 分)
解题思路：
枚
举
N
所
有
≤
n
的
因
子
枚举 N 所有 ≤\sqrt{n} 的因子
枚举N所有≤n
?的因子
，以每个因子为连续因子的左端点，不断 +1 寻找合法的最大右端点，并记录最大长度下的最小序列。如果 N 是质数，那么其最长连续因子的个数为 1，即其本身。
（1）1 不算在内。
（2）N 的连续因子的乘积也必须是 N 的因子。例如 N=12，那么 2*3 和 3*4 都是合法的，但 2*3*4 不合法，因为其结果不是 N 的因子。
#include<bits/stdc++.h>
using namespace std;
bool isprime(int n){
int m=sqrt(n);
for(int i=2;i<=m;i++){
if(n%i==0) return 0;
}
return 1;
}
int ansl=-1,ansr=-2,n;
int main(){
scanf("%d",&n);
if(isprime(n)){
printf("1\n%d",n);
return 0;
}
int m=sqrt(n);
for(int i=2;i<=m;i++){
int j=i,t=n;
while(t%j==0){
t/=j;
j++;
}
if(j-i>ansr-ansl+1){
ansl=i;
ansr=j-1;
}
}
printf("%d\n",ansr-ansl+1);
for(int i=ansl;i<ansr;i++){
printf("%d*",i);
}
printf("%d",ansr);
return 0;
}
7、L1-007 念数字 (10 分)
#include<bits/stdc++.h>
using namespace std;
string s;
map<char,string> mp;
int main(){
mp['0']="ling";
mp['1']="yi";
mp['2']="er";
mp['3']="san";
mp['4']="si";
mp['5']="wu";
mp['6']="liu";
mp['7']="qi";
mp['8']="ba";
mp['9']="jiu";
mp['-']="fu";
cin>>s;
for(int i=0;i<s.length()-1;i++){
cout<<mp[s[i]]<<" ";
}
cout<<mp[s[s.length()-1]];
return 0;
}
8、L1-008 求整数段和 (10 分)
#include<bits/stdc++.h>
using namespace std;
int a,b,cnt;
int main(){
scanf("%d%d",&a,&b);
for(int i=a;i<=b;i++){
printf("%5d",i);
cnt++;
if(cnt%5==0)printf("\n");
}
if(cnt%5) printf("\n");
printf("Sum = %d",(a+b)*(b-a+1)/2);
return 0;
}
9、L1-009 N个数求和 (20 分)
其实就是模拟相加后约分的过程
#include<bits/stdc++.h>
using namespace std;
int n,a,b,c,d=1;//c为分子，d为分母，i=1时，c/d=0/1
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d/%d",&a,&b);
c=c*b+a*d;//新分子
d=b*d;//新分母
int g=__gcd(c,d);//c和d的最大公约数
c/=g;//约分
d/=g;//约分
}
if(c==0||c/d!=0) printf("%d",c/d);
if(c%d!=0&&c/d!=0) printf(" ");
if(c%d!=0) printf("%d/%d",c%d,d);
return 0;
}
10、L1-010比较大小
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main(){
for(int i=1;i<=3;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+1+3);
for(int i=1;i<=2;i++){
printf("%d->",a[i]);
}
printf("%d",a[3]);
return 0;
}
11、L2-001 紧急救援 (25 分)
经典的最短路径模板题，找到了一篇说的比较好的文章紧急救援
12、L2-002 链表去重 (25 分)
用结构体模拟 每个结点的地址为结构体的下标 价值为w 下一个结点为next 按照题意模拟
#include <bits/stdc++.h>
using namespace std;
struct node{
int w;
int next;
}node[100005];
int vis[100005],ans1[100005],ans2[100005];
int head,n,a,cnt1,cnt2;
int main(){
scanf("%d%d",&head,&n);
for(int i=1;i<=n;i++){
scanf("%d",&a);
scanf("%d%d",&node[a].w,&node[a].next);
}
for(int i=head;i!=-1;i=node[i].next){
if(vis[abs(node[i].w)]==0){
vis[abs(node[i].w)]=1;
ans1[++cnt1]=i;
}else{
ans2[++cnt2]=i;
}
}
for(int i=1;i<=cnt1;i++){
if(i==cnt1) printf("%05d %d -1\n",ans1[i],node[ans1[i]].w);
else printf("%05d %d %05d\n",ans1[i],node[ans1[i]].w,ans1[i+1]);
}
for(int i=1;i<=cnt2;i++){
if(i==cnt2) printf("%05d %d -1\n",ans2[i],node[ans2[i]].w);
else printf("%05d %d %05d\n",ans2[i],node[ans2[i]].w,ans2[i+1]);
}
return 0;
}
13、L2-003 月饼 (25 分)
#include <bits/stdc++.h>
using namespace std;
struct yb1{
double sum;
double total;
double price;
}yb[10005];
bool cmp(yb1 x,yb1 y){
return x.price>y.price;
}
int n,d;
double ans;
int main(){
scanf("%d%d",&n,&d);
for(int i=1;i<=n;i++){
scanf("%lf",&yb[i].sum);
}
for(int i=1;i<=n;i++){
scanf("%lf",&yb[i].total);
yb[i].price=yb[i].total/yb[i].sum;
}
sort(yb+1,yb+1+n,cmp);
for(int i=1;i<=n;i++){
if(d>yb[i].sum){
ans+=yb[i].total;
d-=yb[i].sum;
}else{
ans+=yb[i].price*d;
break;
}
}
printf("%.2lf",ans);
return 0;
}
14、L2-004 这是二叉搜索树吗？ (25 分)
因为前序遍历是根左右，所以在插入某个孩子节点时，它的父节点肯定已经被插入了，又由于搜索树的限制关系（小的左边，大的右边），所以可以确定一棵唯一的二叉搜索树，然后对其进行两种不同的前序遍历，再分别与题目所给的序列比较即可。
#include<bits/stdc++.h>
using namespace std;
struct node{
node *l,*r;
int data;
};
int s1[1005],s2[1005],cnt,n,a[10005];;
vector<int> ans;
node *build(node *root,int x){
if(root==NULL){
root=new node();
root->l=root->r=NULL;
root->data=x;
}else if(x<root->data){
root->l=build(root->l,x);
}else{
root->r=build(root->r,x);
}
return root;
}
//正常前序遍历
void qian1(node *root){
if(root==NULL) return;
s1[++cnt]=root->data;
qian1(root->l);
qian1(root->r);
}
//左右颠倒的前序
void qian2(node *root){
if(root==NULL) return;
s2[++cnt]=root->data;
qian2(root->r);
qian2(root->l);
}
//正常后序
void hou1(node *root){
if(root==NULL) return;
hou1(root->l);
hou1(root->r);
ans.push_back(root->data);
}
//左右颠倒的后序
void hou2(node *root){
if(root==NULL) return;
hou2(root->r);
hou2(root->l);
ans.push_back(root->data);
}
//比较两个序列是否完全相同
bool judge(int *s){
for(int i=1;i<=n;i++){
if(s[i]!=a[i]) return false;
}
return true;
}
int main(){
scanf("%d",&n);
node *root=NULL;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
root=build(root,a[i]);
}
qian1(root);
cnt=0;
qian2(root);
if(judge(s1)){
hou1(root);
printf("YES\n");
for(int i=0;i<n;i++){
printf("%d%c",ans[i],i==n-1?'\n':' ');
}
}else if(judge(s2)){
hou2(root);
printf("YES\n");
for(int i=0;i<n;i++){
printf("%d%c",ans[i],i==n-1?'\n':' ');
}
}else{
printf("NO");
}
return 0;
}
15、L2-005 集合相似度 (25 分)
题目大意：输入n个集合，再输入k个询问，每个询问输入两个集合的编号，计算出这两个集合的集合相似度，而集合相似度就是用两个集合都有的不相等整数个数（即两个集合的交集的不重复元素个数）除以两个集合一共有的不相等整数个数（即两个集合并集的不重复元素个数）再乘100%
解题思路：利用c++stl中的set，补充一下，里面的find函数，是在集合里挨个查找某个数，例如，如果在集合s里查找x，就是s.find(x)，如果找到就返回该数的位置，找不到就返回s.end()
#include<bits/stdc++.h>
using namespace std;
set<int> s[55];
set<int>::iterator it;
int n,m,k,a,b;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m);
for(int j=1;j<=m;j++){
scanf("%d",&a);
s[i].insert(a);
}
}
scanf("%d",&k);
while(k--){
scanf("%d%d",&a,&b);
int sum1=s[a].size();
int sum2=s[b].size();
int sum3=0;
for(it=s[a].begin();it!=s[a].end();it++){
if(s[b].find(*it)!=s[b].end()) sum3++;
}
printf("%.2lf%%\n",1.0*sum3/(sum1+sum2-sum3)*100);
}
return 0;
}
|