02-11 18:06 已编辑羽丘女子学园 C++ 发布于福建

关注

牛客寒假营第五场题解

智乃的二进制

https://ac.nowcoder.com/acm/contest/120565/A

牛客寒假营第五场题解

签到：B、J

easy：G

mid：D、E、F

hard：C、H

防AK：A、I

shit：C、I、J

alt

前言

好难，根本不会做！！！！！

A

不会

出题人告诉了我一个结论，然后摆了

时间复杂度： $O()$ 。

B 智乃的瓷砖

模拟

观察可知，横纵坐标奇偶性相同的填 '/' ，奇偶性不同的填 '\' 。

时间复杂度： $O(n \times m)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
   int n, m;
   cin >> n >> m;
   for(int i = 1; i <= n; i++){
       for(int j = 1; j <= m; j++){
           cout << "/\\"[(i ^ j) & 1];
       }
       cout << endl;
   }
}

C 智乃的草坪

计算几何、贪心、二分

首先我们需要发现答案可以二分，也就是当时间大于某个临界值之后，一定都是可行的，而这个临界值就是答案。

然后思考在用 $t$ 的时间时，最少需要几个洒水装置可以覆盖整个草坪。

我们需要计算每一个圆，对于草坪的面积贡献是多少呢？直接计算圆和草坪的面积交是很麻烦的，并且也不好处理更多的圆和之前的面积关系。

实际上，圆和草坪相交的面积中，只有矩形那一部分是有意义的，突出来的弧形必然需要其他的圆再覆盖一次，且其他的圆在这个弧形上必然是矩形（如果两个都是弧形，必然有一小部分不被覆盖，如下图绿色部分）。

alt

如下图，当 $r=1,c=4$ 时，实际上只有橙色和蓝色的矩形是有效的。

alt

也就是说，实际上我们只需要计算这个圆和矩形相交得到的图形中矩形部分的面积就可以了。矩形面积也很好算，下图蓝色的为圆半径，黄色的为高，也就是输入的 $r$ ，用勾股定理就可以求出直角三角形的底边长度，这个长度就是矩形的底边长度的一部分。

alt

再观察可以发现，所有矩形的高都是一样的，我们用这些矩形覆盖草坪，实际上就相当于用矩形的底边覆盖一条草坪的长度，也就是输入的 $c$ 。而矩形的底边实际上就是一条条线段，这个问题就转化成了用最少的线段覆盖一条大的线段。

这是一个比较经典的贪心问题，我们将线段按左端点从小到大排序，首先选择在所有左端点小于等于 $0$ 的线段中贪心的选取右端点最大的线段。然后在所有左端点小于等于前一条所选线段右端点的线段中贪心的选取右端点最大的线段，以此类推。如果不存在符合要求的线段，则一定无法覆盖整个线段，若最后一条线段右端点小于草坪的长度 $c$ ，也一定无法覆盖整个线段。

我们每次二分出一个时间 $t$ 后，每一个圆的半径就是 $v_i \times t$ ，然后可以求出线段的左右端点，贪心选择线段后，我们检查选择的线段数了是否不超过 $k$ 即可。

时间复杂度： $O(n \times logn^2)$ 。

#include<bits/stdc++.h>

using namespace std;

using LD = long double;

const LD eps = 1e-8;

