It's the annual Blue Bridge Cup again , The distribution of the Blue Bridge Cup has changed , As always, if I remember correctly 3-5 Fill in the blanks , This year, contrary to usual, only 2 Fill in the blanks , Relative to previous “ Brute force cup ” and “dp cup ”, Now the reading difficulty of the Blue Bridge Cup is reduced , Mathematical knowledge and greed have also increased .
First question ： test questions A: Nine to ten

Problem solving ： In recent years, the punch in questions have tended to focus on basic computer knowledge , If this question is from a major, you should learn the knowledge of binary conversion in the course of computer composition principle ,93*2+92*0+90
*2=1478
#include <bits/stdc++.h> using namespace std; int main() { cout<<9*9*9*2+9*2+1*
2; return 0; }
Running results

Second question ： test questions B: Shunzi date

Problem solving ： The title seems ambiguous , In the title 20221023 Not shunzi , But it also contains 210, So whether the reverse order is not cis or contains 0 Not shunzi . Explanation in explanation ： Shunzi is three consecutive numbers , So both increasing and decreasing should be counted as shunzi , therefore 2022 year 01 month 20 Day arrival 2022 year 01 month 29 day （ uncertain ）,2022 year 03 month 21 day ,2022 year 02 month 10 day ( uncertain ),2022 year 10 month 12 day ( uncertain )2022 year 11 month 23,2022 year 12 month 10 day （ uncertain ）,2022 year 12 month 30 day ,2022 year 12 month 31 day , altogether 4 species ?.
Question 3 ： test questions C: Question brushing statistics

Problem solving ： Look at the data scale n<=1018
, This is rare in the usual Blue Bridge Cup , The third question begins to time out , You can only get half the score if you directly simulate , So it can be solved by mathematical method , How much work can you do in a week , In calculating the total number of weeks required , Then discuss the rest
#include <bits/stdc++.h> using namespace std; int main() {
// Pay attention to the data scale in the topic , Obvious data range is greater than int Maximum value of // If used here int If , Even if I thought of solving it mathematically, I would be unable to receive it n Cause error long long a
,b,n; cin>>a>>b>>n; int totalday; // First calculate how many questions you can do in a week int weekjob=a*5+b*2; // How many weeks will it take
int week=n/weekjob; // Remaining topics double dayjob=n%weekjob; if(dayjob<=5*a){ totalday=
week*7+ceil(dayjob/a);// Round up }else{ // If the remaining work cannot be completed from Monday to Friday, it shall be done on Saturday and Sunday totalday=week*7+5+
ceil((dayjob-5*a)/b); } cout<<totalday; return 0; }
Question 4 ： test questions D: Pruning shrubs

Problem solving ： The old rule is to look at the data scale first n<=10000, Therefore, the normal simulation method will not time out , In addition to simulation, we can also find rules. Greed can easily know the maximum height of the tree =max((i-1)*2,(n-i)*2); Then the maximum height of the tree is symmetric .
Solution I （ greedy ）：
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; for(
int i=1;i<=n;i++) cout<<max((i-1)*2,(n-i)*2)<<endl; }
Solution II （ simulation ）：
#include <bits/stdc++.h> using namespace std; void all_tree_grow_up(vector<int>
&trees,vector<int> &res,int k){ for(int i=1;i<trees.size();i++){ if(i==k)
continue; ++trees[i]; res[i]=trees[i]>=res[i]?trees[i]:res[i]; } } int main() {
int n; cin>>n; vector<int> trees(n+1,0); vector<int> res(n+1); int k=0;
// Cycle three times to find the maximum height of the tree while(k<3){ // Except for the cut tree , Other trees grow tall 1cm for(int i=1;i<trees.size();i++
){ trees[i]=0; all_tree_grow_up(trees,res,i); } for(int i=trees.size()-1;i>=1;i
--){ trees[i]=0; all_tree_grow_up(trees,res,i); } k++; } for(int i=1;i<res.size(
);i++){ cout<<res[i]<<endl; } return 0; }
Question 5 ： test questions E: X Hexadecimal subtraction

