2024年上海市大学生程序设计竞赛 部分题解

kaederei7 · 2024-07-02 20:52:21 · 题解

附上cf的链接：

The 2024 Shanghai Collegiate Programming Contest

A. 无线网络整点栅格统计

题意

在 n × m 的区域{(x, y)|0 ≤ x ≤ n, 0 ≤ y ≤ m} 中，以任意一点 (a, b)为顶点最多能在区域中划出多少个顶点均为整数的正方形。

思路

数据量(1 ≤ n, m ≤ 100)，直接暴力

对正方形的每个询问顶点(a, b)，枚举对角顶点(c, d)

由已知的两点可得正方形的中点，根据另一条对角线与这条对角线垂直，得已知两点在x, y方向上的改变量与剩下两点在y，x方向上的改变量相同，可以算出剩下两个顶点的位置。

判断剩下两个顶点是否在区域内即可。

具体公式看代码

参考代码

void solve(){
    cin >> n >> m;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            for(int i2 = 0; i2 <= n; i2++){
                for(int j2 = 0; j2 <= m; j2++){
                    int del_i = i - i2, del_j = j - j2;
                    if((abs(del_i) + abs(del_j)) % 2 == 1 || (i == i2 && j == j2)) continue;
                    int x1 = (i + i2 + del_j) / 2, y1 = (j + j2 - del_i) / 2,
                        x2 = (i + i2 - del_j) / 2, y2 = (j + j2 + del_i) / 2;
                    if(x1 >= 0 && x1 <= n && x2 >= 0 && x2 <= n && y1 >= 0 && y1 <= m && y2 >= 0 && y2 <= m) a[i][j]++;
                }
            }
        }
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}

E. 无线软件日

题意

给定一个字符串，其中的字母最多能组合成几个单词 shanghai （大小写不敏感）

思路

签到题

把字符串转换成全小写再进行处理，统计目标字母的出现次数（s,h,a,n,g,i）取最小值

注意 h 和 a 的次数要除2

参考代码

