🌓

zesqwq's Nest

杂题选做

创建于 2023-10-12

杂题选做

CF1019C Sergey's problem

关键思路：逐个满足条件。

先满足第二个条件，将编号从小到大贪心，可以做到距离不超过 $1$ 啥的。

再满足第一个条件，选择相邻点则删去。

code

const int N = 1e6 + 10;
vector<int> vec[N], ans;
bool vis1[N], vis2[N];
int n, m;
int main() {
    read(n, m);
    for (int u, v, i = 1; i <= m; i++) read(u, v), vec[u].push_back(v);
    for (int i = 1; i <= n; i++)
        if (!vis1[i]) { vis1[i] = vis2[i] = 1; for (int v : vec[i]) vis1[v] = 1; }
    for (int i = n; i; i--)
        if (vis2[i]) { for (int v : vec[i]) vis2[v] = 0; ans.push_back(i); }
    println(ans.size());
    for (int v : ans) write(v, ' ');
    return 0;
}

CF1386A Colors

有一个值 $c < n$ ，你可以用最多 $64$ 次询问把它查询出来。

每次询问你可以给出一个 $x \le n$ ，，假设你上次问的是 $y$ ，那么系统将返回 $|x - y| \ge c$ 是否为真。

因为第一次询问没有上次询问的值，所以系统返回什么都可以。此外，你还要保证你询问的 $x$ 不重复。

$n \le 10^{18}$ 。

第一个思路是直接二分。

我们发现直接二分会遇到如果当前点在中间然后下一个要问 $> \dfrac n 2$ 时就完蛋了。

因此考虑防止这种情况发生。

思路是：左右横跳。

我们考虑找到一个点 $p$ 使得二分左右横跳的时候没有跳出去。

这个点可以倒着模拟最坏二分情况做来找到。

这样就可以用 $\log V + C$ ， $C$ 为常数来找到答案。

code

l n, l, r;
inline bool ask(ll x) {
    cout << "? " << x << endl;
    bool ans;
    cin >> ans;
    return ans;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n, l = 0, r = n;
        ll pos = 0, f = 1;
        vector<ll> ans;
        while (r - l > 1) l = l + r >> 1, ans.emplace_back(l);
        for (int i = int(ans.size()) - 1; ~i; i--) pos += ans[i] * f, f = -f;
        l = 0, ask(pos + 1);
        while (r - l > 1) {
            ll mid = l + r >> 1;
            pos += f * mid, f = -f;
            if (ask(pos + 1)) r = mid;
            else l = mid;
        }
        // println(r);
        cout << "= " << r << endl;
    }
    return 0;
}

CF643E Bear and Destroying Subtrees

题意：

给你一棵初始只有根为 $1$ 的树。

共有 $q$ 次操作。

1 x 表示加入一个以 x 为父亲的新点。 2 x 表示求以 x 为根的子树期望最深深度。

每条边都有 $\dfrac 12$ 概率断裂。

$1 \le q \le 5 \times 10^5$ 。

输出保留 $6$ 位小数。

思路：

发现对于根 $x$ 只用计算深度不过 $60$ 的点的贡献，加点时只算向上 $60$ 个的贡献即可。

时间复杂度 $O(60n)$ 。

code

const int N = 5e5 + 10;
int q, fa[N], cnt = 1;
double f[N][62];
int main() {
    read(q), fill(f[1] + 1, f[1] + 62, 1);
    while (q--) {
        int op, u;
        read(op, u);
        if (op == 1) {
            fa[++cnt] = u;
            fill(f[cnt] + 1, f[cnt] + 62, 1);
            vector<int> vec;
            int x = cnt;
            for (int i = 1; i <= 61 && x; i++) vec.push_back(x), x = fa[x];
            for (int i = int(vec.size()) - int(2); i > 0; i--)
                f[vec[i + 1]][i + 1] /= (f[vec[i]][i] + 1) / 2;
            for (int i = 0; i + 1 < vec.size(); i++) 
                f[vec[i + 1]][i + 1] *= (f[vec[i]][i] + 1) / 2;

        } else {
            double ans = 59;
            for (int i = 1; i < 60; i++) ans -= f[u][i];
            printf("%.10lf\n", ans);
        }
    }
    return 0;
}

