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

A. Likes

题意

定义 \(a_i\) 为一个人对 \(|a_i|\) 的"喜欢"状态，当 \(a_i > 0\) 时，该人对 \(|a_i|\) 点了"喜欢"，否则将其撤回了"喜欢"。规定未点喜欢就不能撤回"喜欢"。

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

思路

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

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

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

对应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"表示引入一个未知性别的猪，按规则放入一个栅栏内；
"2"表示确定所有已经引入的猪的性别，按照规则重新排列。

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

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

思路

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

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

若为奇数，那么母猪和公猪的数量一定为一个偶一个奇，那么当前就需要 \((\)总数量\(+1)/2\) 个栅栏
若为偶数，那么会出现两个偶数或两个奇数的可能，但我们不能确定为哪一种情况，所以我们考虑大的那个数量，也就是两个奇数的情况。这个时候，我们需要总数量\(/2+1\) 个栅栏。

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

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

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

题意

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

规模 \(4 \times 4\)；
\(A_{11} \oplus A_{12} \oplus A_{21} \oplus A_{22} = A_{33} \oplus A_{34} \oplus A_{43} \oplus A_{44}\)；
\(A_{13} \oplus A_{14} \oplus A_{23} \oplus A_{24} = A_{31} \oplus A_{32} \oplus A_{41} \oplus A_{42}\)

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

思路

首先，值得留意的是：\(4x \oplus (4x+1) \oplus (4x + 2) \oplus (4x + 3) = 0\)。那么，我们不妨构造这样的子矩阵：

\(\left[ {\begin{array}{cccc} 4x & 4x + 1 \\ 4x + 2 & 4x + 3 \end{array} } \right]\)

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

考虑到数据量，我们不妨让第 \(i\) 行的起始数字为 \(256(i - 1)\)，会让程序更好写。

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

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

题意

给定 \(n\) 个商店，第 \(i\) 个商店具有 \(a_i, b_i\) 两个价格。规定每个商店均需要买一个商品，为 \(A\) 买第 \(i\) 个商店的物品花费 \(a_i\) 元，为 \(B\) 买第 \(i\) 个商店的物品花费 \(b_i\) 元。输出所有方案中为 \(A\) 买的商品的最大价格 \(\max_A\) 和为 \(B\) 买的商品的最大价格 \(\max_B\) 的差值的绝对值的最小值，即 \(\min\{|\max_A - \max_B|\}\)。

思路

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

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

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

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

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

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

对应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();
}

整个人升华了（划掉