void solve(){
    int n; cin >> n;
    string s; cin >> s;
    for(int i = 0; i < n; i++){
        if(s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a'; 
    }
    vector<int> cnt(128);
    int ans = 0;
    for(int i = 0; i < n; i++) cnt[s[i]]++;
    ans = min({cnt['a'] / 2, cnt['h'] / 2, cnt['s'], cnt['i'], cnt['g'], cnt['n']});
    cout << ans << endl;
}

G. 象棋大师

题意

小万和小宁在玩一种很新的象棋。

棋盘的大小是 n × n，棋子仅能在 {(a, b)|0 ≤ a, b ≤ n} 范围的整点上移动。 小万只有一只卒，位于起点 (0, 0) ，这只卒每次移动可以向 x 轴或 y 轴增大的方向移动。换言之，假设卒此刻位于 (x, y) 那么他下一步只能移动到 (x + 1, y) 或 (x, y + 1) 。

小宁有 m 只马，这些马的位置已知，马不能移动，但是一旦小万的卒进入到了小宁任何一只马的攻击范围时，小宁的卒会立即被吃掉。马的攻击范围与中国象棋规则相同，包含了“别马脚”的情况。

现在，小万希望将位于起点 (0, 0) 的卒，安全的移动到终点 (n, n) ，在这个过程中（包括起点和终点）不被任何一只马攻击到，请问他有多少种不同的走法？

注意到，小万可以在移动卒的过程中吃掉小宁的马。只要卒移动到小宁的马所在位置，这只马就会被吃掉。被吃掉的马不再能够攻击，并从棋盘上消失。

思路

P1002 [NOIP2002 普及组] 过河卒 的魔改版

在dp_{i,j}=dp_{i−1,j}+dp_{i,j−1} 的基础上考虑状压马的存活状态，并预处理 (i,j) 位置的马的攻击情况（有没有被攻击，如果有是否有别马脚的情况）

细节比较多，结合代码的注释应该是可以理解的

参考代码

int T,n,m,q,k, ma[M][M], xx[M], yy[M];
int a[M][M][15];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1}; //马脚的位置
int mx[] = {2, 2, 1, -1, -2, -2, -1, 1};
int my[] = {-1, 1, 2, 2, 1, -1, -2, -2};//马的攻击位置，枚举时与马脚的位置对应
int f[M][M][N];
void solve(){
    cin >> n >> m;
    for(int i = 0; i <= n + 1; i++){
        for(int j = 0; j <= n + 1; j++){
            ma[i][j] = -1;
            for(int s = 0; s < m; s++) a[i][j][s] = m; //初始化，代表该位置不是被某个马攻击的位置
        }
    }
    for(int i = 0; i < m; i++){
        int x, y; cin >> x >> y;
        x++; y++;
        ma[x][y] = i; 
        xx[i] = x; yy[i] = y;
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < 8; j++){
            int nx = xx[i] + mx[j], ny = yy[i] + my[j],
                jx = xx[i] + dx[j / 2], jy = yy[i] + dy[j / 2];
            if(nx > 0 && nx <= n + 1 && ny > 0 && ny <= n + 1){
                a[nx][ny][i] = ma[jx][jy];
              // 记录马的某个攻击位置是否存在堵马脚的情况，没有就是-1，反之记录对应堵马脚的马
            }
        }
    }
    f[1][1][0] = 1;
    // 初始状态，全0代表场上的马全活
    for(int i = 1; i <= n + 1; i++){
        for(int j = 1; j <= n + 1; j++){
            for(int s = 0; s < (1 << m); s++){
                bool flag = 0;
                for(int k = 0; k < m; k++){
                    int foot = a[i][j][k];
                    if((s >> k) & 1 == 1 || foot == m) continue;
                  //如果当前状态在这个位置进行攻击的马死了或者位置为空，就是安全的
                    if(foot == -1 || ((s >> foot) & 1) == 1){
                        flag = 1; break;
                    }
                  //如果在这个位置进行攻击的马存活，并且没有被堵马脚或者堵马脚的马死了，卒就被吃了
                }
                if(flag) f[i][j][s] = 0;
                else f[i][j][s] = (f[i][j][s] + f[i - 1][j][s] + f[i][j - 1][s]) % mod;
                if(ma[i][j] != -1 && ((s >> ma[i][j]) & 1) == 0){
                    f[i][j][s | (1 << ma[i][j])] = (f[i][j][s | (1 << ma[i][j])] + f[i][j][s]) % mod;
                    f[i][j][s] = 0;
                }
              // 吃了某个位置的马之后，马的存活状态转移，原状态作废
            }
        }
    }
    int ans = 0;
    for(int s = 0; s < (1 << m); s++) ans = (ans + f[n + 1][n + 1][s]) % mod;
    cout << ans << endl;
}

J. 极简合数序列

题意

对正整数数组a_1,a_2 · · · a_n，找到一个区间 [l, r] （其中 1 ≤ l ≤ r ≤ n ），使得从 a_l 到 a_r 的区间所有整数之和为一个合数，并且此区间两端的距离 r − l 达到最小

思路

答案只可能是 -1,0,1,2,3 中的一种

证明：

1.除2以外的偶数均为合数，任意两个偶数之和必为合数；

2.任意两个奇数之和为偶数；

3.奇数与偶数的和可当作奇数考虑

因此合数区间的长度存在上限，直接遍历判断即可

参考代码

bool check(int x){
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0) return false;
    }
    return true;
}
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int l = 0; l < 4; l++){
        for(int i = 1; i + l <= n; i++){
            int sum = 0;
            for(int j = i; j <= i + l; j++) sum += a[j];
            if(!check(sum)){
                cout << l << endl;
                return;
            }
        }
    }
    cout << "-1" << endl;
}

L. 扩散模型

题意

