02-07 15:01 羽丘女子学园 C++ 发布于福建

关注

牛客寒假营第三场题解

宙天

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

牛客寒假营第三场题解

签到：A

easy：B、G、J

mid：C

hard：F、H

防AK：D、E、I

shit：D、H

alt

前言

本来以为兰子的题会比较简单，但是今年兰子出的也好难，寄！

还以为是良心出题人，原来是凉心出题人啊。总而言之，是非常神秘的一场，大家可以期待一下下一场。

前五题非常顺利，后五题一个比一个折磨，感觉做起来非常痛苦。

前五题不到半小时全是 1 发AC ，然后开计算几何，发现是计算几何后就关了，然后开博弈，发现样例都不懂。

最小生成树终于有了点思路，但是WA了好几发于是放弃。

连线是之前就看过的题，所以大概知道怎么做，但是画L之后WA了。

然后回去看博弈发现读错题了，正确题意想了一会就过了。

构造题一开始也不会，但是看到他们在说**（已删除），立马就想到了（已删除），修改完假的（已删除）**板子后就过了。

然后去写计算几何，输出位数少了，调了半天才过。

再回去调连线，一直WA，写了发网络流还是WA，最后对拍了好久之后终于发现了hack，调了一下过了。

第二天晚上想到了生成树的正确做法，终于过了，呜呜呜。

昨天晚上，兰子紧急将基于（已删除）的构造题换成了基于线性基的构造题。

在28点时，我重新验证了换上去的新题，并修改这份题解。。。。。。。。。。。。。

A 宙天

签到

数据范围最多只有 $100$ ，符合要求的只有 $2,6,12,20,30,42,56,72,90$ 。

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

#include<bits/stdc++.h>

using namespace std;

int main(){
    int x;
    cin >> x;
    for(int i = 1; i <= 10; i++){
        if(x != i * (i + 1)) continue;
        cout << "YES" << endl;
        return 0;
    }
    cout << "NO" << endl;
}

B Random

随机化、概率论

由于数据是随机生成的，因此我们随机选两个数同时为 $2$ 的倍数的概率大概是 $1/4$ ；同时为 $3$ 的倍数的概率大概是 $1/9$ 。

因此我们随机 $1000$ 次几乎能百分百可以成功。

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

#include<bits/stdc++.h>

using namespace std;

int main(){
   mt19937 rd(time(0));
   int T;
   cin >> T;
   while(T--){
       int n;
       cin >> n;
       vector<int> a(n + 1);
       for(int i = 1; i <= n; i++){
           cin >> a[i];
       }
       for(int i = 1; i <= 1000; i++){
           int x = rd() % n + 1;
           int y = rd() % n + 1;
           if(x == y) continue;
           if(gcd(a[x], a[y]) > 1){
               cout << a[x] << " " << a[y] << endl;
               goto end;
           }
       }
       cout << -1 << endl;
       end:;
   }
}

C Inverted World

字符串

一个比较显然的结论是：最终的字符串只会有两种可能性，分别是 $``01010...",``10101..."$ 。

如果我们确定最终字符串 $t$ 的形态，接下来要做的就是如何得到操作的次数。

很显然当 $s_i \neq t_i$ 的时候，位置 $i$ 需要操作奇数次，否则位置 $i$ 需要操作偶数次。手动模拟几个字符串后可以发现，奇数只会是 $1$ ，偶数只会是 $0$ 。

因此我们可以将需要操作的位置拿出来，并按照 $s_i$ 的值分类。我们可以将相邻的同类操作合并在一起形成一个跟操作次数有关的序列，然后一次操作我们可以在序列的每一项中选择一个位置进行操作。

操作序列所有项的最小值次后，序列将会变化。不断重复序列的操作可以将序列清空，并求出次数。

由于最后 $t$ 有两种形态，因此最后的答案是两种形态所需操作次数的最小值。

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

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        string s;
        cin >> s;
        auto get = [&](string t){
            vector<array<int, 2>> stk;
            for(int i = 0; i < n; i++){
                if(s[i] == t[i]) continue;
                if(!stk.size() || stk.back()[1] != s[i]) stk.push_back({1, s[i]});
                else stk.back()[0] += 1;
            }
            int ans = 0;
            while(stk.size()){
                auto [mi, _] = *ranges::min_element(stk);
                ans += mi;
                vector<array<int, 2>> ve;
                for(auto &[x, y] : stk){
                    x -= mi;
                    if(!x) continue;
                    if(!ve.size() || ve.back()[1] != y) ve.push_back({x, y});
                    else ve.back()[0] += x;
                }
                stk = ve;
            }
            return ans;
        };
        string t1, t2;
        for(int i = 1; i <= n; i++){
            t1 += '0' + (i & 1);
            t2 += '0' + (~i & 1);
        }
        cout << min(get(t1), get(t2)) << endl;
    }
}

