考点分析
真题详解
斗牛
问题描述
给定五个 0∼9范围内的整数 a1,a2,a3,a4,a5。
如果能从五个整数中选出三个整数并且这三个整数的和为 10的倍数（包括 0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对 10取余的结果。
可以证明，如果存在多个三元组满⾜和是 10的倍数，那么无论选出哪个三元组，剩下两个数之和对 10取余的结果都是相同的。
如果选不出这样三个整数，则这五个整数的权值为 −1。
现在给定 T组数据，每组数据包含五个 0∼9范围内的整数，分别求这 T组数据中五个整数的权值。
输入格式
第一行包含整数 T。
接下来 T行，每行包含 5个 0∼9范围内的整数，表示一组数据。
输出格式
输出 T行，每行一个整数，表示每组数据中五个整数的权值。
数据范围
T<=1000
输入样例
4
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8
输出样例
2
-1
-1
0
思考
五个数中选三个，枚举所有 10 种组合即可。
如果某个三元组的和是 10 的倍数，那么剩下两个数的和模 10 就等于五个数的总和模 10。
因此只要判断是否存在这样的三元组：存在则输出 sum % 10，否则输出 -1。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {vector<int> a(5);int sum = 0;for (int i = 0; i < 5; ++i) {cin >> a[i];sum += a[i];}bool ok = false;// 枚举所有三元组for (int i = 0; i < 5; ++i) {for (int j = i + 1; j < 5; ++j) {for (int k = j + 1; k < 5; ++k) {if ((a[i] + a[j] + a[k]) % 10 == 0) {ok = true;}}}}if (ok) {cout << sum % 10 << '\n';} else {cout << -1 << '\n';}}return 0;}
排队打饭
问题描述
有 n个同学在同一个食堂窗口排队打饭，按照到达队伍的时间顺序，从先到后依次编号为 1∼n。
其中，第 i个同学的到达队伍时刻为 ai，打饭耗时为 ti。
每个同学的耐心都是有限的，第 i个同学的最大等待时间为 bi，即如果其在第 ai+bi时刻还没有开始打饭，他就会离开队伍，放弃打饭。
在一个同学打完饭后，下一个同学会立即开始打饭，中间的时间损耗忽略不计。
例如，如果一个同学在时刻 1开始打饭，打饭耗时为 3，那么他会在时刻 4打完饭，而下一个同学也会在时刻 4开始打饭。
请你计算，每个同学的开始打饭时刻。
输入格式
第一行包含整数 n。
接下来 n行，其中第 i行包含三个整数 ai,ti,bi。
输出格式
共一行，输出 n个整数，其中第 i个整数表示第 i个同学的开始打饭时刻，如果该同学放弃打饭，则输出 -1。
数据范围
1≤n≤10^5,
1≤ai,ti,bi≤10^9。
数据保证 a1<a2<…<an。
输入样例
4
1 3 3
2 2 2
3 9 1
4 3 2
输出样例
1 4 -1 6
思考
按编号顺序模拟排队过程。维护变量 cur 表示当前窗口最早可开始打饭的时刻。
对于第 i 个同学：
他实际能开始打饭的时刻为 start = max(cur, a_i)，因为如果窗口空闲且他还没到达，就要等到 a_i；否则要等前一个人打完。
如果 start <= a_i + b_i，说明他在耐心耗尽前（含恰好耗尽时刻）能开始打饭，则记录开始时间，并更新 cur = start + t_i。
否则，他会在 a_i + b_i 时刻离开，输出 -1，且 cur 不变（因为他没有占用窗口）。
由于编号已按到达队伍的时间顺序给出，直接顺序处理即可。时间复杂度 O(n)。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;long long cur = 0; // 当前窗口空闲时刻vector<longlong> ans(n);for (int i = 0; i < n; ++i) {long long a, t, b;cin >> a >> t >> b;long long start = max(cur, a);if (start <= a + b) {ans[i] = start;cur = start + t;} else {ans[i] = -1;// cur 保持不变，因为该同学离开，没有占用窗口}}for (int i = 0; i < n; ++i) {if (i) cout << ' ';cout << ans[i];}cout << '\n';return 0;}
序列
问题描述
给定一个长度为 n的整数序列 a1,a2,…,an，保证 0≤ai≤9。
请你构造一个长度为 n的整数序列 b1,b2,…,bn。
假设序列 b的价值等于
我们希望序列 b的价值能够尽可能小，请你计算并输出序列 b的价值的最小可能值。
输入格式
第一行包含一个整数 n。
第二行包含 n个整数 a1,a2,…,an。
输出格式
一个整数，表示序列 b的价值的最小可能值。
数据范围
1≤n≤10^5，
0≤ai≤9。
输入样例
6
1 4 2 8 5 7
输出样例
11
思考
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i) {cin >> a[i];}const int M = 10;const int INF = 1e9;vector<int> dp(M), ndp(M);// 初始：只考虑第 1 个位置for (int v = 0; v < M; ++v) {dp[v] = abs(a[0] - v);}for (int i = 1; i < n; ++i) {for (int v = 0; v < M; ++v) {int best = INF;for (int u = 0; u < M; ++u) {best = min(best, dp[u] + (u - v) * (u - v));}ndp[v] = best + abs(a[i] - v);}dp.swap(ndp);}int ans = INF;for (int v = 0; v < M; ++v) {ans = min(ans, dp[v]);}cout << ans << '\n';return 0;}
长方形中的正方形
问题描述
给出长方形的长和宽，每次从长方形里撕去最大的正方形，输出最后能得到多少正方形。
输入格式
一行，两个整数 n,m。
输出格式
一个整数，表示最后能得到多少正方形。
数据范围
1≤n,m≤10^9
输入样例
3 4
输出样例
4
思考
每次从长方形中撕去最大的正方形，实际上就是不断用长边除以短边，商表示这一次能撕出多少个边长为短边的正方形，余数作为新的短边。
这就是辗转相除法（欧几里得算法）的过程，把每次的商累加起来即可。
代码
#include<bits/stdc++.h>using namespace std;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);long long n, m;cin >> n >> m;long long ans = 0;while (m > 0) {ans += n / m; // 本次能撕出的正方形个数long long r = n % m;n = m;m = r;}cout << ans << '\n';return 0;}
求交点
问题描述
求直线交点，输入两个直线上的各两个端点，求其交点，若无交点或无穷个交点输出一句 Parallel or coincident，输出交点保留两位小数。
输入格式
第一行包含四个整数 x1,y1,x2,y2，表示第一个直线上的两个点坐标。
第二行包含四个整数 x3,y3,x4,y4，表示第二个直线上的两个点坐标。
输出格式
输出两个直线的交点坐标，保留两位小数。
若无交点或无穷个交点输出一句 Parallel or coincident。
数据范围
0≤xi,yi≤10
输入样例
0 0 5 5
0 2 2 0
输出样例
1.00 1.00
思考
计算两条直线方向向量的叉积，若 cross=0，说明两条直线平行或重合，否则两条直线有唯一交点。
代码
#include<bits/stdc++.h>using namespace std;struct Point {double x, y;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int x1, y1, x2, y2;int x3, y3, x4, y4;cin >> x1 >> y1 >> x2 >> y2;cin >> x3 >> y3 >> x4 >> y4;long long dx1 = x2 - x1;long long dy1 = y2 - y1;long long dx2 = x4 - x3;long long dy2 = y4 - y3;long long cross = dx1 * dy2 - dy1 * dx2;if (cross == 0) {cout << "Parallel or coincident\n";return 0;}// 求参数 tlong long px = x3 - x1;long long py = y3 - y1;double t = (double)(px * dy2 - py * dx2) / cross;double x = x1 + t * dx1;double y = y1 + t * dy1;// 避免输出 -0.00if (fabs(x) < 0.0005) x = 0.0;if (fabs(y) < 0.0005) y = 0.0;cout << fixed << setprecision(2) << x << ' ' << y << '\n';return 0;}