Contestant. Rank 2150. Rating -3.

A. We Need the Zero

题意

给定序列 \(a\)，判断是否存在一个数 \(x\)，使 \((a_1 \oplus x) \oplus (a_2 \oplus x) \oplus ... \oplus (a_n \oplus x) = 0\)。若存在，输出这个数，否则输出 \(-1\)。

思路

很显然，异或是具有交换律的，也就是说，我们不妨记 \(p = a_1 \oplus a_2 \oplus ... \oplus a_n\)。

因为两个相同的数异或值为 \(0\)，所以我们只需考虑 \(n\) 的奇偶性。

如果 \(n\) 为奇数，那么我们只需让 \(x = p\)，否则就需要 \(p = 0\)，不然无解。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        ans ^= cur;
    }
    cout << (ans != 0 && n % 2 == 0 ? -1 : ans) << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

找找规律~

B. The String Has a Target

题意

给定一个由小写字母组成的字符串，任选一个字母并将其移动到字符串的开头，使整个字符串的字典序最小。输出这个最小的字典序。

思路

显然，我们只需把一个小的字符移上来就好了。

或者，更具体地说，我们只需找出字符串中最小的那个字符，然后将其移动到第一个即可。

当然，如果第一个使最小的，不管即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n;
    string s;
    cin >> n >> s;
    int mn = 0;
    for(int i=1;i<n;i++){
        if(s[i] <= s[mn]) mn = i;
    }
    cout << s[mn];
    for(int i=0;i<=mn-1;i++) cout << s[i];
    for(int i=mn + 1;i<n;i++) cout << s[i];
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

《Div. 2 B题》

C. Place for a Selfie

题意

给定若干数量两种函数的系数，函数分别为 \(y = kx, y = a x ^ 2 + b x + c\)。

对于所有的二次函数，找出一条直线，使其与二次函数没有交点。若能找到，输出斜率 \(k\)。

思路

首先，对于直线和二次函数，我们将其联立，可得 \(a x ^ 2 + (b - k) x + c = 0\)。

也就是说，只要满足 \(\Delta = (b - k) ^ 2 - 4 a c < 0\) 即可。

提取出 \(k\)，我们可得 \(b - \sqrt{4ac} < k < b + \sqrt{4ac}\)。

那么，我们只需二分，找出边界即可。

对于二分，我们可以用 原数字和相反数的 \(upperbound\)，这样即可快速求出。

注意，合理使用 \(int\) 类型的强制转换，\(double\) 只会向 \(0\) 的方向取整，而不都是向下取整。

