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
Daily Recommendation