.)所有题目思路+代码实现

感觉写的很详细了呢，喵。

update 1.24, [03:40] 赛时通过的题目。

update 1.24, [04:39] 赛时挂的M。

update 1.24, [07:45] I。

update 1.25, [13:02] L。

A题：一起奏响历史之音！

思路：

检查数组中是否存在 4 或者 7 即可。

代码：

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    bool flag = true;
    for (int i = 0; i < 7; i ++ ) {
        int a;
        std::cin >> a;

        if (a == 4 || a == 7) flag = false;
    }

    if (flag) {
        std::cout << "YES\n";
    }else {
        std::cout << "NO\n";
    }
    
    return 0;
}

B题：能去你家蹭口饭吃吗

思路：

$\operatorname{sort}$ 后输出中位数 $-1$ 。

代码：

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i ++ ) {
        std::cin >> a[i];
    }
    
    std::sort(a.begin(), a.end());
    
    std::cout << a[n / 2] - 1 << '\n';

    return 0;
}

C题：字符串外串

思路：

注：每个人的构造方式可能不同。

我的做法偏贪心。

可以先去看 D 题，对构造此题有帮助。

D 题结论，给定一个字符串，对于每一个小写字符开一个数组存其位置（从小到大存）。字符串的可爱值 k，是所有数组中倒数第二个元素、 $n -$ 第二个元素取最大值（正 2 右，倒 2 左）。

当 $m=n$ 的时候，是无解的。

这个可以尝试整个字符串都为同一个字符。

其余情况

我们先去放 $a$ ，由上述结论可知，我们肯定要在 $m$ 和 $n - m$ + $1$ 的位置先放一个。

然后进行分类讨论。

$case1:$ 如果 $m \geq n-m$ + $1$ ，我们则还需在其左右两边放 $a$ 才能使这个位置上的 $a$ 成为正 2 或者倒 2，贪心地放，左右各放一个，我们就放在开头和结尾。

举例：

4 3

???? <- ?aa? <- aaaa

对于出现下列情况。

a???a?????a???a

首先中间的两个 $a$ 之间都可以填 $a$ ，并不会改变 $a$ 的正二或者倒二。

变成。

a???aaaaaaa???a

假设我们现在要放 $b$ ，若我们放好一个在左边，我们不会再放一个在左边，不然就会大于 $m$ 。

贪心地放，左右各一个，但不能超过 $2$ 个。对于一开始的两个 $a$ 放开头和结尾没有任何问题。

$case2:$ 如果 $m < n-m$ + $1$ ，我们不能再在这两个的左右多放 $a$ ，这会导致可爱值大于 $m$ 。

现在是。

??a????a??

然后我们放 $b$ ，如果放在第一个 $a$ 的左边，我们还可以贪心地在第二个 $a$ 的右边放一个。

对称消完以后.

bca????acb

可以证明的是，中间不能放两个相同的字符，我们正常填入其他字符即可。

中间过程中如果放入的字符大于 $z$ ，那么就是不可以的，这也很好理解，如果给定的字符够多，那我们其实是一定可以构造的。

代码：

#include <bits/stdc++.h>
using i64 = long long;

void Solve() {
    int n, m;
    std::cin >> n >> m;

    if (m == n) {
        std::cout << "NO\n";
        return;
    }

    std::vector<int> ans(n + 1, -1);
    ans[m] = ans[n - m + 1] = 0;

    int id = 0;
    if (m >= n - m + 1) {
        ans[1] = ans[n] = 0;
        
        for (int i = n - m + 1; i <= m; i ++ ) {
            ans[i] = 0;
        }
        
        for (int i = 2, j = n - 1; i < n - m + 1; i ++, j -- ) {
            id ++;
            if (id >= 26) {
                std::cout << "NO\n";
                return;
            }

            ans[i] = ans[j] = id;
        }
    }else {
        for (int i = 1, j = n; i < m; i ++, j -- ) {
            id ++;
            if (id >= 26) {
                std::cout << "NO\n";
                return;
            }

            ans[i] = ans[j] = id;
        }

        for (int i = m + 1; i < n - m + 1; i ++ ) {
            id ++;
            if (id >= 26) {
                std::cout << "NO\n";
                return;
            }

            ans[i] = id;
        }
    }

    std::cout << "YES\n";
    for (int i = 1; i <= n; i ++ ) {
        std::cout << char('a' + ans[i]);
    }
    std::cout << '\n';

}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tt; std::cin >> tt;
    while (tt --) Solve();
    return 0;
}

