CCPC 2015 个人题解

CCPC 2015 个人题解

Coast23
  2026-02-03 20:56:53 2026-02-03 20:56:53 创建   2026-02-10 21:51:27 2026-02-10 21:51:27 更新    3.7k 字  18 分钟  

学算法学到自闭，试图靠写远古题找回自信。

不得不说，以前的赛题写起来是真舒服，现在的题目实在是太阴间了。

比赛链接：第一届中国大学生程序设计竞赛（CCPC 2015）

A. Secrete Master Plan

题意：签到。

写太快吃了发罚时，悲。

AC Code:

void solve(){
    std::vector<int> a(4), b(4);
    for(auto& x : a) x = read();
    for(auto& x : b) x = read();
    std::swap(a[2], a[3]); std::swap(b[2], b[3]);
    for(int i = 0; i < 4; ++i){
        bool flag = true;
        for(int j = 0; j < 4; ++j){
            if(a[j] != b[(i + j) % 4]){
                flag = false;
                break;
            }
        }
        if(flag) return puts("POSSIBLE"), void();
    }
    puts("IMPOSSIBLE");
}

C. The Battle of Chibi

题意：

给定长为() 的序列()，求长为() 的严格上升子序列个数，答案对取模。

应该是经典问题。

的大小不重要，先离散化。

定义状态 dp[i] 表示当前长度下，以第个元素为结尾的上升子序列个数。

如果想求长为的上升子序列个数，自然要从长度的结果来推导。也就是找到所有下标且的位置，累加它们在长度为时的 dp 值。

从到枚举长度，并遍历所有点对，复杂度是的，无法接受。

不过，很显然内层是不需要枚举的，只需要拿一个树状数组维护的累加和即可。这样就轻松做到了。

AC Code:

const ll mod = 1e9 + 7;

struct Fenwick {
    int n;
    std::vector<ll> t;
    Fenwick(int _n) : n(_n), t(n + 1, 0) {}
    void add(int x, ll v){
        for(x; x <= n; x += x & -x) t[x] = (t[x] + v) % mod;
    }
    ll query(int x){
        ll sum = 0;
        for(x; x > 0; x -= x & -x) sum = (sum + t[x]) % mod;
        return sum;
    }
};

void solve(){
    int n = read(), m = read();
    std::vector<int> a(n);
    for(auto& x : a) x = read(); 
    std::vector<int> rank = a;
    std::sort(rank.begin(), rank.end());
    rank.erase(std::unique(rank.begin(), rank.end()), rank.end());
    for(int i = 0; i < n; ++i){
        // 1-index
        a[i] = std::lower_bound(rank.begin(), rank.end(), a[i]) - rank.begin() + 1;
    }
    int V = rank.size();
    std::vector<int> dp(n, 1);
    for(int len = 2; len <= m; ++len){
        Fenwick fw(V);
        for(int i = 0; i < n; ++i){
            int pre = dp[i];
            dp[i] = fw.query(a[i] - 1);
            fw.add(a[i], pre);
        }
    }
    ll ans = 0;
    for(auto& x: dp) ans = (ans + x) % mod;
    printf("%lld\n", ans);
}

D. Pick The Sticks

题意：

有() 个金条，金条有长度() 和价值()，以及一个长为() 的条形容器。容器用来放金条，金条可以伸出容器，只要重金在容器内，且金条之间不能重叠，求能得到的最大金条总价值。

显然，合法金条组的充要条件为：

长度之和最左端金条长最右端金条长

分数很讨厌，所以两边乘以：

长度之和最左端金条长最右端金条长

端点的金条贪心选最大和次大，自然想到先把金条按长度从小到大排序，再从到枚举长度次大的金条，在中挑若干金条，在中挑一个金条，
且长度满足上面的约束条件即可。

接下来只需要解决“怎么挑”的问题就行了。

