[Blue Bridge Cup] summary of real questions and solutions over the years
- Results fill in the blanks (full score 5 points)
- Results fill in the blanks (full score 5 points)
- Results fill in the blanks (full score 10 points)
- Results fill in the blanks (full score 10 points)
- Results fill in the blanks (Full Score: 15 points)
- Programming (Full Score: 15 points)
- Programming (Full Score: 20)
- Programming (Full Score: 20)
- Programming (Full Score: 20)
- Programming (Full Score: 25)
- Programming (Full Score: 25)
Question 1: Sum
[problem description]
Xiao Ming is very interested in numbers containing 2, 0, 1 and 9. In the range of 1 to 40, such numbers include 1, 2, 9, 10 to 32, 39 and 40, a total of 28, and their sum is 574. What is the sum of all such numbers from 1 to 2019?
Answer: 1905111
public class Main { //1905111
public static void main(String[] args) {
int count=0,temp=0;
for (int i = 1; i <=2019; i++) {
int b = i;
temp=i;
while(b!=0){
int a = b%10;
if(a==2 || a==0||a==1||a==9){
count+=temp;
break;
}
b/=10;
}
}
System.out.println(count);
}
}Question 2: rectangular cutting
[problem description]
Xiao Ming has some rectangular materials. He wants to cut some squares from these rectangular materials.
When he faces a rectangular material, he always cuts a knife from the middle to cut out the largest square, leaving a rectangle, and then cut the remaining rectangular materials until they are all cut into squares. For example, for a piece of material with 5 and 3 on both sides (recorded as 5 × 3) , Xiao Ming will cut out 3 in turn × 3,2 × 2,1 × 1,1 × 1 there are 4 squares in total. Now Xiaoming has a rectangular piece of material, with the length of 2019 and 324 on both sides. How many squares will Xiao Ming cut out in the end?
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int max = sc.nextInt();
int min=sc.nextInt();
int count=0,num,temp;
while (true){
if ( min==0){//You can quit when you don't have it
break;
}
num = max/min;//Look at how many squares there are when the current length and width do not change
count+=num; //Add all this in
//Instead, after cutting the square, the original length becomes width and the original width becomes length
temp=max-min*num;//The original length minus the cut width is now the width
max=min;
min=temp;
}
System.out.println(count);
}
}
Question 3: different substrings
Problem description]
A non empty substring of a string refers to a string consisting of a continuous segment of characters with a length of at least 1. For example, the string aaab has 7 non empty substrings a, b, aa, ab, aaa, aab, aaab in total. Note that in the calculation, only the number of essentially different strings is calculated. How many different non empty substrings are there in string 0100110001010001?
import java.util.HashSet;
import java.util.Set;
public class Main {//100
public static void main(String[] args) {
String s ="0100110001010001";
Set<String> set = new HashSet<String>(); //The biggest feature of Set is that it cannot store duplicate elements
for (int i = 0; i < s.length(); i++) { //Every possibility of the for loop is added to the set
for (int j = i+1; j <= s.length(); j++) {
String a = s.substring(i,j);
set.add(a);
}
}
System.out.println(set.size());
}
}Question 4: prime number
[problem description]
We know that the first prime number is 2, the second prime number is 3, and the third prime number is 5... Please calculate the 2019 prime number?
public class Main{ //17569
public static void main(String[] args) {
int count = 0;int temp = 0;
A: for (int i = 2; ; i++) {
for (int j = 2; j <i; j++) {
if(i%j==0){
continue A;
}
}
count++;
if(count==2019){
System.out.println(i);
break;
}
}
}
}
Question 5: maximum rainfall
[problem description]
Due to the long-term drought in the land of sand, master Xiao Ming is ready to use one of his mysterious spells to pray for rain. This spell requires 49 spell symbols in his hand, which are written with 49 numbers from 1 to 49. The spell lasts for a total of 7 weeks. Xiao Ming uses a spell charm every day. The spell charm cannot be reused. Every week, the energy generated by Xiaoming's spell is the median of the number on the seven spell runes this week. After the spell is cast for 7 weeks, praying for rain will be successful. The rainfall is the median energy of 7 weeks. Due to the long drought, Xiao Ming hopes that the rainfall will be as large as possible. What is the maximum?
answer:
It is not the sum of the seven week median, but the maximum of the seven week median
a. B, C, x, e, F and G are the median of each week.
And X is the median of a, B, C, x, e, F and G for each of these seven weeks
The requirement of the topic is to let us maximize this x;
We can assume that x is already the value we require. In order for X to meet the subject information, we must make it greater than this value in the last three days of week 4, and the last four days of week 5, 6 and 7.
Then it is obvious that there are 15 numbers larger than x, then x is equal to 49 - 15 = 34;
Question 6: rotation
[problem description]
Picture rotation is one of the simplest ways to deal with pictures. In this problem, you need to rotate the picture 90 degrees clockwise. We use an n × A two-dimensional array of m to represent a picture. For example, a 3 is given below × Example of picture of 4:
1 3 5 7 9 8 7 6 3 5 9 7
After the picture is rotated 90 degrees clockwise, the picture is as follows:
3 9 1 5 8 3 9 7 5 7 6 7
Given the initial picture, please calculate the rotated picture.
[input format]
The first row of input contains two integers n and m, representing the number of rows and columns respectively. The next N lines, each with m integers, represent the given picture. Each element (pixel) in the picture is an integer with a value between 0 and 255 (including 0 and 255).
[output format]
Output m rows and n columns, representing the rotated picture.
[example input] 3 4 1 3 5 7 9 8 7 6 3 5 9 7
[sample output] 3 9 1 5 8 3 9 7 5 7 6 7
For case scale ≤ 10, for case scale ≤ 10, M. For 60% of the evaluation cases, 1 ≤ n,m ≤ 30. For all evaluation cases, 1 ≤ n,m ≤ 100
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int [][] num = new int [n+1][m+1];
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
num[i][j]=sc.nextInt();
}
}
int [][]shu = new int [m+1][n+1];
for (int i = 1; i <=m; i++) {
for (int j = 1; j <=n; j++) {
shu[i][j]=num[n-j+1][i];
}
}
for (int i = 1; i <=m; i++) {
for (int j = 1; j <=n; j++) {
System.out.print(shu[i][j]+" ");
}
System.out.println();
}
}
}
Question 7: priority of takeout stores
Problem description]
N takeout stores are maintained in the "full" takeout system, numbered 1 ∼ n. Each takeout store has a priority, and the priority is 0 at the beginning (at 0 time). After each time unit, if there is no order in the delivery shop, the priority will be reduced by 1 and the lowest will be reduced to 0; If the takeout shop has orders, the priority will be increased instead of decreasing, and the priority will be increased by 2 for each order. If the priority of a takeout store is greater than 5 at a certain time, it will be added to the priority cache by the system; If the priority is less than or equal to 3, it will be cleared out of the priority cache. Given the M order information within time T, please calculate how many takeout stores are in the priority cache at time T.
[input format] the first line contains three integers N, m and T. Each of the following M lines contains two integers ts and id, indicating that the takeout store with TS time number id receives an order.
[output format]
Output an integer representing the answer.
[example input] 2 6 6 1 5 2 3 1 6 2 1 6 2 1 6 2
[sample output] 1
[example explanation] at 6:00, the priority of store 1 is reduced to 3 and the priority cache is removed; The priority of store 2 is raised to 6 and the priority cache is added. So there is one store (No. 2) in the priority cache.
[scale and agreement of evaluation cases] for 80% of evaluation cases, 1 ≤ N,M,T ≤ 10000. For all evaluation cases, 1 ≤ N,M,T ≤ 100000, 1 ≤ ts ≤ T, 1 ≤ id ≤ N.
import java.util.ArrayList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;
public class Main {
static Scanner in = new Scanner(System.in);
static int n, m, t;
static Map<Integer, ArrayList<Integer>> map = new TreeMap<Integer, ArrayList<Integer>>();
static int result;
public static void main(String[] args) {
n = in.nextInt();
m = in.nextInt();
t = in.nextInt();
for (int i = 1; i <= m; ++i) {
int time = in.nextInt();
int id = in.nextInt();
if (map.containsKey(id)) {
map.get(id).add(time);
} else {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(time);
map.put(id, temp);
}
}
ArrayList<Map.Entry<Integer, ArrayList<Integer>>> list = new ArrayList<Map.Entry<Integer, ArrayList<Integer>>>(
map.entrySet());
for (int i = 0; i < list.size(); ++i) {
Entry<Integer, ArrayList<Integer>> entry = list.get(i);
ArrayList<Integer> list2 = entry.getValue();
int num = 0;
int[] count = new int[t + 2];
boolean flag = false;
for (int j = 0; j < list2.size(); ++j)
count[list2.get(j)]++;
for (int j = 1; j <= t; ++j) {
if (count[j] == 0) {
if (num > 0)
num--;
if (num <= 3)
flag = false;
} else {
num += count[j] * 2;
if (num > 5)
flag = true;
}
}
if (flag)
result++;
}
System.out.println(result);
}
}
Question 8: character correlation analysis
[problem description]
Xiao Ming is analyzing the relevance of characters in a novel. He wants to know how many times alice and Bob appear at the same time in the novel. More precisely, Xiao Ming defines alice and Bob as "appearing at the same time", which means that there are no more than K characters between alice and Bob in the novel text. For example, the following text: This is a story about alice and Bob AlicewantstosendaprivatemessagetoBob. Assuming K = 20, alice and Bob appear twice at the same time, namely "alice and Bob" and "Bob" alice”. The former has 5 characters between alice and Bob, and the latter has 2 characters. Note: 1 alice and Bob are case sensitive, and alice or Bob are not included. 2. Alice and Bob should be separate words, with punctuation marks and spaces before and after, but no letters. For example, Bobbi does not count as Bob.
[input format]
The first line contains an integer K. The second line contains a single line of string, containing only uppercase and lowercase letters, punctuation, and spaces. The length shall not exceed 1000000.
[output format]
Output an integer indicating the number of times Alice and Bob appear at the same time.
[sample input]
20 This is a story about Alice and Bob.Alice wants to send aprivate message to Bob.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
int res=0; //save result
int K=reader.nextInt();
reader.nextLine(); //nextLine enter
String str=reader.nextLine();
String words[]=str.split("\\s+|\\."); //With spaces and Split it out, pay attention The combination of spaces is stored as an empty string
// Alice------>Bob
for(int i=0;i<words.length;i++){
if(words[i].equals("Alice")){
for(int j=i+1;j<words.length;j++){
if(words[j].equals("Bob")){
int sum=1; //It's going to be 1
for(int k=i+1;k<j;k++){
sum+=words[k].length()+1;
}
if(sum<=K){
res++;
}
}
}
}
}
//Bob--------->Alice
for(int i=0;i<words.length;i++){
if(words[i].equals("Bob")){
for(int j=i+1;j<words.length;j++){
if(words[j].equals("Alice")){
int sum=1; //It's going to be 1
for(int k=i+1;k<j;k++){
sum+=words[k].length()+1;
}
if(sum<=K){
res++;
}
}
}
}
}
System.out.println(res);
}
}Question 9: arithmetic sequence
Time limit: 1.0s memory limit: 512.0MB total score of this question: 25 points
[problem description]
The math teacher gave Xiao Ming a problem of summing the arithmetic sequence. But the careless Xiao Ming forgot part of the sequence and only remembered N integers. Now give these N integers. Xiao Ming wants to know how many items are the shortest arithmetic sequence containing these N integers?
[input format]
The first line of input contains AN integer N. The second line contains N integers A1,A2, ····, AN. (note that A1 ∼ AN is not necessarily given in the order of the arithmetic sequence)
[output format]
Output an integer to represent the answer.
[example input] 5 2 6 4 10 20
[sample output] 10
[example description]
The shortest arithmetic sequence containing 2, 6, 4, 10 and 20 is 2, 4, 6, 8, 10, 12, 14, 16, 18 and 20.
[evaluation case scale and agreement]
For all evaluation cases, 2 ≤ N ≤ 100000, 0 ≤ Ai ≤ 109.
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n = sc.nextInt();
int [] num = new int [n]; //Number of entered
int [] cha = new int [n-1]; //The smallest difference between adjacent numbers after array sorting
for (int i = 0; i < num.length; i++) {
num[i]=sc.nextInt();
}
Arrays.sort(num);
int min_cha=Integer.MAX_VALUE;
for (int i=0;i<cha.length;i++){
cha[i]=num[i+1]-num[i];
min_cha=Math.min(cha[i],min_cha);
}
// for (int i:cha
// ) {
// System.out.println(i);
// }
int dengcha=Integer.MAX_VALUE;
A: for (;min_cha>0;min_cha--){
boolean bool = false;
for (int i=0;i<cha.length;i++){
if (cha[i]%min_cha!=0){
continue A;
}
}
dengcha=min_cha;
break A;
}
// System.out.println(dengcha);
int num1 = num[num.length-1]-num[0];
int count=1;
count+=num1/dengcha;
System.out.println(count);
}
}Question 10: floor sweeping robot
[problem description]
The office area of Xiaoming company has a long corridor, which is composed of N square areas, as shown in the figure below
Show.
K sweeping robots are deployed in the corridor, of which the i is in the Ai grid area. It is known that the sweeping robot can move to the left and right adjacent squares every minute and clean the area dry
Net.
Please write a program to calculate the cleaning route of each robot so that
They all eventually return to the starting grid,
Each square area is cleaned at least once,
It takes the least time from the start of the robot to the return of the last robot.
Note that multiple robots can clean the same square area at the same time, and they will not affect each other.
Output takes the least time. In the example shown above, the minimum time taken is 6. The first route: 2-1-2-3-4-3-2, sweeping areas 1, 2, 3 and 4. The second route is 5-6-7-6-5, cleaning 5, 6 and 7. The third route is 10-9-8-9-10, cleaning 8, 9 and 10.
[input format]
The first line contains two integers N and K. Next, K lines, with an integer Ai for each line.
[output format]
Output an integer to represent the answer.
[sample input] 10 3 5 2 10
[sample output] 6
[evaluation case scale and agreement]
For 30% of the evaluation cases, 1 ≤ K < N ≤ 10. For 60% of the evaluation cases, 1 ≤ K < N ≤ 1000. For all evaluation cases, 1 ≤ K < N ≤ 100000, 1 ≤ Ai ≤ N
import java.util.Scanner;
public class Main {
static int N;
static int K;
static int[] a = new int[1000000];
static int[] b = new int[1000000];
public static void main(String[] args) {
int i,L;
Scanner sc =new Scanner(System.in);
N=sc.nextInt();
K=sc.nextInt();
for ( i = 1; i <=K; i++) {
a[i]=sc.nextInt();
b[a[i]]=1;
}
L=fun();
System.out.println(2*(L-1));
}
public static boolean check1(int first_L, int L) { //The length of the first interval is first_ 50. After that, the interval length is L
int i, j;
if (first_L + (K - 1) * L < N) {//Can the length of the first section plus other robots and * reach the total length
return false;
}
i = 1; //The ith interval
j = 1; //Currently viewed grid position
while (j <= N) {
if (b[j] == 1) { //There are robots in the i-th interval
j = first_L + (i - 1) * L + 1; //j points to the starting point of the next interval
i++; //Next interval
}
else {
j++;//Always check the next box, if not, until the first_ When l and j are equal, it indicates that there is really no robot
if (j == first_L + (i - 1) * L + 1 || j == N + 1) { //There is no robot in the i-th interval
return false; //Because L keeps getting bigger and the first keeps getting bigger, the check continues to expand further
}
}
}
return true;
}
public static boolean check(int L) {
int first_L; //Length of the first interval (value range: 1~L)
for (first_L = L; first_L > 0; first_L--) {//Flashback is because using a large range can reduce the movement of the robot
if (check1(first_L, L)) {
return true;
}
}
return false;
}
public static int fun() {
int i, j, L;
for (L = N / K; L <= N; L++) {//On average,
if (check(L)) {
return L;
}
}
return L;
}
}