D题：字符串里串

思路：

我们考虑最后可爱值为 k 的字符串 s 的开头和结尾。

首先，如果这个字符出现大于 1 次，那么其就可以成为开头或者结尾。

比如，假定 p 和 q 是我们选择的。

???a???a???

pppp
qqq....q

上面是作为结尾的情况，我们考虑开头

.......pppp
...q....qqq

如果给定的是。

???a?a?a???

任意选两个作为开头或结尾，可以证明的是。

???a?a?a???

.....pppppp
...q..qqqqq
或者
qqqqqq.....
ppppp..p...
是最优的。

那么选定的长度是正 2 右和倒 2 左，注意不能选空串，因此答案为 1 的时候将其归零。

代码：

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::string s;
    std::cin >> s;
    s = ' ' + s;

    std::vector<std::vector<int>> p(26);
    for (int i = 1; i <= n; i ++ ) {
        p[s[i] - 'a'].push_back(i);
    }

    int ans = 0;
    for (int i = 0; i < 26; i ++ ) {
        int m = p[i].size();
        if (m > 1) {
            ans = std::max({ans, p[i][m - 2], n - p[i][1] + 1});
        }
    }
    
    if (ans == 1) ans = 0;
    std::cout << ans << '\n';

    return 0;
}

E题：一起走很长的路！

思路：

考虑一个牌需要多少才会被推倒？

$a_i$ - $($ $pre_{i-1}$ $-$ $pre_{l-1}$ $)$

那么对于一段区间，则是这些值取大。

我们用线段树存入 $a_i$ - $pre_{i-1}$ 即可。

注意 l 不需要 “被” 推倒。

代码

#include <bits/stdc++.h>
using i64 = long long;

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << (int)std::log2(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

struct Info {
    i64 max = -1E18;
    Info() {};
    Info(i64 x) : max(x) {};
};

Info operator+(const Info &a, const Info &b) {
    Info c;
    c.max = std::max(a.max, b.max);
    return c;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for (int i = 0; i < n; i ++ ) {
        std::cin >> a[i];
    }

    std::vector<i64> pre(n + 1);
    for (int i = 0; i < n; i ++ ) {
        pre[i + 1] = pre[i] + a[i];
    }

    std::vector<i64> bk = pre;
    for (int i = 1; i <= n; i ++ ) {
        bk[i] = -pre[i - 1] + a[i - 1];
    }

    SegmentTree<Info> seg(bk);

    for (int i = 0; i < q; i ++ ) {
        int l, r;
        std::cin >> l >> r;
        if (l == r) {
            std::cout << 0 << '\n';
        }else {
            r ++;
            i64 val = seg.rangeQuery(l + 1, r).max;
            std::cout << std::max(0LL, val + pre[l - 1]) << '\n';
        }
    }

    return 0;
}

F题：一起找神秘的数！

思路：

比较显然，如果选定了 x，那么 y 要等于 x。

可以打表去发现，或者直接猜）

代码：

#include <bits/stdc++.h>
using i64 = long long;

void Solve() {
    i64 l, r;
    std::cin >> l >> r;

    std::cout << r - l + 1 << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tt; std::cin >> tt;
    while (tt --) Solve();
    return 0;
}

G题：一起铸最好的剑！

思路：

幂次增长很快，特判 $m=1$ 。

代码：

#include <bits/stdc++.h>
using i64 = long long;

void Solve() {
    int n, m;
    std::cin >> n >> m;

    if (m >= n) {
        std::cout << 1 << '\n';
        return;
    }

    if (m == 1) {
        std::cout << 1 << '\n';
        return;
    }

    i64 base = 1, d = n - m, ans = 1;
    for (int i = 1; base <= n; i ++ ) {
        base *= m;
        if (base >= 2LL * n - m) {
            break;
        }
        if (abs(base - n) < d) {
            d = abs(base - n);
            ans = i;
        }
    }

    std::cout << ans << '\n';
    
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tt; std::cin >> tt;
    while (tt --) Solve();
    return 0;
}

H题：一起画很大的圆！

思路：

感性的题。

如果三点共线，其实是画了一个无穷大的圆。

我们放两个点在一条边上，另外一个点距离这条边越近越好。

感性来说，两个点在长边距离第三个点远一点恰当。

代码：

#include <bits/stdc++.h>
using i64 = long long;

void Solve() {
    int  a, b, c, d;
    std::cin >> a >> b >> c >> d;

    if (b - a > d - c) {
        std::cout << a << ' ' << c << '\n';
        std::cout << a + 1 << ' ' << c << '\n';
        std::cout << b << ' ' << c + 1 << '\n';
    }else {
        std::cout << a << ' ' << c << '\n';
        std::cout << a << ' ' << c + 1 << '\n';
        std::cout << a + 1 << ' ' << d << '\n';
    }

}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tt; std::cin >> tt;
    while (tt --) Solve();
    return 0;
}