一棵以噪声隐表示为根的扩散树，N 为树上的结点数量。在无监督情况下，每一步去噪都会使隐表示从当前所在的结点随机移动到某个儿子结点上。在经过若干步去噪后，隐表示最终将到达某个叶子结点。保证扩散树上每个叶子结点的深度一致。

在这个问题中，我们会标记 K 个不同叶子结点，来表示我们想要隐表示到达的最终结点。然而，扩散模型去噪的随机性往往会导致其无法到达这些结点。

为了解决这个问题，有 M 个候选词，我们可以选择是否使用它们。当选用第 i 个候选词时，该候选词会作用于扩散树的结点 u_i 上，使得当隐表示位于 u_i 上时，会被确定性地去噪而移动到 u_i 的儿子结点 v_i 上。而对于未被候选词作用的结点，隐表示在上面时仍然会随机移动到一个儿子节点。特殊的，在选择候选词时，如果有两个候选词作用于同一结点上且均被选择，输入中靠前的候选词会覆盖靠后者的作用。

出于效率上的考量，我们希望选用尽可能少的候选词，使得隐表示从根节点出发最终一定能走到一个被标记的叶子结点。

思路

原题废话很多，不过读懂就知道本题是树形dp

用 dp(u, 0/1) 表示结点 u 的子树不能够/能够确保走到其一个子结点中的到达目标节点的最小消耗。

初始时有 dp[u_{标记}][0] = dp[u_{标记}][1]=0

考虑状态转移方程，节点 u 上如果没有候选词，u 一定能到达目标节点当且仅当其所有子节点 v 存在一种可达路径。否则 u 有概率走到不被标记的节点，无解。

因此其消耗由所有子节点 v 的到达目标节点的最小消耗决定，即 dp[u][0] = \sum_{v \in son(u)} min(dp[v][0],dp[v][1])

当节点 u 存在到达子节点 v 的候选词时，从节点 u 可确保到达节点 v ，则有 dp[u][1] = min(dp[u][1], dp[v][1] +1)

从根节点1出发遍历，时间复杂度 O(n)

参考代码

void solve(){
    cin >> n >> m >> k;
    vector<int> road(n + 1);
    vector<vector<int>> g(n + 1), dp(n + 1, vector<int>(2, INF));
    for(int i = 1; i <= n; i++){
        int k; cin >> k;
        for(int j = 1; j <= k; j++){
            int v; cin >> v;
            g[i].push_back(v);
        }
    }
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        road[v] = 1;
    }
    for(int i = 1; i <= k; i++){
        int t; cin >> t;
        dp[t][0] = dp[t][1] = 0;
    }
    auto dfs = [&] (auto self, int u) -> void{
        if(g[u].empty()) return;
        int sum = 0;
        for(auto v : g[u]){
            self(self, v);
            sum += min(dp[v][0], dp[v][1]);
            if(road[v]) dp[u][1] = min(dp[u][1], min(dp[v][0], dp[v][1]) + 1);
        }
        dp[u][0] = min(dp[u][0], sum);
    };
    dfs(dfs, 1);
    cout << (min(dp[1][0], dp[1][1]) == INF ? -1 : min(dp[1][0], dp[1][1])) << endl;
}

M. 不共戴天

题意

水面上依次排布着 n 片荷叶，编号为 1, 2, ..., n。

咪蛤有 m 种跳跃策略，第 i 种是从 a_i 号荷叶上跳到 b_i 号荷叶上，其中 a_i < b_i，a_i \ne a_j 且b_i \ne b_j（对i \ne j）。

小夜鹭有 m 种捕食策略，第 i 种是从 x_i 号荷叶旁飞到 y_i 号荷叶旁，其中 x_i < y_i，x_i \ne x_j 且 y_i \ne y_j（对i \ne j）。

如果存在两片荷叶 i \ne j，咪蛤可以从 i 经过一系列跳跃到达 j，小夜鹭也可以从 i 经过一系列飞跃到达