<>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 ,

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

#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

#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
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 )

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 .
#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