xcpc训练题记录第 1 卷

A. Type The Strings

来源：\(2021-2022\) 年度国际大学生程序设计竞赛第 \(10\) 届陕西省程序设计竞赛 \(C\) 题

备注：这题在 \(2024\) 湖北省 \(ICPC\) 省赛的热身赛上也见到了，然后不会，现在属于赛后补题目

题目大意：

• 给你 \(n\) 个字符串，然后首先需要找到一个字符串，将其打印在工作区，然后你要将这个字符串进行变换，使得所有字符串都出现至少一次，求最小的代价，其中：
  1. 打印一个字符串花费为 \(len_{s_i}\)。
  2. 复制一个字符串花费为 \(k\)。
  3. 从当前的序列的任意位置删除一个字符花费为 \(1\)。
  4. 从当前的序列的任意位置添加一个字符花费为 \(1\)。

思路：

• 首先，我们看 \(n\) 的范围，然后可以把时间复杂度控制到 \(10^8\) 以内。
• 然后我们发现，这个字符串的操作，两两之间互相转换的花费 \(w_i\) 为 \(len_{s_i} + len_{s_j} - 2 \times com_{s_i \& s_j}\)，其中 \(com_{s_i \& s_j}\) 表示字符 \(s_i\) 和字符串 \(s_j\) 的最长公共子序列的长度。
• 然后我们把它们的编号作为点，我们将 \(s_i\) 和 \(s_j\) 的花费 \(w_i\) 作为边权，我们建一个虚点，这个虚点到任意一个字符串的边权值就是字符串的长度(\(len_{s_i}\))，然后跑最小生成树，这里我写的 \(prim\)，其实也可以写 \(kruskal\) 算法，可以发现，通过最小生成树算法，我们可以遍历到所有的边，将所有的形态都转换出来。

时间复杂度：\(O(n^4)\)

constexpr int inf = 0x3f3f3f3f;

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k;
    std::cin >> n >> k;

    std::vector<std::string> s(n + 1);
    for (int i = 1; i <= n; i++) {
        int x;
        std::cin >> x >> s[i];
    }

    std::vector<std::vector<int>> G(110, std::vector<int>(110, inf));
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            auto LCS = [&](std::string a, std::string b) {
                std::vector<std::vector<int>> dp(a.size() + 1, std::vector<int>(b.size() + 1));
                for (int i = 1; i <= a.size(); i++) {
                    for (int j = 1; j <= b.size(); j++) {
                        dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
                        if (a[i - 1] == b[j - 1]) {
                            dp[i][j] = std::max(dp[i - 1][j - 1] + 1, dp[i][j]);
                        }
                    }
                }
                int li = a.size(), lj = b.size();
                G[i][j] = G[j][i] = 
                std::min(std::min({li, lj, k}) + li + lj - 2 * dp[a.size()][b.size()], G[i][j]);
            };
            LCS(s[i], s[j]);
        }
    }   

    for (int i = 1; i <= n; i++) {
        G[n + 1][i] = s[i].size();
    }

    std::vector<int> dist(n + 2, inf), vis(n + 2);
    dist[n + 1] = 0;
    std::function<int()> prim = [&]() {
        int res = 0;
        for (int i = 1; i <= n + 1; i++) {
            int t = -1;
            for (int j = 1; j <= n + 1; j++) {
                if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            if (i && dist[t] == inf) return inf;

            if (i) res += dist[t];
            vis[t] = true;

            for (int j = 1; j <= n; j++) dist[j] = std::min(dist[j], G[t][j]);
        }

        return res;
    };

    int t = prim();

    std::cout << t << "\n";

    return 0;
}

B. Countless Me

来源：第 \(49\) 届 \(ICPC\) 国际大学生程序设计竞赛邀请赛武汉站 - 正式赛

备注：赛后补题目

题目大意：

• 给你一个序列，你可以对其中任意一个数进行 \(+x\)，对另一个数进行 \(-x\)，即 \(\begin{cases}{} a_i := a_i + x \\ a_j := a_j - x \end{cases}\)​
• 最后求将这个序列的所有数或起来的最小值，即 \(ans = a_1 \space | \space a_2 \space | \space ... \space | \space a_n\)

思路：

• 怎么让一些数或起来的结果尽可能小，那么我们就需要尽可能的减少最高位的 \(1\)，同时，这里有一个很明显的结论：
  • 在 \(n\) 次操作里，我们每次操作两个数，对其加减任意 \(x\)，我们可以让序列里的数字变成任意数字
• 从高位向低位进行贪心，如果这一位构成的数，尽可能的减少最高位的 \(1\)
• 我们有了贪心的思路，还需要考虑一个特殊情况：当这个数组的和可以整除这一位时，我们要取一个 \(min\)，以保证最小。

时间复杂度：\(O(n)\)

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    i64 sum = 0;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        sum += x;
    }

    i64 ans = 0;
    for (int i = 29; i >= 0; i--) {
        if (((1LL << i) - 1) * n < sum) {
            ans |= 1LL << i;
            int t = std::min(1LL * n, sum >> i);
            sum -= 1LL * t * (1 << i);
        }
    }

    std::cout << ans << "\n";

    return 0;
}