G：积木画
问题描述
小明最近迷上了积木画, 有这么两种类型的积木, 分别为 II 型（大小为 2 个单位面积) 和 LL 型 (大小为 3 个单位面积):
同时, 小明有一块面积大小为 2×N 的画布, 画布由 2×N 个 1×1 区域构 成。小明需要用以上两种积木将画布拼满, 他想知道总共有多少种不同的方式? 积木可以任意旋转, 且画布的方向固定。
输入格式
输入一个整数 N，表示画布大小。
输出格式
输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取模后的值。
样例输入
3
样例输出
5
样例说明
五种情况如下图所示，颜色只是为了标识不同的积木：
评测用例规模与约定
对于所有测试用例，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, 那么
用一次魔法可以 把这一段竹子的高度都变为 
, 其中 ⌊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; }
