The 10th Blue Bridge Cup Individual Finals Group B

The 10th Blue Bridge Cup Individual Finals Group B

A. Square sequence

topic

Xiao Ming wants to find two positive integersXX andYY , meet2019<X<Y2019<X<Y

201922019^2 ,X2X^2 ,Y2Y^2 compose an arithmetic sequence.

Please find out of all possible solutions,X+YX+YWhat is the minimum value of ?

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

will20192019 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 example2+2017=20192+2017=2019 and2017+2=20192017+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:

  1. Calculate first20192019 all prime numbers
  2. Direct cover 01 backpack template

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

State transition expression:dp[j] += dp[j vec[i]];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 intonxnnxn 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, for7X77 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 integertt , always available

To findtt integers in divisors. Xiaoming for containingttThe smallest number of divisors is very interesting, and

Define it asStS_t. E.gS1=1,S2=2,S3=4,Sa=6, .S_1=1, S_2=2, S_3=4, S_a=6,/dots.

Now Xiao Ming wants to know, whent=100t=100What is S at ? That isS100S_{_{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 is100100 , 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 a5x55x5Starting from the upper left corner of the grid matrix, walk along the side of the grid and meet the following conditions

How many routes are there?

  • The total length does not exceed1212 ;
  • Finally back to the upper left corner;
  • The route is not self-accompanied;
  • Not going out5 55 * 5 is outside the range of the grid matrix.

As shown below, ABCABC are three legal routes. noteBB andCC 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:

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

The title given is5 55 * 5 matrix, but each time it passes through a certain point, so each row and each column should be66 Required variables:

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

DFSDFSEvery time 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 exceeds1212 , pruning; when the length is equal to1111 , 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 stringSS contains stringTT meansTT isSSA subsequence of , which can be derived from the stringSSSeveral characters are extracted from , and they are combined into a new string in the original order andTT exactly the same.

Given two stringsSwithTS and T , may I ask for the least modificationSSHow many characters in can makeSS containsTT ?

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 toLCSLCS (find the longest common subsequence), the idea is generally the same, useDPDP

Define the state

dp[i][j]dp[i][j] represents a stringSS beforeii characters into a stringTTBeforejj characters need to be modifiedSSHow many characters in

State initialization

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

dp[i][0]=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][j] = dp[0][j-1]/: (a[1] == b[j])

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

State transition

When the stringSS beforei 1i-1 , and stringTTBeforejj matches, the stringSS 'sii need not match.

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

When the stringSS beforeii number, and stringTTBeforej 1j-1 match, T has morejj comes out, so you need to put the stringSSAdd one afterT[j]T[j] to matchTT ;

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

When the stringSS beforei 1i-1 and stringTTBeforej 1j-1 match, look at theS[i]S[i] andT[j]T[j]Are same? If they are the same, no operation is required. If they are not the same, you need to changeS[i]S[i] amended toT[j]T[j]

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

dp[i][j]=dp[i 1][j 1]+1dp[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 one11 ~nnpermutation of , if you can include this permutationtt turning points, then it is called at+1t+1 Monotonic sequence.

For example, arrange(1,4,2,3)(1, 4, 2, 3) is a33 monotonic sequence, where44 and22 are all turning points.

givennn andkk , may I ask1 n1~nHow many permutations ofkk monotonic queue?

Input format

Enter a line containing two integersn,kn, 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 by123456123456The remainder of is sufficient.

Sample input

42 copy code

Sample output

12 copy code

Ideas

Let the state bedp[i][j]dp[i][j] represents the frontii number of , there arejj 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 forii number of , to becomei+1i+1 number, it must be insertedi+1i+1 and then it hasi+1i+1 position can be selected.

We found that around the crest22 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[i+1][j]+=dp[i][j] 2dp[i+1][j]+=dp[i][j] 2dp\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[i+1][j+1]=dp[i][j] (j+1)dp[i+1][j+1]=dp[i][j] (j+1)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[i+1][j+2]=dp[i][j] (i+1 j 1 2)dp[i+1][j+2]=dp[i][j] (i+1 j 1 2)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 2424 plastic rods,

Of which yellow plastic rod 44 roots, red88 roots, green1212 (for later useYY means yellow,RR means red,GG represents green).

Initially, these plastic rods are arranged in three circles, as shown in the figure above, the outer circle 1212 , middle circle88 pieces, inner circle44 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 00Starting at o clock, clockwise in turnYRYGRYGRGGGGYRYGRYGRGGGG , the middle circle isRGRGGRRYRGRGGRRY , the inner ring isGGGRGGGR . Then after one clockwise rotation, the outer ring, middle ring, and inner ring sequentially become:GYRYGRYGRGGGGYRYGRYGRGGG ,YRGRGGRRYRGRGGRR andRGGGRGGG .

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

For example, the current outer circle is from 00Starting at o clock, clockwise in turnYRYGRYGRGGGGYRYGRYGRGGGG , the middle circle isRGRGGRRYRGRGGRRY , the inner ring isGGGRGGGR . Then, after rotating counterclockwise once, the outer ring, middle ring, and inner ring sequentially become:RYGRYGRGGGGYRYGRYGRGGGGY ,GRGGRRYRGRGGRRYR andGGRGGGRG

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

Specifically: outer ring 00 o'clock the plastic rod moves to the inner circle00 points, inner circle00Move to the middle circle at o'clock00 points, middle circle00Move to the outer circle at o'clock00 points.

For example, the current outer circle is from 00Starting at o'clock, clockwise in turnYRYGRYGRGGGGYRYGRYGRGGGG , the middle circle isRGRGGRRYRGRGGRRY , the inner ring isGGGRGGGR .

Then after one rotation, the outer ring, middle ring, and inner ring sequentially become:RRYGRYGRGGGGRRYGRYGRGGGG ,GGRGGRRYGGRGGRRY andYGGRYGGR .

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 TT represents the number of groups inquired.(1 T 100)(1 T 100) .

Each set of queries contains 33 lines:

The first line contains 1212 capital letters, representing the outer circle from00The color of each plastic rod starts at o'clock clockwise.

The second line contains 88 capital letters, representing the middle circle from00The color of each plastic rod starts at o'clock clockwise.

The third line contains 44 capital letters, representing the inner circle from00The color of each plastic rod starts at o'clock clockwise.

Output format For each group of queries, output one lineYESYES orNONO , 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 circle00 -33 , the middle circle00 -77 , outer ring00 -1111 .

Assuming the inner circle00No. rod rotates clockwise one circle (that is, the whole clockwise rotation44 times) back again00Position , the middle circle is the original44No. stick is here00Position ; the outer circle is the original88 stick is here00Position . If the whole rotates one more clockwise, the inner circle00Position is still the original00No. bar, the middle circle is still the original00No. rod, the outer circle is44No. 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 RR River Basin, there is an ancient clanRR , they have lived along the river for generations and developed a brilliant civilization by the river.

ZZ family inRRMany buildings have been built along the River. Recently, they are keen to compare. They are always comparing whose buildings are the most peculiar.

fortunately ZZ 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,ZZ 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,ZZEveryone in the 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.

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

Now tell at RRThe changes in the buildings around the 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,NL, 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 values00 .

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

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

If the information is Q a bQ\:\:a\:\:b , which means that the scope of personal life is the first of the riveraa tobb positions (includingaa andb,a bb, 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, output00 .

The output format for each is QQ 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%20\% of the cases with the evaluation,1 L 1000,1 N 10001 L 1000, 1 N 1000 .

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

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

All the peculiar values do not exceed 10910^9A non-negative integer of .

Ideas

Sorting Algorithm

Define an array to store the value of each miracle point, usemapmap de-duplication, the data size is10610^6 so it cannot be usedO(N2)O(N^2)time complexity algorithm uses the built-insortsort function, time complexity isO(NlogN)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