看看去年蓝桥考了什么,第十三届蓝桥杯省赛(C/C++ 大学B组)题解(二)

简介: 看看去年蓝桥考了什么,第十三届蓝桥杯省赛(C/C++ 大学B组)题解

G:积木画


问题描述


小明最近迷上了积木画, 有这么两种类型的积木, 分别为 II 型(大小为 2 个单位面积) 和 LL 型 (大小为 3 个单位面积):


87f1018590b820ccacc52c136af6a87b_b41caec1c2494d00a15e6631d771f6ad.png


同时, 小明有一块面积大小为 2×N 的画布, 画布由 2×N 个 1×1 区域构 成。小明需要用以上两种积木将画布拼满, 他想知道总共有多少种不同的方式? 积木可以任意旋转, 且画布的方向固定。

输入格式


输入一个整数 N,表示画布大小。

输出格式


输出一个整数表示答案。由于答案可能很大,所以输出其对 1000000007 取模后的值。

样例输入

3

样例输出

5

样例说明


五种情况如下图所示,颜色只是为了标识不同的积木:


8f73c26d2aaf38a7cbda3704af5b2e68_87f3575a3bb94d4592e780f443d62baa.png


评测用例规模与约定


对于所有测试用例,1≤N≤10000000


题目思路


dp 题目,一共有三种情况,我们把1设为上层不为空,2设为下层不为空,3设成全不为空:


1:f[i][1],这种情况为 f[i] 的上层不为空,可以通过 f[i - 1] 下层不为空和 f[i - 2] 全不为空得来。

2:f[i][2],这种情况为 f[i] 的下层不为空,可以通过 f[i - 1] 上层不为空和 f[i - 2] 全不为空得来。

3:f[i][3],这种情况为 f[i] 的上下层不为空,可以通过 f[i - 1] 上层不为空和 f[i - 1] 全不为空和 f[i - 1]下层不为空和 f[i - 2] 全不为空得来。

最后输出 f[n] 全不为空就是答案。


代码演示


#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n, m;
int f[10000005][4];
int main()
{
    cin >> n;
    f[0][3] = 1;
    for (int i = 1; i <= n; i++) {
        f[i][1] = (f[i - 1][2] + f[i - 2][3]) % mod;
        f[i][2] = (f[i - 1][1] + f[i - 2][3]) % mod;
        f[i][3] = ((f[i - 1][3] + f[i - 1][1]) % mod + (f[i - 1][2] + f[i - 2][3]) % mod) % mod;
    }
    cout << f[n][3] % mod;
}


H:扫雷


问题描述


小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下, 在一个二维平面上放置着 n 个炸雷, 第 i 个炸雷 (xi,yi,ri) 表示在坐标(xi,yi) 处 存在一个炸雷, 它的爆炸范围是以半径为 ri 的一个圆。


为了顺利通过这片土地, 需要玩家进行排雷。玩家可以发射 m 个排雷火 箭, 小明已经规划好了每个排雷火箭的发射方向, 第 j 个排雷火箭 (xj,yj,rj) 表 示这个排雷火箭将会在 (xj,yj) 处爆炸, 它的爆炸范围是以半径为 rj 的一个圆, 在其爆炸范围内的炸雷会被引爆。同时, 当炸雷被引爆时, 在其爆炸范围内的 炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷?


你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个 炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

输入格式


输入的第一行包含两个整数 n、m.


接下来的 n 行, 每行三个整数 xi,yi,ri, 表示一个炸雷的信息。


再接下来的 m 行, 每行三个整数 xj,yj,rj, 表示一个排雷火箭的信息。

输出格式


输出一个整数表示答案。

样例输入

2 1
2 2 4
4 4 2
0 0 5

样例输出

2

样例说明


示例图如下,排雷火箭 1 覆盖了炸雷 1,所以炸雷 1 被排除;炸雷 1 又覆盖了炸雷 2,所以炸雷 2 也被排除。


图片描述


评测用例规模与约定


对于 40 的评测用例: 0≤x,y≤109,0≤n,m≤103,1≤r≤10


对于 100 的评测用例: 0≤x,y≤109,0≤n,m≤5×104,1≤r≤10


