解题思路 在 的网格区域内，有 颗流星会坠落，第 颗流星会在 时刻坠落在 网格内。流星坠落后，其所在的格子以及周围4个相邻的格子都化为焦土，无法行走。现在有一个家族，在 0 时刻在 格子里，每1个时刻，他们能移动到相邻的 4 个格子中的任意一个。如果一个格子在时刻 t 被流星撞击或烧焦，那么他们只能在 t 之前的时刻在这个格子里出现。求，这个家族是否在这场流星雨中幸存（移动到了一个没有被撞击或者烧焦的格子里一直待到流星雨结束），如果幸存，他们最少要花多少时间才移动到安全的格子里。注：移动过程中 x 和 y 都可以超出300（但不能为负）。 本题使用 BFS 算法：使用 fall 记...

解题思路 有 N 个人需要渡河，有一条船，船上最多只能乘坐两人。第 i 个人一个人划船到对面需要 T[i-1] 时间。为了保证船的平衡，当船上有两人时，需按照慢的那个人的速度划船，也就是说船到达对岸的时间等于船上渡河时间长的那个人的时间。求所有人过河的花费时间最少为多少？ 首先将 N 个人按照渡河时间从小到大排序，则第 1 个人和第 2 个人可以作为来回划船的人。 dp[i] 表示前 i+1 个人过河花费的最少的总时间。dp[0] = T[0]，表示1 个人过河时间。dp[1] = T[1]，两个人一起划到对岸。dp[i] = min(dp[i-1]+T[0]+T[i], dp[i-2]+T[...

解题思路 一共有 n 个物品，第 i 个物品的重量是 w[i]。可以将物品放在天平的两端，若两端重量相差小于 m，就可取走物品。求取走的物品的总重量最大为多少？不限操作次数。 dp[i][j] 表示前 i 个物品天平左右相差 j 时的最大重量。如果不选第 i 个物品，d[i][j] = d[i-1][j]。如果 dp[i-1][j+w[i]] 是可行的，即 dp[i-1][j+w[i]] != -1，那么在较轻的那端放置第 i 个物品，dp[i][j] = dp[i-1][j+w[i]] + w[i]，此时，该端依然是较轻的那端。当 j >= a[i] 时，如果 dp[i-1][j-w[...

解题思路 一段长为 L 的路径上有 N + 2 个点，其中两个点位于路径端点，第 i 个点与第 i+1 个点之间的距离为 jump[i]。最多可以消除 M 个点，但不能消除路径两边的端点。求相邻两点之间最短的距离的最大值。 对相邻两点之间最短距离 mid 使用二分法。显然，mid >= 1 且 mid <= L。如果 jump[i] < mid，消除第 i+1 个点，直至第 i 个点与其后相邻的点的距离 >= mid 停止消除，将消除点的次数累加计入 k。如果 k > M，表示 mid 过大；否则 mid 这个距离是可以实现的。 C++代码 #include&lt...

解题思路 给定 ，求一对整数 ，在满足 且 的前提下，要求最大化 的值。 当 时，。当 时，，。求 的最大公因数，辗转相除法： 商 1 余 1， 与 1 的最大公约数 C++代码 #include<iostream> using namespace std; int main(){ long long n; cin >> n; if(n == 1) cout << 2 << endl; else cout << 2*n-1 << endl; ...

题目：Shooting Game来源：东华大学2020年程序设计竞赛（同步赛） 解题思路 一共有 n 个参赛者，其ID为 id，射中红色、白色和黑色靶子的次数分别为 r、w 和 b。每射中红色、白色和黑色靶子计分 1、2、3。求得分最高者的ID和得分。 C++代码 #include<cstdio> #include<vector> #include<algorithm> using namespace std; int main(){ int N; scanf("%d", &N); int maxPoints = 0; ...

解题思路 给定一个 矩阵表示迷宫，其中 C 表示小A的位置，D 表示小B的的位置，# 表示不可通过的障碍，. 表示可正常通过的位置。小A每次可以移动一个位置，移动的方向是上下左右左上左下右上右下 8 个方向；小B每次可以移动两次位置，移动的方向是上下左右 4 个方向。请问他们是否能够相遇，如果能，那么最早什么时候能够找到对方。 广度优先搜索：每单位时间对小A使用一次 ，对小B使用两次 ，如果小A或小B走到了对方走过的位置，则表示相遇。 C++代码 #include<iostream> #include<vector> #include<queue> #in...

解题思路 有 种牌，第 种牌有 个，另有 个 joker 牌，求最多可以组成多少套牌？一副套牌中包含 个牌，每个牌都不相同。 假设可以组成 副套牌，如果 ，可由 joker 牌补充。需要补充的牌数总和应 。使用二分法确定满足条件的 的最大值。 C++代码 #include<iostream> #include<vector> #include<algorithm> using namespace std; int n, m; bool cards(vector<int>& c, int x){ int tmp =...

题目：Sumo and His Followers来源：第十七届浙大城市学院程序设计竞赛（同步赛） 解题思路 有 个人，回答第 个人的问题需要 时间，求平均等待时间最少为多少？ 每回答一个人 的问题，剩下 个人需要等待的总时间为 。将 个人排队，则等待总时间为 。所以，当 时，等待总时间最少。 C++代码 #include<cstdio> #include<vector> #include<algorithm> using namespace std; int main(){ int T; scanf("%d", &T...

题目：Sumo and Keyboard-Cat来源：第十七届浙大城市学院程序设计竞赛（同步赛） 解题思路 求出字符串的大小写转换的次数，初始为大写。 C++代码 #include<iostream> using namespace std; int main(){ string s; cin >> s; bool flag = true; int cnt = 0; for(int i=0; i<s.size(); ++i){ if(flag && s[i]>='a' &&am...

解题思路 迷宫是一个 的矩阵。起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。障碍物不能通过。求能否从起点走到终点。 本题可以使用 BFS算法，使用队列 que 实现。d 表示可以移动的 4 个方向，visited 表示已遍历过的点。 C++代码 #include<iostream> #include<vector> #include<queue> using namespace std; int N, M; int d[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}}; bool ...

题目：夹娃娃来源：牛客IOI周赛17-普及组 解题思路 给定含有 个元素的数组，求第 个元素到第 个元素之间的总和，包含 和 。 使用 数组记录前缀和。。 C++代码 #include<cstdio> #include<vector> using namespace std; int main(){ int n, k; scanf("%d%d", &n, &k); vector<int> sum(n+1, 0); int w; for(int i=1; i<=n; ++i){ ...

题目：No Breakfast for College Students来源：第三届中国计量大学ACM程序设计竞赛个人赛（同步赛） 解题思路 Gyro 在假期吃了 b 次早餐，l 次午餐，s 次晚餐。他是在早餐前、午餐前、晚餐前、晚餐后这四个时间段中的某一段到达家里，在这四个时间段的某一段离开。问 Gyro 在家中最少可能错过了几次进餐。 假设 b = 3, l = 2, s = 1，早餐次数最多，那么在第一天早餐前到达家里，第三天早餐后离开，错过进餐次数最少。三种进餐，最多的记为 maxn，最少的记为 minn，剩下的那餐记为 midn。如果 maxn 与其余两餐的差值 <= 1，那么...

题目：Stay up Late and Wake up Early来源：第三届中国计量大学ACM程序设计竞赛个人赛（同步赛） 解题思路 Gyro 需要在 hh:mm 时间起床，他在“幸运时间”设置闹钟，闹钟每隔 x 分钟响一次，如果没到起床时间，Gyro 就按一次睡眠按钮。求按睡眠按钮的最少次数 y，并输出幸运时间。幸运时间定义：包含数字 7。闹钟设置为 24 小时，23:59 后一秒的时间为 00:00。 数字 7 只能出现在 minute 的个位数上或者 hour 的个位数上。将当前时间减去 x 分钟，直至得到的时间是幸运时间为止。 C++代码 #include<iostream&g...