Virtual Participant. Unofficial Rank 382. Solved 4/7.

A. Likes

题意

定义 为一个人对 的”喜欢”状态，当 时，该人对 点了”喜欢”，否则将其撤回了”喜欢”。规定未点喜欢就不能撤回”喜欢”。

给定打乱顺序后的若干人的”喜欢”操作，定义 为进行第 次操作后得到的”喜欢”数量。将操作按一定方案排序，输出让每次操作得到的数量最大和最小的序列 。

思路

首先，若要让数量最少，我们直接在点了”喜欢”后立刻取消即可，那么最后得到的答案会有 个 ， 即为负数的个数。剩余的数只能让 严格递增 。

若要让数量最多，那么我们只需在全部点完后再取消。这时得到一个先递增后递减的序列。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void init(){}

void solve() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int cur;
        cin >> cur;
        if(cur < 0) cnt ++;
    }
    for(int i=1;i<=n-cnt;i++) cout << i << ' ';
    for(int i=1;i<=cnt;i++) cout << n - cnt - i << ' ';
    cout << '\n';
    for(int i=0;i<cnt;i++) cout << "1 0 ";
    for(int i=1;i<=n-2*cnt;i++) cout << i << ' ';
    cout << '\n';
}

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

瞎模拟即可

B. Settlement of Guinea Pigs

题意

给定一个操作序列，定义操作为下面任选一：

1. “1”表示引入一个未知性别的猪，按规则放入一个栅栏内；

2. “2”表示确定所有已经引入的猪的性别，按照规则重新排列。

定义一个栅栏内的猪性别需一致，且最多有两个猪。

输出最后需要至少多少个不同的栅栏。

思路

首先，在不知道性别的时候，新引入的猪只能单独放到一个栅栏内。

其次，若知道了性别，那么我们需要对奇偶性分类讨论：

1. 若为奇数，那么母猪和公猪的数量一定为一个偶一个奇，那么当前就需要 总数量 个栅栏

2. 若为偶数，那么会出现两个偶数或两个奇数的可能，但我们不能确定为哪一种情况，所以我们考虑大的那个数量，也就是两个奇数的情况。这个时候，我们需要 总数量 个栅栏。

最后，对于每次操作，计算并统计最大值即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void init(){

}

void solve() {
    int n;
    cin >> n;
    int sum = 0, num = 0;
    int ans = 0;
    for(int i=0;i<n;i++){
        int cur;
        cin >> cur;
        if(cur == 1){
            sum ++, num ++;
            ans = max(ans, num);
        }else{
            if(sum == 0) num = 0;
            else num = (sum + 1 + (1 - sum % 2)) / 2;
            ans = max(ans, num);
        }
    }
    cout << ans << '\n';
}

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

怎么奇数的情况搞错了（（

C. The Very Beautiful Blanket

题意

定义美丽矩阵满足下面的要求：

1. 规模 ；

2. $A{11} \oplus A{12} \oplus A{21} \oplus A{22} = A{33} \oplus A{34} \oplus A{43} \oplus A{44}$；

3. $A{13} \oplus A{14} \oplus A{23} \oplus A{24} = A{31} \oplus A{32} \oplus A{41} \oplus A{42}$

给定一个矩阵的规模，规模大于等于 ，构造一个矩阵，使得所有 的子矩阵均为美丽矩阵，且不同元素的数量最大。输出不同数字的数量，以及对应的一个矩阵。

思路

首先，值得留意的是：。那么，我们不妨构造这样的子矩阵：

有趣的是， （巧了我不会证），那么我们不妨按照上面的矩阵依次排满第一行，然后找到大于所用过的数的第一个为 的倍数的数，继续按照上面的矩阵排列即可。那么，任意找出一个子矩阵，结果都为 。

考虑到数据量，我们不妨让第 行的起始数字为 ，会让程序更好写。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void init(){

}

void solve() {
    int n, m;
    cin >> n >> m;
    cout << n * m << '\n';
    for(int i=0;i<n/2;i++){
        int offset = i * 512;
        for(int j=0;j<m/2;j++) {
            cout << offset << ' ' << (offset + 1) << ' ';
            offset += 4;
        }
        if(m % 2 == 1) cout << offset << ' ';
        cout << '\n';
        offset = i * 512 + 2;
        for(int j=0;j<m/2;j++) {
            cout << offset << ' ' << (offset + 1) << ' ';
            offset += 4;
        }
        if(m % 2 == 1) cout << offset << ' ';
        cout << '\n';
    }
    if(n % 2 == 1){
        int offset = n / 2 * 512;
        for(int j=0;j<m/2;j++) {
            cout << offset << ' ' << (offset + 1) << ' ';
            offset += 4;
        }
        if(m % 2 == 1) cout << offset << ' ';
        cout << '\n';
    }
}

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

不会证，但会猜（（（

D. Buying gifts

题意

给定 个商店，第 个商店具有 两个价格。规定每个商店均需要买一个商品，为 买第 个商店的物品花费 元，为 买第 个商店的物品花费 元。输出所有方案中为 买的商品的最大价格 和为 买的商品的最大价格 的差值的绝对值的最小值，即 。

思路

首先，我们不可能去枚举所有的方案，那么我们至少需要一个 复杂度的解法。

我们可以枚举为 买的商品的最大值，也就是枚举所有的 ，将其作为当前的最大值，那么大于 数对应的商品只能给 。

接着，我们可以二分查找 去除第 个商店后 剩余商店中的 所有 中 和 最近的两个数。若我们可以将这个数作为 的最大值，也就是说，所有大于 的数对应的 不能大于 ，那么更新差值的最小值。当然，有可能两个数都不满足，但是当前 中可以用的最大值依然可以和 减，他是有可能作为答案的。

对数复杂度的删除和查询，最佳之选就是 。

而为了让上述操作更方便，我们不妨按 降序排序，那么，之前遍历过的 一定是要放到 里去的，而这些数也肯定不能在二分查找的范围内的，因而我们在遍历的时候，顺便记录前 个商店中 的最大值 ，按照上面的分析执行即可。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void init(){

}

void solve() {
    int n;
    cin >> n;
    multiset<int> a;
    vector<pii> q(n);
    for(int i=0;i<n;i++) cin >> q[i].first >> q[i].second;
    sort(q.begin(), q.end());
    for(auto e : q) a.emplace(e.second);
    a.emplace(inf);
    int ans = inf, mx = -inf;
    for(int i=n-1;i>=0;i--){
        ans = min(ans, abs(q[i].first - mx));
        a.erase(a.find(q[i].second));
        auto it = a.lower_bound(q[i].first);
        if(*it != inf) {
            if (q[i].first >= mx) ans = min(ans, abs(*it - q[i].first));
        }
        if (it != a.begin() && q[i].first > mx) ans = min(ans, abs(*(--it) - q[i].first));
        mx = max(mx, q[i].second);
    }
    cout << ans << '\n';
}

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

整个人升华了（划掉