int main(){
    int n, k;
    LD R, C;
    cin >> n >> k >> R >> C;
    vector<pair<LD, LD>> ve(n);
    for(auto &[x, y] : ve){
        cin >> x >> y;
    }
    auto get = [&](LD r){
        if(r - eps < R) return (LD)-1;
        return sqrtl(r * r - R * R);
    };
    auto check = [&](LD t){
        vector<array<LD, 2>> seg;
        for(auto &[p, v] : ve){
            auto dx = get(v * t);
            if(dx < 0) continue;
            seg.push_back({p - dx, p + dx});
        }
        ranges::sort(seg);
        LD l = 0, r = 0;
        int cnt = 0;
        for(auto &[x, y] : seg){
            if(x <= l + eps) r = max(r, y);
            else{
                if(r < x - eps) return 0;
                l = r;
                r = max(r, y);
                cnt++;
            }
        }
        if(l < C - eps) cnt++;
        if(r < C - eps) return 0;
        if(cnt <= k) return 1;
        return 0;
    };
    LD l = 0, r = 1e12;
    for(int _ = 1; _ <= 100; _++){
        LD mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << setprecision(20) << l << endl;
}

D 智乃的果子

Huffman树、STL

一个经典的 Huffman 树问题，不过这棵树的点数有亿点多。

回忆一下我们 Huffman 树的过程，每次找两个权值最小的点，将它们合并成权值为两个点权值之和的新点。

由于有很多权值相同的点，因此我们可以将权值相同的点放在一起，初始时权值本质不同的点的种数显然不会超过 $n$ 。

且这个东西还需要能找到全局的最小值，于是我们想到了堆。

我们每次需要找两个权值最小的点，首先我们可以用堆顶找到当前最小的权值并删除堆顶，如果这个权值有很多个点，很显然我们可以将点两两合并后丢进堆里，使得最后剩余 $0$ 或 $1$ 个点。若最后剩余 $1$ 个点，我们可以再从堆顶找到新的最小的权值，将之前剩余的点和新点进行合并后丢进堆里即可。

由于初始时有 $n$ 种点，在一轮合并完成后，最多只有 $2n$ 种点，然后这 $2n$ 种点经过合并也只会有 $2n$ 种点（产生新点需要消耗两个不同的点，由于上一次由两个不同的点合并出来的点每种只会有一个，因此限制了新点的数量），因此同时存在的点的种数不会太多。

且一轮合并至少会减少一半的点，因此合并的轮数是 $log(\sum_{i=1}^n c_i)$ 轮的。

时间复杂度： $O(n \times \log(\sum_{i=1}^n c_i) \times logn)$ 。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

const LL M = 1e9 + 7;

int main(){
    int n;
    cin >> n;
    map<LL, LL> mp;
    LL cnt = 0, ans = 0;
    for(int i = 1; i <= n; i++){
        int c, w;
        cin >> c >> w;
        mp[w] += c;
        cnt += c;
    }
    while(cnt > 1){
        auto [x, y] = *mp.begin();
        mp.erase(mp.begin());
        if(y > 1){
            mp[x * 2] += y / 2;
            ans = (ans + (x * 2 % M) * (y / 2 % M)) % M;
            cnt -= y / 2;
            if(y % 2 == 0) continue;
        }
        auto &[x1, y1] = *mp.begin();
        mp[x1 + x] += 1;
        ans = (ans + x1 + x) % M;
        cnt--;
        y1--;
        if(!y1) mp.erase(mp.begin());
    }
    cout << ans << endl;
}

E 智乃的最大子段和取模

STL、贪心、前缀和、二分

思考一下最大子段和怎么做，先对数组做一个前缀和 $f$ ，然后枚举右端点 $r$ ，每次找到前缀和最小的左端点 $min(f_l)$ 就可以了，从前往后时使用一个变量维护 $f$ 的前缀最小值就可以了。

那现在我们需要取模后的最大子段和，也就是求 $(f_r - f_l) \% p$ 的最大值。

可以类似普通的最大子段和，枚举每一个 $r$ ，求出第一个大于 $f_r \% p$ 的 $f_l \% p$ ，若不存在则求全局最小的 $f_l \% p$ ，就可以最大化 $(f_r - f_l) \% p$ 了。

求出第一个大于 $f_r \% p$ 的 $f_l \% p$ ，可以从前往后加入 $f_r$ 后使用 $set$ 或 $map$ 中的二分。

时间复杂度： $O(n \times logn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, p;
    cin >> n >> p;
    map<int, int> mp;
    mp[0] = 0;
    int sum = 0;
    array<int, 3> ans = {-1, 0, 0};
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        sum = (sum + x) % p;
        auto it = mp.upper_bound(sum);
        if(it == mp.end()) it = mp.begin();
        auto &[l, r] = *it;
        array<int, 3> arr = {(sum - l + p) % p, r, i - 1};
        ans = max(ans, arr);
        mp[sum] = i;
    }
    cout << format("{} {} {}", ans[1], ans[2], ans[0]) << endl;
}

