# A. Square sequence

## topic

Xiao Ming wants to find two positive integers$X$ and$Y$ , meet$2019<X<Y$

$2019^2$ ,$X^2$ ,$Y^2$ compose an arithmetic sequence.

Please find out of all possible solutions,$X+Y$What is the minimum value of$Y$ ?

## Ideas

Since it is a fill-in-the-blank question, you can violently enumerate the numbers in a range to determine whether it is the minimum value.

## Code

```
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
ll sum = 2019 * 2019 ;
ll MIN = INT_MAX;
for (ll x = 2020 ; x < 10000 ; x++) {
for (ll y = 2021 ; y < 10000 ; y++) {
if ( 2 * x * x-y * y == sum) {
MIN = min (MIN, x + y);
}
}
}
cout << MIN << endl;
return 0 ;
}
Copy code
```

# B. Prime number split

## topic

will$2019$ divided into the sum of several different prime numbers. How many different methods are there in total?

Note that the order of exchange is considered the same method, for example$2+2017=2019$ and$2017+2=2019$ as the same method

## Ideas

Fill-in-the-blank question. Since this question uses two different prime numbers, each prime number can only be used once, so the abstract is the classic **01 backpack problem** , which can be solved directly by **dynamic programming**

Specific steps:

- Calculate first$2019$ all prime numbers
- Direct cover 01 backpack template

I use the rolling array here to optimize the space complexity of 01 backpack

State transition expression:$dp\left[j\right]\:+=\:dp\left[j\:-\:vec\left[i\right]\right];$

## Code

```
# include <bits/stdc++.h>
using namespace std;
# define mm(a) memset(a, 0, sizeof(a))
const int MAXN = 3000 ;
typedef long long ll;
ll dp[MAXN];
bool isPrime ( int n) {
if (n <= 3 ) {
return n> 1 ;
}
for ( int i = 2 ; i <n; i++) {
if (n% i == 0 ) {
return false ;
}
}
return true ;
}
int main () {
vector<ll> vec;
for (ll i = 1 ; i <= 2019 ; i++) {
if ( isPrime (i)) vec. push_back (i);
}
mm (dp);
dp[ 0 ] = 1 ;
for ( int i = 0 ; i <vec. size (); i++) {
for ( int j = 2019 ; j >= vec[i]; j--) {
dp[j] += dp[j-vec[i]];
}
}
cout << dp[ 2019 ] << endl;
return 0 ;
}
Copy code
```

# C. Splicing

## topic

Xiao Ming wants to cut a piece of wood into two pieces, and then join them into a right angle.

As shown in the figure below, he divided the middle part into$nxn$ small squares, he marked whether each small square belongs to the left or the right. Then cut the wood along the dividing line on both sides, rotate the right side upwards and join them together.

It is required that each small square belongs to the left or the right, and the ones on the same side must be connected.

When splicing, the spliced part must be kept inside the original large square.

Excuse me, for$7 7$ small squares, how many legal ways are there to divide small squares

## Ideas

## Code

# D. Evaluation

## topic

After learning about divisors, Xiao Ming was very curious about divisors. He found that given a positive integer$t$ , always available

To find$t$ integers in divisors. Xiaoming for containing$t$The smallest number of$t$ divisors is very interesting, and

Define it as$S_t$. E.g$S_1=1, S_2=2, S_3=4, S_a=6,/dots.$

Now Xiao Ming wants to know, when$t=100$What is S at$1$$0$$0$ ? That is$S_{_{100}}$how many

## Ideas

Fill-in-the-blank questions can be done directly with violence, and directly calculate the approximate number of each number when the approximate number is$100$ , it is the result value

## Code

```
# include <bits/stdc++.h>
using namespace std;
int solve ( int n)
{
int count = 0 ;
for ( int i = 1 ; i <= n; ++i)
if (n% i == 0 ) count++;
return count;
}
int main () {
for ( int i = 1 ; i < 100000 ; i++) {
if ( solve (i) == 100 ) {
cout << i << endl;
break ;
}
}
return 0 ;
}
Copy code
```

