2022.4.9 Record my first time in the Blue Bridge Cup
Fill in the blanks
answer ：1478
answer 4
feel 012 Three consecutive should not count
7 Tianzuo 5a+2b Question , count n How many of them 5a+2b, How many more days will it take
#include<iostream> using namespace std; int main(){ long long a,b,n;
cin>>a>>b>>n; int day=0; day+=(n/(5*a+2*b))*7; int d=n%(5*a+2*b); int d1=0;
d1+=a; if(d1>=d){ cout<<day+1; return 0; } d1+=a; if(d1>=d){ cout<<day+2;
return 0; } d1+=a; if(d1>=d){ cout<<day+3; return 0; } d1+=a; if(d1>=d){
cout<<day+4; return 0; } d1+=a; if(d1>=d){ cout<<day+5; return 0; } d1+=b;
if(d1>=d){ cout<<day+6; return 0; } d1+=b; if(d1>=d){ cout<<day+7; return 0; } }
Through simulation , Found that it will repeat after trimming two rounds , So just cycle two rounds . Notice when the loop changes direction to the last and first .
#include<iostream> #include<cstring> using namespace std; int n; int h[10001];
int m[10001]; int flag; int main(){ cin>>n; memset(h,0,sizeof(h));
memset(m,0,sizeof(m)); int index=1; flag=0; for(int k=0;k<3*n;k++){ for(int
i=1;i<=n;i++){ h[i]++; m[i]=max(h[i],m[i]); } h[index]=0; if(index==1){ flag=0;
} if(index==n){ flag=1; } if(flag==0){ index++; } else{ index--; } } for(int
i=1;i<=n;i++){ cout<<m[i]<<endl; } return 0; }
This question card took me a long time ~
I didn't know why at first 321 Translate into 65. Later, the law was found by enumerating numbers one by one .
321=3*10*2+2*2+1
Then this question uses greed
#include<iostream> using namespace std; int n; int ma; int a[100000]; int mb;
int b[100000]; int c[100000]; int jin[100000]; int main(){ cin>>n; cin>>ma;
for(int i=ma;i>=1;i--){ cin>>a[i]; } cin>>mb; for(int i=mb;i>=1;i--){
cin>>b[i]; } jin[0]=1; for(int i=1;i<=max(ma,mb);i++){ c[i]=a[i]-b[i];
if(c[i]>=0){ if(a[i]<=2&&b[i]<=2){ jin[i]=2; } else{ jin[i]=max(a[i],b[i])+1; }
} else{ jin[i]=n; } } int sum=0; for(int i=1;i<=max(ma,mb);i++){ int s=1;
for(int k=0;k<i;k++){ s*=jin[k]; } sum+=c[i]*s; } cout<<sum; return 0; }
No simplification , After prefix and preprocessing , Direct violence writing
#include<iostream> #include<cstring> using namespace std; int n,m,k; int
num[501][501]; int sum[501][501]; int sum1[501][501]; int a[501]; int dp[501];
void input(){ cin>>n>>m>>k; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){
cin>>num[i][j]; } } } void init_sum() { memset(sum, 0, sizeof(sum)); for (int j
= 1; j <= m; j++) { for (int i = 1; i <= n; i++) { sum[i][j] = sum[i - 1][j] +
num[i][j]; } } } int cnt(int a[]){ int cnt=0; int sum=0; for(int i=1;i<=m;i++){
for(int j=i;j<=m;j++){ sum=0; for(int k=i;k<=j;k++){ sum+=a[k]; } if(sum<=k)
cnt++; } } return cnt; } int main(){ input(); init_sum(); int count=0; for(int
i=1;i<=n;i++){ for(int j=i;j<=n;j++){ for(int l=1;l<=m;l++){
a[l]=sum[j][l]-sum[i-1][l]; } count+=cnt(a); } } cout<<count; return 0; } /* 3
4 10 1 2 3 4 5 6 7 8 9 10 11 12 */
can't ....
I use this question dfs Written by connected components .
The unity of rocket and mine can be regarded as a radius of r Circle of , When the center distance is less than the radius （d<=r） Time , Indicates that two circles are adjacent . use grid[x][y] Record number is x,y Is the circle adjacent
#include<iostream> #include<cmath> using namespace std; int n, m; int
grid[5000][5000]; struct node { int x, y, r; node() { } node(int _x, int _y,
int _r) { x = _x; y = _y; r = _r; } }no[50001]; void input() { cin >> n >> m;
for (int i = 1; i <= n; i++) { cin >> no[i].x >> no[i].y >> no[i].r; } for (int
i = n+1; i <= n+m; i++) { cin >> no[i].x >> no[i].y >> no[i].r; } } double
dis(int i, int j) { return sqrt((no[i].x - no[j].x) * (no[i].x - no[j].x) +
(no[i].y - no[j].y) * (no[i].y - no[j].y)); } int cnt = 0; void dfs(int n) {
for (int i = 1; i <= n + m; i++) { if (grid[n][i] == 1 && n != i) { grid[n][i]
=grid[i][n]=0; cnt++; dfs(i); } } } int main() { input(); for (int i = 1; i <=
n+m; i++) { for (int j = 1; j <= n+m; j++) { if (dis(i, j)<=no[i].r) {
grid[i][j]=1; } } } for (int i = n + 1; i <= n + m; i++) { dfs(i); } cout <<
cnt; }
I use this question dfs+ Memory search
#include<iostream> #include<cstring> using namespace std; int N, M; int
dp[1000][101][101]; int dfs(int sum, int n, int m) { if (sum < 0)return 0; if
(n > N)return 0; if (m > M - 1)return 0; if (dp[sum][n][m])return
dp[sum][n][m]%1000000007; if (sum == 1 && n == N && m == M - 1)return 1;
dp[sum][n][m] =(dfs(2 * sum, n + 1, m) + dfs(sum - 1, n, m + 1))%1000000007;
return dp[sum][n][m]; } int main() { memset(dp, 0, sizeof(dp)); cin >> N >> M;
cout << dfs(2, 0, 0); }
can't ....
Technology