NOIP

2013

普及组

计数问题

• 题意：统计区间 1..n 中数字 x 出现的总次数。
• 考点：数位统计/数学计数、枚举或按位组合计数。

表达式求值

• 题意：只含 + 与 * 的表达式，无括号，计算值并输出末四位（按 10000 取模）。
• 考点：线性扫描/栈处理运算优先级、取模运算。

小朋友的数字

• 题意：定义每个位置的“特征值”为以该位置结尾的最大子段和；再定义分数为“前面所有人的分数+其特征值”的最大值，求全体最大分数，按符号输出，绝对值对 p 取模。
• 考点：最大子段和 DP（Kadane）、前缀最值维护、取模与符号处理。

车站分级

• 题意：给若干车次的停靠序列，满足“停靠某站则其间所有级别不低于它的都必须停靠”，求最少分成几级。
• 考点：图建模（停靠与未停靠间的约束边）、有向无环图 DAG 拓扑与最长路/层数。

提高组

转圈游戏

• 题意：n 人围圈，每轮位置整体平移 m，进行 10^k 轮，询问第 x 号最终位置。
• 考点：快速幂、取模同余运算。

#include <bits/stdc++.h>
using namespace std;
int power(int x, int n, int mod) {
    int ans = 1;
    while (n) {
        if (n & 1) ans = 1LL * ans * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ans;
}
int main() {
    int n, m, k, x;
    while (scanf("%d%d%d%d", &n, &m, &k, &x) != EOF) {
        int ans = (x + 1LL * m * power(10, k, n)) % n;
        printf("%d\n", ans);
    }
}

火柴排队

• 题意：两列火柴使平方差和最小，求将一列通过相邻交换变为与另一列对应排序一致所需的最少交换次数。
• 考点：排序一致性贪心、逆序对计数（树状数组/归并）。

#include <bits/stdc++.h>
using namespace std;
const int mod = 99999997;
#define N 100010
#define rep(i, l, r) for (int i = l; i <= r; ++i)

int a[N], b[N], h[N];
int c[N];
int n;
int lowbit(int x) {
    return x & (-x);
}
int ask(int x) {
    int ans = 0;
    for (; x <= n; x += lowbit(x))
        ans += c[x];
    return ans;
}
void change(int x, int y) {
    for (; x; x -= lowbit(x))
        c[x] += y;
}
int main() {
    while (scanf("%d", &n) != EOF) {
        rep(i, 1, n) scanf("%d", a + i), h[i] = a[i];
        sort(h + 1, h + n + 1);
        rep(i, 1, n) a[i] = lower_bound(h + 1, h + n + 1, a[i]) - h;
        rep(i, 1, n) scanf("%d", b + i), h[i] = b[i];
        sort(h + 1, h + n + 1);
        rep(i, 1, n) b[i] = lower_bound(h + 1, h + n + 1, b[i]) - h;

        rep(i, 1, n) h[a[i]] = i;
        rep(i, 1, n) b[i] = h[b[i]], c[i] = 0;
        int ans = 0;
        rep(i, 1, n) {
            change(b[i], 1);
            ans += ask(b[i] + 1);
            if (ans >= mod) ans -= mod;
        }
        printf("%d\n", ans);
    }
}

货车运输

• 题意：无向图多次查询两点间路径的“最大最小边权”（路径最小边尽量大）。
• 考点：最大生成树 Kruskal + 并查集，树上 LCA 倍增查询路径最小边。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define dow(i, l, r) for (int i = l; i >= r; --i)
#define N 10010
#define M 50010
const int INF = 0x3f3f3f3f;
struct edge {
    int x, y, c;
} t[M];
int n, m, q;
int fa[N];
bool root[N];
bool cmp(const edge& a, const edge& b) {
    return a.c > b.c;
}
int getfa(int x) {
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
bool Union(int x, int y) {
    x = getfa(x);
    y = getfa(y);
    if (x == y) return false;
    fa[x] = y;
    return true;
}
namespace TREE {
int e, head[M << 1], last[M << 1], w[M << 1], p[N];
int f[N][21], g[N][21];
int deep[N];
void add(int x, int y, int c) {
    head[++e] = y;
    w[e] = c;
    last[e] = p[x];
    p[x] = e;
}
void dfs(int x, int pre, int dep) {
    deep[x] = dep;
    for (int j = p[x]; j; j = last[j]) {
        int y = head[j];
        if (y == pre) continue;
        f[y][0] = x;
        g[y][0] = w[j];
        rep(i, 1, 20) {
            f[y][i] = f[f[y][i - 1]][i - 1];
            g[y][i] = min(g[y][i - 1], g[f[y][i - 1]][i - 1]);
        }
        dfs(y, x, dep + 1);
    }
}
int askmax(int x, int y) {
    if (deep[x] > deep[y]) swap(x, y);
    int ans = INF;
    dow(i, 20, 0) if (deep[f[y][i]] >= deep[x])
        ans = min(ans, g[y][i]),
        y = f[y][i];
    if (x == y) return ans;
    dow(i, 20, 0) if (f[x][i] != f[y][i]) {
        ans = min({ans, g[x][i], g[y][i]});
        x = f[x][i], y = f[y][i];
    }
    ans = min({ans, g[x][0], g[y][0]});
    return ans;
}

}  // namespace TREE

int main() {
    scanf("%d%d", &n, &m);
    rep(i, 1, m) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        t[i] = edge{x, y, c};
    }
    sort(t + 1, t + m + 1, cmp);
    rep(i, 1, n) fa[i] = i;
    rep(i, 1, m) {
        int x = t[i].x;
        int y = t[i].y;
        int c = t[i].c;
        if (Union(x, y)) {
            TREE::add(x, y, c);
            TREE::add(y, x, c);
        }
    }
    rep(i, 1, n) root[getfa(i)] = true;
    memset(TREE::g, INF, sizeof(TREE::g));
    rep(i, 1, n) if (root[i])
        TREE::dfs(i, 0, 1);

    scanf("%d", &q);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (getfa(x) != getfa(y))
            puts("-1");
        else
            printf("%d\n", TREE::askmax(x, y));
    }
}

