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

珠心算测验（Luogu P2141）

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

螺旋矩阵（Luogu P2239）

题意：按顺时针生成 n×n 的螺旋矩阵（填入 $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);
    }
}

无线网络发射器选址

题意：在 $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，求区间内所有整数根。答案可能很大，需按顺序输出。
考点：多项式霍纳法求值、取模避免溢出（如 $1 0^{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);
}

OI

2014

普及组

比例简化（Luogu P2118）

珠心算测验（Luogu P2141）

螺旋矩阵（Luogu P2239）

子矩阵（Luogu P2258）

提高组

生活大爆炸版石头剪刀布

联合权值

飞扬的小鸟

无线网络发射器选址

寻找道路

解方程

Keyboard shortcuts

OI