CF1632E2 Distance Tree (hard version)

题意：

给定一个包含 $n$ 个节点的树，每条边的长度为 $1$ 。给出如下定义：

定义 $d(v)$ 为从节点 $1$ 到节点 $v$ 的距离。
定义 $f(x)$ 为在任意两个点 $a,b$ 之间添加一个长度为 $x$ 的边后， $\max\limits_{1\leqslant v\leqslant n}d(v)$ 的最小值。

现在，对于所有的 $1\leqslant x\leqslant n$ ，求出 $f(x)$ 的值。

数据范围：

$t$ 组数据， $1\leqslant t\leqslant 10^4$ 。
$2\leqslant n,\sum n\leqslant\bf 3\times 10^5$ 。

这道题实属妙极，本蒟蒻确实做不出来。

P3590 [POI2015] TRZ

题意：

给定一个长度为 $n$ 的仅包含 $\texttt B$ 、 $\texttt C$ 、 $\texttt S$ 三种字符的字符串，请找到最长的一段连续子串，使得这一段要么只有一种字符，要么有多种字符，但是没有任意两种字符出现次数相同。

$n \le 10^6$ 。

思路：

答案的 $l \le 3$ 或 $n - 2 \le r$ ，想想为什么。

code

const int N = 1e6 + 10;
char str[N];
int n, ans = 1;
char mp[N];
int c[3];
inline void check(int len) {
    if (c[0] != c[1] && c[1] != c[2] && c[2] != c[0] || (!!c[0] + !!c[1] + !!c[2] == 1)) chkmax(ans, len);
}
int main() {
    mp['C'] = 0, mp['B'] = 1, mp['S'] = 2;
    read(n), read_cstr(str + 1);
    for (int i = 1; i <= n; i++) ++c[mp[str[i]]], check(i); 
    c[1] = c[2] = c[0] = 0;
    for (int i = 2; i <= n; i++) ++c[mp[str[i]]], check(i - 1); 
    c[1] = c[2] = c[0] = 0;
    for (int i = 3; i <= n; i++) ++c[mp[str[i]]], check(i - 2); 
    c[1] = c[2] = c[0] = 0;
    reverse(str + 1, str + n + 1);
    for (int i = 1; i <= n; i++) ++c[mp[str[i]]], check(i); 
    c[1] = c[2] = c[0] = 0;
    for (int i = 2; i <= n; i++) ++c[mp[str[i]]], check(i - 1); 
    c[1] = c[2] = c[0] = 0;
    for (int i = 3; i <= n; i++) ++c[mp[str[i]]], check(i - 2); 
    c[1] = c[2] = c[0] = 0;
    println(ans);
    return 0;
}

CF1844G Tree Weights

题意：

给你一棵节点编号为 $1 \sim n$ （ $2 \le n \le 10^5$ ）的无根树，每条边有未知的正整数边权。

现在对于所有的 $1 \le i < n$ ，给出点 $i$ 到点 $i + 1$ 的距离 $d_i$ （ $1 \le d_i \le 10^{12}$ ），请你还原出任意一组合法的边权或输出 $-1$ 报告无解。

思路：

这道题实属妙极，本蒟蒻确实做不出来。

对于两个点 $(u, v)$ 距离为 $dep_u + dep_v - 2dep_{\text{lca}(u,v)}$ ， $2$ 这个数很不平凡。最粗糙的，我们发现 $dep_u + dep_v = \text{dist}(u, v) \pmod 2$ ，又有 $dep_1 = 0$ ，可以得出 $\text{dep}_i \bmod 2$ 的值。

更进一步！我们发现通过这个规律，我们可以倍增。我们先得出 $\bmod 2$ 的答案。然后再尝试得出 $\bmod 4$ 的答案，不断倍增。

