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