运行限制


最大运行时间:1s

最大运行内存: 256M


题目思路


代码演示


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node {
  int x, y, r;
};
int ans = 0;
int n, m;
map<pair<int, int>, int> mp;
set<pair<int, int> > s;
queue<node> q;
int get_len(int x, int y, int i, int j) {
  return (x - i) * (x - i) + (y - j) * (y - j);
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    int tmp = mp[{x, y}] + 100; 
    mp[{x, y}] = max(tmp, tmp / 100 * 100 + r);
  }
  for (int i = 0; i < m; i++) {
    int x, y, r;
    cin >> x >> y >> r;
    q.push(node({ x,y,r }));
  }
  int ans = 0;
  while (q.size()) {
    int xx = q.front().x;
    int yy = q.front().y;
    int rr = q.front().r;
    q.pop();
    for (int i = xx - rr; i <= xx + rr; i++) {
      for (int j = yy - rr; j <= yy + rr; j++) {
        pair<int, int> p(i, j);
        if (s.count(p)) 
          continue;
        if (!mp.count(p))
          continue;
        if (get_len(xx, yy, i, j) > rr*rr) 
          continue;
        s.insert(p);
        q.push(node({ i,j,mp[p] % 100 }));
        ans = ans + mp[p] / 100;
      }
    }
  }
  cout << ans;
}


I:李白打酒加强版


问题描述


话说大诗人李白, 一生好饮。幸好他从不开车。


一天, 他提着酒显, 从家里出来, 酒显中有酒 2 斗。他边走边唱:


无事街上走,提显去打酒。 逢店加一倍, 遇花喝一斗。


这一路上, 他一共遇到店 N 次, 遇到花 M 次。已知最后一次遇到的是花, 他正好把酒喝光了。


请你计算李白这一路遇到店和花的顺序, 有多少种不同的可能?


注意: 显里没酒 ( 0 斗) 时遇店是合法的, 加倍后还是没酒; 但是没酒时遇 花是不合法的。

输入格式


第一行包含两个整数 N 和 M.

输出格式


输出一个整数表示答案。由于答案可能很大,输出模 1000000007 的结果.


样例输入

5 10


样例输出

14


样例说明


如果我们用 0 代表遇到花,1 代表遇到店,14 种顺序如下:


010101101000000


010110010010000


011000110010000


100010110010000


011001000110000


100011000110000


100100010110000


010110100000100


011001001000100


100011001000100


100100011000100


011010000010100


100100100010100


101000001010100


评测用例规模与约定


对于 40% 的评测用例: 1≤N,M≤10 。


对于 100%100% 的评测用例: 1≤N,M≤100 。


运行限制


最大运行时间:1s

最大运行内存: 256M


题目思路


动态规划,f[i][j][k] 表示在第 i 个位置,遇到第 j 个花,目前还剩 k 斗酒。

当遇到花时:f[i][j][k] =f[i - 1][j - 1][k + 1];

当遇到酒时:f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) % mod;


代码演示


#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int n, m;
int f[205][105][105];  
int main() {
    cin >> n >> m;
    f[0][0][2] = 1;
    for (int i = 1; i <= n + m; i++) {
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= m; k++) {  
                if(j>=1) 
                  f[i][j][k] =f[i - 1][j - 1][k + 1];
                if (k % 2 == 0)   
                    f[i][j][k] = (f[i][j][k] + f[i - 1][j][k / 2]) % mod;
            }
        }
    }
    cout << f[n + m - 1][m - 1][1];
    return 0;
}


J:砍竹子


问题描述


这天, 小明在砍竹子, 他面前有 n 棵竹子排成一排, 一开始第 i 棵竹子的 高度为 hi.


他觉得一棵一棵砍太慢了, 决定使用魔法来砍竹子。魔法可以对连续的一 段相同高度的竹子使用, 假设这一段竹子的高度为 H, 那么


用一次魔法可以 把这一段竹子的高度都变为 24946815734f028ca5ca8fb1521e4098_628da18b02314998b1874baad5edaf08.png


, 其中 ⌊x⌋ 表示对 x 向下取整。小明想 知道他最少使用多少次魔法可让所有的竹子的高度都变为 1 。


