2025“钉耙编程”中国大学生算法设计春季联赛（1）

1001 签到

确实签到题

void solve(){
    cin >> n >> name;
    int pos = 0;
    bool flag = false;
    for(int i = 1; i <= n; i ++){
        cin >> s;
        if(s == name){
            flag = true;
            pos = i;
        }
    }
    if(flag) cout << pos << '\n';
    else cout << -1 << '\n';
}

1002 船长

赛时看到这个数据范围很头疼，先说思路

记答案概率初始时候为 res = 1

• 当两个敌人相遇时，分别记两人的概率为 a, b，则进入下一轮的概率为(a + b) / 2
• 当自己提前与敌人相遇时，记碰到当前敌人的概率为a，为了能够继续走下去，那么答案需要乘以不碰到的概率，即 res = res * (1 - a)
• 那么答案总体上就是，我每碰到一个敌人，我都需要乘以不碰到他的概率，即 res = res * (1 - a) * (1 - b)…

至于怎么处理这个数据范围，那么就只能把他们的下表存到一个数组里然后模拟了，模拟方法：

1 最后一轮（输出概率）

1   2 第三轮（更新了状态后）

1  2  3  4 第二轮（更新了状态后）

1 2 3 4 5 6 7 8  第一轮

即我把每一个人的下标都除以2来判断下一轮是否相遇。方便起见，所有都初始为0下标开始

AC Code：

int ksm(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return ksm(x, MOD - 2);
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    k --; // 下标从 0 开始
    vector<int> enemy(m);
    vector<int> prob(m, 1);
    for(int i = 0; i < m; i ++){
        cin >> enemy[i];
        enemy[i] --;
    }
    sort(enemy.begin(), enemy.end());

    int res = 1;
    int inv2 = inv(2);

    while(n > 1){
        // 进入下一轮
        k >>= 1;
        vector<int> new_enemy;
        vector<int> new_prob;

        for(int i = 0; i < enemy.size(); i ++){
            int t = enemy[i] >> 1;
            if(k == t) res = res * (1 - prob[i] + MOD) % MOD; // 染染与敌人相遇
            else{
                if(t == (enemy[i + 1] >> 1) && i + 1 < enemy.size()){ // 两个敌人相遇
                    new_prob.push_back((prob[i] + prob[i + 1]) * inv2 % MOD);
                    i += 1; // 额外跳过一个敌人
                }
                else new_prob.push_back(prob[i] * inv2 % MOD);

                new_enemy.push_back(t);
            }
        }
        enemy = new_enemy;
        prob = new_prob;
        n = (n + 1) >> 1;
    }
    cout << res << '\n';
}

1005 航线

以dis[i][j][k]记录位于 (i, j)位置且驶入方向为 k 的距离，跑 dijkstra即可

int n, m;
struct Node{
    int x, y;
    int time;
    int dir;

    bool operator < (const Node & t) const{
        return time > t.time; // 小根堆
    }
};
// 右上左下
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};

void solve(){
    cin >> n >> m;
    vector<vector<int>> t(n + 1, vector<int>(m + 1, 0)); // 驶出花费时间
    vector<vector<int>> d(n + 1, vector<int>(m + 1, 0)); // 转向花费时间
    vector<vector<vector<int>>> dis(n + 1, vector<vector<int>>(m + 1, vector<int>(5, 1e18)));
    vector<vector<vector<bool>>> vis(n + 1, vector<vector<bool>>(m + 1, vector<bool>(5, false)));

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> t[i][j];

    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> d[i][j];

    priority_queue<Node> q; // 小根堆
    q.push({1, 1, 0, 0});
    dis[1][1][0] = 0;

    while(q.size()){
        auto now = q.top(); q.pop();
        int x = now.x, y = now.y, time = now.time, dir = now.dir;
        if(vis[x][y][dir]) continue;
        vis[x][y][dir] = true;

        for(int i = 0; i < 4; i ++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
            if(vis[nx][ny][i]) continue;
            if(dis[nx][ny][i] > dis[x][y][dir] + t[x][y] + (dir != i) * d[x][y]){
                dis[nx][ny][i] = dis[x][y][dir] + t[x][y] + (dir != i) * d[x][y];
                q.push({nx, ny, dis[nx][ny][i], i});
            }
        }
    }
    int res = min({dis[n][m][0], dis[n][m][1], dis[n][m][2]}) + d[n][m];
    res = min(res, dis[n][m][3]);
    cout << res + t[n][m] << '\n';
}

1006 密码

对每组方程的 u, v, w进行全排列求解，如果某个答案出现了 n 次，那就是解（这里注意三个数相等的时候直接一组判断输出即可）

int n;
int u[N], v[N], w[N];
map<int, int> mp;
set<int> num;

void cal(int a, int b, int c){
    if((c - b) % a == 0 && (c - b) / a >= 0){
        mp[(c - b) / a] ++;
        num.insert((c - b) / a);
    }
}

void solve(){
    mp.clear();
    num.clear();
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> u[i] >> v[i] >> w[i];
    int a, b, c;
    for(int i = 1; i <= n; i ++){
        a = u[i], b = v[i], c = w[i];
        cal(a, b, c);
        a = u[i], b = w[i], c = v[i];
        cal(a, b, c);
        a = v[i], b = u[i], c = w[i];
        cal(a, b, c);
        a = v[i], b = w[i], c = u[i];
        cal(a, b, c);
        a = w[i], b = u[i], c = v[i];
        cal(a, b, c);
        a = w[i], b = v[i], c = u[i];
        cal(a, b, c);
    }
    if(mp[0] == 6){
        cout << 0 << '\n';
        return;
    }
    for(auto t : num){
        if(mp[t] == n){
            cout << t << '\n';
            return;
        }
    }
}

1007 分配宝藏

• 当只有一个人的时候[0(船长), 1]，船长自己投同意票即可获胜
• 当有两个人时[0, 1, 2]，1 为了获得宝藏肯定会投反对票，如果他获胜了将会进入上面的状态拿到所有宝藏，这对 2 来说是没有好处的，因此船长可以贿赂给 2 一个金币
• 当有三个人时[0, 1, 2, 3]，船长为了获胜肯定会投自己一票，那么只需要贿赂一个人即可保全自己。对于 1，为了拿到宝藏肯定投反对票，这里假设 1 先获胜了，那么进入了上一个状态[1, 2, 3]，可以知道 2 无法获得金币，这对 2 来说是不利的，因此船长贿赂给 2 一个金币即可获胜
• 以此类推下去可以发现，当船长贿赂给编号是偶数的人一个金币时，自己就能获胜。那么答案就是求偶数位的等差数列

int n;

int ksm(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve(){
    cin >> n;
    int x = n / 2;
    cout << x * (x + 1) % MOD << '\n';
}