倍增的过程实际上是简单的，因为 $dep_u \bmod 2^i$ 是前面已经推出的， $dep_{\text{lca}(u,v)}$ 因为前面带个 $2$ 的系数所以只需要用到已经推出的 $\bmod 2^{i-1}$ 的值，然后做完后 $\text{check}$ 一下就行了。

code

const int N = 1e5 + 10;
ll d[N], k[N], dis[N];
int siz[N], n, m, fa[N], son[N], top[N], dep[N], l[N],fac[N];
vector<pair<int, int>> vec[N];
void dfs(int u) {
    siz[u] = 1;
    for (auto [v, id] : vec[u])
        if (v != fa[u]) {
            fa[v] = u, dep[v] = dep[u] + 1, dfs(v), siz[u] += siz[v];
            if (siz[v] > siz[son[u]]) son[u] = v;
        }
}
void dfs2(int u) {
    if (son[u]) top[son[u]] = top[u], dfs2(son[u]);
    for (auto [v, id] : vec[u])
        if (v != fa[u] && v != son[u]) top[v] = v, dfs2(v);
}
inline int lca(int u, int v) {
    while (top[u] != top[v])
        dep[top[u]] > dep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
    return dep[u] < dep[v] ? u : v;
}
ll len[N];
inline void print(int u) {
    for (auto [v, id] : vec[u]) if (v != fa[u]) {
        len[id] = d[v] - d[u];
        if (len[id] <= 0) {
            println(-1);
            exit(0);
        }
        print(v);
    }
}
int main() {
    read(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        read(u, v), vec[u].emplace_back(v, i), vec[v].emplace_back(u, i);
    }
    dfs(1), dfs2(top[1] = 1);
    for (int i = 1; i < n; i++) read(k[i]), l[i] = lca(i, i + 1); // cout << i << ' ' << l[i] << endl;
    // cout << "find:" << 1 << ' ' << k[1] << ' ' << d[1] << endl;
    for (int i = 0; i < 60; i++) {
        for (int j = 1; j < n; j++) {
            // cout << "getx:" << i << ' ' << j << ' '<< k[j] << ' ' << d[j] << ' '<< ((d[j] & (1 << i)) ^ (k[j] & (1 << i))) << endl;
            d[j + 1] ^= ((d[j + 1] + d[j] + (1ll << i + 5) - d[l[j]] - d[l[j]]) & (1ll << i)) ^ (k[j] & (1ll << i));
            // if (j) d[j + 1] ^= (d[l[j]] & (1ll << i - 1)) << 1;
        }
    }
    for (int i = 1; i < n; i++) if (d[i] + d[i + 1] - d[l[i]] - d[l[i]] != k[i]) return println(-1), 0;
    // for (int i = 1; i <= n; i++) cout << d[i] << ' ';
    print(1);
    for (int i = 1; i < n; i++) println(len[i]);
    // cout << endl;
    return 0;
}

[ABC254Ex] Multiply or Divide by 2

题意：

给定大小为 $ n $ 的集合 $ A $ 和 $ B $，你可以对集合 $ A $ 中的元素 $ a_i $ 进行两种操作，分别为 $ a_i \leftarrow \lfloor \dfrac{a_i}{2} \rfloor $，和 $ a_i \leftarrow a_i \times 2 $。你需要操作集合 $ A $ 直至集合 $ A, B $ 完全相同。求最小操作次数，若无解输出 -1。

$n \le 10^5$ 。

思路：

这个题很厉害啊。

我们发现：

对于 $A$ 集合最大的点 $x$ 和 $B$ 集合最大的点 $y$ ：

如果 $x = y$ ，则说明可以消掉；

如果 $x > y$ ，则说明 $x$ 一定要执行 $/ 2$ 操作，试执行后重新放回集合；

如果 $x < y$ ，则说明 $y$ 一定由 $\times 2$ 操作得来，执行 $y /= 2$ 操作，试执行后重新放回集合；

