Problem A space
Basic questions of group work ：256MB=256 * 2^20 * 8 position
So store it 32 Bit elements can be stored 256 * 1024 * 1024 * 8 / 32
ans： 67108864
Send points
Problem B card
The title is 0—9 altogether 9 Kinds of cards , If , each 3 Zhang can be in line 10, So if every one of them 2021 How many rows can I get ?
My thoughts ：
I wrote a question when I did it for the first time 3182, Later, I read the question carefully and found that it was wrong , Finally, it should be output 3181, Almost wrong ,,,
code：
#include<bits/stdc++.h> using namespace std; int num[10]; int del(int n) {
while(n){ int index=n%10; if(num[index]==0)return 0; else num[index]--; n/=10; }
return 1; } int main() { for(int i=0;i<=9;i++){ num[i]=2021; } int n=1; while(1)
{ int ff=del(n); if(ff==0)break; else n++; } printf("%d",n-1); return 0; }
ans：3181
Problem C straight line
My thoughts ：
I am wrong in this question ,
I use it set<pair<double,double> >
line_set; deposit k And b, Final output 20+21+line_set.size(), then ,,, And then it was wrong ,,,double Accuracy leads to errors ;
error code：
#include<bits/stdc++.h> using namespace std; set<pair<double,double> > line_set
; int main() { int x1,y1,x2,y2; for(x1=0;x1<20;x1++){ for(y1=0;y1<21;y1++){ for(
x2=0;x2<20;x2++){ for(y2=0;y2<21;y2++){ if(x1!=x2&&y1!=y2){ double k=(y2-y1)*1.0
/(x2-x1); double b=y2-k*x2; pair<double ,double > newline; newline.first=k;
newline.second=b; line_set.insert(newline); } } } } } printf("%d",line_set.size(
)+20+21); return 0; }
That's how it works out 47753（error ans）, Some people say it is 40257, hey , I feel so hurt ~
Paste the correct solution ：
#include<bits/stdc++.h> using namespace std; set<pair<double,double> > line_set
; int main() { int x1,y1,x2,y2; for(x1=0;x1<20;x1++){ for(y1=0;y1<21;y1++){ for(
x2=0;x2<20;x2++){ for(y2=0;y2<21;y2++){ if(x1!=x2&&y1!=y2){ double k=(y2-y1)*1.0
/(x2-x1); double b=(y2*(x2-x1)-(y2-y1)*x2)*1.0/(x2-x1); // a key ! That's a way to get around it double The problem of blasting accuracy
pair<double ,double> newline; newline.first=k; newline.second=b; line_set.
insert(newline); } } } } } printf("%d",line_set.size()+20+21); return 0; }
//40257
Problem D Goods placement
There is no way to solve this problem , Violence , Pure violence is not enough , It has to be optimized !
My thoughts ：
Because we have to break it down into factors , Three factors of disassembly （ Set to a,b,c）, hold a,b,c Put it in a collection s;
Always a<=b<=c（ Otherwise, it will time out !）
If s.size()==1,ans+=1;//abc The three are equal , It's a situation
If s.size()==2,ans+=3;//abc Two of three are equal , Which of the three methods is independent
If s.size()==3,ans+=6;//abc They are not equal to each other , Full Permutation 3 * 2 *1 species
There must be two layers of circulation , Don't have three layers , Must use sqrt Reduce complexity
code：
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() {
ll n=2021041820210418; ll en1=sqrt(n); ll ans=0; for(ll a=1;a<=en1;a++){ if(n%a
==0){ ll nn=n/a; ll en2=sqrt(nn); for(ll b=1;b<=en2;b++){ if(nn%b==0){ ll c=nn/b
; if(c>=b&&b>=a){ set<int> s; s.insert(a); s.insert(b); s.insert(c); if(s.size()
==1)ans++; else if(s.size()==2)ans+=3; else if(s.size()==3)ans+=6; } } } } }
printf("%lld",ans); return 0; }
ans：2430
Problem E route
My thoughts ：
dijkstra that will do , However , I wrote it dijkstra It's not right after debugging for a long time , It's used in a fit of rage Floyd, three layers for loop , Wait 10 It's about a second. It's finally coming out ,,,
code：
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define INF
999999999 int gcd(int a,int b){ if(b==0)return a; else return gcd(b,a%b); } int
M[2022][2022]; int main(){ for(int i=1;i<=2021;i++){ for(int j=1;j<=2021;j++){
if(i==j)M[i][j]=M[j][i]=0; else if(abs(i-j)>21)M[i][j]=M[j][i]=INF; else M[i][j]
=M[j][i]=i*j/gcd(i,j); } } for(int i=1;i<=2021;i++){ for(int j=i+1;j<=2021;j++){
for(int k=i;k<=j;k++){ if(M[i][k]!=INF&&M[k][j]!=INF&&(M[i][j]>M[i][k]+M[k][j]))
{ M[i][j]=M[j][i]=M[i][k]+M[k][j]; } } } } printf("%lld",M[1][2021]); return 0;
}
ans：10266837
Problem F Time display
Give me a millisecond , Output corresponding hh:mm:ss
My thoughts ：
Sign in questions
input_case1:
46800999
output_case1:
13:00:00
input_case2:
1618708103123
output_case2:
01:08:23
code：
#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() {
ll n; scanf("%lld",&n); n/=1000; n%=(24*60*60); int ss=n%60; n/=60; int mm=n%60
; n/=60; int hh=n%60; n/=60; printf("%02d:%02d:%02d",hh,mm,ss); return 0; }
Problem G Weighing with weights
My thoughts ：
hey , absolutely unexpected , The second programming problem comes directly dp, Blue Bridge Cup , You've changed , Do the provincial competition in previous years b I haven't met any group questions dp, I took the exam last year dp It's just in filling in the blanks , The second direct programming test this year dp, hey , Food is the original sin !
I haven't thought about it for a long time , Look at the scope of the test sample again 50% Examples of 1<=n<=15, decisive dfs Deep search for cheating points ,,,
input_case:
3
1 4 6
output_case:
10
code：
#include<bits/stdc++.h> using namespace std; int n; int w[102]; int flag[102];
set<int> ans; int ff=0; void dfs(int sum1,int sum2){ if(sum1<sum2)return ; else{
if(sum1>sum2){ ans.insert(sum1-sum2); } } for(int i=1;i<=n;i++){ if(!flag[i]){
flag[i]=1; dfs(sum1+w[i],sum2); dfs(sum1,sum2+w[i]); flag[i]=0; } } } int main()
{ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&w[i]); } dfs(0,0); printf(
"%d",ans.size()); return 0; }
Paste the correct solution ：
#include<bits/stdc++.h> using namespace std; typedef long long ll; int dp[102][
100002]; int main() { int n; scanf("%d",&n); int w[n+1]; ll sum=0; for(int i=1;i
<=n;i++){ scanf("%d",&w[i]); sum+=w[i]; } for(int i=1;i<=n;i++){ for(int j=1;j<=
sum;j++){ dp[i][j]=dp[i-1][j]; if(dp[i][j]==0){ if(w[i]>j)dp[i][j]=dp[i-1][w[i]-
j]; if(w[i]==j)dp[i][j]=1; if(w[i]<j)dp[i][j]=dp[i-1][j-w[i]]; } } } ll ans=0;
for(int i=1;i<=sum;i++){ if(dp[n][i])ans++; } printf("%lld",ans); return 0; }
Problem H Yanghui triangle
My thoughts ：
No idea ,, Cheating points by violence ,,
Combinatorial problems
input_case:
6
output_case:
13
code：
#include<bits/stdc++.h> using namespace std; int M[3001][3001]; int main(){ int
n; scanf("%d",&n); for(int i=1;i<=n+1&&i<=3000;i++){ M[i][i]=1; M[i][1]=1; }
for(int i=3;i<=n+1&&i<=3000;i++){ for(int j=2;j<i;j++){ M[i][j]=M[i-1][j]+M[i-1]
[j-1]; } } int num=1; for(int i=1;i<=n+1&&i<=3000;i++){ for(int j=1;j<=i;j++){
if(M[i][j]==n){ printf("%d",num); return 0; }else{ num++; } } } return 0; }
Problem I Two way sorting
My thoughts ：
sort Cheat points ,
I thought it would work at first sort even 30% I can't pass the test point （ After all, the worst-case time complexity of fast scheduling is square !）, Later, I read other people's blogs and learned that ,sort It's still very good , After all, it is c++ Encapsulated sorting function , I remember when I was learning fast platoon , There are several optimization schemes for fast scheduling , What's the middle of the three points , wait ,c++ Inside sort Is optimized to the extreme of fast scheduling , It's easy to use ;
! (~ _ ~;)
n=4000,m=4000 It doesn't time out ,sort At least you can cheat 50% Score of .
input_case:
3 3
0 3
1 2
0 2
output_case:
3 1 2
code:
#include<bits/stdc++.h> using namespace std; bool cmp1(int a,int b)// Ascending order {
return a<b; } bool cmp2(int a,int b)// Descending order { return a>b; } int main(){ int n,m;
scanf("%d %d",&n,&m); int a[n+1]; for(int i=1;i<=n;i++){ a[i]=i; } int op,index;
for(int i=0;i<m;i++){ scanf("%d %d",&op,&index); if(op==0){ sort(a+1,a+index+1,
cmp2); }else{ sort(a+index,a+n+1,cmp1); } } for(int i=1;i<=n;i++){ printf("%d",a
[i]); if(i<n)printf(" "); } return 0; }
Problem J Bracket sequence
My thoughts ：
Hypotension dp, The Blue Bridge Cup has really changed ,,,
again dfs Written , Cheat points ,,,
input_case:
((()
oupput_case:
5
code:
#include<bits/stdc++.h> using namespace std; string s; set<string> e; int
addNum; char c; bool isok() { stack<char> sta; for(int i=0;i<s.size();i++){ if(s
[i]=='('){ sta.push(s[i]); }else{ if(sta.empty()||sta.top()!='(')return false;
else sta.pop(); } } if(sta.empty())return true; else return false; } void dfs(
int depth){ if(depth==addNum){ if(isok()){ e.insert(s); } }else{ for(int i=0;i<s
.size();i++){ s.insert(s.begin()+i,c); dfs(depth+1); s.erase(s.begin()+i,s.begin
()+i+1); } } } int main() { cin>>s; int left=0,right=0; for(int i=0;i<s.size();i
++){ if(s[i]=='(')left++; else right++; } if(left==right){ printf("0"); return 0
; }else{ if(left>right)c=')'; else c='('; addNum=abs(left-right); dfs(0); printf
("%d",e.size()); } return 0; }
summary ：
Fill in the blanks 4 Avenue , Programming problem only the first guarantee ac, other 4 All of them are dfs,,, violence ,,, Cheat points ,,,
The first time I participated in the Blue Bridge Cup, it was suddenly difficult , hey , Food is the original sin ! The Blue Bridge Cup has really changed , Join the cicada title on the hard gas , In recent years, the Blue Bridge Cup has also been criticized , It's a good thing that this year is suddenly hard , I hope the Blue Bridge Cup will develop better and better .
Technology