积木大赛

• 题意：区间加一操作构造目标高度，求最少操作次数。
• 考点：差分/相邻差正贡献、贪心（答案为 h[1] + Σ max(0, h[i]-h[i-1])）。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define N 100010
int n;
int h[N];
int main() {
    scanf("%d", &n);
    int ans = 0;
    rep(i, 1, n) {
        scanf("%d", h + i);
        ans += max(0, h[i] - h[i - 1]);
    }
    printf("%d\n", ans);
}

花匠

• 题意：从高度序列中选出最长“峰谷交替”的子序列（摆动序列）。
• 考点：序列压缩、贪心/线性 DP（维护上升/下降结尾的最优）。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define N 100010
int n;
int a[N];
int main() {
    scanf("%d", &n);
    int ans = 0;
    int now = 0;
    rep(i, 1, n) {
        scanf("%d", a + i);
        if (i == 1 || a[i - 1] == a[i]) continue;
        if (a[i - 1] < a[i]) {
            if (now == -1) ++ans;
            now = 1;
        }
        if (a[i - 1] > a[i]) {
            if (now == 1) ++ans;
            now = -1;
        }
    }
    printf("%d\n", ans + 2);
}

华容道

• 题意：棋盘上一个空格与可移动棋子，询问将指定棋子移到目标的最少时间或不可达。
• 考点：状态图建模（空格在目标周围的方向状态）、BFS 预处理转移代价、最短路（如 SPFA/Dijkstra）。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int INF = 0x3f3f3f3f;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const int N = 31 * 31 * 4;
const int M = 4 * N;
struct node {
    int x, y;
} q[32 * 32 * 4];
int n, m, k;
int dis[32][32];
int can[32][32];

int e, head[M], last[M], w[M], p[N];
bool vis[N];
int dist[N];
bool ok(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && can[x][y];
}