首先是的金条集。我们不关心具体选了哪些金条，只关心选出来的金条总长和总价值 —— 那不就是一个裸的背包吗，从小到大枚举金条总长，求出/维护 总长为时的最大总价值 dp[w]即可。

然后是在中挑一个作为最大的金条。直接枚举的话复杂度过不去，需要一个高效的做法。首先，不是每个的金条都满足 (*) 这个条件，由于我们的是从小到大枚举的，且金条长度递增，所以可以用双指针法找到符合 (*) 的最大金条，接下来只需要快速挑出区间里价值最高的金条，这就是一个 RMQ 问题了，我选择用 ST 表来做。

总的时间复杂度就是。

AC Code:

struct ST {
    int n;
    std::vector<std::vector<ll>> st;
    std::vector<int> lg;
    ST(std::vector<ll>& a){
        n = a.size();
        int lgn = std::__lg(n);
        st.resize(lgn + 1, std::vector<ll>(n));
        lg.resize(n + 1);
        lg[1] = 0;
        for(int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
        for(int i = 0; i < n; ++i) st[0][i] = a[i];
        for(int j = 1; j <= lgn; ++j){
            for(int i = 0; i + (1 << j) <= n; ++i){
                st[j][i] = std::max(st[j-1][i], st[j-1][i + (1 << (j-1))]);
            }
        }
    }
    ll query(int L, int R){
        if(L > R) return 0;
        int j = lg[R - L + 1];
        return std::max(st[j][L], st[j][R - (1 << j) + 1]);
    }
};

void solve(){
    int n = read(), L = read();
    struct Stick {int a; ll v;};
    std::vector<Stick> s(n);
    ll maxv = 0;
    for(auto& [a, v] : s){
        a = read(), v = read();
        maxv = std::max(maxv, v);
    }
    std::sort(s.begin(), s.end(), [](const Stick& X, const Stick& Y){return X.a < Y.a;});
    std::vector<ll> tmp;
    for(auto& [a, v] : s) tmp.push_back(v);
    ST st(tmp);

    std::vector<ll> dp(L << 1 | 1, -1);
    dp[0] = 0;
    ll ans = maxv; // 极端情况就是只够放一个金条，那就挑价值最大的那个。
    for(int i = 0; i < n - 1; ++i){
        auto cur = s[i]; // 次大长的金条
        int k = n - 1;
        for(int w = 0; w <= (L << 1); ++w){
            if(dp[w] == -1) continue;
            ll bound = (L << 1) - w - cur.a; // 根据条件 (*) 得到的最大长度
            if(bound < cur.a) break;
            while(k > i and s[k].a > bound) --k;
            ll best = st.query(i + 1, k);
            ans = std::max(ans, dp[w] + cur.v + best);
        }
        // 用当前物品价值更新背包
        int M = cur.a << 1;
        for(int w = L << 1; w >= M; --w){
            if(dp[w - M] == -1) continue;
            dp[w] = std::max(dp[w], dp[w - M] + cur.v);
        }
    }
    printf("%lld\n", ans);
}

E. Ba Gua Zhen

题意：

给定一个()个点() 条边的边带权 () 连通简单无向图，找一个回路（允许经过重复点和边），使得回路上所有边的权值异或和最大。

和 [WC2011] 最大XOR和路径 很像，唯一不同就是，这里要求是回路。

回路这个要求就松一点了，回路不含链，可以看成若干个“基本环”的组合，由于图是连通的，所以只需要求出所有的“基本环”，并考虑这些基本环所能凑出的异或最大值，那不就是裸的线性基板子了吗。问题就变成了：找到所有环，把环的异或值插到线性基里，最后对线性基 qmax 即可。

找环的方式：

