Contestant~. Rank 96. Rating +99. (+249 -150).

终于ak一场div4了

A. To My Critics

题意

给定三个数，输出最大两个数的和是否 \(\geq 10\)。

思路

如题。

方便写的话可以考虑存到数组里。

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

对应AC代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve(){
    vector<int> a(3);
    for(int i=0;i<3;i++) cin >> a[i];
    sort(all(a));
    if(a[1] + a[2] >= 10) cout << "YES\n";
    else cout << "NO\n";
}

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

无脑签

B. Ten Words of Wisdom

题意

给定 \(n\) 句话的长度以及价值，输出长度不超过 \(10\) 的最大价值对应的下标。

思路

如题。

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

对应AC代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve(){
    int n;
    cin >> n;
    int idx = -1, vidx = -1;
    for(int i=1;i<=n;i++){
        int x, y;
        cin >> x >> y;
        if(x > 10) continue;
        if(idx == -1){
            idx = i;
            vidx = y;
        }else{
            if(y > vidx) idx = i, vidx = y;
        }
    }
    cout << idx << '\n';
}

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

无脑签

C. Word on the Paper

题意

对于一个 \(8 \times 8\) 的矩阵，初始状态下都是 "."。

现在，选定一列，并在该列插入一个连续的单词。

给定插入后的矩阵，输出单词。

思路

既然只会出现在某一列，我们直接一列一列枚举枚举所有位，将所有非 "." 字符拼接到答案上即可。

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

对应AC代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve(){
    vector<string> a(8);
    for(int i=0;i<8;i++) cin >> a[i];
    string ans = "";
    for(int j=0;j<8;j++){
        for(int i=0;i<8;i++){
            if(a[i][j] == '.') continue;
            ans += a[i][j];
        }
    }
    cout << ans << '\n';
}

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

无脑签

D. Balanced Round

题意

给定一个序列，定义操作如下：

删除一些元素；
任意排序序列

在任意次操作后，输出需要删除多少元素，使得最后的序列满足相邻元素差的绝对值 \(\leq k\)，其中 \(k\) 给定。

思路

既然要让差值的绝对值尽可能小，唯一办法就是升序或降序排序。

我们考虑升序排序，那么如果某两个相邻数的差值的绝对值大于 \(k\)，若我们删掉左边的元素，那么右边的元素和其新的相邻数的差值是一定大于 \(k\) 的。另一边也是同理的。

因而我们不难发现，最佳方案就是将排序后的序列切割为若干个区间，满足相邻区间的相邻端点之差的绝对值 \(> k\)，区间内所有相邻数之差的绝对值 \(\leq k\)。

那么，显然我们只能保留一个区间，那么答案就是 \(n - len_{max}\)。

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

对应AC代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 2, inf);
    a[0] = 0;
    for(int i=1;i<=n;i++) cin >> a[i];
    sort(all(a));
    int len = 1, now = 1;
    for(int i=2;i<=n+1;i++){
        if(a[i] - a[i - 1] > k){
            len = max(len, now);
            now = 1;
        }else now ++;
    }
    cout << n - len << '\n';
}

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

有脑签

E. Cardboard for Pictures

题意

给定 \(n\) 个正方形照片的边长 \(s_i\)。

现在，将每张照片裱上宽度为 \(w\) 的边框，将其变成大正方形。

给定最后所有大正方形的面积和，输出 \(w\)。

保证有解。

思路

最简单的思路莫过于推式子 \(+\) 求根公式，但是存在 \(sqrt\) 卡精度和 \(long\ long\) 爆掉的情况。

当然，前者可以加优化，后者可以用 \(\_\_int128\) 代替，不过我们不妨换个思路。

我们直接考虑二分答案。

我们二分 \(w\)，那么根据 \((s[i] + 2w) ^ 2\) 的大小 \(check\) 即可。

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

对应AC代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve(){
    int n, c;
    cin >> n >> c;
    vector<int> s(n + 1);
    for(int i=1;i<=n;i++) cin >> s[i];
    auto check = [&](int x) -> bool{
        int ans = 0;
        for(int i=1;i<=n;i++){
            ans += (s[i] + 2 * x) * (s[i] + 2 * x);
            if(ans >= c) return false;
        }
        return ans < c;
    };
    int l = 0, r = 1e9, mid;
    while(l < r){
        mid = (l + r) >> 1ll;
        if(check(mid)) l = mid + 1;
        else r = mid;
    }
    cout << l << '\n';
}

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

更搞笑的是，我一开始式子还推错了

F. We Were Both Children

题意

给定 \(n\) 只青蛙的跳跃距离 \(a_i\)，所有青蛙从 \(0\) 开始向前跳跃。

现在，规定可以在 \([1, n]\) 之内选择一个节点放上陷阱，青蛙到达这个节点会被困住。

输出能困住最多多少青蛙。

