- 2020-11-14 19:45
*views 2*- queue
- Deep search
- Competition experience
- algorithm

2020/11/14 It split

<> The 11th National Blue Bridge Cup C/C++B Group summary

It is mainly a summary of filling in the blanks （ The big question doesn't work at all ）, Fill in the blanks, I feel it's OK ? Hope to get good results .

The answer is not necessarily correct , The main reason is that more people look at the answer , Welcome to discuss .

The code is also typed right now , Welcome to point out the mistake .

<> test questions A: beautiful 2

Total score of this question :5 branch

【 Problem description 】

Xiao Lan likes it very much 2, This year is A.D 2020 year , He was very happy .

He was curious , In A.D 1 Year to A.D 2020 year ( contain ) in , How many digits of a year contain numbers 2?

right key ：

563

code ：

slightly - -.....

<> test questions B: spread

Total score of this question :5 branch

【 Problem description 】

Xiao Lan paints on an infinite special canvas .

This canvas can be seen as a grid , Each grid can be represented by a two-dimensional integer coordinate .

Xiao Lan first made a few dots on the canvas :(0, 0), (2020, 11), (11, 14), (2000, 2000).

Only these squares are black , The rest are white .

Every minute , Black will spread a little bit . concrete , If the inside of a grid is black , It will spread to the world , lower , Left , In the right four adjacent cells , Make these four squares black ( If it turns out to be black , It's still black ).

Excuse me? , after 2020 Minutes later , How many squares are black on the canvas .

right key ：

20312088

thinking ：

namely BFS, Take these four points push Enter a queue , Then every time you go out of the team, you turn the dots around it black （ Pay attention to weight removal ）, Then mark the time , time =2020 Just exit .

code ：

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include

<cstring> #include<stack> #include<set> #include<map> #include<queue> #include

<algorithm> #include<unordered_set> #define ll long long #define pii

pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back

#define G 6.67430*1e-11 #define rd read() #define pi 3.1415926535 using

namespace std; const ll mod = 998244353; inline ll read() { ll x = 0, f = 1;

char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch =

getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48

); ch = getchar(); } return x * f; } ll gcd(ll a, ll b) { return !b ? a : gcd(b,

a% b); } queue < pair<pair<int, int>, int > >q;

// Record each one <x,y> The coordinates are the third t It turns black in seconds x,y,t Corresponding to the previous three dimensions map<pii, int> vis; int nexti[4][2] = { {1

,0},{0,1},{-1,0},{0,-1} }; int main() { q.push(mp(mp(0, 0), 0)); q.push(mp(mp(

2020, 11), 0)); q.push(mp(mp(11, 14), 0)); q.push(mp(mp(2000, 2000), 0)); vis[mp

(0, 0)] = 1; vis[mp(2020, 11)] = 1; vis[mp(11, 14)] = 1; vis[mp(2000, 2000)] = 1

; ll ans = 4; int bf = -1; while (1) { auto p = q.front().first; int time = q.

front().second; /*if (bf != time) { bf = time; cout << time << endl; }*/ if (

time== 2020)break;// This is 2020 Minutes generated for (int i = 0; i < 4; i++) { int nx = p.first

+ nexti[i][0]; int ny = p.second + nexti[i][1]; if (!vis[mp(nx,ny)]) { vis[mp(nx

, ny)] = 1; ans++; q.push(mp(mp(nx, ny), time + 1)); } } q.pop(); } cout << ans;

}