D 系ぎて

搜索、分类讨论、最短路

这是垃圾广告题，想必大家都看过这种垃圾广告。

一个比较暴力的想法是，先连接一对，再暴力判断另一对是否连通，连接第一对的方法可以使用最短路，检查另一对是否连通可以 BFS 或 DFS 。

100    ###
200 -> 20#
021    02#

有一种暴力的不用最短路的连接方式是先将一对连成 $L$ 型，但这会被以下两个样例 hack 掉：

0000    ###0
1212 -> 12#2
0000    0000

0000    0000
2010 -> 2##0
1020    1#20

这个时候我们只需要尝试用某个 $1/2$ 的 $0$ 去与另一个 $1/2$ 连成 $L$ 型就可以了。

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

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector s(n + 2, string(m + 2, '#'));
        map<int, vector<array<int, 2>>> mp;
        for(int i = 1; i <= n; i++){
            cin >> s[i];
            s[i] = "#" + s[i] + "#";
            for(int j = 1; j <= m; j++){
                s[i][j] = 'b' - s[i][j];
                if(s[i][j] < '2') mp[s[i][j]].push_back({i, j});
            }
        }
        auto get = [&](char c, int t, int idx, int ax, int ay){
            auto ss = s;
            auto ve = mp[c];
            ve[idx][0] += ax;
            ve[idx][1] += ay;
            char ch = s[ve[idx][0]][ve[idx][1]];
            if(ch != '2' && ch != c) return 0;
            int x = ve[t][0], y = ve[t ^ 1][1];
            for(int i = ve[0][0]; i <= ve[1][0]; i++){
                if(s[i][y] == (c ^ 1)) return 0;
                ss[i][y] = c;
            }
            auto [l, r] = minmax(ve[0][1], ve[1][1]);
            for(int i = l; i <= r; i++){
                if(s[x][i] == (c ^ 1)) return 0;
                ss[x][i] = c;
            }
            vector<pair<int, int>> d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            int tar = 0;
            auto dfs = [&](auto dfs, int x, int y) -> void{
                for(auto &[dx, dy] : d){
                    int xx = x + dx;
                    int yy = y + dy;
                    if(array<int, 2>{xx, yy} == mp[c ^ 1][1]) tar = 1;
                    if(ss[xx][yy] != '2') continue;
                    ss[xx][yy] = c ^ 1;
                    dfs(dfs, xx, yy);
                }
            };
            dfs(dfs, mp[c ^ 1][0][0], mp[c ^ 1][0][1]);
            return tar;
        };
        int ans = 0;
        vector<pair<int, int>> d = {{0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for(auto &[x, y] : d){
            for(int i = 0; i <= 1; i++){
                ans |= get('0', 0, i, x, y);
                ans |= get('0', 1, i, x, y);
                ans |= get('1', 0, i, x, y);
                ans |= get('1', 1, i, x, y);
            }
        }
        if(ans) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

E 躯树の墓守

构造、最小生成树、Prim

还记得我在第一场写过 Prim 算法的过程吗？最小生成树上的边一定是连接左右两个点集中权值最小的边。

因此如果我们固定了一组最小生成树上的边权，定义在最小生成树上的边为好边，其他边为坏边，每条好边在当时都必须是从左边点集连向右边点集的。

不妨令从小到大第 $i$ 条好边的左端点为 $1$ ，右端点为 $1 + i$ ，那边权比第 $i$ 条好边小的坏边两个端点都必须在左边点集。（如果在一个在左一个在右则这条边应该在最小生成树上，不符合这是坏边的定义。如果两个都在右边点集，假设两个点分别是 $u, v(u<v)$ ，在连接第 $u-1$ 条好边 $(1,u)$ 后，坏边 $(u, v)$ 权值小于好边 $(1, v)$ 权值，不符合 $(1,v)$ 是好边的定义）

如果要使得最小生成树的权值尽可能小，那么一定是将前 $n-1$ 条边将都变成好边，权值分别是 $1, 2, 3, 4, 5, ...$ 。

如果要使得最小生成树的权值尽可能大，那么一定是在左边点集塞不下坏边的时候，才去增加好边。也就是当左边点集变成完全图后，才去扩充点集大小，好边的权值分别是 $1, 2, 4, 7, 11, 16...$ 。但由于这张图边数有限，因此我们要将后面边权超出 $m$ 的边缩小到 $m$ 之内，也就是说最后一些边是 $..., m - 3, m - 2, m - 1, m$ 。

如果要求构造的生成树权值不在最小到最大的区间中，那一定无解，否则一定有解。

先将最大、最小的权值所包含的每一条边的边权都算出来变成两个集合，接下来我们需要将最大的权值缩小，可以将最大集合中每一条边往最小集合中靠，直到权值变成 $k$ 。

最后，按照上面的做法，将好边 $(1, i)$ 连接，坏边在左边点集两两相连后，就构造完成了。

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

#include<bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m, k;
        cin >> n >> m >> k;
        LL sum = 0;
        vector<LL> ve;
        for(LL i = 1, t = 1; i <= n - 1; t += i++){
            ve.push_back(t);
            sum += t;
        }
        int l = m;
        for(auto &i : ve | views::reverse){
            if(i > l){
                sum -= i - l;
                i = l;
                l--;
            }
        }
        if(k > sum || k < 1ll * n * (n - 1) / 2){
            cout << "NO" << endl;
            continue;
        }
        vector<int> s(m + 1);
        l = 1;
        for(auto &i : ve){
            if(sum > k){
                int t = min(i - l, sum - k);
                sum -= t;
                i -= t;
            }
            s[i] = 1;
            l++;
        }
        cout << "YES" << endl;
        for(int i = 1, x = 3, y = 1, cnt = 1; i <= m; i++){
            if(s[i]) cout << format("1 {} {}", cnt, i) << endl;
            else{
                y++;
                if(y >= x){
                    x++;
                    y = 2;
                }
                cout << format("{} {} {}", y, x, i) << endl;
            }
        }
    }
}

