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，问方案数，结果对 $1 0^{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;
}

Keyboard shortcuts

OI