2021-09-17 11:05 中国海洋大学 C++

关注

2021牛客暑期多校训练营10

A、Browser Games

题目大意

给出 $n(1\le n\le 10^5)$ 个字符串，你需要输出 $n$ 行。

对于第 $i$ 个字符串来说，你需要在 $1\to i$ 这些字符串里面分别找到一个前缀，并且满足这些前缀去重之后长度最小。

其次就是你曾经选择过的前缀不能做为前缀出现在 $i+1\to n$ 这些字符串里面。

卡了空间只允许 $O(n)$ 。

Solution

考点：字符串hash

如果是正序的话比较容易考虑到字典树，但是字典树 $O(26n)$ 的空间这题卡空间过不去。

我们倒序的思考，对于最后一个字符串，只需要考虑前 $1\to n$ 字符串里面第一个字符出现了几种就是答案了。

那么接下来如何处理加入的第 $n$ 个字符串。

我们把第 $n$ 个字符串的全部前缀都 $hash$ 出来，接下来去一个 $map$ 里面把相同的前缀出现过的下标全部找出来，并且让这些下标在的位置前缀长度 $+1$ 即可。然后处理完之后把第 $i$ 个字符串的前缀全部删掉，因为你已经有了它前缀 $+1$ 的新字符串了。

这样一路往前递推就可以在 $O(n)$ 的时间内完成这一系列操作。

const int N = 1e5 + 7, bas = 131;

ull p[N];
unordered_map<ull, vector<int>> mp;
int pos[N], ans[N];
string s[N];

int solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> s[i];
        pos[i] = 0;
        p[i] = s[i][0];
        mp[p[i]].push_back(i);
    }

    for (int i = n; i >= 1; --i) {
        ans[i] = mp.size();
        ull pre = 0;
        for (auto& c : s[i]) {
            pre = pre * bas + c;
            auto it = mp.find(pre);
            if (it == mp.end()) continue;

            for (auto& id : it->second) {
                if (id == i)    continue;
                ++pos[id];
                p[id] = p[id] * bas + s[id][pos[id]];
                mp[p[id]].push_back(id);
            }
            mp.erase(it);
        }
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << endl;
    }

    return 1;
}

F、Train Wreck

题目大意

给你一个长度为 $2·n$ 的出栈入栈序列，你现在有 $n$ 辆列车，第 $i$ 辆列车颜色为 $a_i$ ，你要让每次停留在栈中颜色排列是唯一的。问是否可行，如果可行输出进栈颜色方案。

Solution

考点：堆

我们可以把出栈入栈转换成一棵树来考虑，初始栈为空的时候假设我们有一个节点的树并且这个结点编号为 $1$ ，接下来入栈就是当前节点新开辟一个儿子，出栈就是回到父亲，一直这样操作一个合理的出栈入栈顺序就会生成 $n+1$ 个节点。我们要做的就是给生成的 $n$ 个节点打上颜色，让每个点到 $1$ 的路径上构成的颜色序列唯一。

那么就很明显，我们每次让任意一个节点它的儿子节点们颜色互不相同就可以了。

我们用 $bfs$ 的方式填颜色，把同层次的颜色先选上不一样 $sz[u]$ 种颜色，并且每种颜色减一后插回原来的序列中。

我们使用堆可以很好的维护上面的数据结构。

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define debug(x) cout << #x << ":" << x << '\n'
typedef tuple<int, int> tup;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF64 = 0x3f3f3f3f3f3f3f3f;

const int N = 2e6 + 7;
ll n, m;
int p[N];
char s[N];

// (()()()()()())


multiset<pai, greater<pai>> st;
vector<int> len[N];

int a[N];

