A perm

首先若 \((i+j)\) 为奇数则需要满足其中一个是奇数，另一个必须是偶数。

若 \(k=0\)，那么要求 \(A_i\) 和 \(A_j\) 同号，也就是所有数必须都是同一奇偶性。若满足则答案为 \(n!\) ，否则为 \(0\) 。

若 \(k=1\) ，那么要求 \(A_i\) 和 \(A_j\) 异号。奇下标位置为 \(\lceil \frac{n}{2}\rceil=x\) 个，偶下标位置为 \(\lfloor\frac{n}{2}\rfloor=y\) 个。若 \(a_i\) 中奇数数量和偶数数量分别为 \(x、y\) 或者 \(y、x\) 那么就可以成功放进去。而同奇偶性的数顺序无关，所以方案数为 \(x!y!\) ，否则方案数为 \(0\) 。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define V vector<long long int>
#define pb push_back
#define pi pair<long long int, long long int>
#define forl(var, str, end) for (long long int var = str; var < end; var++)

ll mod = 147744151;

int main() {
    freopen("perm.in", "r", stdin);
    freopen("perm.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t;
    cin >> t;
    ll N = 100001;
    ll fact[N];
    fact[0] = 1;
    fact[1] = 1;
    for (ll i = 2; i < N; i++) {
        fact[i] = (i * fact[i - 1]) % mod;
        fact[i] %= mod;
    }
    while (t--) {
        ll n, k;
        cin >> n >> k;
        ll odd = 0;
        ll eve = 0;
        ll x;
        forl(i, 0, n) {
            cin >> x;
            if (x % 2)
                odd++;
            else
                eve++;
        }
        if (n == 1) {
            cout << "1\n";
            continue;
        }
        if (k == 0 && (odd == 0 || eve == 0)) {
            cout << fact[n] << "\n";
            continue;
        }
        if (k == 0 || (k == 1 && (odd == 0 || eve == 0)))
            cout << "0\n";
        else {
            if (abs(odd - eve) > 1)
                cout << "0\n";
            else {
                ll ans = (odd == eve) ? 2 : 1;
                ans = (((ans * fact[eve]) % mod) * fact[odd]) % mod;
                cout << ans << "\n";
            }
        }
    }
    return 0;
}

B seg

分析一下美丽区间内的数应该长什么样。不妨设这个区间内的数构成数组 \(B\)，假设 \(B_1\leq B_2\leq...\leq B_k\)，那么限制等价于对于所有 \(2\leq i\leq k\) 满足 \(B_i\) 是 \(B_{i-1}\) 的倍数。

所以我们只需要选取一些元素加进这个数组 \(B\) ，也就是把它们放在一起，其余的元素排列顺序无所谓。而且每次要么不选，要么把这种数字全部选完。

因为贡献的计算和最小值有关，所以设 \(dp(x)\) 表示当前加入数组 \(B\) 里最小值是 \(x\) 时，\(B\) 数组大小为多少。

转移有 \(dp(x)=\max(dp(i·x))+cnt(x)\) ，然后取 \(dp(x)\times x\) 的最大值即为答案。

时间复杂度 \(\mathcal O(n+A_{max}\log A_{max})\)。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll INF = 1e18;
const string YES = "YES";
const string NO = "NO";

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, vector<int>> factors;
    unordered_map<int, int> dp;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int x = a[i];
        if (factors.find(x) == factors.end()) {
            for (int d = 1; d * d <= x; d++) {
                if (x % d == 0) {
                    factors[x].push_back(d);
                    if ((x / d) != d) {
                        factors[x].push_back(x / d);
                    }
                }
            }
            sort(factors[x].begin(), factors[x].end());
        }
    }

    ll ans = 0;
    sort(a.rbegin(), a.rend());

    for (int i = 0; i < n; i++) {
        vector<int> f = factors[a[i]];
        for (auto &d : f) {
            dp[d] = max(dp[d], 1 + dp[a[i]]);
        }
    }

    for (int i = 0; i < n; i++) {
        ans = max(ans, 1LL * dp[a[i]] * a[i]);
    }

    cout << ans << endl;
}

