题意：统计区间 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
*/

OI

2013

普及组

计数问题

表达式求值

小朋友的数字

车站分级

提高组

转圈游戏

火柴排队

货车运输

积木大赛

花匠

华容道

Keyboard shortcuts

OI