  • 随便以一个点为根，建一棵生成树，求出每个点到根的异或路径和
  • 如果找到一条非树边，边权为，则该非树边与生成树上的路径构成一个环，环的异或值是。

AC Code:

struct LinearBasis {
    ll p[65] = {0};
    void insert(ll x){
        for(int i = 63; ~i; --i){
            if(!(x >> i & 1)) continue;
            if(!p[i]) return p[i] = x, void();
            x ^= p[i];
        }
    }
    ll qmax(){
        ll ans = 0;
        for(int i = 63; ~i; --i) ans = std::max(ans, ans ^ p[i]);
        return ans;
    }
};

void solve(){
    int n = read(), m = read();
    struct Edge {int v; ll w;};
    std::vector<std::vector<Edge>> adj(n + 1);
    for(int i = 0; i < m; ++i){
        int x = read(), y = read(); ll z = read();
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }
    std::vector<ll> dis(n + 1);
    std::vector<bool> vis(n + 1);
    LinearBasis lb;

    auto dfs = [&](auto&& self, int u, ll cur) -> void {
        vis[u] = true;
        dis[u] = cur;
        for(auto& [v, w] : adj[u]){
            if(!vis[v]) self(self, v, cur ^ w);
            else lb.insert(dis[u] ^ dis[v] ^ w);
        }
    };
    dfs(dfs, 1, 0);
    printf("%lld\n", lb.qmax());
}

F. The Battle of Guandu

题意：

曹操和袁绍在()个战场作战。曹操可以从() 个村庄招募士兵。

对于村庄:

  • 曹操可以招募士兵去战场，每个士兵的费用为。
  • 此时袁绍会自动获得等量士兵去战场。

战场有三种重要度：

  • ：曹操兵力必须严格大于袁绍。
  • ：曹操兵力必须大于或等于袁绍。
  • ：无限制。

求满足所有战场条件的最小花费。

很有意思的题，需要先考虑如何建模。

从村庄招兵，对于曹操来说，战场优势增加，战场优势减少，相当于从战场“借力”，代价为。从势能角度考虑，也就是从到，势能要增加。于是连有向边，边权为。

然后考虑种类型战场的含义：