输入格式


第一行为一个正整数 nn, 表示竹子的棵数。


第二行共 nn 个空格分开的正整数 hihi, 表示每棵竹子的高度。


输出格式


一个整数表示答案。

样例输入

6
2 1 4 2 6 7

样例输出

5

样例说明


其中一种方案:


21426214267

→214262→214222→211222→111222→111111

共需要 5 步完成


评测用例规模与约定


对于 20% 的数据, 保证 n≤1000,hi≤106。 对于 100% 的数据, 保证 n≤2×105,hi≤1018 。


题目思路


代码演示


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int sum = 0;
vector<int>cnt1;
vector<int>cnt2;
ll cnt(ll h) {
  return sqrtl(h / 2 + 1);
}
int main() {
  int n;
  ll h;
  cin >> n;
  while (n--) {
    cin >> h;
    while (h != 1) {
      cnt2.push_back(h);
      h = cnt(h);
    }
    int i = cnt1.size() - 1, j = cnt2.size() - 1;
    while (i >= 0 && j >= 0 && cnt1[i] == cnt2[j]) i--, j--;
    sum += j + 1;
    cnt1 = cnt2;
    cnt2.clear();
  }
  cout << sum;
  return 0;
}


相关文章
|
2月前
|
算法 测试技术 C++
小唐开始刷蓝桥(八)2013年第四届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(八)2013年第四届C/C++ B组蓝桥杯省赛真题
|
2月前
|
算法 C++ 数据格式
小唐开始刷蓝桥(七)2014年第五届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(七)2014年第五届C/C++ B组蓝桥杯省赛真题
|
2月前
|
算法 C++
小唐开始刷蓝桥(五)2016年第七届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(五)2016年第七届C/C++ B组蓝桥杯省赛真题
|
2月前
|
算法 C++
小唐开始刷蓝桥(六)2015年第六届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(六)2015年第六届C/C++ B组蓝桥杯省赛真题
|
2月前
|
数据安全/隐私保护 C++
小唐开始刷蓝桥(九)2012年第三届C/C++ B组蓝桥杯省赛真题
小唐开始刷蓝桥(九)2012年第三届C/C++ B组蓝桥杯省赛真题
|
12天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
32 10
|
17天前
|
C++
C++友元函数和友元类的使用
C++中的友元(friend)是一种机制,允许类或函数访问其他类的私有成员,以实现数据共享或特殊功能。友元分为两类:类友元和函数友元。类友元允许一个类访问另一个类的私有数据,而函数友元是非成员函数,可以直接访问类的私有成员。虽然提供了便利,但友元破坏了封装性,应谨慎使用。
45 9
|
12天前
|
存储 编译器 C语言
【C++基础 】类和对象(上)
【C++基础 】类和对象(上)
|
20天前
|
编译器 C++
【C++】string类的使用④(字符串操作String operations )
这篇博客探讨了C++ STL中`std::string`的几个关键操作,如`c_str()`和`data()`,它们分别返回指向字符串的const char*指针,前者保证以&#39;\0&#39;结尾,后者不保证。`get_allocator()`返回内存分配器,通常不直接使用。`copy()`函数用于将字符串部分复制到字符数组,不添加&#39;\0&#39;。`find()`和`rfind()`用于向前和向后搜索子串或字符。`npos`是string类中的一个常量,表示找不到匹配项时的返回值。博客通过实例展示了这些函数的用法。
|
20天前
|
存储 C++
【C++】string类的使用③(非成员函数重载Non-member function overloads)
这篇文章探讨了C++中`std::string`的`replace`和`swap`函数以及非成员函数重载。`replace`提供了多种方式替换字符串中的部分内容,包括使用字符串、子串、字符、字符数组和填充字符。`swap`函数用于交换两个`string`对象的内容,成员函数版本效率更高。非成员函数重载包括`operator+`实现字符串连接,关系运算符(如`==`, `&lt;`等)用于比较字符串,以及`swap`非成员函数。此外,还介绍了`getline`函数,用于按指定分隔符从输入流中读取字符串。文章强调了非成员函数在特定情况下的作用,并给出了多个示例代码。