F Energy Synergy Matrix

博弈

快去请巴巴博弈大神……

R表示小红
P表示小紫
####P
00R##

####P00R##
00R######P

####P00R######P00R##
00R######P00R######P

每次这样循环即可，可以发现接下来任意一个地方放上字母都无法影响路径。

因此列数每增加 $5$ ，拐弯次数就会增加 $1$ 。

至于为啥是正确的呢？那我就不知道了。

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

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        cout << n - 1 + n / 5 << endl;
    }
}

G スピカの天秤

枚举、排序、分类讨论

如果天秤是平衡的，那么显然只要拿走一个就不平衡了。

如果天秤是不平衡的，我们每次从重的那边拿走砝码直到状态改变就行了，贪心的想法就是重的先拿。

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

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector<int> a(n + 1), b(m + 1);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        for(int i = 1; i <= m; i++){
            cin >> b[i];
        }
        ranges::sort(a);
        ranges::sort(b);
        auto sa = accumulate(a.begin(), a.end(), 0ll);
        auto sb = accumulate(b.begin(), b.end(), 0ll);
        if(sa == sb){
            cout << 1 << endl;
            continue;
        }
        if(sa < sb){
            swap(a, b);
            swap(sa, sb);
        }
        int ans = 0;
        while(sa > sb){
            sa -= a.back();
            a.pop_back();
            ans++;
        }
        cout << ans << endl;
    }
}

H Tic Tac DREAMIN’

计算几何、分类讨论

AI有一个神秘的叉乘做法，看不懂。。。。。寄算寄何真恶心。接下来是基于初中数学的做法。

如果线段平行于 $x$ 轴，那么三角形的底和高都是固定的，面积也是固定，检验一下是否为 $2$ 就行。

如果线段垂直于 $x$ 轴，那么三角形底确定了，只需要用公式算出高就可以了。

一般情况：可以先求出底的长度，然后通过计算得到高；用 $\Delta x, \Delta y$ 得到直线与 $x$ 轴的夹角；用夹角和高算出在 $x$ 轴上的偏移量；最后通过点和夹角可以算出直线与 $x$ 轴的交点加上偏移量即可。

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

#include<bits/stdc++.h>
 
using namespace std;
 
const long double eps = 1e-8;
 
