foreword
...
The 11th Blue Bridge Cup Individual Competition Intramural Selection (Software) Zhenti
1.15.125GB
15,488MB
2. The approximate number
96
3. The number of leaf nodes
1010
4. Number 9
544
5. Digit-incrementing numbers
python
def judge(num):
tmp_max = 9
while(num):
if num % 10 <= tmp_max:
tmp_max = num % 10
num //= 10
else:
return False
return True
n = int(input())
cot = 0
for i in range(1,n+1):
if judge(i):
cot += 1
print(cot)
java
package train;
import java.util.Scanner;
public class lanqiao {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int cot = 0;
for(int i=1;i<=n;i++){
if(judge(i)){
cot += 1;
}
}
System.out.println(cot);
}
public static boolean judge(int num){
int tmp_max = 9;
while(num!=0){
if(num%10 <= tmp_max){
tmp_max = num % 10;
num /= 10;
}else{
return false;
}
}
return true;
}
}
6. Incrementing triples
[Problem Description]
In the sequence a[1], a[2],..., a[n], if the subscript i, j, k satisfies 0<i<j<k<n+1 and a[i]<a[j]<a[k], then a[i], a[j], a[k] is a group of increasing triples, and a[j] is the center of increasing triples
Given a sequence, ask how many elements in the sequence may be the center of an increasing triple.
[Input format]
The first line of input contains an integer n.
The second line contains n integers a[1], a[2], …, a[n], and adjacent integers are separated by spaces, representing the given sequence.
[Output format]
A line of output contains an integer representing the answer.
[Sample input]
5
1 2 5 3 5
[Example output]
2
[Example description]
a[2] and a[4] may be the centers of the triples.
[Scale and conventions of evaluation use cases]
For 50% of the evaluation cases, 2 <= n <= 100, 0 <= number in sequence <= 1000.
For all evaluation cases, 2 <= n <= 1000, 0 <= number in sequence <= 10000.
python
n = int(input())
lst = list(map(int, input().split()))
min_lst = []
max_lst = []
tmp_min = 10001
for idx in range(0, len(lst)-2):
if lst[idx] < tmp_min:
tmp_min = lst[idx]
min_lst.append(tmp_min)
tmp_max = -1
for idx in range(len(lst)-1 ,1, -1):
if lst[idx] > tmp_max:
tmp_max = lst[idx]
max_lst.append(tmp_max)
cot = 0
for idx in range(len(min_lst)):
if min_lst[idx] < lst[idx+1] < max_lst[len(min_lst)-1-idx]:
cot += 1
print(cot)
7. Syllable judgment
python
yuanyin_lst = ['a','e','i','o','u']
def judge(ss):
pre_s = ss[0]
if pre_s in yuanyin_lst:
return False
cot = 0
pre_type = 1
for s in ss:
n_type = 2 if s in yuanyin_lst else 1
if n_type!=pre_type:
cot += 1
pre_type = n_type
if cot == 3:
return True
else:
return False
ss = input()
res = judge(ss)
if res:
print("yes")
else:
print("no")
8. Long grass
[Problem Description]
Xiao Ming has an open space, and he divides the open space into small blocks of n rows and m columns, each of which has a length of 1.
Xiaoming chose some of the small pieces of open space and planted grass, and the other small pieces remained open space.
These grasses grow very fast. Every month, the grass will grow out. If a small piece of grass is planted, it will expand to its own upper, lower, left, and right four small pieces of open space. These four small pieces of open space will become grassy patches.
Please tell Xiao Ming where there will be grass in the open space after k months.
[Input format]
The first line of input contains two integers n, m.
The next n lines, each containing m letters, represent the initial open space state, with no spaces between letters. If it is a decimal point, it means open space, and if the letter is g, it means grass is planted.
Next contains an integer k.
[Output format]
Output n lines, each containing m letters, representing the state of the vacant lot after k months. If it is a decimal point, it means an open space, and if the letter is g, it means grass grows.
[Sample input]
4 5
.g...
.....
..g..
.....
2
[Example output]
gggg.
gggg.
ggggg
.ggg.
[Scale and conventions of evaluation use cases]
For 30% of the evaluation cases, 2 <= n, m <= 20.
For 70% of the evaluation cases, 2 <= n, m <= 100.
For all evaluation cases, 2 <= n, m <= 1000, 1 <= k <= 1000.
n,m = list(map(int, input().split()))
lst = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
ss = input()
for j in range(m):
lst[i][j] = ss[j]
k = int(input())
while k:
k -= 1
tmp_lst = []
for i in range(n):
for j in range(m):
if lst[i][j] == 'g':
tmp_lst.append([i-1,j])
tmp_lst.append([i+1, j])
tmp_lst.append([i, j-1])
tmp_lst.append([i, j+1])
for place in tmp_lst:
x,y = place
if 0 <= x < n and 0<= y < m:
lst[x][y] = 'g'
for idx_i,i in enumerate(lst):
for idx_j, j in enumerate(i):
print(j,end="")
if idx_i != n-1:
print()
9. Sequence count
[Problem Description]
Xiaoming wants to know the number of sequences of positive integers that satisfy the following conditions:
1. The first term is n;
2. The second term does not exceed n;
3. Starting from the third term, each term is less than the absolute value of the difference of the previous two terms.
Calculate, for a given n, how many sequences satisfy the condition.
[Input format]
A line of input contains an integer n.
[Output format]
Output an integer representing the answer. The answer may be large, please output the remainder of dividing the answer by 10000.
[Sample input]
4
[Example output]
7
[Example description]
Here is the sequence that satisfies the condition:
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4
[Scale and conventions of evaluation use cases]
For 20% of the evaluation cases, 1 <= n <= 5;
1 <= n <= 10 for 50% of the evaluation cases;
1 <= n <= 100 for 80% of the evaluation cases;
1 <= n <= 1000 for all evaluation cases.
//recursion
package train;
import java.util.Scanner;
public class lanqiao {
public static int ans;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 1;i<=n;i++){
dfs(n,i);
}
System.out.println(ans);
}
public static void dfs(int a, int b){
for(int i = 1;i<Math.abs(b-a);i++){
dfs(b, i);
}
ans = (ans+1) % 10000;
}
}
//memoized search
package train;
import java.util.Scanner;
public class lanqiao {
public static int ans = 0;
public static int[][] ansArray = new int[1001][1001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int i = 1;i<=n;i++){
ans = (ans + dfs(n,i))%10000;
}
System.out.println(ans);
}
public static int dfs(int a, int b){
if(ansArray[a][b] != 0){
return ansArray[a][b];
}else{
ansArray[a][b] = 1;
for(int i = 1;i<Math.abs(b-a);i++){
ansArray[a][b] = (ansArray[a][b]+dfs(b,i))%10000;
}
}
return ansArray[a][b];
}
}
10. Evening program
[Problem Description]
Xiao Ming wants to organize a party, and has prepared a total of n programs. Then the time for the party is limited, and he can only choose m programs in the end.
These n programs are given in the order Xiao Ming imagined, and the order cannot be changed.
Xiao Ming found that the audience's liking for the evening has a great relationship with the goodness of the previous programs. He hopes that the first program selected is as good as possible. On this premise, he hopes that the second program is as good as possible. analogy.
Xiao Ming defines a good-looking value for each program. Please help Xiao Ming select m programs to meet his requirements.
[Input format]
The first line of input contains two integers n, m , representing the number of programs and the number to select.
The second line contains n integers, followed by the good looks for each show.
[Output format]
The output line contains m integers, the good looks for the selected program.
[Sample input]
5 3
3 1 2 5 4
[Example output]
3 5 4
[Example description]
1st, 4th, 5th shows selected.
[Scale and conventions of evaluation use cases]
1 <= n <= 20 for 30% of the evaluation cases;
1 <= n <= 100 for 60% of the evaluation cases;
For all evaluation cases, 1 <= n <= 100000, 0 <= show good value <= 100000.
Ideas: All programs have 1. Sequence 2, good-looking value First sort according to good-looking value, take out the first m good-looking programs, then sort in order, and output the order.
python
n,m = list(map(int, input().split()))
lst = list(map(int,input().split()))
for i in range(len(lst)):
lst[i] = [i, lst[i]]
lst = sorted(lst, key = lambda x:x[1], reverse=True)
lst = lst[:m]
lst = sorted(lst, key = lambda x:x[0], reverse=False)
for i in range(m):
if i != m-1:
print(lst[i][1],end=" ")
else:
print(lst[i][1],end="")
java
package train;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class lanqiao {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] original_order = new int[n];
int[] sorted_order = new int[n];
for(int i = 0;i<n;i++){
original_order[i] = sc.nextInt();
sorted_order[i] = original_order[i];
}
Arrays.sort(sorted_order);
ArrayList<String> list = new ArrayList<String>();
for(int i = n-m;i<n;i++){
list.add(sorted_order[i]+"");
}
StringBuilder sb = new StringBuilder();
for(int i:original_order ){
if(list.contains(i+"")){
list.remove(i+"");
if (list.size() != 0){
sb.append(i+" ");
}else{
sb.append(i+"");
}
}
}
System.out.println(sb);
}
}
expand
memoized search
understand
Save what has been calculated.
Brush questions
1.P1434 SHOI2002 Skiing
https://www.luogu.com.cn/problem/P1434
(The first question in Luogu, it seems that the class name must be Main, and the main method name must be main... This took a long time)
Topic description
Michael loves to ski. That's not surprising, because skiing is really exciting. But to gain speed, the slippery area has to slope down, and when you get to the bottom of the slope, you have to walk uphill again or wait for the lift to pick you up. Michael wants to know the longest landslide in an area. The area is given by a two-dimensional array. Each number of the array represents the height of the point. Below is an example:
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
A person can slide from a point up, down, left and right to one of the four adjacent points if and only if the height decreases. In the example above, a feasible landslide is 2424-1717-1616-11 (starting at 2424 and ending at 11). Of course 2525-2424-2323-\ldots...-33-22-11 is longer. In fact, this is the longest one.
input format
The first row of the input is the row number RR and the column number CC of the two-dimensional array representing the region. Below are the RR lines, each with CC numbers representing the height (with 11 spaces between the two numbers).
output format
The length of the longest landslide in the output area.
Input and output example
enter
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
output
25
Instructions/Tips
For 100%100% of the data, 1\leq R,C\leq 1001≤R,C≤100.
Idea: Recursive idea, using a two-dimensional array to save the points that have been calculated.
java
import java.util.Scanner;
public class Main {
static int[] dx = {-1,+1,0,0};
static int[] dy = {0,0,-1,+1};
static int[][] map = new int[100][100];
static int[][] ans_lst = new int[100][100];
static int ans = 0;
static int R;
static int C;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
R = sc.nextInt();
C = sc.nextInt();
for(int i = 0;i<R;i++){
for(int j =0;j<C;j++){
map[i][j] = sc.nextInt();
}
}
for(int i = 0;i<R;i++){
for(int j =0;j<C;j++){
// ans = Math.max(ans, dfs(i,j));
dfs(i,j);
}
}
System.out.println(max(ans_lst));
return;
}
public static int max(int[][] arr_lst){
int max = -1;
for (int[] ints : ans_lst) {
for (int j = 0; j < ans_lst[0].length; j++) {
max = Math.max(max, ints[j]);
}
}
return max;
}
public static void dfs(int i, int j){
if(ans_lst[i][j]!=0){
// return ans_lst[i][j];
}else {
ans_lst[i][j] = 1;
for(int x=0;x<4;x++){
int ii = i + dx[x];
int jj = j + dy[x];
//1. lower than (i,j) 2. is_in within the boundary
if((is_in(ii,jj)&&(map[i][j]>map[ii][jj]))){
dfs(ii,jj);
ans_lst[i][j] = Math.max(ans_lst[i][j], ans_lst[ii][jj]+1);
}
}
}
// return ans_lst[i][j];
}
public static boolean is_in(int i,int j){
return (0<=i)&&(i<R)&&(0<=j)&&(j<C);
}
}
RMQ algorithm st table
understand
Thanks big guy https://www.bilibili.com/video/av94863271/
f[i][j] means start from ai
2
j
2^j
The maximum value of 2j elements, for example: f[1][0] means starting from a1
2
0
=
1
2^0=1
20 = the maximum value of 1 element, so f[1][0] to f[n][0] is the original sequence. Take an example of an array with n=10👇:
do questions
...