void bfs(int sx, int sy) {
    memset(dis, INF, sizeof(dis));
    dis[sx][sy] = 0;
    int l = 0, r = 0;
    q[r++] = node{sx, sy};
    while (l != r) {
        int x = q[l].x;
        int y = q[l].y;
        l++;
        rep(i, 0, 3) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (ok(xx, yy) && dis[xx][yy] == INF) {
                dis[xx][yy] = dis[x][y] + 1;
                q[r++] = node{xx, yy};
            }
        }
    }
}
int calc(int x, int y, int k) {
    return x * m * 4 + y * 4 + k;
}
void add(int x, int y, int c) {
    head[++e] = y;
    w[e] = c;
    last[e] = p[x];
    p[x] = e;
}
void init() {
    rep(i, 0, n - 1)
        rep(j, 0, m - 1) if (ok(i, j)) {
        rep(k, 0, 3) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (!ok(x, y)) continue;
            can[i][j] = 0;
            bfs(x, y);
            can[i][j] = 1;
            rep(h, 0, 3) if (h != k) {
                int xx = i + dx[h];
                int yy = j + dy[h];
                if (ok(xx, yy) && dis[xx][yy] != INF)
                    add(calc(i, j, k), calc(i, j, h), dis[xx][yy]);
            }
            add(calc(i, j, k), calc(x, y, k ^ 1), 1);
        }
    }
}
void spfa(int sx, int sy) {
    queue<int> q;
    memset(vis, 0, sizeof(vis));
    memset(dist, INF, sizeof(dist));
    rep(i, 0, 3) if (ok(sx + dx[i], sy + dy[i]) && dis[sx + dx[i]][sy + dy[i]] != INF) {
        int now = calc(sx, sy, i);
        dist[now] = dis[sx + dx[i]][sy + dy[i]];
        vis[now] = true;
        q.push(now);
    }
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = false;
        for (int j = p[x]; j; j = last[j]) {
            int y = head[j];
            if (dist[y] > dist[x] + w[j]) {
                dist[y] = dist[x] + w[j];
                if (!vis[y]) {
                    vis[y] = true;
                    q.push(y);
                }
            }
        }
    }
}
int work(int x, int y, int sx, int sy, int tx, int ty) {
    if (sx == tx && sy == ty) return 0;
    can[sx][sy] = 0;
    bfs(x, y);
    can[sx][sy] = 1;
    spfa(sx, sy);
    int ans = INF;
    rep(i, 0, 3) ans = min(ans, dist[calc(tx, ty, i)]);
    if (ans == INF) ans = -1;
    return ans;
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    rep(i, 0, n - 1)
        rep(j, 0, m - 1)
            scanf("%d", &can[i][j]);
    init();
    while (k--) {
        int x, y, sx, sy, tx, ty;
        scanf("%d%d%d%d%d%d", &x, &y, &sx, &sy, &tx, &ty);
        --x;
        --y;
        --sx;
        --sy;
        --tx;
        --ty;
        printf("%d\n", work(x, y, sx, sy, tx, ty));
    }
}
/*
3 4 2
0 1 1 1
0 1 1 0
0 1 0 0
3 2 1 2 2 2
1 2 2 2 3 2
*/

2014

普及组

比例简化（Luogu P2118）

• 题意：给定支持人数 A、反对人数 B 与上限 L，在 1..L 中选取互质的 A'、B'，满足 $\frac{A^{\prime }}{B^{\prime }}\ge \frac{A}{B}$，并使差值 $\frac{A^{\prime }}{B^{\prime }}-\frac{A}{B}$ 最小，输出 A' B'。
• 考点：枚举与比较、最大公约数 gcd、有理数比较（交叉乘）、边界与互质判定。

珠心算测验（Luogu P2141）

• 题意：给出一个互不相同的正整数集合，统计其中有多少个数可以表示为集合中另外两个不同数之和。
• 考点：三重枚举 O(n^3) 或两数和标记 O(n^2)；去重与“不同数”限制处理；空间换时间的布尔标记。

螺旋矩阵（Luogu P2239）

• 题意：按顺时针生成 n×n 的螺旋矩阵（填入 $\mathrm{1..}{n}^2$），给出位置 (i,j)，求该格的数。
• 考点：模拟走位、分层递推与公式法、坐标边界与方向切换；时间与空间优化（无需真的构建 $n^2$ 矩阵时的分层公式）。

子矩阵（Luogu P2258）

• 题意：从 n×m 矩阵中选 r 行与 c 列构成子矩阵，定义分值为相邻（上下左右）元素差的绝对值之和，要求最小分值。
• 考点：枚举行集 + 列集的最优选择、行间/列间代价预计算、动态规划或贪心优化、绝对值与边界处理。

提高组

生活大爆炸版石头剪刀布

• 题意：两人按各自周期序列出拳，进行 N 次，按扩展规则统计两人得分。
• 考点：模拟、周期取模、胜负关系打表、边界与平局判定。

#include <bits/stdc++.h>
using namespace std;
#define N 205
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int n, na, nb;
int a[N], b[N];
const int w[5][5] = {{0, -1, 1, 1, -1}, {1, 0, -1, 1, -1}, {-1, 1, 0, -1, 1}, {-1, -1, 1, 0, 1}, {1, 1, -1, -1, 0}};
int main() {
    while (scanf("%d%d%d", &n, &na, &nb) != EOF) {
        rep(i, 0, na - 1) scanf("%d", a + i);
        rep(i, 0, nb - 1) scanf("%d", b + i);
        int ans1 = 0, ans2 = 0;
        rep(i, 0, n - 1) {
            int x = a[i % na], y = b[i % nb];
            if (w[x][y] > 0)
                ++ans1;
            else if (w[x][y] < 0)
                ++ans2;
        }
        printf("%d %d\n", ans1, ans2);
    }
}

联合权值