# E. Path count

## topic

From a$5x5$Starting from the upper left corner of the$5$$x$$5$ grid matrix, walk along the side of the grid and meet the following conditions

How many routes are there?

- The total length does not exceed$12$ ;
- Finally back to the upper left corner;
- The route is not self-accompanied;
- Not going out$5 * 5$ is outside the range of the grid matrix.

As shown below, $ABC$ are three legal routes. note$B$ and$C$ due to different directions, so

Treated as a different route

## Ideas

Fill-in-the-blank questions, classic search questions, here I use **DFS backtracking pruning** to count the number of paths.

There are several requirements for the topic:

- The total length does not exceed$12$ (Use count to count distance)
- Finally back to the upper left corner (ie the starting point)
- The route is not self-intersecting (can only pass through a certain point once, except for the starting point)
- Do not go out of the grid range (always keep within this range)

The title given is$5 * 5$ matrix, but each time it passes through a certain point, so each row and each column should be$6$ Required variables:

- Define a matrix to store whether a certain point has passed
- Define a variable ($ans$ ) to store the results, how many paths are there in total?
- Define a two-dimensional array to store specific enumeration directions

$DFS$Every time$D$$F$$S$ passes through a point, it needs to be judged whether it is within the interval, whether it has visited the point and whether the path length exceeds$12$ , pruning; when the length is equal to$11$ , and the position is exactly to the right of the starting point or below the starting point at this time, it is the correct path, and statistics are required;

## Code

```
# include <bits/stdc++.h>
using namespace std;
const int N = 6 ;
bool vis[N][N];
int d[ 4 ][ 2 ] = {{ 1 , 0 }, { -1 , 0 } , { 0 , 1 }, { 0 , -1 }};
int ans = 0 ;
bool inArea ( int x, int y) {
return x >= 0 && x < 6 && y >= 0 && y < 6 ;
}
void dfs ( int x, int y, int len) {
//If it is out of bounds, the length is greater than 12, or if it has been visited, it will directly return
if (! inArea (x, y) || len> 12 || vis[x][y] ) return ;
//If the length is less than 12 and it is the point to the right of the starting point or the point below, it can be reached.
//Among them, there is a special case where the traversal has not started when the number of steps is 1,
so you need to exclude these two special cases
if (len <= 11 && ((x == 0 && y == 1 ) || (x == 1 && y == 0 ))) {
if (len != 1 ) {
ans++;
return ;
}
}
vis[x][y] = true ; //mark the change point has been visited
for ( int i = 0 ; i < 4 ; i++) {
int x1 = x + d[i][ 0 ], y1 = y + d [i][ 1 ];
dfs (x1, y1, len + 1 );
}
vis[x][y] = false ;
}
int main () {
dfs ( 0 , 0 , 0 );
cout << ans<< endl; //206
return 0 ;
}
Copy code
```

# F. Optimal inclusion

## topic

**Problem Description**

We call a string$S$ contains string$T$ means$T$ is$S$A subsequence of$S$ , which can be derived from the string$S$Several characters are extracted from$S$ , and they are combined into a new string in the original order and$T$ exactly the same.

Given two strings$S and T$ , may I ask for the least modification$S$How many characters in$S$ can make$S$ contains$T$ ?

**Input format**

Enter two lines, one string per line. The string in the first line is S, and the string in the second line is T.

Both strings are non-empty and only contain uppercase English letters.

**Output format**

Output an integer to indicate the answer.

**Sample input**

ABCDEABCD XAABZ Copy code

**Sample output**

3 copy the code

## Ideas

Programming questions, somewhat similar to$LCS$ (find the longest common subsequence), the idea is generally the same, use$DP$

**Define the state**

$dp[i][j]$ represents a string$S$ before$i$ characters into a string$T$Before$T$$j$ characters need to be modified$S$How many characters in$S$

**State initialization**

