[ABC268D] Unique Username Solution

更好的阅读体验戳此进入

题面

给定 $n$$n$ 各字符串，另外给定 $m$$m$ 个字符串。你需要对 $n$$n$ 个字符串进行排列，并在每相邻两个字符串中间插入至少一个下划线，并且最终字符串与给定的 $m$$m$ 个字符串均不同。输出任意一个长度在 $[3,16]$$[3, 16]$ 的方案。

Solution

第一眼没什么想法，看了一眼数据范围才反应过来这似乎就是个暴力，我们尝试分析一下：

令 $n$$n$ 个字符串总长度和为 $s$$s$，我们还要至少插入 $n-1$$n - 1$ 个下划线，那么剩下的可能长度就只有 $16-s-(n-1)=17-n-s$$16 - s - (n - 1) = 17 - n - s$，同时显然 $s\ge n$$s \ge n$。对于剩下的长度不难发现可以认为其是将下划线可空地放入 $n-1$$n - 1$ 个不同盒子里，显然这就是 $17-n-s$$17 - n - s$ 个可空的不同球盒问题。关于球盒问题可以去看我的 Blog：浅析排列组合、斯特林数、贝尔数、二项式定理与推论及其反演、子集反演、广义容斥。再加上枚举全排列的 $n!$$n!$，最终的复杂度大约是：

化简一下：

这一大坨东西我不知道我是否分析错了，不过大概也八九不离十，总之这个东西我们随便带入几个 $n$$n$ 算一下，或者感性理解一下发现显然是远小于 $1e8$$1e8$ 的，所以暴力即可通过。

做法的话先通过调用 $n!$$n!$ 次 next_permutation() 函数枚举全排列，此时还会多一个 $O(n)$$O(n)$ 的常数，不过区别不大。

然后每次跑一遍深搜，用 string 的本质是 basic_string，且 basic_string 支持 + 和 += 等的特性，即可十分便捷地实现一般的深搜思路，注意每两个之间至少插入一个下划线，且注意需要限制最多额外添加 $17-n-s$$17 - n - s$ 个下划线，否则复杂度是不正确的。

Code

xxxxxxxxxx
71
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N, M;
26
int mx(-1);
27
string S[10];
28
unordered_set < string > block;
29
string ans;
30

31
void dfs(int dep = 1, int lft = mx, string cur = string()){
32
    if(dep > N){
33
        if(3 <= (int)cur.length() && (int)cur.length() <= 16 && block.find(cur) == block.end())ans = cur;
34
        return;
35
    }
36
    if(dep == 1)return dfs(dep + 1, lft, cur + S[dep]);
37
    dfs(dep + 1, lft, cur + "_" + S[dep]);
38
    for(int i = 1; i <= lft; ++i)
39
        cur += "_", dfs(dep + 1, lft - i, cur + "_" + S[dep]);
40
}
41

42
int main(){
43
    N = read(), M = read();
44
    int slen(0);
45
    for(int i = 1; i <= N; ++i)cin >> S[i], slen += S[i].length();
46
    for(int i = 1; i <= M; ++i){string T; cin >> T; block.insert(T);}
47
    mx = 16 - slen - N + 1;
48
    if(mx < 0)printf("-1\n"), exit(0);
49
    int tot(1); for(int i = 1; i <= N; ++i)tot *= i;
50
    for(int i = 1; i <= tot; ++i)dfs(), next_permutation(S + 1, S + N + 1);
51
    if(ans.empty())printf("-1\n"), exit(0);
52
    cout << ans << endl;
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

UPD

update-2023_01_18 初稿