admin管理员组

文章数量:817321

2020天梯赛训练1 题目整理

7-1 比较大小 (10分)

题目链接:
7-1 比较大小
代码如下:

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] a=new int[3];for (int i=0;i<3;i++){a[i]=sc.nextInt();}Arrays.sort(a);for(int i=0;i<3;i++){System.out.print(a[i]);if(i<2) System.out.print("->");}System.out.println();}
}

7-2 计算指数 (5分)

题目链接:
7-2 计算指数
代码如下:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n=sc.nextInt();System.out.println("2^"+n+" = "+(1<<n));}
}

7-3 计算阶乘和 (10分)

题目链接:
7-3 计算阶乘和

代码如下:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int ans=0;int x=1;for (int i=1;i<=n;i++){x*=i;ans+=x;}System.out.println(ans);}
}

7-4 简单题 (5分)

题目链接:
7-4 简单题
代码如下:

public class Main {public static void main(String[] args) {System.out.println("This is a simple problem.");}
}

7-5 跟奥巴马一起画方块 (15分)

题目链接:
7-5 跟奥巴马一起画方块
代码如下:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n =sc.nextInt();String s = sc.next();long lie = Math.round(n/2.0);for (long i=0;i<lie;i++){for (int j=0;j<n;j++)System.out.print(s.charAt(0));if(i<lie-1) System.out.println();}}
}

7-6 个位数统计 (15分)

题目链接:
7-6 个位数统计
代码如下:

import java.util.Scanner;public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.next();int[] num =new int[10];for (int i=0;i<s.length();i++){int x=s.charAt(i)-'0';num[x]++;}for (int i=0;i<=9;i++){if(num[i]>0)System.out.println(i+":"+num[i]);}}
}

7-7 查验身份证 (15分)

题目链接:
7-7 查验身份证
代码如下:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n =sc.nextInt();int [] quan={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};String map = "10X98765432";List<String> list = new ArrayList<>();for (int i=0;i<n;i++){String s = sc.next();int sum=0;int flag=0;for (int j=0;j<s.length()-1;j++){if(s.charAt(j)<'0'||s.charAt(j)>'9'){flag=1;break;}int x = s.charAt(j)-'0';sum=(sum+x*quan[j])%11;}if(flag==1){list.add(s);continue;}if(s.charAt(s.length()-1)==map.charAt(sum)) continue;list.add(s);}if(list.size()==0) System.out.println("All passed");else{for(int i=0;i<list.size();i++){System.out.println(list.get(i));}}}
}

7-8 计算摄氏温度 (5分)

题目链接:
7-8 计算摄氏温度
代码如下:

public class Main {public static void main(String[] args) {System.out.println("fahr = "+100+", celsius = "+5*(100-32)/9);}
}

7-9 打印沙漏 (20分)

题目链接:
7-9 打印沙漏
代码如下:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();String s = sc.next();int x=0;while(2*x*x-1<=n) x++;x--;for (int i=x;i>0;i--){for (int j=0;j<x-i;j++) System.out.print(" ");for (int j=0;j<2*i-1;j++){System.out.print(s.charAt(0));}System.out.println();}for (int i=2;i<=x;i++){for (int j=0;j<x-i;j++){System.out.print(" ");}for (int j=0;j<2*i-1;j++){System.out.print(s.charAt(0));}System.out.println();}System.out.println(n-2*x*x+1);}
}

7-10 连续因子 (20分)

题目链接:
7-10 连续因子
代码如下:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long n =sc.nextLong();long tn=n;int num=0;long ans=0;for (long i=2;i*i<=n;i++){//if(tn<i) break;tn=n;int tnum=0;long tans=i;long j=i;while(tn%j==0&&j*j<=n){tn/=j;j++;tnum++;}if(tnum>num){num=tnum;ans=tans;}}if(num==0){num=1;ans=n;}System.out.println(num);for (int i=0;i<num;i++){System.out.print(ans+i);if(i<num-1) System.out.print("*");}System.out.println();}
}

7-11 链表去重 (25分)