I题：一起看很美的日落！

思路：

拆位。

二进制下每位独立，且只有 0/1，极大地方便了操作。

那么题目就转变成了由 0/1 权值构成的数的全部连通块的权值和。

下面所说的仅考虑第 k 位。

考虑 dp，我们记录经过 u 但是不向上的所有连通块的答案， $dp_u$

因为是异或，我们再记录经过 u 但是不向上的所有连通块 0/1 数量的总和。

还有其所有的连通块数量。

当回溯到 u 节点的时候，可以将 u 本身看作一个块，其连通块数量为 1，0/1 数量取决于第 k 位为 0 还是 1。

将其与其儿子一一进行 $\operatorname{merge}$ 操作，就可以算出 $dp_u$ 了。

具体转移先考虑自身在两个块合并之后的贡献（乘以另一个块中连通块的数量），再加上两者合并中产生的贡献（两者所有连通块 0/1 数量总和的相互乘积）。

还要注意应输出答案 x2。

实现借鉴了 pyy 的代码。

代码：

#include <bits/stdc++.h>
using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

constexpr int P = 1000000007;
using Z = MInt<P>;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i ++ ) {
        std::cin >> a[i];
    }

    std::vector<std::vector<int>> g(n);
    for (int i = 1; i < n; i ++ ) {
        int u, v;
        std::cin >> u >> v;
        u --, v --;

        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    struct Node {
        Z c0[30], c1[30], c, ans;

        Node () {
            for (int i = 0; i < 30; i ++ ) {
                c0[i] = c1[i] = 0;
            }

            c = 0;
            ans = 0;
        }
    };

    auto merge = [&](const Node &u, const Node &v)  {
        Node res = u;
        for (int i = 0; i < 30; i ++ ) {
            res.c0[i] += u.c0[i] * v.c + u.c * v.c0[i];
            res.c1[i] += u.c1[i] * v.c + u.c * v.c1[i];
        }

        res.c += u.c * v.c;
        res.ans += u.ans * v.c + u.c * v.ans;
        for (int i = 0; i < 30; i ++ ) {
            res.ans += (u.c0[i] * v.c1[i] + u.c1[i] * v.c0[i]) * (1LL << i);
        }
        
        return res;
    };

    Z ans = 0;

    auto dfs = [&](auto &&dfs, int u, int f) -> Node {
        Node now = Node();
        now.c = 1;
        now.ans = 0;

        for (int i = 0; i < 30; i ++ ) {
            if (a[u] >> i & 1) {
                now.c1[i] = 1;
            }else {
                now.c0[i] = 1;
            }
        }

        for (auto v : g[u]) {
            if (v == f) continue;
            now = merge(now, dfs(dfs, v, u));
        }

        ans += now.ans;

        return now;
    };

    dfs(dfs, 0, -1);
    
    std::cout << ans * 2 << '\n';

    return 0;
}

J题：数据时间？

思路：

比较经典的想法是，将所有时间转化成秒。

代码：

