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

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?
solution : Just direct violence ,
answer :563

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 .

solution :BFS, Put the four starting points in queue In the queue , Then one at a time , Turn the four squares around to black , Mark minutes , until 2020 stop it

answer :20312088
#include<iostream> #include<cstring> #include<string> #include<vector> #include
<cmath> #include<algorithm> #include<stack> #include<queue> #include<iomanip> #
define N 100000 #define INF 0x3f3f3f3f #define ll long long #define lson
rt<<1,l,mid #define rson rt<<1|1,mid+1,r using namespace std; bool a[8000][8000]
; int cnt=2020; int dir[4][2]={0,1,0,-1,1,0,-1,0}; struct node{ int x,y,step; };
queue<node>qu; void bfs() { a[0+3000][0+3000]=1; a[2020+3000][11+3000]=1; a[11+
3000][14+3000]=1; a[2000+3000][2000+3000]=1; qu.push(node{0+3000,0+3000,0}); qu.
push(node{2020+3000,11+3000,0}); qu.push(node{11+3000,14+3000,0}); qu.push(node{
2000+3000,2000+3000,0}); while(qu.size()) { node temp=qu.front(); qu.pop(); if(
temp.step==cnt) continue; for(int i=0;i<4;i++) { int xx=temp.x+dir[i][0]; int yy
=temp.y+dir[i][1]; if(!a[xx][yy]) { a[xx][yy]=1; qu.push(node{xx,yy,temp.step+1}
); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int i,j; int sum=0; bfs(); for(i=0;i<8000;i++) for(j=0;j<8000;j++) { sum+=a[i][j
]; } cout<<sum<<endl; return 0; }
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 .

solution : In fact, it is to pick out the factors and ask how many numbers you can make up at most .
To prevent 23=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!=12345=2331*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

answer :39001250856960000
#include<iostream> #include<string> #include<cstring> using namespace std; int
main() { int a[101]; long long sum=1; memset(a,0,sizeof(a)); for(int i=2;i<=100;
i++) { int temp=i; for(int j=2;j<=temp;j++) { while(temp%j==0) { temp=temp/j; a[
j]++; } } } for(int i=2;i<=100;i++) { if(a[i]!=0) sum=sum*(a[i]+1); } cout<<sum
<<endl; }
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
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 )

How many increasing subsequences are there in different nature ?

solution : 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 .
answer :3616159
#include<iostream> #include<cstring> #include<string> #include<queue> #include
<map> using namespace std; map<string,int>mp; int main() { string str; int ans=0
; cin>>str; queue<pair<string,int> >qu; for(int i=0;i<=str.size()-1;i++) {
string s=""; s=s+str[i]; if(!mp[s]) { mp[s]++; qu.push(make_pair(s,i)); ans++; }
} while(qu.size()) { string st=qu.front().first; int ii=qu.front().second; qu.
pop(); for(int i=ii+1;i<=str.size()-1;i++) { if(str[i]>str[ii]&&!mp[st+str[i]])
{ mp[st+str[i]]=1; qu.push(make_pair(st+str[i],i)); ans++; } } } cout<<ans<<endl
; }
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 :

solution : similarly BFS, Start with each grid , Violence is good
answer :552
#include<iostream> #include<cstring> using namespace std; long long ans; int
dir[4][2]={ {0,1},{1,0},{0,-1},{-1,0} }; int vis[4][4]; void dfs(int x,int y,int
cnt) { if(x>=4||y>=4||x<0||y<0) return ; if(cnt==16) { ans++; } for(int i=0;i<4
;i++) { int xx=x+dir[i][0]; int yy=y+dir[i][1]; if(vis[xx][yy]) continue; vis[xx
][yy]=1; dfs(xx,yy,cnt+1); vis[xx][yy]=0; } } int main() { for(int i=0;i<4;i++)
for(int j=0;j<4;j++) { memset(vis,0,sizeof(vis)); vis[i][j]=1; dfs(i,j,1); vis[i
][j]=0; } cout<<ans<<endl; }

©2019-2020 Toolsou All rights reserved,
Huawei 2021 session Hardware Engineer Logical post (FPGA) Super detailed surface !!!Vue-element-admin upgrade ui edition virtual machine VMware Download and install the most detailed tutorial !C++ Move constructor and copy constructor sound of dripping water java Backstage interview pygame Realize full screen mode and adjustable window size mysql Database setting character set configuration modification my.ini file (windows)30 What's the experience of being a junior programmer at the age of 20 C++ Multithreading programming ( Summary of common functions and parameters )python_ cherry tree