  • 的战场没有限制，可以无限抽取兵力，视为“源点”，势能为。
  • 的战场必须胜利，是花费的目标，满足胜利条件的最小代价就是它到源点的最短路径长度。
  • 的战场只需打平，作为从运兵到的中间节点，本身不需要产生代价（从源点运兵到的节点，再运到的节点，前者的费用已经包含在到源点的路径里了）。

这个模型看着就很对，跑一个多源 Dijkstra，累和的所有点的最短路径即可（若其中某个点不可达，说明无解）。

AC Code:

void solve(){
    int n = read(), m = read();
    std::vector<int> X(n), Y(n), C(n);
    for(auto& x : X) x = read();
    for(auto& y : Y) y = read();
    for(auto& c : C) c = read();
    std::vector<int> w(m + 1);
    for(int i = 1; i <= m; ++i) w[i] = read();

    struct Edge {int v; ll c;};
    std::vector<std::vector<Edge>> adj(m + 1);
    for(int i = 0; i < n; ++i){
        adj[Y[i]].push_back({X[i], C[i]});
    }
    const ll inf = 2e18;
    std::vector<bool> vis(m + 1);
    std::vector<ll> d(m + 1, inf);
    std::priority_queue<std::pair<ll, int>> q;

    for(int i = 1; i <= m; ++i){
        if(!w[i]) d[i] = 0, q.push({0, i});
    }

    while(q.size()){
        int x = q.top().second; q.pop();
        if(vis[x]) continue;
        vis[x] = 1;
        for(auto& [y, c] : adj[x]){
            if(d[y] > d[x] + c){
                d[y] = d[x] + c;
                q.push({-d[y], y});
            }
        }
    }

    ll ans = 0;
    for(int i = 1; i <= m; ++i){
        if(w[i] == 2){
            if(d[i] == inf) return puts("-1"), void();
            ans += d[i];
        }
    }
    printf("%lld\n", ans);
}

G. Ancient Go

模拟题，没啥好说的。

注意数气的时候别对同一个位置重复计数即可。

AC Code:

const int move1[4] = {0, 0, 1, -1};
const int move2[4] = {1, -1, 0, 0};

void solve(){
    std::vector<std::string> board(9);
    for(auto& x: board) std::cin >> x;
    std::vector<std::vector<int>> vis(9, std::vector<int>(9));
    std::vector<std::vector<int>> tmp(9, std::vector<int>(9)); 

    // 判断是否有气
    auto chk = [&](int x, int y) -> bool {
        if(x < 0 or x > 8 or y < 0 or y > 8) return false;
        // 数过了
        if(tmp[x][y]) return false;
        return board[x][y] == '.';
    };

    // 数连通块的气
    auto count = [&](auto&& self, int x, int y, int& cnt) -> void {
        if(vis[x][y]) return;
        vis[x][y] = 1;
        for(int i = 0; i < 4; ++i){
            int nx = x + move1[i], ny = y + move2[i];
            if(chk(nx, ny)) tmp[nx][ny] = 1, ++cnt;
        }
        for(int i = 0; i < 4; ++i){
            int nx = x + move1[i], ny = y + move2[i];
            if(nx >= 0 and nx <= 8 and ny >= 0 and ny <= 8 and board[nx][ny] == 'o'){
                self(self, nx, ny, cnt);
            }
        }
    };

    for(int i = 0; i < 9; ++i){
        for(int j = 0; j < 9; ++j){
            if(board[i][j] != 'o' or vis[i][j]) continue;
            int cnt = 0;
            tmp.assign(9, std::vector<int>(9, 0));
            count(count, i, j, cnt);
            if(cnt == 1) return puts("Can kill in one move!!!"), void();
        }
    }
    puts("Can not kill in one move!!!");
}

H. Sudoku

题意：

求解的数独，保证有解。

写这题的时候犯了不少唐，一开始以为的爆搜能过，无脑写了个爆搜交上去 T 了，然后改用 bitmask 优化，结果 WA 了两发，回去读题才发现我只判了行和列，没判宫格…

AC Code:

void solve(){
    std::vector<std::string> board(4);
    for(auto& x : board) std::cin >> x;

    std::vector<int> rm(4), cm(4), bm(4);
    for(int i = 0; i < 4; ++i){
        for(int j = 0; j < 4; ++j){
            if(board[i][j] == '*') continue;
            int bit = board[i][j] - '1';
            rm[i] |= (1 << bit);
            cm[j] |= (1 << bit);
            bm[(i >> 1 << 1) + (j >> 1)] |= (1 << bit);
        }
    }

    auto print = [&]() -> void {
        puts("");
        for(auto& x : board) std::cout << x << '\n';
    };

    bool flag = false;

    auto dfs = [&](auto&& self, int x, int y) -> void {
       // printf("x = %d, y = %d\n", x, y);
        if(x == 4) return true;
        int nx = x, ny = y + 1;
        if(ny == 4) ++nx, ny = 0;
        if(board[x][y] != '*') return self(self, nx, ny);
        for(int i = 0; i < 4; ++i){
            if((rm[x] >> i) & 1) continue;
            if((cm[y] >> i) & 1) continue;
            if((bm[(x >> 1 << 1) + (y >> 1)] >> i) & 1) continue;
            int pr = rm[x], pc = cm[y];
            rm[x] |= (1 << i);
            cm[y] |= (1 << i);
            board[x][y] = i + '1';
            if(self(self, nx, ny)) return true;
            board[x][y] = '*';
            rm[x] = pr;
            cm[y] = pc;
        }
        return false;
    };
    dfs(dfs, 0, 0);
    print();
}

K. Game Rooms

题意：

一栋() 层大楼，每一层只能设立一种游戏室：T 或 P。每层楼有名想去的员工和名想去的员工（）。整栋大楼里必须至少有一间 T 室和一间 P 室。

安排每一层的游戏室类型，使得所有员工的距离（到最近游戏室的楼层差）总和最小。求最小距离总和。

很容易想到 DP。

游戏室的分配，可以视为若干个连续的 T 段和 P 段的组成。

设表示处理完前层，且第层是 T/P 连续段的最后一个楼层（即层和层不同）的最小总代价。

然后，再枚举上一个与第层类型不同的游戏室的最后一个楼层，也就是为完整的一个连续段，然后统计这个连续段的最小总代价。

代价如何计算？令，的人去第层，的人去第层，分别统计代价即可。

为了求代价，需要预处理前缀和（人数的前缀和、人数坐标的前缀和）。

还有一个细节，题目要求至少有一间 T 室和一间 P 室，所以，当为最后一层时，从开始枚举，否则从（代表不存在）开始枚举。

时间复杂度。

AC Code:

void solve(){
    int n = read();
    struct X {ll Tcnt, Pcnt;};
    std::vector<X> a(n + 1);
    for(int i = 1; i <= n; ++i){
        a[i].Tcnt = read();
        a[i].Pcnt = read();
    }
    std::vector<ll> sumT(n + 1), sumP(n + 1), sumIT(n + 1), sumIP(n + 1);
    for(int i = 1; i <=n; ++i){
        sumT[i] = sumT[i - 1] + a[i].Tcnt;
        sumP[i] = sumP[i - 1] + a[i].Pcnt;
        sumIT[i] = sumIT[i - 1] + i * a[i].Tcnt;
        sumIP[i] = sumIP[i - 1] + i * a[i].Pcnt;
    }
    std::vector<std::vector<ll>> dp(n + 1, std::vector<ll>(2, 2e18));
    dp[0][0] = dp[0][1] = 0;

    auto get_cost = [&](int type, int iL, int iR) -> ll {
        int L = iL + 1, R = iR - 1;
        if(L > R) return 0;
        std::vector<ll>& sum = type ? sumP : sumT;
        std::vector<ll>& sumI = type ? sumIP : sumIT;
        if(!iL) return iR * (sum[R] - sum[L - 1]) - (sumI[R] - sumI[L - 1]);
        if(iR > n) return (sumI[R] - sumI[L - 1]) - iL * (sum[R] - sum[L - 1]);
        int mid = (L + R) >> 1;
        ll tot = 0;
        // [L, mid]
        tot += (sumI[mid] - sumI[L - 1]) - iL * (sum[mid] - sum[L - 1]);
        // [mid + 1, R]
        tot += iR * (sum[R] - sum[mid]) - (sumI[R] - sumI[mid]);
        return tot;
    };

    for(int i = 1; i <= n; ++i){
        int start = (i == n) ? 1 : 0;
        for(int j = start; j < i; ++j){
            ll cost = get_cost(0, j, i + 1);
            dp[i][0] = std::min(dp[i][0], dp[j][1] + cost);
        }
        for(int j = start; j < i; ++j){
            ll cost = get_cost(1, j, i + 1);
            dp[i][1] = std::min(dp[i][1], dp[j][0] + cost);
        }
    }
    printf("%lld\n", std::min(dp[n][0], dp[n][1]));
}

L. Huatuo’s Medicine

题意：签到。

写得很快啊，连样例都没测就交，然后就吃了发罚时，大悲啊。

AC Code:

void solve(){
    printf("%d\n", (read() << 1) - 1);
}
  • 标题: CCPC 2015 个人题解
  • 作者: Coast23
  • 创建于 : 2026-02-03 20:56:53
  • 更新于 : 2026-02-10 21:51:27
  • 链接: https://coast23.github.io/2026/02/03/CCPC-2015-个人题解/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
CCPC 2015 个人题解
  1. A. Secrete Master Plan
  2. C. The Battle of Chibi
  3. D. Pick The Sticks
  4. E. Ba Gua Zhen
  5. F. The Battle of Guandu
  6. G. Ancient Go
  7. H. Sudoku
  8. K. Game Rooms
  9. L. Huatuo’s Medicine