#include <bits/stdc++.h>
using i64 = long long;
using i128 = __int128;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, h, m;
    std::cin >> n >> h >> m;
    
    std::set<std::string> a[3] = {};
    auto to = [&](std::string &s, std::string &id) {
        int res = 0;
        res += ((s[0] - '0') * 10 + (s[1] - '0')) * 3600;
        res += ((s[3] - '0') * 10 + (s[4] - '0')) * 60;
        res += ((s[6] - '0') * 10 + (s[7] - '0')) * 1;

        if (res >= 7 * 3600 && res <= 9 * 3600 || res >= 18 * 3600 && res <= 20 * 3600) {
            a[0].insert(id);
        }else if (res >= 11 * 3600 && res <= 13 * 3600) {
            a[1].insert(id);
        }else if (res >= 22 * 3600 || res <= 1 * 3600) {
            a[2].insert(id);
        }
    };

    for (int i = 0; i < n; i ++ ) {
        std::string id, y, t;
        std::cin >> id >> y >> t;
        
        if (std::stoi(y.substr(0, 4)) == h && std::stoi(y.substr(5, 2)) == m) {
            to(t, id);
        }
    }

    for (int i = 0; i < 3; i ++ ) {
        std::cout << int(a[i].size()) << " \n"[i == 2];
    }

    return 0;
}

K题：可以分开吗？

思路：

bfs。

代码：

#include <bits/stdc++.h>
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;

    std::vector<std::vector<int>> a(n + 1, std::vector<int>(m + 1));
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            char c;
            std::cin >> c;
            a[i][j] = c == '1';
        }
    }

    std::vector<std::vector<int>> vis(n + 1, std::vector<int>(m + 1));
    std::vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    int ans = 1E9 + 7;
    auto work = [&](int x, int y) {
        std::set<std::pair<int, int>> p;
        vis[x][y] = 1;
        std::queue<std::pair<int, int>> q;
        q.push({x, y});
        
        while (q.size()) {
            auto [xn, yn] = q.front();
            q.pop();
            for (int i = 0; i < 4; i ++ ) {
                int xt = xn + dx[i], yt = yn + dy[i];
                if (xt < 1 || xt > n || yt < 1 || yt > m) continue;
                if (vis[xt][yt]) continue;
                if (!a[xt][yt]) {
                    p.insert({xt, yt});
                    continue;
                }
                
                vis[xt][yt] = 1;
                q.push({xt, yt});
            }
        }
        ans = std::min(ans, int(p.size()));
    };

    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) {
            if (a[i][j] && !vis[i][j]) {
                work(i, j);
            }
        }
    }

    std::cout << ans << '\n';
    
    return 0;
}

L题：还会再见吗？

思路：

虚树 + 最短路。

首先仅考虑单种颜色的情况，若此点是关键点，要有颜色重复，我们还需要去找一个关键点。

另一个关键点的求法使用 dp。

我们将所有的关键点求出答案后，使用最短路算法就可以求出所有点的答案了。

此题有很多种颜色。使用虚树可以压缩信息。

就变成了板子题？）

代码：

#include <bits/stdc++.h>
using i64 = long long;

struct HLD {
    int n;
    std::vector<int> siz, top, dep, parent, in, out, seq;
    std::vector<std::vector<int>> adj;
    int cur;
    
    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 0;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root = 0) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1) {
            adj[u].erase(std::find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                std::swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    
    int jump(int u, int k) {
        if (dep[u] < k) {
            return -1;
        }
        
        int d = dep[u] - k;
        
        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }
        
        return seq[in[u] - dep[u] + d];
    }
    
    bool isAncester(int u, int v) {
        return in[u] <= in[v] && in[v] < out[u];
    }
    
    int rootedParent(int u, int v) {
        std::swap(u, v);
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = std::upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
    
    int rootedSize(int u, int v) {
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return siz[v];
        }
        return n - siz[rootedParent(u, v)];
    }
    
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};