• 题意：给一棵无向连通图（树）和点权，所有距离为 2 的有序点对产生联合权值，求最大值与总和（对 10007 取模）。
• 考点：树的性质、对每个点的邻居两两配对；最大值取邻居权值的最大与次大；总和用恒等式 $2{\sum }_{i<j}{w}_i{w}_j=(\sum w{)}^2-\sum w^2$。

#include <bits/stdc++.h>
using namespace std;
const int mod = 10007;
#define N 200010
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int e, head[N << 1], last[N << 1], p[N];
int deep[N];
int a[N];
int sum[N], md[N];
int ans1, ans2;
int n;
void add(int& x, int y) {
    (x += y) >= mod && (x -= mod);
}
void addedge(int x, int y) {
    head[++e] = y;
    last[e] = p[x];
    p[x] = e;
}
void dfs(int x, int pre, int dep) {
    deep[x] = dep;
    sum[x] = 0;
    md[x] = 0;
    int now = 0, ss = 0, mm = 0;
    int max1 = 0, max2 = 0;
    for (int j = p[x]; j; j = last[j]) {
        int y = head[j];
        if (y == pre) continue;
        dfs(y, x, dep + 1);
        add(sum[x], a[y]);
        add(now, a[y] * a[y] % mod);
        add(ss, sum[y]);
        md[x] = max(md[x], a[y]);
        mm = max(mm, md[y]);
        if (a[y] >= max1)
            max2 = max1, max1 = a[y];
        else
            max2 = max(max2, a[y]);
    }
    add(ans2, 2 * ss * a[x] % mod);
    add(ans2, (sum[x] * sum[x] - now + mod) % mod);
    ans1 = max(ans1, mm * a[x]);
    ans1 = max(ans1, max1 * max2);
}
int main() {
    while (scanf("%d", &n) != EOF) {
        e = 0;
        memset(p, 0, sizeof(p));
        rep(i, 1, n - 1) {
            int x, y;
            scanf("%d%d", &x, &y);
            addedge(x, y);
            addedge(y, x);
        }
        rep(i, 1, n) scanf("%d", a + i);
        ans1 = 0, ans2 = 0;
        dfs(1, 0, 1);
        printf("%d %d\n", ans1, ans2);
    }
}

飞扬的小鸟

• 题意：在长度为 n、高度上限 m 的界面上前进，每列上升高度 X、不点下降高度 Y 可不同，穿过若干管道，若能到达终点求最少点击次数，否则求最多通过的管道数。
• 考点：动态规划、点击上升视作完全背包、下落视作 $0/1$ 背包的混合转移、障碍列合法区间裁剪、状态压缩与边界处理。

#include <bits/stdc++.h>
using namespace std;
#define N 10010
#define M 1010
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int INF = 0x3f3f3f3f;
bool wall[N];
vector<int> now, las;
int n, m, q;
int a[N], b[N];
int l[N], r[N];
int main() {
    scanf("%d%d%d", &n, &m, &q);
    rep(i, 0, n - 1) {
        scanf("%d%d", a + i, b + i);
        l[i] = 0;
        r[i] = m + 1;
    }
    l[n] = 0;
    r[n] = m + 1;
    rep(i, 1, q) {
        int x;
        scanf("%d", &x);
        scanf("%d%d", &l[x], &r[x]);
        wall[x] = true;
    }

    now.resize(m + 5);
    las.resize(m + 5);
    rep(i, 1, m) las[i] = 0;
    las[0] = INF;
    int ans1 = INF, ans2 = 0;
    rep(i, 1, n) {
        int x = a[i - 1];
        rep(j, 0, m) now[j] = INF;
        rep(j, x, m) {
            now[j] = min(now[j], las[j - x] + 1);
            now[j] = min(now[j], now[j - x] + 1);
        }
        rep(j, m - x, m) {
            now[m] = min(now[m], las[j] + 1);
            now[m] = min(now[m], now[j] + 1);
        }
        rep(j, l[i] + 1, r[i] - 1) if (j + b[i - 1] <= m)
            now[j] = min(now[j], las[j + b[i - 1]]);
        rep(j, 0, l[i]) now[j] = INF;
        rep(j, r[i], m) now[j] = INF;
        if (wall[i])
            rep(j, l[i] + 1, r[i] - 1) if (now[j] < INF) {
                ++ans2;
                break;
            }
        swap(now, las);
    }
    rep(j, 1, m) ans1 = min(ans1, las[j]);
    if (ans1 < INF) {
        puts("1");
        printf("%d\n", ans1);
    } else {
        puts("0");
        printf("%d\n", ans2);
    }
}

无线网络发射器选址

