P7876 「SWTR-7」Scores（hard version）

这是一个构造 $n$ 维偏序的问题。

容易想到，利用“吊打”的关系做拓扑排序。

由于给出了“如果 $i,j$ 被同一个人吊打，或同时吊打同一个人，则他们之间也有一方被另一方吊打”的限制，在一个弱连通块（此题中也为半连通块）内，这个拓扑序总是唯一的。

而在弱连通块之间，并无偏序关系。

如何处理？以二维情况举例：我们不妨设一个连通块内的分数在平面上围成了一块正方形区域，那么要让不同连通块无偏序关系，只需要使这些正方形区域自左上到右下任意轴不交地排布即可。如下图：

至于其他的维度，只需令它们等于某一维度即可。如此则不会破坏原有的偏序关系。

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

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

老规矩，来看题解。

说明

$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，这样建立映射的常数可以小一些。这么小的数据范围不状压可惜了。

截至我写这篇题解时，此算法仍是最优解。

代码

优化一重循环

#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;
}

优化两重循环

#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;
}