int main(){
    vector p(2, array<long double, 2>());
    auto &[x0, y0] = p[0];
    auto &[x1, y1] = p[1];
    cin >> x0 >> y0;
    cin >> x1 >> y1;
    ranges::sort(p);
    auto dx = x1 - x0;
    auto dy = y1 - y0;
    if(abs(dy) <= eps){
        if(4 - eps <= dx * abs(y0) && dx * abs(y0) <= 4 + eps) cout << 0 << endl;
        else cout << "no answer" << endl;
        return 0;
    }
    if(abs(dx) <= eps){
        cout << setprecision(15) << x0 + 4 / dy << endl;
        return 0;
    }
    auto th = atan(dy / dx);
    auto h = 4 / sqrtl(dx * dx + dy * dy);
    auto l = h / sin(th);
    auto x = x0 - y0 / dy * dx;
    cout << setprecision(15) << x + l << endl;
}

I BenzenE

构造、线性基

本题题解于2月6日28点写完，因此可能不够清晰。

如果这道题值域小于 $2^{10}$ ，那这题可以用 DP 加上路径还原，但这个值域有点过大了，显然不是很能 DP 。

思考异或相关的算法，无非是 01-Trie 和线性基，这题看上去似乎更靠近是否能用很多个数表示一个数，线性基的概率更大。

如果我们直接用 $a$ 数组构造答案，会发现异或出了一个结果 $sum$ ，我们如果可以通过将一些 $a_i$ 替换成 $b_i$ 使得 $sum$ 归 $0$ ，那这道题似乎就写完了。

思考一下将 $a_i$ 替换成 $b_i$ 的过程，相当于是在 $sum$ 中去掉一个 $a_i$ 再异或一个 $b_i$ ，实际上也可以认为 $sum := sum \oplus a_i \oplus b_i$ （两个 $a_i$ 互相消去）。

也就是说，我们希望用一些 $a_i \oplus b_i$ 组成 $sum$ ，那这就是一个很典型的线性基板子了，对着板子改一下就能过了。

我的板子好像有点烂，记录路径还原时似乎多了个 $logA$ 。

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

#include<bits/stdc++.h>

using namespace std;

template<typename T>
class XXJ{
public:
    int n;
    vector<T> a;
    vector<set<T>> in;

    XXJ(int _n) : n(_n), a(n + 1){
        in.resize(n + 1);
    }
    
    void merge(auto &a, auto &b){
        for(auto &i : b){
            if(a.count(i)) a.erase(i);
            else a.insert(i);
        }
    }

    int insert(T x, T t){
        set<T> v = {t};
        for(int i = n; i >= 0; i--){
            if(!((x >> i) & 1)) continue;
            if(a[i]){
                x ^= a[i];
                merge(v, in[i]);
            }
            else{
                a[i] = x;
                in[i] = v;
                return 1;
            }
        }
        return 0;
    }

    vector<T> check(T x){
        set<T> ans;
        for(int i = n; i >= 0; i--){
            if(!((x >> i) & 1)) continue;
            if(a[i]){
                x ^= a[i];
                merge(ans, in[i]);
            }
            else return {};  
        }
        return vector(ans.begin(), ans.end());
    }
};

int main(){
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 1), b = a;
        int sum = 0;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            sum ^= a[i];
        }
        auto c = a;
        XXJ<int> xxj(32);
        for(int i = 1; i <= n; i++){
            cin >> b[i];
            xxj.insert(b[i] ^ a[i], i);
        }
        auto ans = xxj.check(sum);
        if(sum && ans.size() == 0){
            cout << -1 << endl;
            continue;
        }
        for(auto &i : ans){
            c[i] = b[i];
        }
        for(int i = 1; i <= n; i++){
            cout << c[i] << " ";
        }
        cout << endl;
    }
}

J Branch of Faith

树、数据结构

首先要知道完全二叉树的定义，不知道的可以搜一下试试。

首先可以发现树的层数不超过 $64$ ，每一层的节点编号是连续递增的。

我们可以求出每层的节点数量，以及每层最后一个节点的编号大小。

然后每次查询时，从低往高层枚举，当点的编号小于等于这层最后一个节点的编号时，就得到了答案。

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

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T;
    cin >> T;
    while(T--){
        auto n = 0ll;
        int q;
        cin >> n >> q;
        vector<array<long long, 2>> ve;
        for(auto t = 1ll; n > 0; t <<= 1){
            ve.push_back({min(n, t), t * 2 - 1});
            n -= t;
        }
        while(q--){
            auto x = 0ll;
            cin >> x;
            for(auto &[l, r] : ve){
                if(x <= r){
                    cout << l << endl;
                    break;
                }
            }
        }
    }
}