F 智乃的算法竞赛群友

字符串、DP、分类讨论、贪心、矩阵快速幂

包含公共部分只可能是 $``qcjjkktd"$ ，那很显然每次给字符串加后缀只有三个选择，那可以写出一个比较显然的 DP 状态转移。

dp[i] = max({dp[i - 1], dp[i - 2] + b, dp[i - 7] + a, dp[i - 8] + a + b);

但是由于字符串长度有 $10^9$ ，因此直接 DP 很显然是行不通的，不过我们直接使用矩阵快速幂暴力优化这个 DP 。

观察上面的转移方程，可以转化成：

dp[i] = dp[i - 56] + max({b * 28, a * 8, (a + b) * 7});

实际上这个 DP 并不需要暴力转移，直接做除法就行了。但是我们字符串长度不足 56 时怎么办呢？很显然是无法转移，就可以用第一个暴力的方式去转移。

然后交上去 or 认真观察就会发现，这份代码在长度为 $56n+6$ 的时候（还有一些其他情况），是有可能出错的。如果 $qcjjkktd$ 是最优解，最后剩余 $6$ 个字符，只能填 $3$ 个 $td$ ，而如果将结尾的 $qcjjkktd$ 删除剩下 $14$ 个字符，改成两个 $qcjjkkt$ ，也许答案会更优。

因此我们最后留下至少 $56$ 个字符用来暴力 DP ，才会是正确的。

时间复杂度： $O(T \times C)$ 。

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){
    int T;
    cin >> T;
    while(T--){
        LL n, a, b;
        cin >> n >> a >> b;
        LL ans = 0;
        if(n > 112){
            ans += (n / 56 - 1) * max({b * 28, a * 8, (a + b) * 7});
            n -= 56 * (n / 56 - 1);
        }
        vector<LL> f(n + 1);
        for(int i = 1; i <= n; i++){
            if(i >= 2) f[i] = max(f[i], f[i - 2] + b);
            if(i >= 7) f[i] = max(f[i], f[i - 7] + a);
            if(i >= 8) f[i] = max(f[i], f[i - 8] + a + b);
        }
        ans += f[n];
        cout << ans << endl;
    }
}

G 智乃的箭头魔术

模拟、找规律

找规律，按题意模拟即可。

首先最后两种操作对于状态无非是加一或是减一后对 $4$ 取模。

$0$ 操作会将 $(0, 3), (1, 2)$ 互换，相当于是异或 $3$ 。

$1$ 操作会将 $(1, 3)$ 互换， $(0, 2)$ 不变，相当于是对奇数异或 $2$ 。

$2$ 操作会将 $(0, 1), (2, 3)$ 互换，相当于是异或 $1$ 。

$3$ 操作会将 $(0, 2)$ 互换， $(1, 3)$ 不变，相当于是对偶数异或 $2$ 。

时间复杂度： $O(1)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    string s = "01122334451420153201254102145302145102141023";
    s += "02142025101203201451451522302514203214510021454101002532";
    int tar = 0;
    for(auto &i : s){
        if(i == '0') tar ^= 3;
        if(i == '1' && (tar & 1)) tar ^= 2;
        if(i == '2') tar ^= 1;
        if(i == '3' && !(tar & 1)) tar ^= 2;
        if(i == '4') tar = (tar + 1) % 4;
        if(i == '5') tar = (tar + 3) % 4;
        cout << tar;
    }
    cout << endl;
}

H 智乃的矩阵

guess、找规律

首先最容易发现的一点是：每次操作不改变矩阵的总和，因此矩阵总和必须是 $n^2$ 的倍数，否则无解。

进一步发现：每次操作 $2 \times 2$ 矩阵的两条对角线上的数字之和一定是 $0$ ，因此矩阵就类似国际象棋的棋盘，黑色/白色的点的数字之和不会改变。

还可以发现：每次操作 $2 \times 2$ 矩阵的两行两列数字之和都是偶数，因此每行每列的奇偶性无法改变。

