Students who participate in the blue bridge cup can pay attention to the blogger. The blogger is also preparing the Blue Bridge Cup and can brush questions with the blogger's blog.

# Blue Bridge Cup

The title and pictures are from the counseling class of group ab of Blue Bridge Cup C + +

# simulation

According to the operation given by the topic, use the code to describe it in turn.

Simulation is generally some very basic topics, but don't underestimate simulation. Seemingly simple operations may have unexpected situations.

Simulation needs to be careful! Be sure to take all the circumstances into account.

## Examples

### AcWing 466. Palindrome date

Enumeration + simulation

Most date problems can be solved by simulation.

This question is to judge whether the date is a palindrome string in a certain range.

Enumerate the palindromes of the year, and then judge whether the month and date are legal.

① Enumerate only the first four digits

② Judge whether it is within the range

③ Then judge whether the last four digits are legal

Time complexity O ( 1 0 4 ) O(10^4) O(104) enumeration 1 0 4 10^4 104 numbers. The amount of calculation to judge whether each number is legal is constant, so the total amount of calculation is O ( 1 0 4 ) O(10^4) O(104)

import java.util.Scanner; public class Main { static int[] days = new int[]{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // Number of days per month in a normal year public static void main(String[] args) { Scanner sc = new Scanner(System.in); int date1 = sc.nextInt(); int date2 = sc.nextInt(); int res = 0; for (int i = 1000; i < 10000; i++) { int date = i, x = i; // data and x are the first four digits for (int j = 0; j < 4; j++) { // Turn the data over and put it behind the data date = date * 10 + x % 10; x /= 10; } // At this time, the palindrome string of the year has been simulated. Next, as long as the date is within the range and whether the month and date are legal if (date1 <= date && date <= date2 && check_valid(date)) res++; } System.out.println(res); } private static boolean check_valid(int date) { int year = date / 10000; int month = date % 10000 / 100; int day = date % 100; if (month == 0 || month > 12) return false; // Normal year judgment if (day == 0 || month != 2 && day > days[month]) return false; // Judge leap year if (month == 2) { int leap = 0; // 0 indicates a normal year and 1 indicates a leap year if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) leap = 1; if (day > 28 + leap) return false; } return true; } }

## The fourth 2013 Blue Bridge Cup

### AcWing 1204. Wrong note

Java group A / b question 7

What this problem needs to deal with is input. It only gives us the number of lines and does not give us the number of elements in each line. We can't just use Scanner class to read in. We can use BufferedReader to read in. When there is a lot of data, we can also use this class to optimize the reading in. See the code for details.

simulation

Time complexity O ( N ) O(N) O(N)

Open a Boolean array st[] to record whether the number has appeared. If so, it is marked as true; When traversing, if the state of the number has been marked as true, it indicates that the number is a duplicate sign; We can find the maximum and minimum values during the first traversal. If the state of the number from small to large is false, it indicates that the number is a hyphen.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N = 100010; static boolean[] st = new boolean[N]; // The tag status defaults to false public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; int res1 = 0; // Broken sign int res2 = 0; // Duplicate sign while (n-- > 0) { String[] nums = in.readLine().split(" "); for(int i = 0; i < nums.length; i++) { int t = Integer.parseInt(nums[i]); max = Math.max(max, t); // Maximum found min = Math.min(min, t); // Find minimum value if (st[t]) res2 = t; // If the previous value is true, the duplicate number is found st[t] = true; } } for (int i = min ; i <= max ; i ++) { if (!st[i]) res1 = i; // If the status is false, a hyphen is found } System.out.println(res1 + " " + res2); } }

sort

Time complexity O ( N l o g N ) O(NlogN) O(NlogN)

Sort all numbers, and judge the double sign elements and broken sign elements according to the subscript of the array.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static final int N = 100010; static int[] a = new int[N]; public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); int index = 0; while (n-- > 0) { String[] nums = in.readLine().split(" "); for (int i = 0; i < nums.length; i++) { a[index++] = Integer.parseInt(nums[i]); } } Arrays.sort(a, 0, index); int res1 = 0; // Broken sign int res2 = 0; // Duplicate sign for(int i = 1; i < index; i++) { if (a[i] == a[i - 1]) res2 = a[i]; // Duplicate sign else if (a[i] == a[i - 1] + 2) res1 = a[i] - 1; // Broken sign } System.out.println(res1 + " " + res2); } }

## Real topic of the 6th 2015 Blue Bridge Cup

### AcWing 1219. Moving distance

JavaA/C group question 8

Manhattan distance d ( i , j ) = ∣ x i − x j ∣ + ∣ y i − y j ∣ d(i,j)=|x_{i}-x_{j}|+|y_{i}-y_{j}| d(i,j)=∣xi−xj∣+∣yi−yj∣

The numbers in the matrix are arranged in a serpentine shape, and the difficulty is to find the coordinates of the numbers. We can learn from the two-dimensional array and reduce all the numbers in the matrix to - 1, so as to find our line number:

The original coordinate of 1 is (1, 1), now it is (0, 1). The line number of 1: 1 / 6 = 0. Let these two numbers be n and m, w is the width of the line, and the line number: n / w, m / w

How to find the column number? Let's take a look at the two-dimensional array with normal sorting:

Column No.: n% w, M% w

But the problem is serpentine, that is, all odd rows. We should flip the coordinates. Here's a special judgment.

simulation

Time complexity O ( 1 ) O(1) O(1)

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int w = sc.nextInt(); int m = sc.nextInt() - 1; int n = sc.nextInt() - 1; // The starting position starts from 0 to facilitate the calculation of row and column coordinates int x1 = m / w, x2 = n / w; // Line number int y1 = m % w, y2 = n % w; // Column number if (x1 % 2 != 0) y1 = w - 1 - y1; // Special judgment on odd sequence, flip y coordinate if (x2 % 2 != 0) y2 = w - 1 - y2; System.out.print(Math.abs(x1 - x2) + Math.abs(y1 - y2)); // Manhattan distance formula } }

## Real topic of the 8th 2017 Blue Bridge Cup

### AcWing 1229. Date issue

JavaB group question 7

Enumeration + simulation

We enumerate all numbers between 19600101 and 20591231: ① judge whether it is legal; ② judge whether it may be a given representation

import java.util.Scanner; public class Main { static int[] days = new int[]{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // Number of days per month in a normal year public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); String[] data = str.split("/"); int a = Integer.parseInt(data[0]); int b = Integer.parseInt(data[1]); int c = Integer.parseInt(data[2]); for (int date = 19600101; date <= 20591231; date++) { int year = date / 10000; int month = date % 10000 / 100; int day = date % 100; if (check_valid(year, month, day)) { if (year % 100 == a && month == b && day == c || // Year / month / day month == a && day == b && year % 100 == c || // Month / day / year day == a && month == b && year % 100 == c) { // Day / month / year System.out.printf("%d-%02d-%02d\n", year, month, day); // Remember to add '-' to the formatted output } } } } private static boolean check_valid(int year, int month, int day) { if (month == 0 || month > 12) return false; if (day == 0 || month != 2 && day > days[month]) return false; if (month == 2) { int leap = 0; if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) leap = 1; if (day > 28 + leap) return false; } return true; } }

## True topic of the 9th 2018 Blue Bridge Cup

### AcWing 1231. Flight time

Java group a question 6

When flying from Beijing to the Middle East, we don't know the time difference with the Middle East, but let's first sort out the formula of flight time: first, when the plane flies from Beijing to the Middle East, the landing time minus the take-off time also needs to add the time difference: end1 - start1 + time. When the plane flies back to Beijing from the Middle East, the landing time minus the take-off time also needs to subtract the time difference: end2 - start2 - time, What we are looking for is the flight time of the plane. Because the flight time of the plane back and forth is the same, we can add the flight time back in the future: end1 - start1 + end2 - start2. We find that the time difference is offset, so this question has nothing to do with the time difference. The flight time of the plane: $t = (end1 - start1 + end2 - start2) / 2$

The formula has been introduced. The next thing to deal with is the input and output of string.

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { String[] input = in.readLine().split(" "); int n = Integer.parseInt(input[0]); while (n-- > 0) { int time = (get_time() + get_time()) / 2; int hour = time / 3600, minute = time % 3600 / 60, second = time % 60; System.out.printf("%02d:%02d:%02d\n", hour, minute, second); } } private static int get_time() throws IOException { String[] line = in.readLine().split(":| "); // Separating: and spaces int d = 0; if (line.length == 7) d = line[6].charAt(2) - '0'; // If the length is 7, it means that there is (+ n) after the string. Remember to turn it to int int h1 = Integer.parseInt(line[0]); int m1 = Integer.parseInt(line[1]); int s1 = Integer.parseInt(line[2]); int h2 = Integer.parseInt(line[3]); int m2 = Integer.parseInt(line[4]); int s2 = Integer.parseInt(line[5]); return get_seconds(h2, m2, s2) - get_seconds(h1, m1, s1) + d * 24 * 3600; } // Convert all time into seconds from 00:00:00 of the day private static int get_seconds(int h, int m, int s) { return h * 3600 + m * 60 + s; } }

## True topic of the 10th 2019 Blue Bridge Cup

### AcWing 1241. Take out priority

JavaB group question 7

Analyze the first example:

Finally, at time 6, only takeout 2 is in the priority cache, and the answer is output 1.

Violent enumeration (memory overrun)

Time complexity O ( N 2 ) O(N^2) O(N2)

Enumerate take out orders at each time

AcWingMLE, 7 out of 10 data, 90 out of 100 in the Blue Bridge Cup. The last data memory exceeded the limit, but it was also a considerable score.

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(), t = sc.nextInt(); // Array definition saves memory in global variables int[][] a = new int[t + 1][n + 1]; // Order i is the time and j is the delivery number int[] p = new int[n + 1]; // priority for (int i = 0; i < m; i++) a[sc.nextInt()][sc.nextInt()]++; for (int i = 1; i < t + 1; i++) { for (int j = 1; j < n + 1; j++) { if (a[i][j] > 0) { a[i][j] = a[i - 1][j] + a[i][j] * 2; // Add the priority of this order if (a[i][j] > 5) p[j] = 1; // Prioritize takeout at this time } else { if (a[i - 1][j] > 0) { a[i][j] = a[i - 1][j] - 1; if (a[i][j] <= 3) p[j] = 0; } } } } int res = 0; for (int i = 0; i < p.length; i++) res += p[i]; System.out.println(res); } }

optimization

The time when we get the order from each takeout is discrete. It may take a long time before there is a second order. In fact, we can compress the middle part and unify the continuous period of time without order to the next time when there is an order, or put it at time T:

The advantage of this is that we only need to consider the stores with orders when we go to do every moment, and we don't need to consider the stores without orders.

At this time, we can sort all orders in chronological order without enumerating the time, and process a batch of the same orders each time. As long as the time point of the order is the same as the store id, we will regard it as one.

score[i] indicates the current priority of the ith store

last[i] indicates the last time there was an order in the ith store

st[i] indicates whether the ith store is currently in the priority cache

Pseudo code

Content before processing t time:

In this way, the time when there is no order in the middle can be compressed:

score[id] -= t - last[id] - 1; // If there are orders at the 3rd and 6th times, the time when things are not sold should be 4 and 5, so it is necessary to reduce one 6-3-1 = 2

There are also two judgments:

if (score[id] < 0) score[id] = 0; if (score[id] <= 3) st[id] = false; // Remove priority cache

Update last: last[id] = t

Content of processing t time:

score[id] += cnt * 2; // Add priority if (score[id] > 5) st[id] = true; // Put in priority cache

There may be no orders in each store in the last period of time. We also need to calculate how long we haven't sold anything between last[id] ~ T in the last period of time:

for (int i = 1; i <= n; i++) { if (last[i] < T) { score[i] -= T - last[i]; // - 1 is not needed at this time, because there is no order at time T if (score[i] <= 3) st[i] = false; } }

Obtained results:

int res = 0; for (int i = 1; i <= n; i++) { if (st[i]) res++; } sout(res);

Complete code

import java.util.Scanner; import java.util.Arrays; public class Main { static final int N = 100010; static int[] score = new int[N]; // Store priority static int[] last = new int[N]; // Last time there was an order static boolean[] st = new boolean[N]; // Indicates whether the store is in the priority cache static PII[] order = new PII[N]; // order public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(), T = sc.nextInt(); for (int i = 0; i < m; i++) order[i] = new PII(sc.nextInt(), sc.nextInt()); Arrays.sort(order, 0, m); for (int i = 0; i < m;) { // Cycle to find the same order int j = i; while (j < m && order[j].ts == order[i].ts && order[j].id == order[i].id) j++; int t = order[i].ts, id = order[i].id; int cnt = j - i; // Quantity of orders in the same batch i = j; // Process information before time t score[id] -= t - last[id] - 1; // There is no order quantity in the middle if (score[id] < 0) score[id] = 0; if (score[id] <= 3) st[id] = false; // Remove priority cache // Processing information at time t score[id] += cnt * 2; // Add priority if (score[id] > 5) st[id] = true; // Put in priority cache last[id] = t; } for (int i = 1; i <= n; i++) { if (last[i] < T) { score[i] -= T - last[i]; // - 1 is not needed at this time, because there is no order at time T if (score[i] <= 3) st[i] = false; } } int res = 0; for (int i = 1; i <= n; i++) if (st[i]) res++; System.out.println(res); } static class PII implements Comparable<PII> { int ts; int id; public PII(int ts, int id) { this.ts = ts; this.id = id; } @Override public int compareTo(PII o) { if(this.ts > o.ts) return 1; if(this.ts == o.ts) { if (this.id > o.id) return 1; return -1; } return -1; } } }

If you don't understand the code, you can comment below