constexpr int Iinf = 1E9 + 7;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q;
    std::cin >> n >> q;

    std::vector<int> ans(n, Iinf);
    std::map<int, std::vector<int>> col_;
    for (int i = 0; i < n; i ++ ) {
        int a;
        std::cin >> a;
        
        std::set<int> s;
        for (int j = 0; j < a; j ++ ) {
            int c;
            std::cin >> c;

            if (s.count(c)) {
                ans[i] = 0;
            }else {
                col_[c].push_back(i);
            }
            s.insert(c);
        }
    }

    HLD g(n);
    std::vector<std::vector<int>> adj(n);
    for (int i = 1; i < n; i ++ ) {
        int u, v;
        std::cin >> u >> v;
        u --, v --;

        g.addEdge(u, v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    g.work();

    std::vector<std::vector<int>> vir(n);
    std::vector<int> isvir(n), d1(n), d2(n);
    
    for (auto &[_, h] : col_) {
        for (auto &v : h) {
            isvir[v] = 1;
        }

        std::sort(h.begin(), h.end(), [&](int &i, int &j) {
            return g.in[i] < g.in[j];
        });

        std::vector<int> stk = {0};
        int top = 0;
        vir[0].clear();
        
        for (auto &v : h) {
            if (v == 0) continue;
            
            int lca = g.lca(v, stk[top]);
            if (lca != stk[top]) {
                while (g.in[lca] < g.in[stk[top - 1]]) {
                    vir[stk[top - 1]].push_back(stk[top]);
                    top --;
                    stk.pop_back();
                }

                if (g.in[lca] != g.in[stk[top - 1]]) {
                    vir[lca].clear();
                    vir[lca].push_back(stk[top]);
                    stk[top] = lca;
                }else {
                    vir[lca].push_back(stk[top]);
                    top --;
                    stk.pop_back();
                }
            }

            vir[v].clear();
            top ++;
            stk.push_back(v);
        }

        for (int i = 0; i < top; i ++ ) {
            vir[stk[i]].push_back(stk[i + 1]);
        }

        auto dfs1 = [&](auto &&dfs1, int u) -> void {
            d1[u] = Iinf;
            for (auto &v : vir[u]) {
                dfs1(dfs1, v);
                d1[u] = std::min(d1[u], d1[v] + g.dep[v] - g.dep[u]);
            }

            d2[u] = d1[u];
            if (isvir[u]) d1[u] = 0;
        };

        dfs1(dfs1, 0);

        auto dfs2 = [&](auto &&dfs2, int u, int up = Iinf) -> void {
            if (isvir[u]) {
                ans[u] = std::min({ans[u], d2[u], up});
                up = 0;
            }

            int min1 = up, min2 = Iinf;
            for (auto &v : vir[u]) {
                int min = d1[v] + g.dep[v] - g.dep[u];
                if (min <= min1) {
                    min2 = min1;
                    min1 = min;
                }else if (min < min2) {
                    min2 = min;
                }
            }

            for (auto &v : vir[u]) {
                int min = d1[v] + g.dep[v] - g.dep[u];

                if (min == min1) {
                    dfs2(dfs2, v, min2 + g.dep[v] - g.dep[u]);
                }else {
                    dfs2(dfs2, v, min1 + g.dep[v] - g.dep[u]);
                }
            }

            isvir[u] = 0;
        };

        dfs2(dfs2, 0);
    }
    
    using P = std::pair<int, int>;
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
    for (int i = 0; i < n; i ++ ) {
        pq.push({ans[i], i});
    }

    std::vector<int> vis(n);
    while (pq.size()) {
        auto u = pq.top().second;
        pq.pop();

        if (vis[u]) continue;
        vis[u] = 1;
        for (auto &v : adj[u]) {
            if (ans[v] > ans[u] + 1) {
                ans[v] = ans[u] + 1;
                pq.push({ans[v], v});
            }
        }
    }

    for (int i = 0; i < q; i ++ ) {
        int x;
        std::cin >> x;
        x --;

        if (ans[x] == Iinf) {
            std::cout << "IMPOSSIBLE!\n";
        }else {
            std::cout << ans[x] << '\n';
        }
    }

    return 0;
}

M题：那是我们的影子

思路：

性质题。

我们可以发现，位置 %3 后出现的元素应该是相同的。

具体来说。

1??2
2??1
3??3

对于第四列，它使用的元素只能是 {1, 2, 3}。

那么其实我们确定了前三列后，每列上具体元素是啥其实已经确定了。

记该列上有 $cnt$ 个？，这列上能提供的不同方案数为 $A(cnt, cnt)$ 。

所以，我们要去确定前三列到底是啥。

具体来说，我们先去确定前三列到底已经确定了哪些数。

这个确定指的是。

???1
???2
???4

这个看起来第一列全是？，但是其实已经被确定为 {1, 2, 4}了。

我们将未被确认的数，选入前三列的每一列，使其确认的数达到 3 个。

比如说，我们得到的是。

???
???
???

我们实际上是， $C(9,3) * C(6,3) * C(3, 3) *$ $A(3,3)^3$

再来一个例子。

???1
????
????

我们实际上是， $C(8,2) * C(6,3) * C(3, 3) *$ $A(3,3)^3$ $A(2,2)$

然后就是要注意输出 0 的情况了。

有下列三种情况。

1.该列上有相同的元素

1??
1??
???

2.前三列中确认的元素超过了 3 个

1??2
3??4
????

3.前三列中确认的元素有重复

11?
???
???

代码：

#include <bits/stdc++.h>
using i64 = long long;

template<class T>
constexpr T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}