• 题意：在 $\mathrm{0..128}$ 的网格路口中，有若干带权点，发射器覆盖以中心为边长 2d 的轴对齐正方形，问“覆盖点权之和的最大值”与“达到最大值的选址个数”。
• 考点：二维前缀和、枚举中心并计算正方形覆盖和、边界含闭区间处理、统计最大值计数。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int n, d;
int a[130][130];
int main() {
    scanf("%d", &d);
    // d=2*d+1;
    scanf("%d", &n);
    rep(i, 1, n) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        ++x;
        ++y;
        a[x][y] += c;
    }
    int ans1 = 0, ans2 = 0;
    rep(i, 1, 129)
        rep(j, 1, 129)
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    rep(i, 1, 129) {
        rep(j, 1, 129) {
            int x = min(129, i + d);
            int y = min(129, j + d);
            int xx = max(0, i - d - 1);
            int yy = max(0, j - d - 1);
            int now = a[x][y] - a[x][yy] - a[xx][y] + a[xx][yy];
            if (now > ans2)
                ans1 = 1, ans2 = now;
            else if (now == ans2)
                ++ans1;
        }
    }
    printf("%d %d\n", ans1, ans2);
}

寻找道路

• 题意：在有向图中，从起点到终点的路径需满足：路径上每个点的所有出边指向的点都（直接或间接）与终点连通；在此约束下求最短路径长度；不存在则输出 -1。
• 考点：反图 BFS 标记“可达终点”的点集、筛掉“指向不可达点”的点、在剩余图上最短路（BFS/SPFA），连通性与约束过滤。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define N 10010
#define M 200010
vector<int> edge[N];
vector<int> redge[N];
queue<int> q;
bool vis[N];
bool ok[N];
int dis[N];
int n, m;
void pre(int s) {
    vis[s] = true;
    q.push(s);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto& y : redge[x])
            if (!vis[y]) {
                vis[y] = true;
                q.push(y);
            }
    }
}
int bfs(int st, int ed) {
    if (!ok[st]) return -1;
    memset(dis, -1, sizeof(dis));
    dis[st] = 0;
    q.push(st);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (auto& y : edge[x])
            if (ok[y] && dis[y] == -1) {
                dis[y] = dis[x] + 1;
                q.push(y);
            }
    }
    return dis[ed];
}
int main() {
    scanf("%d%d", &n, &m);
    rep(i, 1, m) {
        int x, y;
        scanf("%d%d", &x, &y);
        redge[y].push_back(x);
        edge[x].push_back(y);
    }
    int st, ed;
    scanf("%d%d", &st, &ed);
    pre(ed);
    memset(ok, true, sizeof(ok));
    rep(y, 1, n) if (!vis[y]) for (auto& x : redge[y])
        ok[x] = false;
    printf("%d\n", bfs(st, ed));
}

解方程

• 题意：给定次数为 n 的整系数多项式与区间 1..m，求区间内所有整数根。答案可能很大，需按顺序输出。
• 考点：多项式霍纳法求值、取模避免溢出（如 $10^9+9$）、枚举整数并判零、输入系数的大数取模读入。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define N 1000010
char s[105][10010];
int val[105][205];
int f[20000][10];
bool ok[N];
const int prime[] = {19997, 19961, 19759, 18013, 17011, 15359};
const int tot = 6;
int n, m;

int calc(char* s, int mod) {
    int now = 0;
    for (int i = (s[0] == '-') ? 1 : 0; s[i]; ++i)
        now = (1LL * now * 10 + s[i] - '0') % mod;
    if (s[0] == '-') now = (mod - now) % mod;
    return now;
}
int check(int x, int y, int mod) {
    int now = 1, ans = 0;
    rep(i, 0, n) {
        ans += 1LL * val[i][y] * now % mod;
        if (ans >= mod) ans -= mod;
        now = 1LL * now * x % mod;
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &m);
    rep(i, 0, n) {
        scanf("%s", s[i]);
        rep(j, 0, tot - 1) val[i][j] = calc(s[i], prime[j]);
    }
    rep(i, 1, m) ok[i] = true;
    int ans = 0;
    rep(i, 0, m) if (ok[i]) {
        for (int j = 0; j < tot; ++j) {
            if (i < prime[j]) f[i][j] = check(i, j, prime[j]);
            if (f[i % prime[j]][j]) ok[i] = false;
        }
        if (i > 0 && ok[i]) ++ans;
    }
    printf("%d\n", ans);
    rep(i, 1, m) if (ok[i]) printf("%d\n", i);
}

2015

普及组

金币

