Codeforces Round 862 (Div. 2)

Date: 04/07/2023

Link: Dashboard - Codeforces Round 862 (Div. 2) - Codeforces

A|We Need the Zero

Brief: 给定非负整数序列，求一个 \(x\)，使得序列每个元素异或 \(x\) 后再全部异或起来的结果为 \(0\). 没有输出 \(-1\).

Data: \(T\leq 1e3, x< 2^8\).

Solution: 【异或】

考虑到异或的性质，\(\oplus_{i=1}^n (a_i\oplus x) = (\oplus_{i=1}^n a_i)\oplus(\oplus_{i=1}^n x)\)。 因此，对于每一个二进制位，若 \(\oplus_{i=1}^n a_i\) 为 \(1\), 当 \(n\) 为偶数时无解，\(n\) 为奇数时令 \(x\) 此位为 \(1\)；若 \(\oplus_{i=1}^n a_i\) 为 \(0\), 令 \(x\) 此位为 \(0\).

Review: -

State: AC.

B|The String Has a Target

Brief: 给定字符串，可以进行一次且仅一次这样的操作，将任意一个字符提前到字符串首位，求字典序最小的字符串。

Data: \(T\leq 1e4, n\leq 1e5\).

Solution: 【字符串】【简单思维题】

首先只可能提前最小的字符，因为第一位最小一定最优。

再考虑提前哪个位置的最小字符。假设 \(i<j\), 提前后比较两个字符串，显然第一个字符串的第 \(i + 1\) 位是一个大于等于最小字符的字符，而第二个字符串的第 \(i + 1\) 位恰好是最小字符（即原来的第 \(i\) 位）。所以提前后面的位置更优。

因此，只需把最后出现的最小字符提前即可。

Review: 考虑复杂了。注意最值的性质，可以省去不必要的比较。

State: AC.

C|Place for a Selfie

Brief: 平面坐标系给出 \(n\) 条过原点的直线(k)，\(m\) 条抛物线(a,b,c)，对于每条抛物线，找出任意一条不与之相交的直线。

Data: \(T\leq 1e4, n,m\leq 1e5, \sum n,\sum m\leq 1e5\).

Solution: 【数学】【计算几何】

高中数学题。可以考虑求切线，也可以考虑求使得 delta 最小的 \(k\).

Review: 假如只和值相关，建议去重一下，否则可能像我一样遍历被卡（）。unique 返回值是右开。还有就是谨防循环变量重名/条件写错/自增写错变量，这次三个都占全了（）。以及，推出的公式别敲代码时抄错……记得 double check.

State: TLE => AC.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAXN 100010
#define int long long

int k[MAXN];

signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; ++i)
            cin >> k[i];
        sort(k + 1, k + n + 1);
        int tot = unique(k + 1, k + n + 1) - k - 1;
        for (int i = 1; i <= m; ++i)
        {
            int a, b, c;
            cin >> a >> b >> c;
            if (c <= 0)
            {
                cout << "NO\n";
                continue;
            }
            // (x, ax^2+bx+c)
            // 2ax + b = ax + b + c/x
            // ax = c/x
            // x^2 = c/a
            // x = +-sqrt(c/a)
            // k = +-2a sqrt(c/a) + b
            double kmin = -2 * a * sqrt((double)c / a) + b;
            double kmax = 2 * a * sqrt((double)c / a) + b;
            if (kmin > kmax)
                swap(kmin, kmax);
            kmin = floor(kmin) - 1, kmax = ceil(kmax) + 1;
            bool flag = false;
            for (int j = lower_bound(k + 1, k + tot + 1, (int)kmin) - k; j <= tot && k[j] <= (int)kmax; ++j)
                if ((b - k[j]) * (b - k[j]) - 4 * a * c < 0)
                {
                    cout << "YES\n" << k[j] << '\n';
                    flag = true;
                    break;
                }
            if (!flag)
                cout << "NO\n";
        }
    }
    return 0;
}

D|A Wide, Wide Graph

Brief: 给出一棵树，定义一个图：在树上距离至少是 \(k\) 的点之间有一条边。求对于每个 \(k\), 有几个连通块。

Data: \(n\leq 1e5\).

Solution: 【图论】【树】

Observation 1: 树上最远的距离是直径端点之间的距离。

Observation 2: 图的连通状态一定是一个大连通块和其他单个节点。最大的连通块是距离其中一个直径端点至少为 \(k\) 的点集。

因此只需要计算出每个点到两个直径端点的最大距离，若 \(dis >= k\), 则在大联通块，否则，在是单个节点形成小连通块。

Review: 太慢咧~复健一下树相关。

State: - => AC.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 100010

int n;
vector <int> e[MAXN];
int dep[MAXN];
int end1, end2;
int dis[MAXN];

void dfs(int u, int f, int &end)
{
    dep[u] = dep[f] + 1;
    if (dep[u] > dep[end])
        end = u;
    for (auto v : e[u])
    {
        if (v == f) continue;
        dfs(v, u, end);
    }
}

void calc_dis(int u, int f)
{
    dis[u] = dis[f] + 1;
    for (auto v: e[u])
    {
        if (v == f) continue;
        calc_dis(v, u);
    }
    dis[u] = max(dis[u], dep[u]);
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> n;
    for (int i = 1 ; i < n ; ++i)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    dep[0] = -1;
    dfs(1, 0, end1);
    dfs(end1, 0, end2);
    dis[0] = -1;
    calc_dis(end2, 0);
    sort(dis + 1, dis + n + 1);
    int ans = 1;
    // for (int i = 1 ; i <= n ; ++i)
    //     cerr << dis[i] << ')';
    for (int i = 1 ; i <= n ; ++i)
    {
        while (ans < n && dis[ans] < i)    ++ans;
        cout << ans << ' ';
    }

    return 0;
}

E|There Should Be a Lot of Maximums

Brief: 给出一棵树，每个节点包含一个整数，定义 MAD(maximum double) 参数为树上出现两次及以上的最大整数。定义一条边的边权为删去这条边后两棵子树的 MAD 参数的较大值。求每条边的边权。

Data: \(n\leq 1e5\).

Solution: 【图论】【树】

假如整棵树的 MAD 是 M。根据 M 的数量分类讨论：

1. 如果不存在重复的整数，即MAD 是 0，那么所有答案都是 0；
2. 如果有超过两个点的 M，那么所有答案都一定是 M，因为 M 一定是最大的，任何分割都会把两个 M 分到同一子树上，那么答案只能是 M.
3. 当仅有两个 M 时，它们连线上的答案不是 M，其他边的答案是 M。考虑求解两个 M 连线上的答案，可以暴力维护两个set，直接按照定义求答案即可。

Review: 太慢咧~~注意“最大”这一性质。学一下STL。

State: - => ?

Code: 暂时咕咕~

F|Survival of the Weakest

Brief: 给出 \(n\) 个非负整数，定义 \(F(a_1,a_2,\dots,a_n)\) 为集合 \(\{a_i+a_j\}\) 中最小的 \(n-1\) 个数。求整数 \(\underbrace{F(F(F\dots F}_{n-1}(a_1,a_2,\dots,a_n)\dots))\)，对 \(1e9+7\) 取模。

Data: \(n\leq 3000\) (easy version) / \(n\leq 2e5\) (hard version).

Solution: 暂时咕咕~