考点总结
真题详解
面试
问题描述
生活在在外星球X上的小Z想要找一些小朋友组成一个舞蹈团，于是他在网上发布了信息，一共有 n个人报名面试。
面试必须按照报名的顺序依次进行。
小Z可以选择在面试完若干小朋友以后，在所有已经面试过的小朋友中进行任意顺序的挑选，以组合成一个舞蹈团。
虽然说是小朋友，但是外星球X上的生态环境和地球上的不太一样，这些小朋友的身高可能相差很大。
小Z希望组建的这个舞蹈团要求至少有 m个小朋友，并且这些小朋友的最高身高和最低身高之差不能超过 k个长度单位。
现在知道了这些小朋友的身高信息，问小Z至少要面试多少小朋友才能在已经面试过的小朋友中选出不少于 m个组成舞蹈团。
输入格式
第一行 3个整数 n,m,k，意义见题面描述；
第二行 n个整数，第 i个数 hi表示第 i个报名面试的小朋友的身高。
输出格式
如果可以选出舞蹈团，输出至少要面试多少人；否则输出 impossible。
数据范围
输入样例
6 3 5
170 169 175 171 180 175
输出样例
4
思考
对于已经面试过的人，若能选出至少 m 个人且最高身高与最低身高之差不超过 k，等价于：
存在一个长度为 k的身高区间 [x,x+k]，其中包含至少 m个已面试的人。
因为区间左端点 x一定可以取为某一个人的身高。
所以把所有出现过的身高离散化，线段树维护：
以每个离散化身高作为区间左端点时，该窗口内有多少个已面试的人；
每次加入一个身高 h，它会影响所有满足x≤h≤x+k的左端点 x，即h−k≤x≤h
对这些左端点区间加 1；
查询全局最大值，若最大值 ≥m，说明当前前缀已经可以组成舞蹈团。
时间复杂度：
O(nlogn)。
代码
#include<bits/stdc++.h>using namespace std;struct SegTree {int n;vector<int> mx, lazy;SegTree(int _n = 0) {init(_n);}voidinit(int _n){n = _n;mx.assign(4 * n + 5, 0);lazy.assign(4 * n + 5, 0);}voidapply(int p, int v){mx[p] += v;lazy[p] += v;}voidpush(int p){if (lazy[p] != 0) {apply(p << 1, lazy[p]);apply(p << 1 | 1, lazy[p]);lazy[p] = 0;}}voidadd(int p, int l, int r, int ql, int qr, int v){if (ql <= l && r <= qr) {apply(p, v);return;}push(p);int mid = (l + r) >> 1;if (ql <= mid) add(p << 1, l, mid, ql, qr, v);if (qr > mid) add(p << 1 | 1, mid + 1, r, ql, qr, v);mx[p] = max(mx[p << 1], mx[p << 1 | 1]);}voidadd(int l, int r, int v){if (l <= r) add(1, 0, n - 1, l, r, v);}intgetMax()const{return mx[1];}};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;long long k;cin >> n >> m >> k;vector<longlong> h(n);vector<long long> vals;for (int i = 0; i < n; i++) {cin >> h[i];vals.push_back(h[i]);}sort(vals.begin(), vals.end());vals.erase(unique(vals.begin(), vals.end()), vals.end());int sz = vals.size();SegTree seg(sz);for (int i = 0; i < n; i++) {// 当前身高 h[i] 会影响左端点 x 满足：// h[i] - k <= x <= h[i]long long leftVal = h[i] - k;int l = lower_bound(vals.begin(), vals.end(), leftVal) - vals.begin();int r = upper_bound(vals.begin(), vals.end(), h[i]) - vals.begin() - 1;seg.add(l, r, 1);if (seg.getMax() >= m) {cout << i + 1 << '\n';return 0;}}cout << "impossible\n";return 0;}
多项式求和
问题描述
小K最近刚刚习得了一种非常酷炫的多项式求和技巧，可以对某几类特殊的多项式进行运算。
非常不幸的是，小K发现老师在布置作业时抄错了数据，导致一道题并不能用刚学的方法来解，于是希望你能帮忙写一个程序跑一跑。
给出一个 m阶多项式
对给定的正整数 a，求
由于这个数可能比较大，所以你只需计算 S(n)对 10^9+7取模后的值（即计算除以 10^9+7后的余数）。
输入格式
第一行包含三个整数 n,m,a。
第二行包含m+1个整数，b0,b1,…,bm描述给定多项式的系数。
对于所有数据，1≤a,bi≤10^9。
输出格式
输出一行一个数，表示 S(n)对 10^9+7取模后的结果。
数据范围
输入样例
5 2 3
1 1 1
输出样例
9658
思考
代码
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MOD = 1000000007;ll modpow(ll a, ll e) {ll r = 1;while (e) {if (e & 1) r = r * a % MOD;a = a * a % MOD;e >>= 1;}return r;}ll inv(ll x) {return modpow(x, MOD - 2);}// 已知 y[i] = S(i)，i=0..d，求 S(n)ll lagrange(const vector<ll>& y, ll n) {int d = (int)y.size() - 1;if (n <= d) return y[n];ll ans = 0;for (int i = 0; i <= d; i++) {ll num = y[i];ll den = 1;for (int j = 0; j <= d; j++) {if (i == j) continue;num = num * ((n - j) % MOD + MOD) % MOD;den = den * ((i - j) % MOD + MOD) % MOD;}ans = (ans + num * inv(den)) % MOD;}return ans;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);ll n;int m;ll a;cin >> n >> m >> a;vector<ll> b(m + 1);for (int i = 0; i <= m; i++) cin >> b[i];// 计算 f(k)auto calc_f = [&](ll k) -> ll {ll val = 0;ll x = k % MOD;for (int i = m; i >= 0; i--) {val = (val * x + b[i]) % MOD;}return val;};if (a % MOD == 1) {// S(n) 是 m+1 次多项式int d = m + 1;vector<ll> y(d + 1);ll sum = 0;for (int i = 0; i <= d; i++) {sum = (sum + calc_f(i)) % MOD;y[i] = sum;}cout << lagrange(y, n) << '\n';} else {// 预处理组合数vector<vector<ll>> C(m + 1, vector<ll>(m + 1, 0));for (int i = 0; i <= m; i++) {C[i][0] = C[i][i] = 1;for (int j = 1; j < i; j++) {C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;}}// 求 Q(x) = q[0] + q[1]x + ... + q[m]x^m// 满足 a Q(x+1) - Q(x) = f(x)vector<ll> q(m + 1, 0);ll inv_am1 = inv((a - 1 + MOD) % MOD);for (int i = m; i >= 0; i--) {ll sum = 0;for (int j = i + 1; j <= m; j++) {sum = (sum + q[j] * C[j][i]) % MOD;}ll rhs = (b[i] - a * sum % MOD + MOD) % MOD;q[i] = rhs * inv_am1 % MOD;}ll Q0 = q[0];// 计算 Q(n+1)ll x = (n + 1) % MOD;ll Qn = 0;for (int i = m; i >= 0; i--) {Qn = (Qn * x + q[i]) % MOD;}ll an = modpow(a % MOD, n + 1);ll ans = (an * Qn % MOD - Q0 + MOD) % MOD;cout << ans << '\n';}return 0;}
扫雷
问题描述
扫雷（minesweeper）是一个有趣的单人益智类游戏，游戏目标是在最短的时间内根据棋盘上的提示信息，找出所有非雷方块，同时避免踩到地雷。随着桌面操作系统Windows的流行，其自带的扫雷游戏也因为有趣的玩法、精致的画面受到大家的欢迎。
小L的电脑上曾经也有一个扫雷游戏，它和主流的扫雷游戏基本相似，但是有一些不同的地方，具体介绍如下：
游戏开始时，玩家可以看到 N×M个整齐排列的空白方块，玩家须根据棋盘已有的信息，运用逻辑推理来推断哪些方块含或不含地雷。
玩家可以用鼠标左键点击空白方块，表示推断这个方块没有地雷，尝试探明它。
如果玩家点开没有地雷的方块，会有一个数字显现其上，这个数字代表着八连通的相邻方块有多少颗地雷（至多为 8）
如果这个方块八连通的方块中没有地雷（也即，方块显示的数字为 0），则系统会自动帮玩家点开它相邻的方块，这个过程可能会引起连锁反应。
如果玩家点开有地雷的方块，则游戏结束，玩家失败。
玩家可在推测有地雷的方块上点鼠标右键，表示放置旗帜来标明地雷的位置；在有旗帜的方块上再次点击右键，会使旗帜消失，成为空白的方块。在已标明旗帜的方块点击左键，方块不会有任何的变动。若在游戏进行中错置旗帜，可以用右键来改变方块状态。
玩家可以在一个已探明的方块上同时点击左键及右键。此时，如果方块相邻的 8
个方块放置旗帜的数目与方块上的数字相同，那么周围未探明的方块就会自动打开。然而，玩家若错置旗帜位置，此动作可能会打开真正藏有地雷的方块，导致游戏失败。不过这样的点击动作可加快游戏速度以便得到高分。
然而，年代久远，小 L 已经找不到当年陪他度过十年求学时光的扫雷游戏了，于是他找到了精通编程的你，希望你能帮他写一个简单的扫雷游戏，帮助他回忆那些快乐时光。
具体来说，你的程序应该读入一个地雷布置图。然后读入用户的每一次游戏操作，并在每次操作后给用户以反馈，帮助用户进行游戏。
输入格式
约定：我们用坐标 (x,y)表示棋盘第 x行、第 y列的方块。
第一行用空格隔开的两个整数 n,m，表示棋盘的规模。
接下来 n行，每行一个长为 m的字符串，描述棋盘，其中第 i行的第 j个字符表示棋盘的方块 (i,j)。为 * 表示方块里有一个地雷，为 . 表示方块是安全的。
接下来每一行按时间顺序描述每一次用户操作，直到文件结束。每一行的格式如下：
1、首先读入一个字符串，表示这次操作的内容：
Flag：表示右键点击某个方块，插上／撤销一面旗帜。
Sweep：表示左键点击某个方块，判断这个方块没有地雷，要探明之。
DSweep：表示左右键同时点击某个方块，尝试探明与它相邻的方块。
Quit：表示放弃本局游戏并退出。
2、若操作不为 Quit，则之后有空格隔开的两个整数 x,y，表示这次操作的坐标为 (x,y)，保证 1≤x≤n, 1≤y≤m。
输入数据保证存在有且仅有一次 Quit 操作。
输出格式
数据范围
我们令 n,m表示棋盘的规模，q表示输入的操作次数，有以下约定：
输入样例
3 3
...
..*
...
Sweep 1 1
DSweep 1 2
Flag 1 3
Flag 2 3
DSweep 1 2
Sweep 1 3
Flag 1 1
DSweep 1 3
Flag 1 3
DSweep 1 2
DSweep 1 2
Sweep 3 3
Quit
输出样例
6 cell(s) detected
1 1 0
1 2 1
2 1 0
2 2 1
3 1 0
3 2 1
failed
success
success
failed
flagged
swept
not swept
cancelled
1 cell(s) detected
1 3 1
no cell detected
1 cell(s) detected
3 3 1
finish
total step 12
思考
扫雷展开：手写 BFS 队列
doSweep(x, y) 的核心：
若已探明 → 直接成功；若是雷 → 返回 false（boom）。
标记 opened，计算 num，把坐标塞进 newCells（本次新探明列表）。
若 num == 0，把该格入队。
队列非空时，取出队首，枚举 8 邻居：
先判坐标 nx∈[1,n], ny∈[1,m] 是否合法；
跳过已探明；
清除旗帜 → 标记探明 → 计算 num → 记录 → 若 num==0 入队。
用全局预分配数组 qx[]/qy[] 当头尾指针队列，避免反复 queue<pair<>> 的动态分配与 STL 开销。newCells 也用全局数组记录本次新探明的 id，最后统一排序输出。
代码
#include<bits/stdc++.h>using namespace std;const int MAXN = 1100000;int n, m, W;vector<char> mine, opened, flagged;vector<int> num;int qx[MAXN], qy[MAXN];int newCells[MAXN];int newCnt;long long totalStep = 0;int safeTotal = 0;int openedSafe = 0;inlineintid(int x, int y){ return x * W + y; }inlineintcalcNum(int x, int y){int cnt = 0;int base = id(x, y);for (int dx = -1; dx <= 1; ++dx) {int bx = base + dx * W;for (int dy = -1; dy <= 1; ++dy) {if (dx == 0 && dy == 0) continue;cnt += mine[bx + dy];}}return cnt;}intcountFlags(int x, int y){int cnt = 0;int base = id(x, y);for (int dx = -1; dx <= 1; ++dx) {int bx = base + dx * W;for (int dy = -1; dy <= 1; ++dy) {if (dx == 0 && dy == 0) continue;cnt += flagged[bx + dy];}}return cnt;}booldoSweep(int sx, int sy){int sid = id(sx, sy);if (opened[sid]) return true;if (mine[sid]) return false;int head = 0, tail = 0;opened[sid] = 1;int c = calcNum(sx, sy);num[sid] = c;newCells[newCnt++] = sid;++openedSafe;if (c == 0) {qx[tail] = sx;qy[tail] = sy;++tail;}while (head < tail) {int x = qx[head], y = qy[head];++head;for (int dx = -1; dx <= 1; ++dx) {for (int dy = -1; dy <= 1; ++dy) {if (dx == 0 && dy == 0) continue;int nx = x + dx, ny = y + dy;if (nx < 1 || nx > n || ny < 1 || ny > m) continue; // 边界检查int nid = id(nx, ny);if (opened[nid]) continue;flagged[nid] = 0;opened[nid] = 1;int nc = calcNum(nx, ny);num[nid] = nc;newCells[newCnt++] = nid;++openedSafe;if (nc == 0) {qx[tail] = nx;qy[tail] = ny;++tail;}}}}return true;}voidoutputNewCells(){if (newCnt == 0) {printf("no cell detected\n");return;}printf("%d cell(s) detected\n", newCnt);sort(newCells, newCells + newCnt);for (int i = 0; i < newCnt; ++i) {int code = newCells[i];int x = code / W;int y = code % W;printf("%d %d %d\n", x, y, num[code]);}}voidendGame(constchar* result){printf("%s\n", result);printf("total step %lld\n", totalStep);}intmain(){scanf("%d %d", &n, &m);W = m + 2;int totalCells = (n + 2) * W;mine.assign(totalCells, 0);opened.assign(totalCells, 0);flagged.assign(totalCells, 0);num.assign(totalCells, 0);int mineCount = 0;char buf[1005];for (int i = 1; i <= n; ++i) {scanf("%s", buf);for (int j = 1; j <= m; ++j) {if (buf[j - 1] == '*') {mine[id(i, j)] = 1;++mineCount;}}}safeTotal = n * m - mineCount;char op[20];while (scanf("%s", op) != EOF) {if (op[0] == 'Q') {endGame("give up");return 0;}int x, y;scanf("%d %d", &x, &y);++totalStep;newCnt = 0;if (op[0] == 'F') { // Flagint idx = id(x, y);if (opened[idx]) {printf("swept\n");} else {if (flagged[idx]) {flagged[idx] = 0;printf("cancelled\n");} else {flagged[idx] = 1;printf("success\n");}}} else if (op[0] == 'S') { // Sweepint idx = id(x, y);if (opened[idx]) {printf("swept\n");} else if (flagged[idx]) {printf("flagged\n");} else {bool ok = doSweep(x, y);if (!ok) {printf("boom\n");endGame("game over");return 0;}outputNewCells();if (openedSafe == safeTotal) {endGame("finish");return 0;}}} else if (op[0] == 'D') { // DSweepint idx = id(x, y);if (!opened[idx]) {printf("not swept\n");} else {int c = num[idx];if (c == 0) {printf("failed\n");} else {int flags = countFlags(x, y);if (flags != c) {printf("failed\n");} else {bool boom = false;for (int dx = -1; dx <= 1 && !boom; ++dx) {int nx = x + dx;for (int dy = -1; dy <= 1 && !boom; ++dy) {if (dx == 0 && dy == 0) continue;int ny = y + dy;if (nx < 1 || nx > n || ny < 1 || ny > m) continue;int nid = id(nx, ny);if (opened[nid]) continue;if (flagged[nid]) continue;if (!doSweep(nx, ny)) {boom = true;}}}if (boom) {printf("boom\n");endGame("game over");return 0;}outputNewCells();if (openedSafe == safeTotal) {endGame("finish");return 0;}}}}}}return 0;}