• 题意：每天领取的金币数按“每个正整数 k 连续领取 k 天”的模式分配，给定天数 n，求累计金币总数。
• 考点：数学归纳与分段求和、前缀和/模拟、分块累加优化。

#include <cstdio>
#include <iostream>
using namespace std;
int main() {
    int k;
    while (cin >> k) {
        int now = 1, ans = 0;
        while (k >= now) {
            k -= now;
            ans += now * now;
            ++now;
        }
        ans += now * k;
        cout << ans << endl;
    }
}

扫雷游戏

• 题意：给出网格中布雷情况（*/.），要求将每个非雷格替换为周围八方向雷的数量。
• 考点：二维遍历、方向数组、边界判定、字符串/数组就地更新。

#include <cstdio>
#include <iostream>
using namespace std;
const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int n, m;
char s[105][105];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", s[i]);
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j)
            if (s[i][j] == '?') {
                int ans = 0;
                for (int k = 0; k < 8; ++k) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && s[x][y] == '*') {
                        ++ans;
                    }
                }
                s[i][j] = '0' + ans;
            }
    }
    for (int i = 0; i < n; ++i)
        printf("%s\n", s[i]);
}

求和

• 题意：纸带上有编号与颜色，定义满足条件的三元组分数并累加，输出结果对 10007 取模。
• 考点：分类统计（按颜色与编号奇偶分组）、前缀与交叉项累加、取模与溢出防护、线性遍历优化。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 10007;
#define N 100010
int n, m;
int a[N], sum0[N][2], sum1[N][2], sum2[N][2], sum3[N][2];
void add(int& x, int y) {
    x += y;
    x %= mod;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int c;
        scanf("%d", &c);
        add(ans, 1LL * i * a[i] * sum0[c][i & 1] % mod);
        add(ans, 1LL * a[i] * sum1[c][i & 1] % mod);
        add(ans, 1LL * i * sum2[c][i & 1] % mod);
        add(ans, sum3[c][i & 1]);
        add(sum0[c][i & 1], 1);
        add(sum1[c][i & 1], i);
        add(sum2[c][i & 1], a[i]);
        add(sum3[c][i & 1], 1LL * i * a[i] % mod);
    }
    printf("%d\n", ans);
}

推销员

• 题意：一条街上多户人家，已知各户到入口距离与推销疲劳值；对不同的拜访数量，求在“不走多余路”条件下的最大疲劳值。
• 考点：按距离排序、前缀最大值/前缀和维护、枚举拜访终点的贡献拆分、线性/线性对数优化。

#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
#define N 100010
struct node {
    int a, s;
} t[N];
bool cmp(const node& t1, const node& t2) {
    return t1.a > t2.a;
}
int n;
int sum[N], sub[N], pre[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &t[i].s);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &t[i].a);
    sort(t + 1, t + n + 1, cmp);
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + t[i].a;
    for (int i = 1; i <= n; ++i)
        pre[i] = max(pre[i - 1], t[i].s);
    for (int i = n; i >= 1; --i)
        sub[i] = max(sub[i + 1], 2 * t[i].s + t[i].a);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", max(sum[i - 1] + sub[i], sum[i] + 2 * pre[i]));
}

提高组

神奇的幻方

• 题意：当 N 为奇数时，按规定规则构造 N×N 幻方，使每行、每列与两条对角线和相等，输出矩阵。
• 考点：模拟构造、坐标移动规则与边界换行、数组下标与初始化、数学性质验证。

