外观
Skip to content 查看源代码：
查看源代码：
blue-problems-20250815.md
---
title: 三道蓝题
createTime: 2025/8/15
categories:
- IT
tags:
- OI
---
## [P7876 「SWTR-7」Scores（hard version）](https://www.luogu.com.cn/problem/P7876)
这是一个构造 $n$ 维偏序的问题。
容易想到，利用“吊打”的关系做拓扑排序。
由于给出了“如果 $i,j$ 被同一个人吊打，或同时吊打同一个人，则他们之间也有一方被另一方吊打”的限制，在一个弱连通块（此题中也为半连通块）内，这个拓扑序总是唯一的。
而在弱连通块之间，并无偏序关系。
如何处理？以二维情况举例：我们不妨设一个连通块内的分数在平面上围成了一块正方形区域，那么要让不同连通块无偏序关系，只需要使这些正方形区域自左上到右下任意轴不交地排布即可。如下图：
至于其他的维度，只需令它们等于某一维度即可。如此则不会破坏原有的偏序关系。
时间复杂度 $O(n^2)$。
## [P8250 交友问题](https://www.luogu.com.cn/problem/P8250)
问题即为“求 $u$ 的所有相邻节点中，不是 $v$ 且不与 $v$ 相邻的数量”
询问是不是邻居可以用 `unordered_set` 做到 $O(1)$，但这样单次询问仍然是 $O(\operatorname{deg}(u))$的，显然可以被菊花图卡爆.
转化问题为求
$$
\operatorname{deg}(u) - |\operatorname{neibor}(u) \cap \operatorname{neibor}(v)| - [(u, v) \in E]
$$
有进步，但第二项仍为 $O(\min\{\operatorname{deg}(u), \operatorname{deg}(v)\})$ 的，仍然可以被卡到单次 $O(n)$.
但是 $\operatorname{deg}(u)$ 和 $\operatorname{deg}(v)$ 都很大的情况是很稀有的，这是由于
$$
\sum_{v \in V} \operatorname{deg}(v) = 2m \Longrightarrow \#\bigl\{v \mid \operatorname{deg}(v) > T \bigr\} < \frac{2m}{T}.
$$
于是考虑对度数超过阈值 $T$ 的点单独处理。显然我们需要一种可以快速求交集的数据结构. 事实上 `bitset` 就可以，虽然是 $O\left(\dfrac{n}{w}\right)$ 的，但是常数极小.
考虑把所有度数大的点的相邻节点预处理成 `bitset`，这样整体的时间复杂度就为
$$
\frac{2m}{T} \cdot n + q_1 T + q_2\frac{n}{w} \xlongequal[T=O(\sqrt {m})]{m, n, q\text{ 同阶}} O\left( n\sqrt{n} + \frac{n^2}{w} \right)
$$
别看 $O\left( \dfrac{n^2}{w} \right)$ 很吓人，但是 `bitset` 是高度优化的，~~加上本题数据很水而且时间很松~~，T 不了.
## [P2753 [USACO4.3] 字母游戏 Letter Game](https://www.luogu.com.cn/problem/P2753)
老规矩，来看题解。
### 说明
$O(n^2)$ 的题解主要依赖于数据中输入的很多单词是无效的，但是这种性质并未在题面写明，~~加之此题是一道蓝题，正解不会这么简单~~，因此我认为 $O(n^2)$ 的做法并非此题的正解。
### 思路
首先，注意到 $3 \times 3 > 7$，于是词组最多可能有两个单词。一种朴素的思路是枚举词组的两个单词。
如何优化？我们不难发现：在判断最优性的时候，我们并不需要关心字母具体的排列，`cbac ef` 和 `abcc fe` 二者的价值是一样的。
因此，我们可以维护一个字母多重集到单词的映射，把字母数量相同的单词放到一起判断，优化循环。
### 复杂度分析
由于多重集 $S$ 的子集最多有 $2^{|S|}$ 个，这个算法的时间复杂度是 $O(2^{2|c|} + a \log a)$，
其中 $|c|$ 是卡片的个数，$a$ 是答案的个数。
后面一项是因为此算法不保证答案有序（毕竟我们都不关心字母的具体排列了），还要对答案排一次序。
不过由于常数问题，在本题的数据下，只优化一重循环的 $O(n \cdot 2^{|c|} + a \log a)$ 的做法与优化两重循环的做法时间相差无几（甚至最优解是只优化一重循环的），在后面我会同时贴出。
### 状态压缩优化
更进一步地，对字符进行离散化，映射到 $0 \sim 7$，此时可以发现字母多重集可以压缩成一个 `unsigned long long`，这样建立映射的常数可以小一些。~~这么小的数据范围不状压可惜了。~~
截至我写这篇题解时，此算法仍是最优解。
### 代码
:::details 优化一重循环
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned char ui8;
typedef unsigned long long char_multiset; // 离散化之后的字符多重集可以状压
#define split(cms) ((ui8*)&(cms))
const int maxc=8, maxn=4e4+100;
int varr[26] = {
2, 5, 4, 4, 1, 6, 5, 5,
1, 7, 6, 3, 5, 2, 3, 5,
7, 2, 1, 2, 4, 6, 6, 7, 5, 7
};
int charmap[256]; // 字符离散化
int valmap[maxc];
char limits[maxc]; // 卡片限制
char words[maxn][8];
struct node {
int value;
vector<int> idx;
};
unordered_map<char_multiset, node> mp;
pair<int, int> ans[200000];
int maxval = 0, anscnt = 0;
inline int value(char_multiset cms) {
int ans = 0;
for (int i=0; i<8; i++) {
ans += valmap[i] * split(cms)[i];
}
return ans;
}
inline char_multiset to_cms(char *s) {
char_multiset ans=0ll;
for (; *s!=0; s++) {
if (charmap[*s] == -1) {
return 0;
}
split(ans)[charmap[*s]]++;
}
return ans;
}
inline bool check(char_multiset cms) {
for (int i=0; i<8; i++) {
if (split(cms)[i] > limits[i]) {
return false;
}
}
return true;
}
inline bool check2(char_multiset cms1, char_multiset cms2) {
for (int i=0; i<8; i++) {
if (split(cms1)[i] + split(cms2)[i] > limits[i]) {
return false;
}
}
return true;
}
inline void upd_maxval(int val) {
if (val > maxval) {
maxval = val;
anscnt = 0;
}
}
inline void add_ans(int i1, int i2) {
anscnt++;
ans[anscnt] = {i1, i2};
}
// 调试专用
inline void print(char_multiset cms) {
putchar('{');
for (int i=0; i<8; i++) {
printf("%d%s", split(cms)[i], i==7?"}":", ");
}
}
// 为了抢最优解写的快读
inline bool read(char *s){
char c = getchar();
while (c=='\n' || c=='\r') {
c = getchar();
}
if (c == '.') {
return false;
}
for (; c!='\n'&&c!='\r'; s++) {
*s = c;
c = getchar();
}
*s = '\0';
return true;
}
int main() {
char cards[8];
read(cards);
memset(charmap, -1, sizeof charmap);
int ccnt=0;
for (int i=0; cards[i]; i++) {
char c = cards[i];
if (charmap[c] == -1) {
charmap[c] = ccnt;
valmap[ccnt] = varr[c - 'a'];
ccnt++;
}
limits[charmap[c]]++;
}
int i=0;
while (true) {
i++;
if (!read(words[i])) {
break;
}
char_multiset cms = to_cms(words[i]);
if (!cms || !check(cms) {
// 超出卡片表示范围
continue;
}
int val = value(cms);
if (val >= maxval) {
upd_maxval(val);
add_ans(i, 0);
}
for (auto [cms2, no]: mp) {
if (check2(cms, cms2) && val+no.value>=maxval) {
upd_maxval(val + no.value);
for (int j: no.idx) {
add_ans(j, i);
}
}
}
mp[cms].value = val;
mp[cms].idx.push_back(i);
}
sort(ans + 1, ans + 1 + anscnt); // 这个算法不能保证答案有序
printf("%d\n", maxval);
for (int i=1; i<=anscnt; i++) {
printf("%s %s\n", words[ans[i].first], words[ans[i].second]);
// 尾部空格不会影响测评机判断，因此 ans[i][2]==0 也能工作
}
return 0;
}
```
:::
:::details 优化两重循环
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef unsigned char ui8;
typedef unsigned long long char_multiset; // 离散化之后的字符多重集可以状压
#define split(cms) ((ui8*)&(cms))
const int maxc=8, maxn=4e4+100;
int varr[26] = {
2, 5, 4, 4, 1, 6, 5, 5,
1, 7, 6, 3, 5, 2, 3, 5,
7, 2, 1, 2, 4, 6, 6, 7, 5, 7
};
int charmap[256]; // 字符离散化
int valmap[maxc];
char limits[maxc]; // 卡片限制
char words[maxn][8];
struct node {
int value;
vector<int> idx;
};
map<char_multiset, node> mp; // 甚至比 unordered 快（unordered 由于无序，在 i==j 时退出是危险的）
pair<int, int> ans[200000];
int maxval = 0, anscnt = 0;
inline int value(char_multiset cms) {
int ans = 0;
for (int i=0; i<8; i++) {
ans += valmap[i] * split(cms)[i];
}
return ans;
}
inline char_multiset to_cms(char *s) {
char_multiset ans=0ll;
for (; *s!=0; s++) {
if (charmap[*s] == -1) {
return 0;
}
split(ans)[charmap[*s]]++;
}
return ans;
}
inline bool check(char_multiset cms) {
for (int i=0; i<8; i++) {
if (split(cms)[i] > limits[i]) {
return false;
}
}
return true;
}
inline bool check2(char_multiset cms1, char_multiset cms2) {
for (int i=0; i<8; i++) {
if (split(cms1)[i] + split(cms2)[i] > limits[i]) {
return false;
}
}
return true;
}
inline void upd_maxval(int val) {
if (val > maxval) {
maxval = val;
anscnt = 0;
}
}
inline void add_ans(int i1, int i2) {
anscnt++;
ans[anscnt] = {i1, i2};
}
// 调试专用
inline void print(char_multiset cms) {
putchar('{');
for (int i=0; i<8; i++) {
printf("%d%s", split(cms)[i], i==7?"}":", ");
}
}
// 为了抢最优解写的快读
inline bool read(char *s){
char c = getchar();
while (c=='\n' || c=='\r') {
c = getchar();
}
if (c == '.') {
return false;
}
for (; c!='\n'&&c!='\r'; s++) {
*s = c;
c = getchar();
}
*s = '\0';
return true;
}
int main() {
char cards[8];
read(cards);
memset(charmap, -1, sizeof charmap);
int ccnt=0;
for (int i=0; cards[i]; i++) {
char c = cards[i];
if (charmap[c] == -1) {
charmap[c] = ccnt;
valmap[ccnt] = varr[c - 'a'];
ccnt++;
}
limits[charmap[c]]++;
}
int n = 0;
while (true) {
n++;
if (!read(words[n])) {
break;
}
char_multiset cms = to_cms(words[n]);
if (!cms || !check(cms)) {
// 超出卡片表示范围
continue;
}
int val = value(cms);
if (val >= maxval) {
upd_maxval(val);
add_ans(n, 0);
}
if (strlen(words[n]) <= 4) {
node &no = mp[cms];
no.value = val;
no.idx.push_back(n);
}
}
for (auto [cms1, no1]: mp) {
if (check2(cms1, cms1) && no1.value*2>=maxval) {
upd_maxval(no1.value*2);
for (int i: no1.idx) {
for (int j: no1.idx) {
if (i == j) { break; }
add_ans(j, i);
}
}
}
for (auto [cms2, no2]: mp) {
if (cms2 == cms1) {
break;
}
if (check2(cms1, cms2) && no1.value+no2.value>=maxval) {
upd_maxval(no1.value + no2.value);
for (int i: no1.idx) {
for (int j: no2.idx) {
if (i < j) {
add_ans(i, j);
} else {
add_ans(j, i);
}
}
}
}
}
}
sort(ans + 1, ans + 1 + anscnt); // 这个算法不能保证答案有序
printf("%d\n", maxval);
for (int i=1; i<=anscnt; i++) {
printf("%s %s\n", words[ans[i].first], words[ans[i].second]);
// 尾部空格不会影响测评机判断，因此 ans[i][2]==0 也能工作
}
return 0;
}
```
:::