$dp[i][1] = dp[i-1][0]\:/: (a[i] != b[1])$

$dp[i][0] = 0\:/: (a[i] == b[1])$

$dp[0][j] = dp[0][j-1]/: (a[1] == b[j])$

$dp[0][1] = dp[0][i-1] + 1/:/: (a[1] != b[j])$

**State transition**

When the string$S$ before$i-1$ , and string$T$Before$T$$j$ matches, the string$S$ 's$i$ need not match.

$dp[i][j] = dp[i-1][j]$

When the string$S$ before$i$ number, and string$T$Before$T$$j-1$ match, T has more$j$ comes out, so you need to put the string$S$Add one after$S$$T[j]$ to match$T$ ;

$dp[i][j] = dp[i][j-1] + 1$

When the string$S$ before$i-1$ and string$T$Before$T$$j-1$ match, look at the$S[i]$ and$T[j]$Are$T$$[$$j$$] the$ same? If they are the same, no operation is required. If they are not the same, you need to change$S[i]$ amended to$T[j]$

$dp[i][j] = dp[i-1][j-1]$

$dp[i][j] = dp[i-1][j-1] + 1$

## Code

```
# include <bits/stdc++.h>
using namespace std;
const int N = 1010 ;
int dp[N][N];
char a[N], b[N];
int m, n;
int main () {
//ABCDEABCD
//XAABZ
scanf ( "%s%s" , a + 1 , b + 1 );//The subscript starts from 1 for easy operation
int n = strlen (a + 1 ), m = strlen (b + 1 );
dp[ 0 ][ 0 ] = a[ 1 ] == b[ 1 ]? 0 : 1 ;
for ( int i = 1 ; i <= n; i++) {
if (a[i] == b[ 1 ] ) dp[i][ 0 ] = 0 ;
else dp[i][ 1 ] = dp[i- 1 ][ 0 ];
}
for ( int j = 1 ; j <= m; j++) {
if (a[ 1 ] == b[j]) dp[ 0 ][j] = dp[ 0 ][j- 1 ];
else dp[ 0 ][j] = dp[ 0 ][j- 1 ] + 1 ;
}
for ( int i = 1 ; i <= n; i++) {
for ( int j = 1 ; j <= m; j++) {
dp[i][j] = min (dp[i][j- 1 ] + 1 , dp[i- 1 ][j]);
if (a[i] == b[j]) dp[i] [j] = min (dp[i][j], dp[i- 1 ][j- 1 ]);
else dp[i][j] = min (dp[i][j], dp[i- 1 ][j- 1 ] + 1 );
}
}
cout << dp[n][m] << endl;
return 0 ;
}
Copy code
```

# G. Number of permutations

## topic

**Problem Description**

In an arrangement, a breakpoint refers to an element in the arrangement that is smaller than the elements on both sides at the same time, or larger than the elements on both sides at the same time.

For one$1$ ~$n$permutation of$n$ , if you can include this permutation$t$ turning points, then it is called a$t+1$ Monotonic sequence.

For example, arrange$(1, 4, 2, 3)$ is a$3$ monotonic sequence, where$4$ and$2$ are all turning points.

given$n$ and$k$ , may I ask$1~n$How many permutations of$1$$n$$k$ monotonic queue?

**Input format**

Enter a line containing two integers$n, k$ .

**Output format**

Output an integer to indicate the answer. The answer may be large, but you need to output the permutation that meets the conditions

Number divided by$123456$The remainder of$1$$2$$3$$4$$5$$6$ is sufficient.

**Sample input**

42 copy code

**Sample output**

12 copy code

## Ideas

Let the state be$dp[i][j]$ represents the front$i$ number of$i$ , there are$j$ breakpoints, we can find that the number of breakpoints is the number of crests + troughs.

Although the transfer equation is very simple after the introduction, it is not particularly easy to push. We have to look at the various situations first, and finally sum up and you will find that the transfer is very simple.

For the number of different turning points, we consider the odd and even numbers, and for each situation we consider whether the last one is the peak or the trough.