int solve() {
    n = read();
    scanf("%s", s + 1);
    unordered_map<int, int> cnt;
    for (int i = 1; i <= n; ++i)    p[i] = read(), ++cnt[p[i]];

    for (int i = 1; i <= n; ++i) {
        if (cnt.count(i)) {
            st.insert({ cnt[i],i });
        }
    }

    int now = 0;
    for (int i = 1; i <= 2 * n; ++i) {
        if (s[i] == '(') {
            ++now;
            len[now].push_back(i);
        }
        else --now;
    }

    for (int i = 1; i <= n; ++i) {
        int sz = len[i].size();
        if (sz) {
            multiset<pai, greater<pai>> tmp;
            for (int j = 1; j <= sz; ++j) {
                if (st.empty()) {
                    puts("NO");
                    exit(0);
                }
                auto it = *st.begin();
                if (it.first == 0) {
                    puts("NO");
                    exit(0);
                }
                st.erase(st.find(it));
                tmp.insert(it);
            }
            for (auto& pos : len[i]) {
                auto it = *tmp.begin();
                a[pos] = it.second;
                tmp.erase(tmp.find(it));
                st.insert({ it.first - 1, it.second });
            }
        }
    }


    return 1;
}

signed main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        //solve();
        cout << (solve() ? "YES" : "NO") << endl;
        stack<int> stk;
        for (int i = 1; i <= 2 * n; ++i) {
            if (s[i] == '(')    print(a[i], 32);
        }
        puts("");
    }
    return 0;
}

G、Game of Death

题目大意

场上共有 $n$ 个人，现在每个人都会随机选择一个其他人开枪，并且成功命中其他人的概率为 $p=\frac{a}{b}$ 。

你需要输出场上留下 $0,1...n$ 个人的概率，分式对 $998244353$ 取模。

Solution

考点：子集反演+NTT

首先考虑状态设计，我们让 $f(S)$ 代表被击中的是集合 $S$ 的概率，我们让 $g(S)$ 代表被击中的是 $S$ 子集的概率。

所以我们可以得出 $g(S) = \sum\limits_{T\subset S}f(T)$ 。

接下来根据子集反演的公式，我们可以得出 $f(S)=\sum\limits_{T\subset S}(-1)^{|S|-|T|}g(T)$ 。

我们就把问题转变成求击中概率是 $S$ 子集的概率了，这个是比较好求的，如果我们假设 $q=1-p$ 代表开枪没打中人的概率。

$g(S)=(q+p*\frac{|S|-1}{n})^{|S|}*(q+p*\frac{|S|}{n})^{n-|S|}$

集合 $S$ 中的人只能开枪没打中或者打中了 $S$ 中除自己以外的某个人，由于每个人都是独立的，概率直接做乘法即可；对于 $S$ 集合外的人，他们只能开枪没打中或者打中了 $S$ 集合中的某个人，同样做出乘法就可以算到 $g(S)$ 。

然后又可以发现 $g(S)$ 和 $f(S)$ 只和集合大小有关和具体选择了那个集合没有关系。

所以我们假设 $F(x)$ 是被击中集合大小为 $x$ 的所有概率之和，那么他就是 $n-x$ 行的答案。

$F(x)=C_n^xf(x)=C_n^x\sum\limits_{i=0}^{x}(-1)^{x-i} C_x^ig(i)\\F(x)=C_n^xx!\sum\limits_{i=0}^x\frac{(-1)^{x-i}}{(x-i)!}\frac{g(i)}{i!}$

然后后面那个求和又可以转换成卷积的形式快速求解到，我们把 $x-i$ 看成 $j$ ，那么后面这个式子就变成了 $i+j=x$ 定值的多项式，直接让 $A_i=\frac{(-1)^i}{i!},B_i=\frac{g(i)}{i!}$ ，把 $A*B$ 就可以求解到后面的答案了。

const int N = 3e5 + 7; // 2^21

int n, a, b, p, q;
int jc[N], inv[N], G[N];

