标签：Username 下划线 string int 题解 ABC268D ret 字符串 define

[ABC268D] Unique Username Solution

目录

• [ABC268D] Unique Username Solution
  • 更好的阅读体验戳此进入
  • 题面
  • Solution
  • Code
  • UPD

更好的阅读体验戳此进入

题面

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

Solution

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

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

\[O(n! \sum_{i = 0}^{17 - n - s} \dfrac{(i - 1 + n - 1)!}{(n - 2)!(i - 1 + n - 1 - (n - 2))!}) \]

化简一下：

\[O(n! \sum_{i = 0}^{17 - n - s} \dfrac{(i + n - 2)!}{(n - 2)!i!}) \]

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

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

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

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N, M;
int mx(-1);
string S[10];
unordered_set < string > block;
string ans;

void dfs(int dep = 1, int lft = mx, string cur = string()){
    if(dep > N){
        if(3 <= (int)cur.length() && (int)cur.length() <= 16 && block.find(cur) == block.end())ans = cur;
        return;
    }
    if(dep == 1)return dfs(dep + 1, lft, cur + S[dep]);
    dfs(dep + 1, lft, cur + "_" + S[dep]);
    for(int i = 1; i <= lft; ++i)
        cur += "_", dfs(dep + 1, lft - i, cur + "_" + S[dep]);
}

int main(){
    N = read(), M = read();
    int slen(0);
    for(int i = 1; i <= N; ++i)cin >> S[i], slen += S[i].length();
    for(int i = 1; i <= M; ++i){string T; cin >> T; block.insert(T);}
    mx = 16 - slen - N + 1;
    if(mx < 0)printf("-1\n"), exit(0);
    int tot(1); for(int i = 1; i <= N; ++i)tot *= i;
    for(int i = 1; i <= tot; ++i)dfs(), next_permutation(S + 1, S + N + 1);
    if(ans.empty())printf("-1\n"), exit(0);
    cout << ans << endl;
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    int flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2023_01_18 初稿

标签：Username,下划线,string,int,题解,ABC268D,ret,字符串,define
From： https://www.cnblogs.com/tsawke/p/17124344.html