int main() {
    freopen("seg.in", "r", stdin);
    freopen("seg.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

C destroy

摧毁最多的道路就对应着保留最少的路径。当 \(s_1=s_2,t_1=t_2\) 时，直接保留最短路即可。

所以答案上界是 \(dis(s_1,t_1)+dis(s_2,t_2)\)，其中 \(dis(x,y)\) 表示 \(x\) 到 \(y\) 的最短路长度。

但是存在两条路径会重叠的情况，重叠情况只需要被计算一次。

由于 \(n,m\) 只有 \(3000\) ，所以可以通过枚举两个最短路重叠部分。设枚举的重叠部分端点为 \(a,b\) ，那么答案为 \(\min_{(a,b)}\{dis(a,b)+\min(dis(s_1,a)+dis(b,t_1),dis(t_1,a)+dis(b,s_1))+\min(这里和前一个式子类似)\}\).

所以需要处理任意两点最短路，使用 BFS 即可。时间复杂度 \(\mathcal O(n(n+m))\)。

#include <cstdio>
#define For(a, b, c) for (register int a = b; a <= c; ++a)
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define CMin(a, b) (a > (b) ? a = (b) : 0)
int s1, s2, t1, t2, l1, l2, N, M, d[3005][3005], to[6010], n[6010], l[3005], num, ans;
inline void Add(int x, int y) {
    to[++num] = x;
    n[num] = l[y];
    l[y] = num;
    to[++num] = y;
    n[num] = l[x];
    l[x] = num;
}
void Bfs(int x) {
    int q[6002] = { x }, t = 0, h = 0, now, *dis = d[x];
    bool vis[3005] = {};
    vis[x] = 1;
    while (h <= t, now = q[h++])
        for (int zd, zb = l[now]; zb; zb = n[zb]) {
            zd = to[zb];
            if (vis[zd])
                continue;
            dis[zd] = dis[now] + 1;
            vis[zd] = 1;
            q[++t] = zd;
        }
}
int main() {
    freopen("destroy.in", "r", stdin);
    freopen("destroy.out", "w", stdout);
    scanf("%d%d", &N, &M);
    For(a, 1, M) {
        scanf("%d%d", &t1, &t2);
        Add(t1, t2);
    }
    For(a, 1, N) Bfs(a);
    scanf("%d%d%d%d%d%d", &s1, &t1, &l1, &s2, &t2, &l2);

    if (d[s1][t1] > l1 || d[s2][t2] > l2)
        return !printf("-1");
    ans = d[s1][t1] + d[s2][t2];

    int md, da, db, dc, dd, *d1 = d[s1], *d2 = d[t1], *d3 = d[s2], *d4 = d[t2];
    For(i, 1, N) For(j, i + 1, N) {
        md = d[i][j];
        da = Min(d1[i], d1[j]);
        db = Min(d2[i], d2[j]);
        dc = Min(d3[i], d3[j]);
        dd = Min(d4[i], d4[j]);
        if (da + db + md > l1 || dc + dd + md > l2)
            continue;
        CMin(ans, da + db + dc + dd + md);
    }
    return !printf("%d", M - ans);
}

D party

因为 \(2\) 操作是对整个连通块做贡献，所以使用并查集维护比较方便，记 \(cnt_i\) 为以 \(i\) 为代表节点的并查集举行了多少次聚会。

现在考虑 \(1\) 操作，操作相当于将两个并查集合并。假设将 \(Y\) 合并到 \(X\) 上，会发现此时 \(X\) 此前的聚会并未对 \(Y\) 进行贡献。要对 \(Y\) 的代表节点 \(y\) 再记一个 \(tmp_y\)，表示父亲节点在与自己合并之前，已经举行了多少次聚会，来起到一个差分的作用。

另外多出 \(1\) 点关系度的两人，可以用哈希表来记录。考虑查询，如果不在一个并查集里关系度肯定为 \(0\)。反之，则先暴力跳到他们的 \(lca\)，再暴力地往上跳，每次先加 \(cnt\) 再减 \(tmp\)。

最后的答案，还要先减去 \(lca\) 两个儿子 \(tmp\) 的较大值，再加上哈希表里二人额外的关系度。因为并查集树高是 \(log\) 级别的，所以暴力往上跳的复杂度是正确的。时间复杂度 \(O(n logn)\)

#include <cstdio>
#include <cstring>
#include <map>
#define reg register
#define max(_a, _b) (_a > _b ? _a : _b)
const int N = 100006;
int fa[N], siz[N], r[N], pas[N], a[30], b[30];
std::map<int, int> un[N];
int R() {
    reg int x = 0;
    reg char ch = getchar_unlocked();
    reg bool f = 0;
    for (; ch < 48 || ch > 57; ch = getchar_unlocked()) f |= ch == '-';
    for (; ch >= 48 && ch <= 57; ch = getchar_unlocked()) x = x * 10 + ch - 48;
    return f ? -x : x;
}
int find(reg int x) {
    while (x != fa[x]) x = fa[x];
    return x;
}
void swap(reg int &a, reg int &b) {
    reg int t = a;
    a = b, b = t;
}
void unionset(reg int u, reg int v) {
    reg int x = find(u), y = find(v);
    if (x == y)
        return;
    if (siz[x] < siz[y])
        swap(x, y);
    fa[y] = x, siz[x] += siz[y], pas[y] = r[x];
}
int main() {
    freopen("party.in", "r", stdin);
    freopen("party.out", "w", stdout);
    reg int n = R(), m = R(), t1, t2, ans, opt, x, y, i, j;
    for (i = 1; i <= n; ++i) fa[i] = i, siz[i] = 1;
    while (m--) {
        opt = R(), x = R(), y;
        if (opt == 1) {
            y = R();
            unionset(x, y);
            if (x > y)
                swap(x, y);
            ++un[x][y];
        } else if (opt == 2)
            ++r[find(x)];
        else {
            y = R(), t1 = t2 = ans = 0;
            if (find(x) != find(y)) {
                puts("0");
                continue;
            }
            for (i = x; i != fa[i]; i = fa[i]) a[++t1] = i;
            a[++t1] = i;
            for (i = y; i != fa[i]; i = fa[i]) b[++t2] = i;
            b[++t2] = i;
            for (i = t1, j = t2; a[i] == b[j]; --i, --j) ans += r[a[i]] - pas[a[i]];
            ans -= max(pas[a[i]], pas[b[j]]);
            if (x > y)
                swap(x, y);
            if (un[x].find(y) != un[x].end())
                ans += un[x][y];
            printf("%d\n", ans);
        }
    }
}

E graph

考虑 \(L=R\) ，此时图一定是基环森林。那么只有 \(T\) 为 \(S\) 祖先或者 \(T\) 在环上的时候答案不为 \(-1\) ，直接把图建出来做就行。

对于其他情况，当 \(T\) 不在环上时，问题可以转化为：

找到最小的 \(k\) 使得有 \(k\) 个值域在 \([L,R]\) 中的数和为 \(a\) 。

这个直接预处理每个 \(a\) 的答案即可。

当 \(T\) 在环上的时，问题可以转化为：

找到最小的 \(k\) 使得有 \(k\) 个值域在 \([L,R]\) 中的数和为 \(ai+b\) ，其中 \(a\) 是环长。

答案是连通块大小级别。因为 \(k\) 个数能组合出 \([kL,kR]\) 间的所有数，当 \(kR-kL\geq a\) 的时候一定能覆盖所有同余系。

当 \(b\geq a\) 时，把限制变为 \(ci+b\%a\) 其中限制 \(c\geq \lfloor\frac{b}{a}\rfloor\)，然后把 \([kL,kR]\) 区间按照 \(k\) 从大到小排序，维护 \(c\geq x\) 时候每个同余系的最小的 \(k\) 。具体实现可能需要提前把区间相交处理一下。时间复杂度 \(\mathcal O(n\log n)\)。

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
#define debug(...) [](auto... a) { ((cout << a << ' '), ...) << endl; }(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif  // LOCAL
const int inf = 1e18;
const int maxn = 2e5 + 5;
int a[maxn];
int col[maxn];
bool used[maxn];
int h[maxn];
int de[maxn];
int u[maxn][20];
bool cy[maxn];
int di[maxn];
int me[maxn];
int mo[maxn];
int f[maxn];
vector<int> ps;
vector<int> mem[maxn];
int32_t main() {
    freopen("graph.in", "r", stdin);
    freopen("graph.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, l, r;
    cin >> n >> l >> r;
    set<int> unu;
    f[0] = 0;
    fill(f + 1, f + maxn, inf);
    for (int i = 1; i <= n; ++i) unu.insert(i);
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        set<int>::iterator it = unu.lower_bound(x + l);
        while (it != unu.end() && (*it) <= x + r) {
            f[*it] = f[x] + 1;
            q.push(*it);
            unu.erase(it);
            it = unu.lower_bound(x + l);
        }
    }
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        u[i][0] = a[i];
    }
    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i <= n; ++i) {
            u[i][j] = u[u[i][j - 1]][j - 1];
        }
    }
    for (int i = 1; i <= n; ++i) {
        cy[u[i][19]] = true;
    }
    for (int i = 1; i <= n; ++i) {
        if (cy[i] && !used[i]) {
            int x = i;
            int c = 0;
            while (true) {
                col[x] = i;
                used[x] = true;
                h[x] = c;
                ++c;
                x = a[x];
                if (x == i)
                    break;
            }
            de[i] = c;
            ps.app(de[i]);
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (cy[i]) {
            me[i] = i;
            continue;
        }
        di[i] = 0;
        int x = i;
        for (int j = 19; j >= 0; --j) {
            if (!cy[u[x][j]]) {
                di[i] += (1 << j);
                x = u[x][j];
            }
        }
        me[i] = a[x];
        di[i]++;
        mo[de[col[me[i]]]] = max(mo[de[col[me[i]]]], di[i]);
    }
    sort(all(ps));
    ps.erase(unique(all(ps)), ps.end());
    auto ok = [&](int p, int x) -> bool { return ((l + 2 * p - 1 - x) / p != (r + 2 * p - x) / p); };
    for (int p : ps) {
        vector<int> ans(mo[p] + p + 1);
        fill(all(ans), inf);
        ans[0] = 0;
        set<int> unuse;
        for (int i = 1; i < ans.size(); ++i) {
            unuse.insert(i);
            unuse.insert(i + p);
        }
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            int wis = x + l;
            for (int i = 20; i >= 0; --i) {
                if (wis - p * (1 << i) >= ((int)(ans.size())))
                    wis -= p * (1 << i);
            }
            if (wis >= ans.size())
                wis -= p;
            debug(x, wis);
            set<int>::iterator it = unuse.lower_bound(wis);
            while (it != unuse.end() && (*it) <= x + r && ok(p, (*it) - x)) {
                int v = (*it);
                unuse.erase(it);
                if (v >= ans.size()) {
                    v -= p;
                }
                if (ans[v] == inf) {
                    ans[v] = ans[x] + 1;
                    q.push(v);
                }
                if (unuse.count(v))
                    unuse.erase(v);
                it = unuse.lower_bound(wis);
            }
        }
        for (int i = ans.size() - 1 - p; i >= 0; --i) {
            ans[i] = min(ans[i], ans[i + p]);
        }
        debug(ans.size());
        for (int x : ans) debug(x);
        mem[p] = ans;
    }
    auto up = [&](int x, int h) {
        for (int i = 19; i >= 0; --i) {
            if (h & (1 << i)) {
                x = u[x][i];
            }
        }
        return x;
    };
    int q1;
    cin >> q1;
    while (q1--) {
        int x, y;
        cin >> x >> y;
        if (col[me[x]] != col[me[y]]) {
            cout << (-1) << '\n';
            continue;
        }
        if (!cy[y]) {
            if (di[x] < di[y]) {
                cout << (-1) << '\n';
                continue;
            }
            if (x == y) {
                cout << 0 << '\n';
                continue;
            }
            int h = di[x] - di[y];
            if (up(x, h) != y) {
                cout << (-1) << '\n';
                continue;
            }
            cout << (f[h] == inf ? -1 : f[h]) << '\n';
            continue;
        }
        int p = de[col[me[x]]];
        int o = ((h[y] - h[me[x]]) % p + p) % p;
        o += di[x];
        if (o < mem[p].size()) {
            cout << (mem[p][o] == inf ? -1 : mem[p][o]) << '\n';
        } else {
            for (int i = 20; i >= 0; --i) {
                if (o - p * (1 << i) >= ((int)(mem[p].size()))) {
                    o -= p * (1 << i);
                }
            }
            o -= p;
            cout << (mem[p][o] == inf ? -1 : mem[p][o]) << '\n';
        }
    }
    return 0;
}
/*
2 101 101
2 1
1
1 2
*/