然后直接模拟即可。

时间复杂度 $O(n \log n)$ 。

code

priority_queue<int> q1, q2;
int main() {
    int n, x;
    read(n);
    for (int i = 1; i <= n; i++) read(x), q1.push(x);
    for (int i = 1; i <= n; i++) read(x), q2.push(x);
    int ans = 0;
    while (q1.size()) {
        int a = q1.top();
        q1.pop();
        int b = q2.top();
        q2.pop();
        if (a == b) continue;
        ++ans;
        if (a > b) {
            a >>= 1;
            q1.push(a), q2.push(b);
        } else {
            if (b & 1) return println(-1), 0;
            b >>= 1;
            q1.push(a), q2.push(b);
        }
    }
    cout << ans;
    return 0;
}

AGC003E Sequential operations on Sequence

题意：

一串数，初始为 $1\sim n$ ，现在给 $Q$ 个操作，每次操作把数组长度变为 $q_i$ ，新增的数为上一个操作后的数组的重复。问 $Q$ 次操作后 $1\sim n$ 每个数出现了多少次。

$Q, n \le 10^5, q_i \le 10^{18}$ 。

思路：

这个题很厉害啊。

发现实际上操作如果 $q_{x+1} < q_x$ 那 $q_x$ 这个操作可以忽略，这样操作串单调递增。

考虑如何找到 $x$ 位置的值，实际上就是先找到第一个 $p \le x$ 然后 $x = x \bmod p$ 这样不断跳。

你发现实际上增加的也是一样的，首先是重复 $\lfloor \dfrac {q_{x+1}} {q_x} \rfloor$ 次，然后再做 $q_{x+1} \bmod q_x$ 次，由于一次有效的 $\bmod$ 操作 $2(x \bmod y) \le x$ ，因此直接做就行了。

时间复杂度 $O(q\log^2 + n)$ 。

P3587 [POI2015] POD

题意：

长度为 $n$ 的一串项链，每颗珠子是 $k$ 种颜色之一。第 $i$ 颗与第 $i-1,i+1$ 颗珠子相邻，第 $n$ 颗与第 $1$ 颗也相邻。

切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。

求方案数量（保证至少存在一种），以及切成的两段长度之差绝对值的最小值。

$n \le 10^6$ 。

思路：

哈希。

环上选择可以考虑为选择一个区间。

对于每种颜色，我们在保证集合所有点的权值异或和为 $0$ 的情况下随机赋值，那么区间成立当且仅当区间权值异或和为 $0$ 。

注意发现区间为前缀时后缀会多算一次。

code

unordered_map<ull, vector<int> > mp;
const int N = 1e6 + 10;
int n, k, a[N];
vector<int> vec[N];
ull h[N];
mt19937_64 rng(random_device{}());
bool o2;

int main() {
    cerr << (&o2 - &o1) / 1048576. << endl;
    read(n, k);
    for (int i = 1; i <= n; i++) read(a[i]), vec[a[i]].push_back(i), h[i] = rng();
    for (int i = 1; i <= k; i++) {
        ull c = 0;
        for (int v : vec[i]) c ^= h[v];
        if (c) h[vec[i].back()] ^= c;
        clear(vec[i]);
    }
    mp[0].push_back(0);
    for (int i = 1; i <= n; i++) mp[h[i] ^= h[i - 1]].push_back(i);
    ll ans = 0;
    int mn = inf;
    for (auto &[u, v] : mp) ans += 1ll * v.size() * (int(v.size()) - 1) / 2;
    for (int i = 1; i <= n; i++) {
        int c = n + 1 >> 1;
        auto it = lower_bound(mp[h[i]].begin(), mp[h[i]].end(), i - c + 1);
        if (it != mp[h[i]].begin()) chkmin(mn, abs(n - i + *prev(it) -  i + *prev(it)));
        if (it != mp[h[i]].end()) chkmin(mn, abs(n - i + *it - i + *it));
    }
    cout << ans - (mp[0].size() - 1) << ' ' << mn;
    return 0;
}