然后就过了，为什么呢？完全不知道呢。

想过网络流和高斯消元，但是没想到网络流怎么写，高斯消元的方程不够，寄。

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

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){
    int n;
    cin >> n;
    vector a(n + 1, vector<int>(n + 1));
    LL sum = 0, sum1 = 0, sum2 = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
            sum += a[i][j];
            if(i % 2 == j % 2) sum1 += a[i][j];
            else sum2 += a[i][j];
        }
    }
    int l = n * n + 1 >> 1;
    int r = n * n >> 1;
    vector<LL> R(n + 1), C(n + 1);
    if(sum % (n * n)) goto no;
    if(sum1 % l) goto no;
    if(r && sum2 % r) goto no;
    if(r && sum1 / l != sum2 / r) goto no;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] -= sum / n / n;
            R[i] += a[i][j];
            C[j] += a[i][j];
        }
    }
    for(auto &i : R){
        if(i & 1) goto no;
    }
    for(auto &i : C){
        if(i & 1) goto no;
    }
    cout << "Yes" << endl;
    if(0) no: cout << "No" << endl;
}

I 智乃挖坑

数据结构、二分、差分、线段树

首先观察，可以发现实际上的操作是变成两个区间加等差数列。

火箭背包毛毛虫做法：写一棵区间加等差数列的线段树就可以了。（强烈建议补题的时候写一下）

智慧做法：显然答案具有二分性，因此我们可以二分答案。然后就是离线加等差数列就是二次差分，再写一写就过了。

维护区间加等差数列的求和问题 - _Ackerman - 博客园

时间复杂度： $O(n \times logn)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    auto h = 0ll;
    cin >> n >> m >> h;
    vector<pair<int, int>> ve(m);
    for(auto &[p, f] : ve){
        cin >> p >> f;
    }
    auto check = [&](int cnt){
        vector a(n + 3, 0ll), d1 = a, d2 = a, d3 = a;
        for(int i = 0; i < cnt; i++){
            auto &[p, f] = ve[i];
            int l = max(1, p - f + 1);
            int r = min(n, p + f - 1);
            d1[l] += f;
            d1[r + 1] -= f;
            if(f > 1){
                d2[p + 1] -= 1;
                d2[r + 1] += r - p + 1;
                d2[r + 2] -= r - p;
                d3[p - 1] -= 1;
                d3[l - 1] += p - l + 1;
                if(l - 2 >= 0) d3[l - 2] -= p - l;
            }
        }
        for(int i = 1; i <= n; i++){
            d1[i] += d1[i - 1];
            d2[i] += d2[i - 1];
        }
        for(int i = n; i >= 1; i--){
            d3[i] += d3[i + 1];
        }
        for(int i = n; i >= 1; i--){
            d3[i] += d3[i + 1];
        }
        for(int i = 1; i <= n; i++){
            d2[i] += d2[i - 1];
            d1[i] += d2[i] + d3[i];
            if(d1[i] > h) return 1;
        }
        return 0;
    };
    int l = 1, r = m;
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    if(check(l)) cout << format("Yes\n{}", l) << endl;
    else cout << "No" << endl;
}

J 智乃的幻方

模拟

按题意模拟，计算每一行、每一列、每一对角线之和是否相等以及是否为排列即可。

时间复杂度： $O(1)$ 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    array<array<int, 3>, 3> a;
    int tar = 0;
    for(auto &i : a){
        for(auto &j : i){
            cin >> j;
            tar |= 1 << j;
        }
        if(accumulate(i.begin(), i.end(), 0) != 15) goto no;
    }
    if(tar != 1022) goto no;
    for(int j = 0; j < 3; j++){
        int sum = 0;
        for(int i = 0; i < 3; i++){
            sum += a[i][j];
        }
        if(sum != 15) goto no;
    }
    if(a[1][1] != 5) goto no;
    if(a[0][0] + a[2][2] != 10) goto no;
    if(a[0][2] + a[2][0] != 10) goto no;
    cout << "Yes" << endl;
    if(0) no: cout << "No" << endl;
}