时间复杂度：\(O(n \log m)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> p(n + 2, inf);
    p[0] = -inf;
    vector<int> q(n + 2, -inf);
    q[0] = inf;
    for(int i=1;i<=n;i++) {
        cin >> p[i];
        q[i] = -p[i];
    }
    sort(p.begin(), p.end());
    sort(q.begin(), q.end());
    while(m --){
        double a, b, c;
        cin >> a >> b >> c;
        if(a * c < 0){
            cout << "NO\n";
            continue;
        }
        double sq = sqrt(4 * a * c);
        double lk = b - sq, rk = b + sq;
        if(rk <= p[1] || lk >= p[n]){
            cout << "NO\n";
            continue;
        }
        int l = upper_bound(p.begin(), p.end(), (int) floor(lk)) - p.begin(),
            r = n - (upper_bound(q.begin(), q.end(), (int) floor(-rk)) - q.begin()) + 1;
        if(l > r){
            cout << "NO\n";
        }else{
            cout << "YES\n";
            cout << p[l] << '\n';
        }
    }
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

草，相反数 \(upperbound\) 真好用（x

D. A Wide, Wide Graph

题意

给定一个边权为 \(1\) 的无向无环图，对于 \(k \in [1, n]\)，输出以距离 \(k\) 为边连结得到的图中连通块的个数。

如 \(1 -2 -3 -4 -5\)，\(k = 2\) 的时候 \(1 -3, 2 - 4, 3 - 5\)，可以发现连通块个数为 \(1\)。

思路

我们不妨考虑 \(k = 1\) 的情况，然后逐一递增。

首先，对于一个点，若它到所有点的最大距离 \(p < k\)，那么这个点无法被连接上，而反之，就可以被连上。

如果一个点连不上了，那么连通块的个数会增加。有趣的是，既然这个点无法和其他点连接，那么他一定是孤立的单点。

为什么呢？因为我们在逐一减小剔除的时候，已经把它旁边的全都拿掉了，那么自然会成为单点。

那么，我们不妨用 \(Dfs\) 的方法，找出所有点到其他点的最大距离，然后排个序，计算答案即可。

我们可以正反跑两遍，来找出最大的距离。

时间复杂度：不会分析捏

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

vector<int> e[N];

void dfs(int x, int f, int st, int &mx, vector<int> &out){
    out[x] = st;
    if(out[mx] < out[x]) mx = x;
    for(auto w : e[x]){
        if(w == f) continue;
        dfs(w, x, st + 1, mx, out);
    }
}

void solve() {
    int n;
    cin >> n;
    for(int i=0;i<n-1;i++){
        int u, v;
        cin >> u >> v;
        u --, v --;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    int a = 0;
    vector<int> tv(n);
    dfs(0, -1, 0, a, tv);
    vector<int> f1(n), f2(n);
    int b = 0, ti = 0;
    dfs(a, -1, 0, b, f1);
    dfs(b, -1, 0, ti, f2);
    for(int i=0;i<n;i++)
        f2[i] = max(f1[i], f2[i]);
    sort(f2.begin(), f2.end());
    int ans = 0;
    for(int i=1;i<=n;i++){
        while(ans < n - 1 && f2[ans] < i) ans ++;
        cout << ans + 1 << ' ';
    }
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

嘶，有点抽象（

F1. Survival of the Weakest (easy version)

题意

定义 \(F(a_1, a_2, \ldots, a_n)\) 为任意两个元素相加得到的新集合的前 \(n - 1\) 小项构成的新集合。给定一个序列，求出 \(n - 1\) 次操作后最终的值的最大值。

思路

首先！我们来试试暴力！

暴力如何解呢？我们将新集合构造出来，然后排序，最后取前 \(n - 1\) 项覆盖原集合。

排序直接用 \(multiset\) 就好了，会快一点。

不过，这里会有一个问题，因为我们需要排序，所以我们不可以取模，但这样会导致爆 \(int\)。

那么，我们不妨在每次做完后，将所有元素减掉最小值，那么最后我们不难发现最小值被减去了 \(\min \times 2 ^ {n - 1}\) 次，最后的答案加上即可。

很好，这样很简单，但是太慢了。

那么，我们不妨观察一下，如何卡过去 如何优化。

首先，固定第二个元素遍历的时候，\(a_2 \geq a_1\)，那么我们可以贪心地认为 \(\frac{n}{2}\) 后面的元素是不用考虑的，瞎猜即可。

归纳得到结论：遍历到 \(\frac{n}{i}\) 为止。

具体证明我不会（瞎猜的

用了 \(2.5s\) 卡过去的（不建议参考这个思路

时间复杂度：卡过去的（

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), p(n + 1, 1);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) p[i] = (p[i - 1] * 2) % mod;
    sort(a.begin(), a.end());
    n++;
    int tot = 0;
    while (n-- > 2) {
        multiset<int> ans;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= min(n - 1, n / (i + 1)); j++) {
                ans.insert(a[i] + a[j]);
            }
        }
        int mn = *ans.begin();
        auto it = ans.begin();
        for (int i = 0; i < n - 1; i++) {
            a[i] = *it - mn;
            it++;
        }
        tot = (tot + mn * p[n - 2]) % mod;
    }
    cout << (tot + a[0]) % mod << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    //cin >> t;
    while(t --) solve();
}

卡过去了就离谱