CF482C Game with Strings

题意：

你和你的朋友玩一个游戏，游戏规则如下。

你的朋友创造出了 $n$ 个长度均为 $m$ 的不相同的字符串，然后他随机地选择其中一个。他选择这些字符串的概率是相等的，也就是说，他选择 $n$ 个字符串中的每一个的概率是 $\frac{1}{n}$ 。你想猜猜你的朋友选择了哪个字符串。

为了猜到你的朋友选择了哪个字符串，你可以问他问题，形式如下：字符串中第 $pos$ 个字符是什么？当这些问题的答案能够唯一确定一个字符串时，我们认为这个字符串被猜到了。在字符串被猜到后，你将停止提问。

你没有特殊的策略，所以你每次可能会等概率的问任何一个你从没猜过的位置。求猜到你的朋友选的字符串所需次数的期望。

$n \le 50, len \le 20$ 。

思路：

有一个简单的 $O(2^{len}\text{poly}(n, len))$ 的做法，就是考虑状压 $\text{dp} $对于每个 $i$ 具体来说，设 $f_j$ 表示当前已经询问了 $i$ 这个状态，期望再问多少次能够确定这个串（当前枚举的这个串）。

这样直接做要 $O(nlen 2^{len})$ 。

然后考虑优化：

我们记录 $g_i$ 表示询问 $i$ 这个集合不能区分哪些串。

这样可以 $n$ 个串一起做，时间复杂度 $O(len 2^{len})$ 。

code

const int N = 21, M = 55;
int n, m;
char str[M][N];
double f[1 << 20];
ull g[1 << 20];
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read_cstr(str[i]);
    m = strlen(str[1]);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            int now = 0;
            for (int k = 0; k < m; k++) {
                if (str[i][k] == str[j][k]) now |= 1 << m - k - 1;
                g[now] |= (1ll << i - 1) | (1ll << j - 1);
            }
        }
    for (int i = 0; i < m; i++)
        for (int j = 0; j < (1 << m); j++)
            if (!((j >> i) & 1)) g[j] |= g[j | (1 << i)];
    for (int i = (1 << m) - 1; ~i; i--) if (g[i]){
        int cnt = 0;
        for (int j = 0; j < m; j++)
            if (!((i >> j) & 1)) f[i] += f[i | (1 << j)], ++cnt;
        f[i] /= cnt, f[i] += __builtin_popcountll(g[i]);
    }
    printf("%.9lf", f[0] / n);
    return 0;
}

CF1270G Subset with Zero Sum

题意：

给你 $n$ 个整数 $a_1 \,,a_2 \dots a_n$ ，第 $i$ 个整数 $a_i$ 满足 $i-n\le a_i \le i-1$ .

找到一个这些整数的一个非空子集，使得它们的和为 $0$ 。可以证明在给出的条件下一定存在这样的子集。如果有多个子集满足条件，输出其中一个。

思路：

这个题太妙了！

$i$ 向 $i - a_i$ 连边，输出任意一个环。

我们发现根据题意，环一定存在。

又有若找到环，则 $\sum i = \sum i - a_i$ ，即 $\sum a_i = 0$ 。

太妙了！

code

const int N = 2e6 + 10;
int fa[N], g[N], n;
inline int find(int x) { return g[x] == x ? x : (g[x]  =find(g[x])); }
void work() {
    read(n);
    for (int i = 1; i <= n; i++) g[i] = i, read(fa[i]), fa[i] = i - fa[i];
    for (int i = 1; i <= n; i++)
        if (find(i) == find(fa[i])) {
            int cc = 1;
            for (int u = fa[i]; u != i; u = fa[u]) ++cc;
            write(cc, '\n', i);
            for (int u = fa[i]; u != i; u = fa[u]) write(' ', u);
            return println();
        } else
            g[find(i)] = find(fa[i]);
}
int main() {
    int T;
    read(T);
    while (T--) work();
    return 0;
}