namespace NTT {
    int limit;
    vector<int> A, B, rev;
    inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
    inline int mul(int x, int y) { return 1ll * x * y % MOD; }
    int qpow(int x, int y) {
        int res = 1;
        for (; y; y >>= 1, x = mul(x, x)) if (y & 1) res = mul(res, x);
        return res;
    }
    void init() {
        int ed = n * 2, bit = -1;
        for (limit = 1; limit <= ed; limit <<= 1) ++bit;
        A.resize(limit); B.resize(limit); rev.resize(limit);
        for (int i = 0; i < limit; ++i)    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit);
    }
    void ntt(vector<int>& P, int op) {
        for (int i = 0; i < limit; ++i) {
            if (i < rev[i])swap(P[i], P[rev[i]]);
        }
        for (int mid = 1; mid < limit; mid <<= 1) {
            int euler = qpow(3, (MOD - 1) / (mid << 1));
            if (op < 0)    euler = qpow(euler, MOD - 2);
            for (int i = 0, pos = mid << 1; i < limit; i += pos) {
                int wk = 1;
                for (int j = 0; j < mid; ++j, wk = mul(wk, euler)) {
                    int x = P[i + j], y = mul(wk, P[i + j + mid]);
                    P[i + j] = add(x, y), P[i + j + mid] = add(x, MOD - y);
                }
            }
        }
        if (op > 0)    return;
        int inv = qpow(limit, MOD - 2);
        for (int i = 0; i < limit; ++i)    P[i] = mul(P[i], inv);
    }
    void work() {
        for (int i = 0; i <= n; ++i) A[i] = i & 1 ? MOD - inv[i] : inv[i];
        for (int i = 0; i <= n; ++i) B[i] = mul(G[i], inv[i]);
        ntt(A, 1), ntt(B, 1);
        for (int i = 0; i < limit; ++i)    A[i] = mul(A[i], B[i]);
        ntt(A, -1);
    }
}using namespace NTT;


void init(int n) {
    jc[0] = 1;
    for (int i = 1; i <= n; ++i) {
        jc[i] = mul(jc[i - 1], i);
    }
    inv[n] = qpow(jc[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) {
        inv[i] = mul(inv[i + 1], i + 1);
    }
}
int C(int n, int m) {
    return 1ll * jc[n] * inv[n - m] % MOD * inv[m] % MOD;
}

int solve() {
    n = read(), a = read(), b = read();

    init(n);
    p = mul(a, qpow(b, MOD - 2)); // 没打中概率
    q = (1 - p + MOD) % MOD; // 打中概率

    int tmp_inv = mul(inv[n - 1], jc[n - 2]);
    for (int i = 0; i <= n; ++i) {
        G[i] = mul(qpow(add(q, mul(mul(p, i - 1), tmp_inv)), i), qpow(add(q, mul(mul(p, i), tmp_inv)), n - i));
    }
    init(), work();
    for (int i = n; i >= 0; --i) {
        print(1ll * C(n, i) * A[i] % MOD * jc[i] % MOD);
    }

    return 1;
}

H、War of Inazuma (Easy Version)

题目大意

你要构造一个长度为 $2^n$ 的 $01$ 字符串，一个下标 $u$ 在和其他下标 $v$ 的二进制表示只有一个不相同的有一条边，和这个点直接相连的下标和 $u$ 同一种字符最多出现次数为 $\lceil\sqrt{n}\rceil$ 。

Solution

方法1.队列实现

我们让字符串最后一个为 $1$ ，它对应的下标就是一个二进制全为 $1$ 的 $2^n-1$ ，接下来和它相连的就是有一位为 $0$ 的二进制表示，把这些全部标成 $0$ 。这样一层一层往下用队列防止多次标记，用 $lowbit$ 去依次把某些位置变成 $u$ 相反的值。

ll n, m;
int p[N];
bool vis[N];

inline int lowbit(int x) { return x & (-x); }

int solve() {
    n = read();
    m = (1 << n) - 1;
    queue<int> pq;

    pq.push(m);
    p[m] = 1;

    while (pq.size()) {
        int now = pq.front();
        pq.pop();
        if (vis[now])   continue;
        vis[now] = 1;
        for (int x = now, y; x; x -= y) {
            y = lowbit(x);
            p[now ^ y] = !p[now];
            pq.push(now ^ y);
        }
    }
    for (int i = 0; i <= m; ++i) {
        printf("%d", p[i]);
    }

    return 1;
}

方法2.内置函数

我们把上面那种方法展开画图可以发现，二进制表示有 $0$ 个 $1$ 的在一层，有 $1$ 个 $1$ 的在一层，有 $2$ 个 $1$ 的在一层，所以我们直接按每个数二进制里面有多少个 $1$ 分类就行。

int solve() {
    n = read();
    m = (1 << n) - 1;

    for (int i = 0; i <= m; ++i) {
        putchar('0'+(__builtin_popcount(i) & 1));
    }

    return 1;
}

多校补题暂时告一段落了，度过了一个充实的暑假 $\\HappyEnd\ 2021.9.17$