Contestant. Rank 3134. Rating -36.

坐大牢局

A. Showstopper

题意

给定两个序列 ，规定一次操作为任取 ，交换 。输出任意次操作后，是否可以让 。

思路

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

时间复杂度：

对应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

题意

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

思路

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

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

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

时间复杂度：

对应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

题意

给定 组 ，定义 为 的因数，。

构造一组 ，将 划分为 段值相等的序列，输出 。

思路

我们来考虑 的情况：

首先，，也就是说， 是 的倍数。那么， 是 的倍数。

其次， 是 的因数，那么 就是 的因数，也就是说， 是 的倍数。

所以， 就是其能成为一段区间的条件。

显然，如果一个元素能划分到前面的序列中，那么我们完全可以不考虑它，因为就算把他放进来，不影响数量。

因此，我们可以贪心地直接遍历统计个数。

时间复杂度：

对应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

题意

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

$\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),$

若不能满足，输出 。

思路

首先，我们定义 为前 个数的前缀和，那么

$\max\limits{1 \le l \le r \le n} \lvert a_l + a{l+1} + \ldots + ar \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)$ 即可。

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

考虑到总和为 ，所以如果 ，剩余的数的和一定为 ，所以后面一定会有几个负数，让 。

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

对细节的证明

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

为什么呢？因为，$sum{max}sum{min}$ 右边。

或者说，，这样的区间要如何保证 呢？

首先，根据思路，$Sx\max(a_1, a_2, \ldots, a_n)|S_x| \geq |S{y-1}|$，所以

。

因此得证。

时间复杂度：

对应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