思路

我们用类似预处理的方式，先记录能跳 \(p\) 距离的青蛙一共有多少只，然后在 \([1, n]\) 里枚举能跳到的点，记录该点有多少青蛙经过。

那么，最后答案就是 \([1, n]\) 中青蛙数量最多的节点对应的个数。

时间复杂度：\(O(\frac{n}{1} + \frac{n}{2} + \ldots +\frac{n}{n}) = O(n \log n)\)

对应AC代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1), s(n + 1);
    map<int, int> mp;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        mp[a[i]]++;
    }
    for(auto [x, y] : mp){ //分块暴力
        for(int i=x;i<=n;i+=x) s[i] += y;
    }
    int ans = 0;
    for(int i=1;i<=n;i++) ans = max(ans, s[i]);
    cout << ans << '\n';
}

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

真就暴力呗

G. The Morning Star

题意

给定 \(n\) 个点的二维坐标，输出有多少不同的两个点组成的二元组，满足两个点所在直线的倾斜角为 \(0°, 45°, 90°, 135°\)。

思路

这四个倾斜角对应的方程为 \(x = t, y = x + t, y = t, y = -x + t\)。

可以发现，每个方程都只有一个特征值 \(t\)，我们将其作为 \(map\) 的参数，分别统计每个方程不同参数下有多少个点。

那么，如果对于 \(y = x + t\)，在某个特定的 \(t\) 下，满足该方程的点有 \(cnt\) 个，那么该情况下的二元组个数为 \(cnt(cnt - 1)\)。

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

对应AC代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

void solve(){
    int n;
    cin >> n;
    map<int, int> a, b, c, d;
    vector<pii> p(n + 1);
    for(int i = 1; i <= n; i ++){
        cin >> p[i].fs >> p[i].sc;
        a[p[i].fs] ++;
        b[p[i].sc] ++;
        c[p[i].fs - p[i].sc] ++;
        d[p[i].fs + p[i].sc] ++;
    }
    int ans = 0;
    for(auto [x, y] : a) ans += y * (y - 1);
    for(auto [x, y] : b) ans += y * (y - 1);
    for(auto [x, y] : c) ans += y * (y - 1);
    for(auto [x, y] : d) ans += y * (y - 1);
    cout << ans << '\n';
}

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

还是很暴力捏

H. The Third Letter

题意

给定 \(n\) 个人，以及 \(m\) 个限制条件。

第 \(i\) 个限制条件包含三个整数 \(a_i, b_i, c_i\)，表示在数轴上，第 \(a_i\) 个人在第 \(b_i\) 个人前面 \(c_i\) 个单位长度位置。

输出限制是否存在冲突。

思路

首先，这是一道很经典的带权并查集，并且有一道约等于一模一样的题：Zjnu Stadium.

下面给出具体思路：

我们可以对每个连通块单独考虑。

对于每一个连通块，根据并查集的做法，我们知道每个点最后会连结到一个父节点。

那么，我们不妨在连结的时候，加入一个新的参数：距离 \(d\)。

我们设一条有向边为 \(u \rightarrow v\)，距离为 \(w\)。\(u\) 在并查集中的父节点为 \(f1\)，\(v\) 在并查集中的父节点为 \(f2\)。

我们在连边的时候，也就是 \(unite\) 函数内，添加对距离 \(d\) 的更新。

我们将 \(u\) 的父节点更新为 \(f2\)，那么 \(u\) 与 \(f2\) 之间的距离就是 \(w\)，但是在之前 \(u\) 的权重值是相对于 \(f1\) 计算的，所以我们需要减去 \(d[u]\)，再加上 \(d[v]\)，才能得到相对于 \(f2\) 的权重值。

因而，我们在 \(unite\) 函数内添加 \(d[f2] = d[u] + w - d[v]\).

当然，因为我们进行了路径压缩，所以在 \(find\) 函数里也得对应更新一下 \(d\)。

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

对应AC代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

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

struct DSU {
    vector<int> pa;
    void init(int n) { pa = vector<int>(n + 1), iota(all(pa), 0); }
    int find(vector<int> &d, int x) {
        if(pa[x] != x){
            int root = find(d, pa[x]);
            d[x] += d[pa[x]];
            return pa[x] = root;
        }
        return x;
    }
}dsu;

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> d(n + 1);
    dsu.init(n);
    bool f = true;
    while(m --){
        int u, v, w;
        cin >> u >> v >> w;
        int f1 = dsu.find(d, u), f2 = dsu.find(d, v);
        if(f1 == f2){
            if(d[v] - d[u] != w){
                f = false;
            }
        }else{
            dsu.pa[f2] = f1;
            d[f2] = d[u] + w - d[v];
        }
    }
    cout << (f ? "YES\n" : "NO\n");
}

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

一开始忘了更新 \(find\) 了，能过样例还是很抽象的