Problem solving ： For a long time , I don't quite understand , Direct swing .

Question 6 ：F： Statistical submatrix

Problem solving : Look at the size of the data and feel that the solution should be the prefix sum or the solution of looking up the score group , There was not much time at that time bf Four cycles of violence solved it
#include <bits/stdc++.h> using namespace std; bool sum_matrix(vector<vector<int
>> &nums,int x,int y,int right,int down,int k){ int sum=0; for(int i=x;i<=right;
i++){ for(int j=y;j<=down;j++){ sum+=nums[i][j]; if(sum>k){ return false; } } }
return true; } int main() { int n,m,k; cin>>n>>m>>k; vector<vector<int>> nums(n,
vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>nums[i][j]; }
} int cnt=0; //i,j Is the coordinate of the upper right corner of the matrix ,p,q Is the length and width of the matrix for(int i=0;i<n;i++){ for(int j=0;j<m;j++)
{ // A small matrix cannot exceed the bounds of a large matrix for(int p=0;p+i<n;p++){ for(int q=0;q+j<m;q++){ if(sum_matrix(
nums,i,j,p+i,q+j,k)){ cnt++; } } } } } cout<<cnt; return 0; }
Question 7 ： test questions G： Block painting

Problem solving ： The obvious one dp subject , It can be classified and discussed in three cases , Specific state transition equation Not sure if it's right , So the solution of this problem is not issued .

* N%3==0
* N%3==1
* N%3==2
Question 8 ： mine clearance

Problem solving ： The more I feel, the simpler the topic becomes , An obvious recursion problem , Traverse demining rocket , Then recursion thunder , Until there is no ray in the range to exit recursion .
Problem solving ： #include <bits/stdc++.h> using namespace std; int cnt=0; void clear_booms(
vector<vector<double>> &bombs,double x,double y,double r){ if(bombs.empty()){
return; } for(int i=0;i<bombs.size();i++){ double x1=bombs[i]-x; double y1=
bombs[i]-y; double r1=sqrt(pow(x1,2)+pow(y1,2)); if(r1<=r){ ++cnt;
// Delete the current mine after explosion , Prevent duplicate statistics bombs.erase(bombs.begin()+i); clear_booms(bombs,bombs[i],
bombs[i],bombs[i]); } } } int main() { int n,m; cin>>n>>m; vector<vector<
double>> bombs(n,vector<double>(3)); vector<vector<double>> rockets(m,vector<
double>(3)); for(int i=0;i<n;i++){ cin>>bombs[i]>>bombs[i]>>bombs[i]; }
for(int i=0;i<m;i++){ cin>>rockets[i]>>rockets[i]>>rockets[i]; } for(
int i=0;i<m;i++){ clear_booms(bombs,rockets[i],rockets[i],rockets[i]);
} cout<<cnt; return 0; }
Question 9 ： Li Bai liquor Enhanced Edition

Problem solving ： At that time, I only thought of using dfs+ Prune to solve , This problem can be regarded as a permutation and combination problem with additional conditions , You should get half the score for the following problem solution , The efficiency of pruning is not very high .
#include <bits/stdc++.h> using namespace std; int cnt=0; void dfs(int n,int m,
int wire){ // When the flowers meet m Times, but there are still stores left to visit if(m==0&&n>0){ return; } // When the wine is gone , There were still flowers to visit if(wire
==0&&m>=0){ return; } // When the maximum amount of wine is not enough to drink if(pow(2,n)*wire<m){ return; } if(n==0&&m
==wire){ ++cnt; return; }else if(n==0&&m!=wire){ return; } //
if(n==0&&m==1&&wire==1){ // ++cnt; // return; // } if(wire>=1){ dfs(n,m-1,wire-1
); } dfs(n-1,m,wire*2); } int main() { int n,m; cin>>n>>m; if(pow(2,n+1)<m){
cout<<0; return 0; } dfs(n,m,2); cout<<cnt; return 0; }
Question 10 ： Chop bamboo

Problem solving ： can't !

Technology
Daily Recommendation