8.16总结

今天心情愉悦，又是AK的一天。

考试题目

T1 : Hyperset

这题本质是 SET 卡牌合法三元组计数。

给定 n 张互不相同的卡片，每张有 k 个位置，每个位置是 S/E/T。三张卡合法的条件是：对每一位来说，三个字符要么全相同，要么刚好是 S/E/T 各一个。

核心思路：

任意确定两张卡 a 和 b，如果它们想和第三张卡组成合法集合，那么第三张卡 t 是唯一确定的：

• 如果 a[i] == b[i]，那么 t[i] 必须也等于这个字符；
• 如果 a[i] != b[i]，那么 t[i] 必须是 S/E/T 中剩下的那个字符。

因此可以枚举前两张卡，构造出唯一需要的第三张卡，然后用 unordered_set 判断它是否存在。

复杂度：

• 枚举两张卡：O(n^2)
• 每次构造第三张卡：O(k)
• 总复杂度：O(n^2 k)
• 空间复杂度：O(nk)

代码中 get_goal(a, b) 就是在构造这张唯一的第三张卡。

注意最后答案要除以 3：

一个合法三元组 {A, B, C} 会在枚举两两组合时被统计三次：

• 枚举 A, B 找到 C
• 枚举 A, C 找到 B
• 枚举 B, C 找到 A

所以最终输出 cnt / 3。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
unordered_set <string> st;
vector <string> c;
string get_goal (const string& a, const string& b) {
    string res;
    for (int i = 0; i < k; i++) {
        char ca = a[i], cb = b[i];
        if (ca == cb) res += ca;
        else {
            if(ca != 'S' && cb != 'S') res += 'S';
            else if (ca != 'E' && cb != 'E') res += 'E';
            else res += 'T';
        }
    }
    return res;
}
int main () {
    scanf ("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        c.push_back (s);
        st.insert (s);
    }
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            string t = get_goal (c[i], c[j]);
            if (st.count (t)) cnt ++;
        }
    }
    printf ("%lld", cnt / 3);
    return 0;
}

T2 : Social Network

题可以理解成：每个前缀条件下，用并查集找出“必须连在一起的人群”，再用多余的介绍次数尽量扩大最大连通块。

核心思想：

对于前 i 个条件，把每个条件 (x, y) 看成要求 x 和 y 必须在同一个连通块里。用并查集合并这些关系后，可以得到若干个必须连通的集合。

如果一个集合大小是 s，要让这 s 个人连通，至少需要 s - 1 次介绍。

所以当前所有必须满足的连通关系，最少需要：

need = Σ(size - 1)

但题目要求 恰好进行 i 次介绍，所以剩下的多余介绍次数是：

sheng = i - need

这些多余介绍可以用来连接原本没有强制要求连通的不同集合。为了让某个人认识的人最多，就应该把最大的集合和其他较大的集合优先合并。

因此做法是：

1. 对前 i 个条件重新建并查集；
2. 得到所有连通块大小 b；
3. 计算满足条件所需的最少边数 need；
4. 多余边数 sheng = i - need；
5. 将连通块大小从大到小排序；
6. 用 sheng 次机会，把最大的连通块和后面最大的几个连通块合并；
7. 最大连通块大小为 maxn，答案是 maxn - 1，因为不能算自己。

代码里的关键部分：

int need = 0;
for (int s : b) need += s - 1;
int sheng = i - need;

这里 need 是当前条件必须消耗的最少介绍次数，sheng 是可以自由利用的额外介绍次数。

然后：

sort(b.rbegin(), b.rend());
int maxn = b[0];
for (int j = 1; j < (int)b.size() && sheng > 0; j++) {
    maxn += b[j];
    sheng--;
}
printf("%d\n", maxn - 1);

表示把最大的连通块不断和其他最大的连通块合并，从而最大化某个人能联系到的人数。

复杂度方面，这份代码每次都重新处理前缀：

• 外层枚举 i：O(d)
• 每次并查集合并最多 O(d)
• 排序连通块最多 O(n log n)

总复杂度大约是：$O(d * (d + n log n))$

由于 n, d ≤ 1000，完全可以通过。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
const ll INF = 1e18;
int n;
ll dist[N][N], res[N];
int x[N], idx[N];
int main () {
	scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) scanf ("%lld", &dist[i][j]);
    }
    for (int i = 1; i <= n; i++) scanf ("%d", &x[i]);
    for (int i = 1; i <= n; i++) idx[x[i]] = n - i + 1;
    vector <ll> ans;
    for (int id = 1; id <= n; id++) {
        int k = x[n - id + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) 
                dist[i][j] = min (dist[i][j], dist[i][k] + dist[k][j]);
        }
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            if (idx[i] > id) continue;
            for  (int j = 1; j <= n; j++) {
                if (idx[j] > id) continue;
                sum += dist[i][j];
            }
        }
        ans.push_back (sum);
    }
    reverse (ans.begin (), ans.end ());
    for (int i = 0; i < (int) ans.size (); i++) printf ("%lld ", ans[i]);
	return 0;
}

T3 : Greg and Graph

这题是经典的 反向加点 Floyd。

题目按顺序删除点 x1, x2, ..., xn，但直接模拟删除很难维护最短路。反过来看：删除顺序的逆序就是加点顺序。