template<int P>
struct MInt {
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}
    
    static int Mod;
    constexpr static int getMod() {
        if (P > 0) {
            return P;
        } else {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_) {
        Mod = Mod_;
    }
    constexpr int norm(int x) const {
        if (x < 0) {
            x += getMod();
        }
        if (x >= getMod()) {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const {
        return x;
    }
    explicit constexpr operator int() const {
        return x;
    }
    constexpr MInt operator-() const {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) & {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) & {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) {
        return lhs.val() != rhs.val();
    }
};

constexpr int P = 1000000007;
using Z = MInt<P>;

int C (int a, int b) {
    int res = 1;
    for (int i = a; i >= a - b + 1; i -- ) {
        res *= i;
    }
    for (int i = 1; i <= b; i ++ ) {
        res /= i;
    }
    return res;
}

void Solve() {
    int n;
    std::cin >> n;

    std::vector<std::vector<char>> a(3, std::vector<char>(n));
    std::set<int> s[3] = {};

    for (int i = 0; i < 3; i ++ ) {
        for (int j = 0; j < n; j ++ ) {
            std::cin >> a[i][j];
        }
    }
    
    for (int i = 0; i < 3; i ++ ) {
        for (int j = 0; j < n; j ++ ) {
            if (a[i][j] != '?') {
                s[j % 3].insert(a[i][j] - '0');
            }
        }
    }

    for (int i = 0; i < 3; i ++ ) {
        if (int(s[i].size()) > 3) {
            std::cout << 0 << '\n';
            return;
        }
    }

    std::vector<int> use(10);
    for (int i = 0; i < 3; i ++ ) {
        for (auto v : s[i]) {
            if (use[v]) {
                std::cout << 0 << '\n';
                return;
            }
            use[v] = 1;
        }
    }

    for (int i = 0; i < n; i ++ ) {
        std::set<int> s;
        for (int j = 0; j < 3; j ++ ) {
            if (a[j][i] != '?') {
                if (s.count(a[j][i] - '0')) {
                    std::cout << 0 << '\n';
                    return;
                }
                s.insert(a[j][i] - '0');
            }
        }
    }

    int cnt = 0;
    for (int i = 0; i < 3; i ++ ) {
        cnt += 3 - int(s[i].size());
    }

    Z ans = 1;
    for (int i = 0; i < 3; i ++ ) {
        ans *= C(cnt, 3 - int(s[i].size()));
        cnt -= 3 - int(s[i].size());
    }

    for (int i = 0; i < n; i ++ ) {
        int cnt = 0;
        for (int j = 0; j < 3; j ++ ) {
            if (a[j][i] == '?') {
                ans *= ++cnt;
            }
        }
    }

    std::cout << ans << '\n';

}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tt; std::cin >> tt;
    while (tt --) Solve();
    return 0;
}

2025牛客寒假算法基础集训营2