Contestant. Rank 3058. Rating -35.

坐大牢局

A. Showstopper

题意

给定两个序列 \(a, b\)，规定一次操作为任取 \(i\)，交换 \(a_i, b_i\)。输出任意次操作后，是否可以让 \(a_n = \max(a_i), b_n = \max(b_i)\)。

思路

首先，既然最后方案我们无需考虑，那么我们不妨定义 \(a\) 为最小值的序列，\(b\) 为最大值的序列，那么只要满足上面的条件，就是有解，否则无解。

时间复杂度：\(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;
    vector<int> a(n), b(n);
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> b[i];
    if(a[n - 1] > b[n - 1]) swap(a[n - 1], b[n - 1]);
    bool f = true;
    for(int i=0;i<n-1;i++) {
        int mn = min(a[i], b[i]), mx = max(a[i], b[i]);
        if (mn > a[n - 1] || mx > b[n - 1]) f = false;
    }
    cout << (f ? "Yes\n" : "No\n");
}

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

猜结论题 x1

B. Three Sevens

题意

给定 \(n\) 局的参赛情况，在前面一局胜利的玩家不会参与下面的比赛。输出任意一种获胜玩家列表排列。

思路

我们不妨反过来考虑，也就是说，在后面出现的玩家一定不是前面的赢家，那么我们直接倒着遍历即可。

首先，我们遍历参加了该局的玩家，若只要有一个没被标记，那么就是有解的，我们随便输出一个即可。

然后，我们标记参加了该局的玩家，这样即可防止其在前面作为赢家。

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

对应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;
    vector<vector<int>> a(n, vector<int>());
    for(int i=0;i<n;i++){
        int cnt;
        cin >> cnt;
        a[i] = vector<int>(cnt);
        for(int j=0;j<cnt;j++) cin >> a[i][j];
    }
    vector<bool> st(50010, false);
    vector<int> ans(n);
    for(int i=n-1;i>=0;i--){
        bool f = false;
        for(auto e : a[i]){
            if(!st[e]) ans[i] = e, f = true;
            st[e] = true;
        }
        if(!f){
            cout << -1 << '\n';
            return;
        }
    }
    for(auto e : ans) cout << e << ' ';
    cout << '\n';
}

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

这可比A题好做多了

C. Candy Store

题意

给定 \(n\) 组 \(a_i, b_i\)，定义 \(d_i\) 为 \(a_i\) 的因数，\(c_i = b_id_i\)。

构造一组 \(d\)，将 \(c\) 划分为 \(x\) 段值相等的序列，输出 \(x_{\min}\)。

思路

我们来考虑 \(x = 1\) 的情况：

首先，\(c_i = b_id_i\)，也就是说，\(c_i\) 是 \(b_i\) 的倍数。那么，\(c_1 \times c_2 \times \ldots \times c_n\) 是 \(lcm(b_1, b_2, \ldots, b_n)\) 的倍数。

其次，\(d_i\) 是 \(a_i\) 的因数，那么 \(b_id_i\) 就是 \(a_ib_i\) 的因数，也就是说，\(gcd(a_1b_1, a_2b_2, \ldots, a_nb_n)\) 是 \(c_1 \times c_2 \times \ldots \times c_n\) 的倍数。

所以，\(gcd(a_1b_1, a_2b_2, \ldots, a_nb_n) \% lcm(b_1, b_2, \ldots, b_n)=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(){}

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
    }
    int g = 0, l = 1, ans = 1;
    for(int i=0;i<n;i++){
        g = gcd(g, a[i] * b[i]);
        l = lcm(l, b[i]);
        if(g % l != 0){
            ans ++;
            g = a[i] * b[i];
            l = b[i];
        }
    }
    cout << ans << '\n';
}

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

没想到啊没想到...

D. Shocking Arrangement

题意

给定一个总和为 \(0\) 的序列，重新排序这个序列，满足

\(\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert < \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n),\)

若不能满足，输出 \(No\)。

思路

首先，我们定义 \(sum_i\) 为前 \(i\) 个数的前缀和，那么

\(\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert = sum_{\max} - sum_{\min}\)。

那么，我们让 \(sum_{\max} < \max(a_1, a_2, \ldots, a_n), sum_{\min} > \min(a_1, a_2, \ldots, a_n)\) 即可。

如何实现？我们不妨随便放一个数上去，然后记录当前放入的前 \(i\) 个数的和 \(x\)，若 \(x > 0\)，那么我们加上一个负数，直到 \(x \leq 0\)，反之亦然。

考虑到总和为 \(0\)，所以如果 \(x > 0\)，剩余的数的和一定为 \(-x\)，所以后面一定会有几个负数，让 \(x \leq 0\)。

此时，一定有解，而若要判无解，当且仅当整个序列都是 \(0\)。

对细节的证明

思路的第一句话是贪心的（有乱猜的嫌疑）。

为什么呢？因为，\(sum_{\max}\) 不一定在 \(sum_{\min}\) 右边。

或者说，\(S_x, S_y, S_z, Sx>0, S_y < 0, S_z > 0\)，这样的区间要如何保证 \(|S_y| < \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n)\) 呢？

首先，根据思路，\(S_x\) 一定小于等于 \(\max(a_1, a_2, \ldots, a_n)\)，而 \(|S_x| \geq |S_{y-1}|\)，所以

\(|S_y| < \max(a_1, a_2, \ldots, a_n) + abs(\min(a_1, a_2, \ldots, a_n))\)。

因此得证。

时间复杂度：\(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;
    stack<int> p, q;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        if(cur >= 0) p.emplace(cur);
        else if(cur < 0) q.emplace(cur);
    }
    if(q.empty()){
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    int now = 0;
    for(int i=0;i<n;i++){
        if(now <= 0){
            now += p.top();
            cout << p.top() << ' ';
            p.pop();
        }else{
            now += q.top();
            cout << q.top() << ' ';
            q.pop();
        }
    }
    cout << '\n';
}

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

猜结论题 x2