也就是说：

删除：x1, x2, x3, ..., xn
加点：xn, ..., x3, x2, x1

当反向加入一个点 k时，就允许最短路经过这个新点k，于是可以用 Floyd 的一次中转更新。

每加入一个点后，只统计当前已经加入的点之间的最短路总和。

复杂度：

• Floyd 更新每次 O(n^2)，一共 n 次；
• 总复杂度 O(n^3)；
• 空间复杂度 O(n^2)。

n ≤ 500，O(n^3) 可以接受。

这份代码的关键思想就是：删点不好维护，反过来加点；每加一个点，就用它做 Floyd 中转点更新最短路。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
const ll INF = 1e18;
int n;
ll dist[N][N], res[N];
int x[N], idx[N];
int main () {
	scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) scanf ("%lld", &dist[i][j]);
    }
    for (int i = 1; i <= n; i++) scanf ("%d", &x[i]);
    for (int i = 1; i <= n; i++) idx[x[i]] = n - i + 1;
    vector <ll> ans;
    for (int id = 1; id <= n; id++) {
        int k = x[n - id + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) 
                dist[i][j] = min (dist[i][j], dist[i][k] + dist[k][j]);
        }
        ll sum = 0;
        for (int i = 1; i <= n; i++) {
            if (idx[i] > id) continue;
            for  (int j = 1; j <= n; j++) {
                if (idx[j] > id) continue;
                sum += dist[i][j];
            }
        }
        ans.push_back (sum);
    }
    reverse (ans.begin (), ans.end ());
    for (int i = 0; i < (int) ans.size (); i++) printf ("%lld ", ans[i]);
	return 0;
}

T4 : The Sports Festival

核心思路

先将所有速度从小到大排序。

设排序后的数组为：s[1] <= s[2] <= ... <= s[n]

对于任意一种出场顺序，当前已经出场的人在排序数组中可以看成某个区间逐渐扩展。因为当前不协调度只和已经出场速度的最大值、最小值有关。

因此可以使用 区间 DP。

---

状态定义

dp[l][r]

表示当前已经选择了排序后区间 [l, r] 内的所有参赛者时，能够得到的最小不协调度总和。

---

初始状态

当区间长度为 1 时，只有一个人出场：dp[i][i] = 0

因为最大值等于最小值，不协调度为 0。

---

状态转移

对于区间 [l, r]，最后加入的人只可能是左端点 s[l] 或右端点 s[r]。

所以：dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + (s[r] - s[l]);

其中：s[r] - s[l]

表示当前区间 [l, r] 的不协调度。

---

最终答案

dp[1][n]

表示所有参赛者都已经出场时，最小的不协调度总和。

---

复杂度分析

• 排序复杂度：O(n log n)
• DP 状态数：O(n^2)
• 每个状态转移：O(1)

总时间复杂度：$O(n^2)$

空间复杂度：$O(n^2)$

T5 : Dijkstra?

这道题目其实是一道很裸的dijk，所以就不用讲了

T6 : Zuma

核心思路

这是一道经典的 区间 DP。

每次可以删除一个连续回文子段，要求删除完整个序列的最少秒数。

由于操作对象是连续区间，并且删除后两侧会拼接，所以可以用区间 DP 来描述一段宝石被完全删除的最优答案。

---

状态定义

设：$dp[l][r]$

表示删除区间 [l, r] 内所有宝石所需的最少秒数。

---

初始状态

单个宝石本身就是回文，因此：$dp[i][i] = 1$

---

状态转移

1. 两端颜色相同

如果：$c[l] = c[r]$

那么两端宝石可以和中间区间的某次删除合并在一起。

因此：$dp[l][r] = dp[l + 1][r - 1]$

特殊地，当区间长度为 2 时：$dp[l][r] = 1$

---

2. 枚举断点拆分区间

也可以把区间 [l, r] 分成两段分别删除：

$[l, k], [k + 1, r]$

状态转移为：

$dp[l][r] = \min(dp[l][r], dp[l][k] + dp[k + 1][r])$

其中：

$l \le k < r$

---

最终答案

$dp[1][n]dp[1][n]dp[1][n]dp[1][n]$

表示删除整个宝石序列所需的最少秒数。

---

复杂度分析

区间总数为：$O(n^2)$

每个区间枚举断点，复杂度为：$O(n)$

所以总时间复杂度为：$O(n^3)$

空间复杂度为：$O(n^2)$

---

一句话总结

这题使用 区间 DP，令 dp[l][r] 表示删除区间 [l, r] 的最少次数；如果 c[l] == c[r]，两端可以并入中间的某次回文删除，否则枚举断点拆分区间。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
const int INF = 0x3f3f3f3f;
int c[N];
int dp[N][N];
int n;
int main () {
	scanf ("%d", &n);
    for (int i = 1; i <= n; i++) scanf ("%d", &c[i]);
    for (int i = 1; i <= n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            dp[l][r] = INF;
            if (c[l] == c[r]) {
                if (len == 2) dp[l][r] = 1;
                else dp[l][r] = dp[l + 1][r - 1];
            }
            for (int k = l; k < r; k++) dp[l][r] = min (dp[l][r], dp[l][k] + dp[k + 1][r]);
        }
    }
    printf ("%d\n", dp[1][n]);
	return 0;
}