( It's a long run , I attached the screenshot directly ）

<> test questions C: Factorial divisor

Total score of this question :10 branch

【 Problem description 】

Define factorial n! = 1 × 2 × 3 × · · · × n.

Excuse me? 100! （100 factorial ） How many divisors are there .

right key ：

39001250856960000

thinking ：

In fact, it is to pick out the factors and ask how many numbers you can make up at most .

To prevent 2*3=6 Repeated calculation of , We can't just pick , So we should first use the unique decomposition theorem to decompose it into the product of prime factors

as ：5!=1*2*3*4*5=23*31*51;

So now the situation has changed ：2 yes 4 A choice （0,1,2,3 individual ）,3 yes 2 A choice （0,1 individual ）,5 yes 2 A choice （0,1 individual ）. That is, the number of choices of each prime factor is its power +1.

So for 100! The answer to this question is to 2-100 To decompose each number of , Record the number of each prime factor , then +1 Just multiply it

code ：

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include

<cstring> #include<stack> #include<set> #include<map> #include<queue> #include

<algorithm> #include<unordered_set> #define ll long long #define pii

pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back

#define G 6.67430*1e-11 #define rd read() #define pi 3.1415926535 using

namespace std; const ll mod = 998244353; inline ll read() { ll x = 0, f = 1;

char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch =

getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48

); ch = getchar(); } return x * f; } ll gcd(ll a, ll b) { return !b ? a : gcd(b,

a% b); } int flag[105]; int main() { int i; for (int i = 2; i <= 100; i++) {

int tmp = i; for (int j = 2; j <= tmp; j++) { while (tmp % j == 0) { tmp /= j;

flag[j]++; } } } ll ans = 1; for (int i = 1; i <= 100; i++) { ans *= flag[i] + 1

; } cout << ans; }

<> test questions D: Essential ascending sequence

Total score of this question :10 branch

【 Problem description 】

Xiao Lan especially likes monotonous things .

In a string , If you take out several characters , It is monotonically incrementing to arrange these characters in the order in the string , Becomes a monotonically increasing subsequence of the string .

for example , In string lanqiao in , If you take out characters n and q, be nq Form a monotone increasing subsequence . Similar monotone increasing subsequences also exist lnq,i,ano wait .

Xiaolan found , Some subsequences have different positions , But the character sequence is the same , For example, the second character and the last character can be retrieved ao, You can also get the last two characters

ao. Xiao Lan doesn't think they are fundamentally different .

For a string , Xiao Lan wants to know , How many increasing subsequences are there in different nature ?

for example , For Strings lanqiao, The increasing subsequences with different nature are 21 individual . They are

l,a,n,q,i,o,ln,an,lq,aq,nq,ai,lo,ao,no,io,lnq,anq,lno,ano,aio.

For the following string ( common 200

A small English letter , Display in four lines ):( If you copy the following text to a text file , Be sure to check that the copied content is consistent with that in the document . There is a file under the examination directory

inc.txt, The content is the same as the text below )

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

How many increasing subsequences are there in different nature ?

right key ：

3616159

thinking ：

Let's first consider what to do if there are duplicate strings ： such as axxbxxxb, So there are two ab Longest increasing subsequence , For the ab Longest increasing subsequence , We can find that it must be the previous one ab The number of increasing subsequences of >= The second one is , It can be said that the answer to the second one is that the first one is a subset . For the same incremental subsequence, we only need to record the earliest occurrence , There is no need to manage the subsequent emergence .

Based on the above , We can use it BFS, Using queues , The position of the string and the last character of the incremental subsequence are recorded in the queue , For each string at the head of the team s, Its end position is set to t, We just need to start from the t+1 reach s.size()-1 Location to find anything better than s[t] Large ones can be inserted into the queue , This process is de duplication , Just count .

code ：

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include

<cstring> #include<stack> #include<set> #include<map> #include<queue> #include

<algorithm> #include<unordered_set> #define ll long long #define pii

pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back

#define G 6.67430*1e-11 #define rd read() #define pi 3.1415926535 using

namespace std; const ll mod = 998244353; inline ll read() { ll x = 0, f = 1;

char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch =

getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48

); ch = getchar(); } return x * f; } ll gcd(ll a, ll b) { return !b ? a : gcd(b,

a% b); } map<string, int> vis; int main() { queue<pair<string, int>> q; string

s; cin >> s; int i; ll ans = 0; for (i = 0; i < s.size(); i++) { string tmp = ""

; tmp += s[i]; if (!vis[tmp]) { vis[tmp] = 1; q.push(mp(tmp, i)); ans++; } }

while (q.size()) { string t = q.front().first; int pos = q.front().second; q.pop

(); for (int i = pos + 1; i < s.size(); i++) { if (s[i] > s[pos] && !vis[t + s[i

]]) { vis[t + s[i]] = 1; q.push(mp(t + s[i], i)); ans++; } } } cout << ans; }