Then for$i$ number of$i$ , to become$i+1$ number, it must be inserted$i+1$ and then it has$i+1$ position can be selected.

We found that around the crest$2$ positions are special. Insert them here, and the number of breakpoints remains unchanged.

If the last one is a trough, then the insertion at the end will not change. If the first one is also a trough, then the insertion at the first position will also be the same (divided into odd and even, and the last one is the peak and trough, you can judge the two cases. ).

Inserting at the remaining positions will add two breakpoints. The final summary is

$dp\left[i+1\right]\left[j\right]+=dp\left[i\right]\left[j\right]\cdot 2dp\left[i+1\right]\left[j/right]+=dp\left[i\right]\left[j\right] 2$

$dp\left[i+1\right]\left[j+1\right]=dp\left[i\right]\left[j\right]\cdot/left(j+1\right)dp\left[ i+1\right]\left[j+1\right]=dp\left[i\right]\left[j\right]/left(j+1\right)$

$dp\left[i+1\right]\left[j+2\right]=dp\left[i\right]\left[j\right]\cdot/left(i+1-j-1-2/right)dp\left[i+1\right]\left[j+2\right]=dp\left[i\right]\left[j\right]/left(i+1 j 1 2/right)$

## Code

```
# include <bits/stdc++.h>
using namespace std;
const int N = 505 ;
const int mod = 123456 ;
int dp[N][N];
int main () {
int n, k;
cin >> n >> k;
dp[ 1 ][ 0 ] = 1 ;
for ( int i = 2 ; i <= n; i++) {
dp[i][ 0 ] = 2 ;
for ( int j = 0 ; j <= i- 2 ; j++) {
dp[i][j] %= mod;
dp[i + 1 ][j] += dp[i][j] * (j + 1 );
dp[i + 1 ][j + 1 ] += dp[i][j] * 2 ;
dp[i + 1 ][j + 2 ] += dp[i][j] * (i-j- 2 );
}
}
cout << dp[n][k- 1 ]% mod << endl;
return 0 ;
}
Copy code
```

# H. Puzzle game

## topic

**Title description**

Xiao Ming is playing a puzzle game, the puzzle is $24$ plastic rods,

Of which yellow plastic rod $4$ roots, red$8$ roots, green$12$ (for later use$Y$ means yellow,$R$ means red,$G$ represents green).

Initially, these plastic rods are arranged in three circles, as shown in the figure above, the outer circle $12$ , middle circle$8$ pieces, inner circle$4$ pieces.

Xiao Ming can perform three operations:

Rotate all three circles of the plastic rod clockwise by one unit.

For example, the current outer circle is from $0$Starting at$0$ o clock, clockwise in turn$YRYGRYGRGGGG$ , the middle circle is$RGRGGRRY$ , the inner ring is$GGGR$ . Then after one clockwise rotation, the outer ring, middle ring, and inner ring sequentially become:$GYRYGRYGRGGG$ ,$YRGRGGRR$ and$RGGG$ .

Rotate the three circles of plastic rods counterclockwise by one unit.

For example, the current outer circle is from $0$Starting at$0$ o clock, clockwise in turn$YRYGRYGRGGGG$ , the middle circle is$RGRGGRRY$ , the inner ring is$GGGR$ . Then, after rotating counterclockwise once, the outer ring, middle ring, and inner ring sequentially become:$RYGRYGRGGGGY$ ,$GRGGRRYR$ and$GGRG$

Will three laps $0$The plastic rod at$0$ o'clock is rotated.

Specifically: outer ring $0$ o'clock the plastic rod moves to the inner circle$0$ points, inner circle$0$Move to the middle circle at$0$ o'clock$0$ points, middle circle$0$Move to the outer circle at$0$ o'clock$0$ points.

For example, the current outer circle is from $0$Starting at$0$ o'clock, clockwise in turn$YRYGRYGRGGGG$ , the middle circle is$RGRGGRRY$ , the inner ring is$GGGR$ .