#include <bits/stdc++.h>
using namespace std;
int n;
int a[50][50];
int main() {
    scanf("%d", &n);
    int x = 1, y = (n + 1) / 2;
    a[x][y] = 1;
    for (int i = 2; i <= n * n; i++) {
        if (x == 1 && y != n)
            x = n, y++;
        else if (x != 1 && y == n)
            x--, y = 1;
        else if (x == 1 && y == n)
            x++;
        else if (!a[x - 1][y + 1])
            x--, y++;
        else
            x++;
        a[x][y] = i;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            printf("%d%c", a[i][j], (j < n) ? ' ' : '\n');
}

信息传递

• 题意：每人把消息传给恰好一个人，形成“每点出度为 1”的图；求最小环的大小。
• 考点：功能图（基环树）最小环检测、DFS/并查集/拓扑剥离、访问标记与入栈标记处理。

#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int n;
int a[N];
int fa[N];
int getfa(int x) {
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
bool Union(int x, int y) {
    x = getfa(x);
    y = getfa(y);
    if (x == y) return false;
    fa[x] = y;
    return true;
}
int walk(int x) {
    int ans = 0, y = x;
    while (true) {
        y = a[y];
        ++ans;
        if (y == x) break;
    }
    return ans;
}
int main() {
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", a + i), fa[i] = i;
    int ans = ~0U >> 1;
    rep(i, 1, n) if (!Union(i, a[i]))
        ans = min(ans, walk(i));
    printf("%d\n", ans);
}

斗地主

• 题意：给定若干组手牌，问每组最少出牌次数打光，牌型近似斗地主但略有差异。
• 考点：搜索与剪枝（优先消耗复合牌型）、打表判型、贪心/DP 装配顺子与连对、上界估计优化搜索。

#include <bits/stdc++.h>
using namespace std;
int T, n, ans;
int a[16];
int calc() {
    int now = 0;
    for (int i = 0; i <= 14; ++i)
        if (a[i])
            ++now;
    return now;
}
void dfs(int step, int x) {
    if (step >= ans) return;
    ans = min(ans, step + calc());
    for (int i = 3; i <= 13; ++i)  // san shun
    {
        int j = i;
        while (j <= 14 && a[j] >= 3) ++j;
        if (j - i < 2) continue;
        a[i] -= 3;
        for (int k = i + 1; k < j; ++k) {
            a[k] -= 3;
            dfs(step + 1, x - (k - i + 1) * 3);
        }
        for (int k = i; k < j; ++k)
            a[k] += 3;
    }

    for (int i = 3; i <= 12; ++i)  // shuang shun
    {
        int j = i;
        while (j <= 14 && a[j] >= 2) ++j;
        if (j - i < 3) continue;
        a[i] -= 2;
        a[i + 1] -= 2;
        for (int k = i + 2; k < j; ++k) {
            a[k] -= 2;
            dfs(step + 1, x - (k - i + 1) * 2);
        }
        for (int k = i; k < j; ++k)
            a[k] += 2;
    }
    for (int i = 3; i <= 10; ++i)  // dan shun
    {
        int j = i;
        while (j <= 14 && a[j] >= 1) ++j;
        if (j - i < 5) continue;
        a[i]--;
        a[i + 1]--;
        a[i + 2]--;
        a[i + 3]--;
        for (int k = i + 4; k < j; ++k) {
            a[k]--;
            dfs(step + 1, x - (k - i + 1));
        }
        for (int k = i; k < j; ++k)
            a[k]++;
    }
    for (int i = 2; i <= 14; ++i)
        if (a[i] == 4) {
            a[i] = 0;
            dfs(step + 1, x - 4);
            for (int j = 0; j <= 14; ++j)
                if (a[j] > 0) {
                    a[j]--;
                    for (int k = j; k <= 14; ++k)
                        if (a[k] > 0) {
                            a[k]--;
                            dfs(step + 1, x - 6);
                            a[k]++;
                        }
                    a[j]++;
                }
            for (int j = 2; j <= 14; ++j)
                if (a[j] > 1) {
                    a[j] -= 2;
                    for (int k = j; k <= 14; ++k)
                        if (a[k] > 1) {
                            a[k] -= 2;
                            dfs(step + 1, x - 8);
                            a[k] += 2;
                        }
                    a[j] += 2;
                }
            a[i] = 4;
        }

    for (int i = 2; i <= 14; ++i)
        if (a[i] >= 3) {
            a[i] -= 3;
            dfs(step + 1, x - 3);
            for (int j = 0; j <= 14; ++j)
                if (a[j] >= 1) {
                    a[j]--;
                    dfs(step + 1, x - 4);
                    a[j]++;
                }
            for (int j = 2; j <= 14; ++j)
                if (a[j] >= 2) {
                    a[j] -= 2;
                    dfs(step + 1, x - 5);
                    a[j] += 2;
                }
            a[i] += 3;
        }
}
int main() {
    scanf("%d%d", &T, &n);
    while (T--) {
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; ++i) {
            int x;
            scanf("%d%*d", &x);
            if (x == 1) x = 14;
            a[x]++;
        }
        ans = n;
        dfs(0, n);
        printf("%d\n", ans);
    }
}

跳石头

• 题意：在 0..L 线上有 N 块石头，可移走至多 M 块，最大化比赛时“最短跳跃距离”。
• 考点：答案二分与可行性贪心（相邻距离至少为 mid）、终点补石、边界细节与单调性证明。

#include <bits/stdc++.h>
using namespace std;
#define N 50010
#define rep(i, l, r) for (int i = l; i <= r; ++i)
int a[N];
int n, m, H;
bool ok(int len) {
    int last = 0, i = 0, ans = 0;
    while (true) {
        while (i <= n && a[i] - last < len) ++i;
        if (i > n) break;
        ++ans;
        last = a[i];
    }
    if (ans > 0 && H - last < len) --ans;
    return n - ans <= m;
}

int main() {
    scanf("%d%d%d", &H, &n, &m);
    rep(i, 1, n) scanf("%d", a + i);
    int l = 1, r = H;
    while (l < r) {
        int mid = l + (r - l + 1) / 2;
        if (ok(mid))
            l = mid;
        else
            r = mid - 1;
    }
    printf("%d\n", l);
}

子串

• 题意：从字符串 A 中取互不重叠的 k 段子串按顺序拼接成 B，问方案数，结果对 $10^9+7$ 取模。
• 考点：字符串动态规划（分段与是否延续）、滚动数组、匹配转移与取模、复杂度优化到 O(nmk)。

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n, m, K;
int dp[2][1005][205];
char a[1005], b[205];
void add(int& x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
int main() {
    scanf("%d%d%d", &n, &m, &K);
    scanf("%s", a + 1);
    scanf("%s", b + 1);
    for (int i = 0; i <= n; ++i)
        dp[0][i][0] = 1;

    for (int k = 1; k <= K; ++k) {
        memset(dp[k & 1], 0, sizeof(dp[k & 1]));
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                add(dp[k & 1][i][j], dp[k & 1][i - 1][j]);
                int l = 0;
                while (l < j && l < i && a[i - l] == b[j - l]) {
                    ++l;
                    add(dp[k & 1][i][j], dp[(k & 1) ^ 1][i - l][j - l]);
                }
                // cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
            }
    }
    printf("%d\n", dp[K & 1][n][m]);
}

运输计划

• 题意：给一棵带权树与 m 条路径，可将一条边权变为 0，使所有路径长度的最大值尽量小，求该最小最大值。
• 考点：答案二分、路径长度计算（LCA + 距离）、树上差分找“所有超标路径的公共边”、最大边权抵消判定。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 300010
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define dow(i, l, r) for (int i = l; i >= r; --i)
int e, head[N << 1], w[N << 1], last[N << 1], p[N];
int deep[N], fa[N], num[N], son[N];
int top[N];
int a[N], dis[N];
int u[N], v[N], lca[N], val[N];
int n, m;
void add(int x, int y, int c) {
    head[++e] = y;
    w[e] = c;
    last[e] = p[x];
    p[x] = e;
}
void dfs(int x, int pre, int dep) {
    deep[x] = dep;
    fa[x] = pre;
    num[x] = 1;
    for (int j = p[x]; j; j = last[j]) {
        int y = head[j];
        if (y == pre) continue;
        dis[y] = dis[x] + w[j];
        dfs(y, x, dep + 1);
        num[x] += num[y];
        if (son[x] == -1 || num[y] > num[son[x]])
            son[x] = y;
    }
}
void dfs_son(int x, int rt) {
    top[x] = rt;
    if (son[x] == -1)
        return;
    else
        dfs_son(son[x], rt);
    for (int j = p[x]; j; j = last[j])
        if (head[j] != fa[x] && head[j] != son[x])
            dfs_son(head[j], head[j]);
}
void dfs(int x) {
    for (int j = p[x]; j; j = last[j]) {
        int y = head[j];
        if (y == fa[x]) continue;
        dfs(y);
        a[x] += a[y];
    }
}
int calc(int x, int y) {
    int f1 = top[x], f2 = top[y];
    while (f1 != f2) {
        if (deep[f1] < deep[f2]) {
            swap(x, y);
            swap(f1, f2);
        }
        x = fa[f1];
        f1 = top[x];
    }
    if (deep[x] > deep[y]) swap(x, y);
    return x;
}

bool ok(int mid) {
    int tot = 0, mx = 0, ans = 0;
    memset(a, 0, sizeof(a));
    rep(i, 1, m) if (val[i] > mid) {
        a[u[i]]++;
        a[v[i]]++;
        a[lca[i]] -= 2;
        ++tot;
        ans = max(ans, val[i]);
    }
    dfs(1);
    rep(i, 1, n) if (a[i] >= tot)
        mx = max(mx, dis[i] - dis[fa[i]]);
    return ans - mx <= mid;
}
int main() {
    scanf("%d%d", &n, &m);
    rep(i, 1, n - 1) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
        add(y, x, c);
    }
    memset(son, -1, sizeof(son));
    dfs(1, 0, 1);
    dfs_son(1, 1);
    rep(i, 1, m) {
        scanf("%d%d", u + i, v + i);
        lca[i] = calc(u[i], v[i]);
        val[i] = dis[u[i]] + dis[v[i]] - 2 * dis[lca[i]];
    }
    int l = 0, r = 4e8;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (ok(mid))
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d\n", l);
    return 0;
}

CSP