2022蓝桥杯省赛C++B组

蓝桥杯省赛C++B组"/>

2022蓝桥杯省赛C++B组

2031: [蓝桥杯2022初赛] 九进制转十进制

#include <iostream>  
using namespace std;  
int main()  
{  printf("1478");  return 0;  
}

2032: [蓝桥杯2022初赛] 顺子日期

#include <iostream>  
using namespace std;  
int main()  
{  printf("14");  return 0;  
}

2033: [蓝桥杯2022初赛] 刷题统计

#include <iostream>  
using namespace std;  
typedef long long LL;  
LL ans = 0, a, b, n;  
int main()  
{  cin >> a >> b >> n;  ans = n / (5 * a + 2 * b);  ans *= 7;  LL re = n % (5 * a + 2 * b);  LL time = 1, ch = 0;  while(ch < re)  {  if(time % 6 == 0 || time % 7 == 0)  {  ans += 1; ch += b;  time += 1;  }  else  {  ans += 1; ch += a;  time += 1;  }  }  cout << ans << endl;  return 0;  
}

2034: [蓝桥杯2022初赛] 修剪灌木

#include <iostream>  
using namespace std;  
int main()  
{  int N; cin >> N;  for( int i = 1; i <= N; i ++ )  {  if(2 * i <= N) printf("%d\n", (N-i)*2);  else printf("%d\n", 2*i - 2);  }  return 0;  
}

2035: [蓝桥杯2022初赛] X进制减法

#include<bits/stdc++.h>  
using namespace std;  
typedef long long LL;  
const LL N = 1e5+10;  
const LL mod = 1000000007;  
LL n, ma, mb, ans = 0;  
LL a[N], b[N], Jz[N];  
int main()  
{  cin >> n; cin >> ma;  for( LL i = ma; i >= 1; i -- ) scanf("%lld", &a[i]);  cin >> mb;  for( LL i = mb; i >= 1; i -- ) scanf("%lld", &b[i]);  for( LL i = 1; i <= ma; i ++ )  {  Jz[i-1] = max(a[i], b[i]) + 1;  if(Jz[i-1] < 2) Jz[i-1] = 2;  }  for( LL i = 1; i <= ma; i ++ ) a[i] -= b[i];  LL res = 0;  for( LL i = ma; i >= 1; i -- )  res = (res*Jz[i-1]+a[i]) % mod;  printf("%lld", res);  return 0;  
}

2036: [蓝桥杯2022初赛] 统计子矩阵

#include <bits/stdc++.h>  
using namespace std;  
typedef long long LL;  
const int N = 510;  
int n, m, K;  
LL a[N][N], s[N][N];  
int main()  
{  cin >> n >> m >> K;  for(int i = 1; i <= n; i ++)  for(int j = 1; j <= m; j ++)  {  cin >> a[i][j];  s[i][j] = s[i - 1][j] + a[i][j];  }  LL res = 0;  for(int i = 1; i <= n; i ++)  for(int j = i; j <= n; j ++)  {  int l = 1; LL sum = 0;  for(int r = 1; r <= m; r ++)  {  LL sumr = s[j][r] - s[i - 1][r];  if(sum + sumr <= K)  {  sum += sumr;  res += (r - l + 1);  }  else  {  LL suml = s[j][l] - s[i - 1][l];  while(l != r && sum + sumr > K)  {  sum -= suml; l ++;  suml = s[j][l] - s[i - 1][l];  }  if(sum + sumr <= K)  {  sum += sumr;  res += (r - l + 1);  }  else l ++;  }  }  }  cout << res << endl;  return 0;  
}

2037: [蓝桥杯2022初赛] 积木画

#include<iostream>  
using namespace std;  
const int N = 1e7+10;  
const int mod = 1000000007;  
int f[N];  
int main()  
{  int n; cin >> n;  f[1] = 1, f[2] = 2, f[3] = 5;  for(int i = 4; i <= n; i ++)  f[i] = (2*f[i-1]%mod + f[i-3]%mod) % mod;  cout << f[n];  return 0;  
}

2038: [蓝桥杯2022初赛] 扫雷