Then after one rotation, the outer ring, middle ring, and inner ring sequentially become:$RRYGRYGRGGGG$ ,$GGRGGRRY$ and$YGGR$ .

Xiao Ming's goal is to move all green to the outer circle, all red to the middle circle, and all yellow to the inner circle. Given the initial state, would you please judge whether Xiao Ming can achieve the goal?

**Input format**

The first line contains an integer $T$ represents the number of groups inquired.$(1 T 100)$ .

Each set of queries contains $3$ lines:

The first line contains $12$ capital letters, representing the outer circle from$0$The color of each plastic rod starts at$0$ o'clock clockwise.

The second line contains $8$ capital letters, representing the middle circle from$0$The color of each plastic rod starts at$0$ o'clock clockwise.

The third line contains $4$ capital letters, representing the inner circle from$0$The color of each plastic rod starts at$0$ o'clock clockwise.

**Output format**
For each group of queries, output one line$YES$ or$NO$ , represents whether Xiao Ming can achieve the goal.

**Sample input**

2 GYGGGGGGGGGG RGRRRRRR YRYY YGGGRRRRGGGY YGGGRRRR YGGG Copy code

**Sample output**

YES NO Copy code

## Ideas

After observation, each rotation can only rotate three times together, but the side lengths are different, the inner ring is four times a week, the middle ring is eight times a week, and the outer ring is twelve times a week.

Set the initial rod number as the inner circle$0$ -$3$ , the middle circle$0$ -$7$ , outer ring$0$ -$11$ .

Assuming the inner circle$0$No.$0$ rod rotates clockwise one circle (that is, the whole clockwise rotation$4$ times) back again$0$Position$0$ , the middle circle is the original$4$No.$4$ stick is here$0$Position$0$ ; the outer circle is the original$8$ stick is here$0$Position$0$ . If the whole rotates one more clockwise, the inner circle$0$Position$0$ is still the original$0$No.$0$ bar, the middle circle is still the original$0$No.$0$ rod, the outer circle is$4$No.$4$ stick;

By analogy with the above, it will be found that no matter how the whole rod rotates, each rod in the inner ring follows the two rods in the middle ring and the three rods in the outer ring. That is, each rod in the inner circle is bound to the two rods in the middle circle and the three rods in the outer circle.

The above picture is an example, the blue box in the picture is bound together.

In the same way, the whole can be divided into four parts, and it is only necessary to judge whether the color in each part can be satisfied.

## Code

```
# include <bits/stdc++.h>
using namespace std;
int t;
string s1, s2, s3;
int main ()
{
cin >> t;
while (t--)
{
int flag = 0 ;
cin >> s3 >> s2 >> s1;
for ( int i = 0 ; i < 4 ; i++)
{
map< char , int > mp; //Inner circle
mp[s1[i]] += 1 ; //Middle circle
mp[s2[i]] += 1 ;
mp[s2[i + 4 ]] += 1 ; //outer ring
mp[s3[i]] += 1 ;
mp[s3[i + 4 ]] += 1 ;
mp[s3[i + 8 ]] += 1 ;
if (mp[ 'Y' ] != 1 || mp[ 'R' ] != 2 || mp[ 'G' ] != 3 )
{
flag = 1 ;
break ;
}
}
if (flag == 0 )
cout << "YES" << endl;
else
{
cout << "NO" << endl;
}
}
return 0 ;
}
Copy code
```

# I. The Eighth Wonder

## topic

The problem is described in one $R$ River Basin, there is an ancient clan$R$ , they have lived along the river for generations and developed a brilliant civilization by the river.

$Z$ family in$R$Many buildings have been built along the$R$ River. Recently, they are keen to compare. They are always comparing whose buildings are the most peculiar.

fortunately $Z$ people have the same understanding of peculiarities. They quickly scored each building, so that it is easy to choose who is the most peculiar.

So, based on the score, everyone quickly rated the most peculiar building, called a miracle.