题目链接:
7-11 链表去重
分析:
建两个头指针分别表示没有重复元素的链表和重复元素的链表
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct node
{int next;int addr;int val;
};
int vis[100000+5];
struct node a[maxn];
int st,n;
int rst=-1,rtnod=rst;
int lst=-1,ltnod=lst;
int main()
{memset(vis,0,sizeof(vis));scanf("%d%d",&st,&n);for (int i=0;i<n;i++){int addr,next,val;scanf("%d%d%d",&addr,&val,&next);a[addr].addr=addr;a[addr].next=next;a[addr].val=val;}int tnod=st;while(tnod!=-1){int val=abs(a[tnod].val);if(vis[val]==0) {vis[val]++;if(rst==-1){rst=a[tnod].addr;rtnod=rst;}else{a[rtnod].next=a[tnod].addr;rtnod=a[tnod].addr;}tnod=a[tnod].next;a[rtnod].next=-1;}else{if(lst==-1){lst=a[tnod].addr;ltnod=lst;}else{a[ltnod].next=a[tnod].addr;ltnod=a[tnod].addr;}tnod=a[tnod].next;a[ltnod].next=-1;}//a[tnod].next=-1;}while(rst!=-1){printf("%05d %d ",rst,a[rst].val);if(a[rst].next!=-1) printf("%05d\n",a[rst].next);else printf("-1\n");rst=a[rst].next;}while(lst!=-1){printf("%05d %d ",lst,a[lst].val);if(a[lst].next!=-1) printf("%05d\n",a[lst].next);else printf("-1\n");lst=a[lst].next;}
}

7-12 搜索树判断 (25分)

题目链接:
7-12 搜索树判断
代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <malloc.h>
#include <vector>
using namespace std;
const int maxn=1e3+5;
int n;
int a[maxn];
vector<int>v1,v2,v3,V2,V3;
struct node
{struct node* left,*right;int data;
};
node* Create (node *root,int data)
{if(root==NULL){node* t=(node*)malloc(sizeof(node));t->data=data;t->left=t->right=NULL;root=t;}else{if(root->data>data){root->left=Create(root->left,data);}else{root->right=Create(root->right,data);}}return root;
}
void Traverse1(node* root)
{if(root){v2.push_back(root->data);Traverse1(root->left);Traverse1(root->right);}
}
void Traverse2(node* root)
{if(root){v3.push_back(root->data);Traverse2(root->right);Traverse2(root->left);}
}
void Traverse3(node* root)
{if(root){Traverse3(root->left);Traverse3(root->right);V2.push_back(root->data);}
}
void Traverse4(node* root)
{if(root){Traverse4(root->right);Traverse4(root->left);V3.push_back(root->data);}
}
int main()
{scanf("%d",&n);node * root=NULL;for (int i=0;i<n;i++){int x;scanf("%d",&x);v1.push_back(x);root=Create(root,x);}Traverse1(root);Traverse2(root);if(v1!=v2&&v1!=v3){printf("NO\n");}else{printf("YES\n");if(v1==v2){Traverse3(root);for (int i=0;i<V2.size();i++){printf("%d%c",V2[i],i==V2.size()-1?'\n':' ');}}else{Traverse4(root);for (int i=0;i<V3.size();i++){printf("%d%c",V3[i],i==V3.size()-1?'\n':' ');}}}return 0;
}

7-13 回文串问题 (25分)

题目链接:
7-13 回文串问题
分析:
找出正序字符串和倒序字符串的最长公共子串,然后用字符串长度减去最长公共子串的长度就是答案。
代码如下:

import java.util.Scanner;public class Main {public static void main(String[] args) {final int maxn=1005;Scanner sc = new Scanner(System.in);String s = sc.next();String rs ="";for (int i=s.length()-1;i>=0;i--) rs+=s.charAt(i);int[][]dp = new int[maxn][maxn];for (int i=1;i<=s.length();i++){for (int j=1;j<=rs.length();j++){if(s.charAt(i-1)==rs.charAt(j-1)){dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]+1);}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}System.out.println(s.length()-dp[s.length()][s.length()]);}
}

7-14 社交集群 (30分)

题目链接:
7-14 社交集群
分析:
并查集,通过各自的爱好进行并查集unit操作,最后通过find统计个数。
代码如下:

import java.util.*;public class Main {public static int find(int a,int[] pre){if(a==pre[a]) return a;return pre[a]=find(pre[a],pre);}public static void unit(int a,int b,int[] pre){int fa=find(a,pre);int fb=find(b,pre);if(fa!=fb) pre[fa]=fb;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();final int maxn=1005;int[][] hob = new int[maxn][maxn];int[] pre = new int[maxn];int[] kind = new int [maxn];for (int i=0;i<maxn;i++) pre[i]=i;List<List<Integer>> list = new ArrayList<>();for (int i=0;i<n;i++){String s = sc.next();int num = s.charAt(0)-'0';List<Integer> temp = new ArrayList<>();for (int j=0;j<num;j++){int h =sc.nextInt();hob[i][h]=1;temp.add(h);}list.add(temp);}for (int i=0;i<n;i++){List<Integer> temp=list.get(i);for (int j=i+1;j<n;j++){for (int k=0;k<temp.size();k++){int h=temp.get(k);if(hob[j][h]==1){unit(i,j,pre);break;}}}}int ans=0;for (int i=0;i<n;i++){int fa = find(i,pre);if(kind[fa]==0) ans++;kind[fa]++;}Arrays.sort(kind,0,n+1);System.out.println(ans);for (int i=0;i<ans;i++){System.out.print(kind[n-i]);if(i<ans-1) System.out.print(" ");}System.out.println();}
}

7-15 特殊堆栈 (30分)

题目链接:
7-15 特殊堆栈
分析:
树状数组+二分查找
这个题用java写会超时。
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int t[maxn];
int Max=-1;
int lowbit(int x)
{return x&(-x);
}
void add(int loc,int data)
{for (int i=loc;i<maxn;i+=lowbit(i)) t[i]+=data;
}
int sum(int loc)
{int ans=0;for (int i=loc;i>=1;i-=lowbit(i)) ans+=t[i];return ans;
}
int binary (int target)
{int ans=-1;int left=1,right=Max;while(left<=right){int mid=(left+right)/2;if(sum(mid)<target) left=mid+1;else{right=mid-1;ans=mid;}}return ans;}
int main()
{memset(t,0,sizeof(t));int n;scanf("%d",&n);stack<int> st;while(n--){char cmd[30];scanf("%s",cmd);if(cmd[1]=='o'){if(st.size()==0){printf("Invalid\n");continue;}int temp=st.top();st.pop();add(temp,-1);printf("%d\n",temp);}else if(cmd[1]=='u'){int temp;scanf("%d",&temp);Max=max(Max,temp);st.push(temp);add(temp,1);}else{if(st.size()==0){printf("Invalid\n");continue;}int target=(st.size()+1)/2;int ans=binary(target);printf("%d\n",ans);}}}

本文标签: 2020天梯赛训练1 题目整理