#include <bits/stdc++.h>  
#define int long long  
using namespace std;  
const int mod = 1000003; // 哈希表表长  
int n, m;  
int x[100005], y[100005], r[100005];  
int h[1000005];  
bool vis[1000005];  
pair<int, int> mp[1000005]; // 记录该点处最大半径及雷数  
int get_key(int xx, int yy) { return xx*1000000001+yy; } // 转化为一个1e9+1进制的数  
int find(int xx, int yy) // 将一个二维坐标映射到小于mod的数字  
{  int key = get_key(xx, yy);  int temp = key; temp = (temp%mod + mod) % mod;  while(!(h[temp] == -1 || h[temp] == key))  temp = (temp+1) % mod;  return temp;  
}  
signed main()  
{  cin >> n >> m; memset(h, -1, sizeof h);  for(int i = 1; i <= n; i++)  {  scanf("%lld%lld%lld", &x[i], &y[i], &r[i]);  h[find(x[i], y[i])] = get_key(x[i], y[i]);  int id = find(x[i], y[i]);  mp[id].second ++;  mp[id].first = max(mp[id].first, r[i]);  }  for(int i = n+1; i <= n+m; i ++)  {  scanf("%lld%lld%lld", &x[i], &y[i], &r[i]);  h[find(x[i], y[i])] = get_key(x[i], y[i]);  int id = find(x[i], y[i]);  mp[id].first = max(mp[id].first, r[i]);  }  queue<pair<int, int> > q;  for(int i = n+1; i <= n+m; i ++)  {  int id = find(x[i], y[i]);  if(!vis[id])  {  vis[id] = true;  q.push(make_pair(x[i], y[i]));  }  }  int res = 0;  while(q.size())  {  pair<int, int> now = q.front(); q.pop();  int nowx = now.first, nowy = now.second;  int id = find(nowx, nowy);  int rmax = mp[id].first, num = mp[id].second;  res += num;  for(int xx = nowx-rmax; xx <= nowx+rmax; xx++)  for(int yy = nowy-rmax; yy <= nowy+rmax; yy++)  if(rmax*rmax >= (xx-nowx)*(xx-nowx)+(yy-nowy)*(yy-nowy))  {  int id = find(xx, yy);  if(!vis[id] && mp[id].second) // 如果该处有雷且未被访问过  {  vis[id] = true;  q.push(make_pair(xx, yy));  }  }  }  cout << res << endl;  return 0;  
}

2039: [蓝桥杯2022初赛] 李白打酒加强版

对于酒的上限数量，应该想好范围，因为花最多只有 m 朵，意味着我们最多只能喝 m 壶酒，所以对于 k 超过 m 的状态都是无效状态。而剩余酒的上限也就是 k 应该也定为 m 。他一共遇到店 n 次，遇到花 m 次。已知最后一次遇到的是花，他正好把酒喝光了，所以最后一次肯定遇到的是花，那么最后的结果便是dp[n][m-1][1]，并且酒壶中酒的容量不能超过m。
状态设计：dp[i][j][k]的值表示遇到i家店，j朵花，酒壶中还剩k斗酒的可能情况数。
状态转移方程：dp[i][j][k]=dp[i-1][j][k/2] + dp[i][j-1][k+1]；dp[i][j][k] = dp[i][j - 1][k + 1]。
边界设计：除了 dp[0][0][2]=1，其他元素全为0。
考虑进行状态转移，对于状态 f[i][j][k]，假设最后一次遇到的是店，那么此时需要保证 i 大于0，并且 k 是偶数，因为遇到店剩余酒翻倍，k 一定不可能为奇数，那么便可以得到如上的转移方程。
并且假设最后一次遇到的是花，那么此时只需要保证 j 是大于 0 的即可，同样也可以获得如上的转移方程。最后进行代码编写即可解决本题。

#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const int mod = 1000000007;  
const int N = 110;  
ll check(int a, int b)  
{  int ans = 1;  while(b)  {  if(b & 1) ans = ans * a;  a = a * a ;  b >>= 1;  }  return ans;  
}  
void solve()  
{  ll dp[N][N][N]; // 表示遇到i个店和j朵花现在还剩k壶酒的所有路线数  int n, m; cin >> n >> m;  dp[0][0][2] = 1, dp[0][1][1] = 1; // 只遇到花  for(int i = 0; i <= 7 ; i ++)  dp[i][0][check(2, i + 1)] = 1; // 初始化 将只遇到店的初始化为1  for(int i = 1; i <= n; i ++)  for(int j = 1; j <= m ; j ++)  for(int k = 0; k <= m; k ++)  {  if(k % 2 == 0) dp[i][j][k] = (dp[i - 1][j][k / 2] + dp[i][j - 1][k + 1] ) % mod ; // 遇到店或者遇到花  else dp[i][j][k] = dp[i][j - 1][k + 1]; // 只能遇到花  }  cout << dp[n][m - 1][1] << endl;  return ;  
}  
int main()  
{  int T; cin >> T;  while(T --) solve();  return 0;  
}

2040: [蓝桥杯2022初赛] 砍竹子

首先是贪心的策略，根据题目的要求，优先选择砍所剩竹子中高度最大的竹子，因为无论怎么砍高度低的竹子，这都不可能使得高度低的竹子高度变高，从而能够和高度高的竹子一起会被砍掉，所以相反的去思考，由于去砍高度高的竹子，其高度会变低，然后再去砍的时候，可能会跟原来高度低的竹子一块被砍，所以这种贪心策略显然是正确的。而且高度相同的连续竹子一定要放在一起砍，根据题目的要求来说这是显然的。
在做题时，可以先存下来第 i 棵树还剩 j 次砍为 1 时的高度，将它记录为f[i][j]，例如：第 i 棵树高度为15，那么第一次砍完后高度为 2，第二次砍完后高度为 1。那么还剩一次就能砍为1的高度为 2，还剩两次就能砍为 1 的高度为 15。然后对于题目进行分析，首先可以知道的一点就是，当且仅当两棵树在同一层时，才有可能会被同时砍，能被同时砍不仅要求在同一层，还需要要求高度相同且编号相邻，所以我们可以直接遍历每一层，只要发现有相邻的两棵树高度相同我们的砍树次数就可以减少 1，一开始的砍树次数就是所有的树都一次一次地砍为 1 所需要的次数和。由此可以得到本题的代码。

#include<bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const int N = 200003;  
ll f[N][8]; // f[i][j]表示第i个数还剩j次砍为1的高度  
ll s[8], ans = 0;  
int main()  
{  int n; cin >> n;  for(int i = 1; i <= n; i ++)  {  ll x, tt = 0; cin >> x;  while(x != 1)  {  s[++ tt] = x; // s[i]记录的是当前竹子砍i-1次后剩余的高度  x = sqrt(x/2 + 1);  }  ans += tt;  for(int j = 1; tt > 0; j ++, tt --)  f[i][j] = s[tt];  }  for(int i = 1; i <= 7; i ++)  for(int j = 2; j <= n; j ++)  if(f[j][i] && f[j][i]==f[j-1][i]) ans --;  cout << ans << endl;  return 0;  
}