Later, they successively selected the second peculiar, second peculiar,..., and seventh peculiar buildings, which were called the second miracle, the third miracle,..., and the seventh miracle in turn.

Recently, they began to select the eighth peculiar building, preparing to name it the eighth wonder. In the selection, they encountered some problems.

first of all,$Z$ family has been developing. Some buildings have been demolished and new buildings have been built. The peculiar values of the new buildings are different from the original ones, which makes the selection not so easy.

Secondly,$Z$Everyone in the$Z$ family may live in different areas. The buildings they have seen are not all buildings. They insist that the eighth strange building they have seen is the eighth wonder.

$Z$ leader of the$Z$ family has a headache recently. He is afraid that it will be caused by disagreement.$Z$ group is divided. When he found you, he wanted to know what the miracle the people think is like.

Now tell at $R$The changes in the buildings around the$R$ River and the living areas of some people during the change process, please program to find out what is the peculiar value of the eighth miracle that everyone thinks.

**Input format**

The first line of input contains two integers $L, N$ represents the length of the river and the amount of information to be processed. At the beginning there are no buildings along the river, or all the peculiar values$0$ .

Next $N$ lines, each line has one piece of information you want to process.

If the information is $C\:\:p\:\:x$ , which means the$p$ positions$(1 p L)$ established a building with a peculiar value$x$ . If there is an original building at this location, the original building will be demolished.

If the information is $Q\:\:a\:\:b$ , which means that the scope of personal life is the first of the river$a$ to$b$ positions (including$a$ and$b, a b$ ), then you have to calculate the peculiar value of the eighth miracle in this interval and output it. If you can t find the eighth wonder, output$0$ .

The output format for each is $Q$ information, you need to output an integer that represents the peculiar value of the eighth wonder in the interval.

Sample input

10 15 C 1 10 C 2 20 C 3 30 C 4 40 C 5 50 C 6 60 C 7 70 C 8 80 C 9 90 C 10 100 Q 1 2 Q 1 10 Q 1 8 C 10 1 Q 1 10 Copy code

**Sample output**

0 30 10 20 Copy code

**data range**

for $20\%$ of the cases with the evaluation,$1 L 1000, 1 N 1000$ .

for $40\%$ Reviews use cases,$1 L 10000, 1 N 10000$ .

for $100\%$ Reviews use cases,$1 L 100000, 1 N 100000$ .

All the peculiar values do not exceed $10^9$A non-negative integer of$_{9}$ .

## Ideas

Sorting Algorithm

Define an array to store the value of each miracle point, use$map$ de-duplication, the data size is$10^6$ so it cannot be used$O(N^2)$time complexity algorithm uses the built-in$sort$ function, time complexity is$O(NlogN)$ , but it is recommended to merge and sort by hand

## Code

```
# include <bits/stdc++.h>
using namespace std;
int L, N;
vector<pair< int , int >> vec;
map< int , int > mp;
bool cmp (pair< int , int > a, pair< int , int > b) {
return a.second> b.second;
}
void add ( int postion, int value) {
if (mp. find (postion) != mp. end ()) {
for ( int i = 0 ; i <vec. size (); i++) {
if (vec[i ].first == postion) {
vec[i].second = value;
break ;
}
}
} else {
pair< int , int > p (postion, value);
vec. push_back (p);
}
mp[postion] = value;
}
void sout ( int start, int end) {
vector<pair< int , int >> temp;
for ( int i = 0 ; i <vec. size (); i++) {
if (vec[i].first <= end && vec[i].first >= start )
temp. push_back (vec[i]);
}
if (temp. size () < 8 ) {
cout << 0 << endl;
return ;
}
sort (temp. begin (), temp. end (), cmp);
cout << temp[ 7 ].second << endl;
}
int main () {
cin >> L >> N;
while (N--) {
char op;
int a, b;
cin >> op >> a >> b;
if (op == 'C' ) add (a, b);
else sout (a, b);
}
return 0 ;
}
Copy code
```