This problem also needs some time to put the screenshot directly ：

<> test questions E: paper serpent

Total score of this question :15 branch

【 Problem description 】

Xiao Lan has a toy snake , All in all 16 section , It's marked with numbers 1 to 16. Each section is in the shape of a square . The two adjacent sections can be in a straight line or in a straight line 90 Degree angle .

Xiaolan has another one 4 × 4 The square box of , For storing toy snakes , The square of the box is marked with letters in turn A reach P common 16 Two letters .

Xiaolan can fold her toy snake into a box . He found that , There are many ways to put a toy snake in it .

The figure below shows two options :

right key ：

552

thinking ：

This question ... It's a little simple. What's going on .... It's mindless DFS, enumeration 4*4 The location of a snake's head , Then search down and it's done .... It's not as good as it feels B,C,D It's very difficult .

code ：

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include

<cstring> #include<stack> #include<set> #include<map> #include<queue> #include

<algorithm> #include<unordered_set> #define ll long long #define pii

pair<int,int> #define pll pair<ll,ll> #define mp make_pair #define pb push_back

#define G 6.67430*1e-11 #define rd read() #define pi 3.1415926535 using

namespace std; const ll mod = 998244353; inline ll read() { ll x = 0, f = 1;

char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch =

getchar(); } while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48

); ch = getchar(); } return x * f; } ll gcd(ll a, ll b) { return !b ? a : gcd(b,

a% b); } int vis[5][5]; int nexti[4][2] = { {0,1},{1,0},{0,-1},{-1,0} }; ll ans

= 0; void dfs(int x, int y,int count) { if (x >= 4 || x < 0 || y >= 4 || y < 0)

return; if (count == 16) { ans++; } for (int i = 0; i < 4; i++) { int nx = x +

nexti[i][0]; int ny = y + nexti[i][1]; if (!vis[nx][ny]) { vis[nx][ny] = 1; dfs(

nx, ny, count + 1); vis[nx][ny] = 0; } } } int main() { int i; for (i = 0; i < 4

; i++) { for (int j = 0; j < 4; j++) { vis[i][j] = 1; dfs(i, j, 1); vis[i][j] =

0; } } cout << ans; }

The main topic is omitted .. I know a little about it, so I'm not mistaken for others .

Here is my idea of answering the question （ No guarantee of correctness ）：

<> test questions H: answering question

Total score of this question :20 branch

【 Problem description 】

yes n Each student asked the teacher to answer questions at the same time . Each student estimated the time of answering questions in advance .

The teacher can arrange the order of answering questions , Students should enter the teacher's office in turn to answer questions .

The process of a student answering questions is as follows ：

* Enter the office first , No i What do you need si Millisecond time .

* Then students ask questions and teachers answer them , No i What do you need ai Millisecond time .

* After answering questions , My classmates are very happy , A message will be sent in the course group , It will take a long time

To ignore .

* Finally, the students packed up and left the office , need ei Millisecond time . General needs 10 second ,

20 Seconds or 30 second , Namely ei The value is 10000,20000 or 30000.

After a classmate left the office , Then the next student can enter the office .

Answer questions from 0 The moment begins . The teacher wants to arrange the order of answering questions reasonably , Make students in the course group

The sum of sending messages is the smallest .

thinking ：

greedy , greedy strategy ：s+a+e Sort from small to large . Proof process ：

Technology

- Python146 blogs
- Java131 blogs
- Vue86 blogs
- Flow Chart79 blogs
- javascript42 blogs
- C++41 blogs
- programing language38 blogs
- MySQL37 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

The problem of string left rotation Interview essential ： Data structure time complexity and usage Remove outliers , use python to write matlab Of hampel(X) function BN layer pytorch realization Linux C Three methods of redirecting standard input and output to file [ Thesis reading ]HRNetV1,HRNetV2,HRNetV2p2021 World ranking of Computer Science Major ! This year's ranking reshuffle What certificates can big data test ? use Python and Pygame Implementation of code rain 2020 The 11th National Blue Bridge Cup B group C/C++