寒假营第二场题解

Easy：A、B、F、G

Mid：D、J、K

Hard：C、E、H、M

AK：I、L

前言

本场难度极大，本来mid题还少一题，防AK题多一个，最后时刻紧急撤换了，但是这场难度依然极大。

本场只有C、D稍微有趣一些，原本L有一个启发式合并的做法比较有趣，甚至是当时的std，但是启发式合并的做法在对拍中被hack了。

这场打的时间跨度较大，码量极大，在上面说的那个防AK题下掉之前码量甚至更大，总体来说是一坨*山。打的时候血压很高，典原板的比例有点太高了，不过看上去大家都挺喜欢的。

大家可以期待一下下一场，我还没看下一场的题，但听起来非常克苏鲁。

A 一起奏响历史之音！

模拟

语法题，相当于是判断数组中有没有 4 和 7 。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    vector<int> v(7);
    int ans = 1;
    for(auto &i : v){
        cin >> i;
        if(i == 4 || i == 7) ans = 0;
    }
    if(ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}

B 能去你家蹭口饭吃吗

排序

实际上就是找中位数

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a){
        cin >> i;
    }
    ranges::sort(a);
    cout << a[n >> 1] - 1 << endl;
}

F 一起找神秘的数！

数论

一个比较经典的结论： ，本质就是在 2 进制不同的位置直接加，相同的位置就进位。

那么我们就要找有多少对 满足 ，也就是 。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        auto l = 0ll, r = 0ll;
        cin >> l >> r;
        cout << r - l + 1 << endl;
    }
}

G 一起铸最好的剑！

模拟

如果 ，那么无论提升多少次，温度都是 1 ，所以只需要升温 1 次就行。

如果是其他温度，那么升温次数肯定不会超过 30 ，所以接下来按题目描述模拟即可，但是要注意别爆精度。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        if(m == 1){
            cout << 1 << endl;
            continue;
        }
        pair<int, int> ans = {abs(n - m), 1};
        auto t = 1ll * m;
        int k = 1;
        while(1){
            t *= m;
            k++;
            ans = min(ans, {abs(t - n), k});
            if(t >= n) break;
        }
        cout << ans.second << endl;
    }
}

D 字符串里串

思维、贪心

这题一点都不可爱！

有一个比较容易想到的结论，如果从前往后第 个字符在 之后的第 个位置还出现过，那么选择这 前缀作为子串，子序列就把 和 拼在一起，就得到了两个不一样的子串。

然后把字符串翻转一下，再跑一次即可（从前往后和从后往前都是可以的）。

注意 "aba" 的答案是 0 ，而不是 1 ，之前 std 也错了，不过数据里没有这个，所以不考虑这一个也能过。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = " " + s;
    set<int> st;
    int ans = 0;
    for(int i = n; i >= 2; i--){
        if(st.count(s[i])) ans = max(ans, i);
        st.insert(s[i]);
    }
    st = set<int>();
    for(int i = 1; i <= n - 1; i++){
        if(st.count(s[i])) ans = max(ans, n - i + 1);
        st.insert(s[i]);
    }
    cout << ans << endl;
}

J 数据时间？

模拟

最后时刻紧急加的题，由于牛可乐在演奏不属于 Crychic 的春日影，所以我 Mortis 不做这题（才不是不想写大模拟）。

应该就是按照题面模拟一下就行。

时间复杂度不详。

#include<傻Bushiroad>

using namespace BanG Dream!;

fire sheep(){

	Crychic.erase(Kefu);
	
	Crychic = {Widow};

	using MyGO!!!!! = Crychic;
	
	MyGO!!!!! = {Penguin, Cat, Tang, Widow, Ha?};
	
	MyGO!!!!!.play(Haruhi Kage);
	
	Widow.cry("Why ...... ?");
	
	Widow.cut(MyGO!!!!!);

	MyGO!!!!!.erase(Tang);
	
	MyGO!!!!!.erase(Cat);
	
	MyGO!!!!! = {Sheep};
	
	MyGO!!!!!.insert(Cat);
	
	MyGO!!!!!.insert(Ha?);
	
	Tang.run();
	
	MyGO!!!!!.insert(Tang);
	
	Tang.Unboxing(Widow);
	
	MyGO!!!!!.insert(Widow);
	
	Widow.rename(Soyorin);
	
	if(MyGO!!!!!.rename(Anon Tokyo) == false) Tang.cry();
	
	Cat.cut(dress);
	
	if(MyGO!!!!!.insert(Cucumber) == false){
		cout << "This don't need!" << endl;
		Soyorin.cut(Cucumber);
	}
	

    悴（かじか）んだ心（こころ） ふるえる眼差（まなざ）し世界（せかい）で
    ka ji kan da ko ko ro fu ru e ru ma na za shi se kai de
    憔悴的心 摇曳不定的目光 这世间

    僕（ぼく）はひとりぼっちだった散（ち）ることしか 知（し）らない春（はる）は
    boku wa hitori bocchi da tta chi ru koto shika shi ra nai ha ru wa
    唯我是 孤身一人 这不停凋零的春季

    毎年（まいとし）冷（つめ）たくあしらう
    mai toshi tsu metaku ashi ra u
    每年都只是冷淡地应付

    暗（くら）がりの中（なか） 一方通行（いっぽうつうこうに）ただ ただ
    kuragari no naka ippou tsuukou ni tadatada
    在黑暗深处 单向通行 仅仅 仅仅是

    言葉（ことば）を書（か）き殴（なぐ）って 期待（きたい）するだけ むなしいと分かっていても
    kotoba wo kaki nagutte kitai suru dake munashi to wakatte i te mo
    草草写下话语 仅仅是心怀期待 即便知道一切空虚

    救（すく）いを求（もと）め続（つづ）けた
    sukui wo motome tsuzuke ta
    也在持续寻求着救赎

    せつなくて いとおしい
    setsunaku te itooshii
    苦闷不已 惹人怜悯

    今（いま）ならば分（わ）かる気（き）がする
    ima nara ba wakaru ki ga suru
    若是如今 好像已经明白

    しあわせで くるおしい
    shiawase de kuruoshi
    幸福满溢 宛若疯狂

    あの日（ひ）泣（な）けなかった僕（ぼく）を
    ano hi nake nakatta boku wo
    那天没有哭出来的我

    光（ひかり）は やさしく連（つ）れ立（だ）つよ
    hikari wa yasashiku tsuredatsu yo
    是光芒温柔地与我结伴前行 

    雲間（くもま）をぬって きらり きらり 心満（こころみ）たしては溢（あふ）れ
    kumoma wo nutte kirari kirari kokoro mitashi te wa afure
    穿过彩云之间 闪闪发光 心中满足 似要溢出

    いつしか頬（ほお）を きらり きらり 熱（あつ）く 熱く 濡（ぬ）らしてゆく
    itsushika hoo wo kirari kirari atsuku atsuku nurashi te yuku
    不知何时 脸颊莹莹闪光 炽热地 炽热地将其濡湿

    君（きみ）の手（て）は どうして こんなにも 温（あたた）かいの？
    kimi no te wa doushite konna ni mo atatakai no ?
    你的手心 为何会这样温暖呢？

    ねえ お願（ねが）い　どうかこのまま
    nee onegai douka kono mama
    那个 求求你 请你永远这样

    離（はな）さないでいて
    hanasa nai de i te
    不要离开我的身边


    縁（えん）を結（むす）んではほどきほどかれ誰（だれ）しもが
    en wo musun de wa hodoki hodoka re dareshimo ga
    缔结于人人之间的缘分 却总是分分合合 无论是谁

    それを喜（よろこ）び　悲（かな）しみながら 愛（あい）を数（かぞ）えてゆく
    sore wo yorokobi kanashi mi nagara ai wo kazoe te yuku
    都在其中的欢喜 与悲痛之中 细数那一份又一份的爱意

    鼓動（こどう）を確（たし）かめるように
    kodou wo tashikameru you ni
    似在确认这心脏的搏动

    うれしくてさびしくて
    ureshiku te sabishiku te
    喜悦不已 却又孤寂

    今（いま）だからわかる気（き）がした
    ima da kara wakaru ki ga shi ta
    若是如今 好像已经察觉

    たいせつでこわくって
    taise tsu de kowakutte
    无比重要 却又畏惧

    あの日（ひ）泣（な）けなかった僕（ぼく）を
    ano hi nake nakatta boku wo
    那天没有哭出来的我

    光（ひかり）はやさしく抱（だ）きしめた
    hikari wa yasashiku daki shime ta
    是光芒温柔地与我紧紧相拥

    照（て）らされた世界（せかい）
    terasa re ta sekai
    在这明媚耀眼的世界

    咲（さ）き誇（ほこ）る大切（たいせつ）な人（ひと）
    sakihokoru taisetsu na hito
    绽放着最为重要之人

    あたたかさを知（し）った春（はる）は
    atatakasa wo shitta haru wa
    这春日知晓温暖何来

    僕（ぼく）のため　君（きみ）のための涙（なみだ）を流（なが）すよ
    boku no tame kimi no tame no namida wo nagasu yo
    为我 亦为你 流淌下热泪

    あぁ　なんて眩（まぶ）しいんだろう
    a a nante mabushiin darou u
    啊啊 这是如此耀眼

    あぁ　なんて美（うつく）しいんだろう
    a a nante utsukushiin darou u ...
    啊啊 又是多么迷人

    雲間（くもま）をぬって きらり きらり 心満（こころみ）たしては溢（あふ）れ
    kumoma wo nutte kirari kirari kokoro mitashi te wa afure
    穿过彩云之间 闪闪发光 心中满足 似要溢出

    いつしか頬（ほお）を きらり きらり 熱（あつ）く 熱く 濡（ぬ）らしてゆく
    itsushika hoo wo kirari kirari atsuku atsuku nurashi te yuku
    不知何时 脸颊莹莹闪光 炽热地 炽热地将其濡湿

    君（きみ）の手（て）は どうして こんなにも 温（あたた）かいの？
    kimi no te wa doushite konna ni mo atatakai no ?
    你的手心 为何会这样温暖呢？

    ねえ お願（ねが）い　どうかこのまま
    nee onegai douka kono mama
    那个 求求你 请你永远这样

    離（はな）さないでいて
    hanasa nai de i te
    不要离开我的身边

    ずっと　ずっと
    zutto zutto
    永远 永远

    離（はな）さないでいて
    hanasa nai de i te
    不要离开我的身边
}

K 可以分开吗？

搜索

一道经典的搜索题，BFS、DFS都可以写，就是记录每一块边界的 0 的个数（要记得去重），然后取最小值。

我使用的方法是用一个 记录每一个 0 ，可以直接去重。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector s(n + 2, string(m + 2, '0'));
    for(int i = 1; i <= n; i++){
        cin >> s[i];
        s[i] = "0" + s[i] + "0";
    }
    vector vis(n + 2, vector<int>(m + 2));
    int ans = 1e9;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(vis[i][j]) continue;
            if(s[i][j] == '0') continue;
            set<pair<int, int>> st;
            vector<pair<int, int>> d = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            auto dfs = [&](auto &dfs, int x, int y) -> void{
                vis[x][y] = 1;
                for(auto &[dx, dy] : d){
                    int xx = x + dx;
                    int yy = y + dy;
                    if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
                    if(vis[xx][yy]) continue;
                    if(s[xx][yy] == '0') st.insert({xx, yy});
                    else dfs(dfs, xx, yy);
                }
            };
            dfs(dfs, i, j);
            ans = min(ans, (int)st.size());
        }
    }
    cout << ans << endl;
}

C 字符串外串

构造

首先要知道D题的结论，那我们需要构造一个字符串使得从前往后看和从后往前看可爱度都是 的字符串。

那就思考一下类似回文串的构造方法。

如果 超过了 的两倍，意味着前 个和后 个字母对称（"abcdefcba"），中间 个字母在整个字符串中全都只能出现一次，总共需要的字母种类是 ，很显然字母种类不能超过26个。

如果 不超过 的两倍，意味着前 个和后 个字母对称（"abczzzcba"），中间字母任意，总共需要的字母种类是 ，很显然字母种类不能超过26个。

按上述情况分类讨论构造一下即可。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        int d = n - m;
        if(d == 0 || d > 26){
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;
        string s(n, 'z');
        int t = m;
        if(m * 2 > n) t = d - 1;
        for(int i = 0; i < t; i++){
            s[i] = 'a' + i;
        }
        for(int i = 0; i < t; i++){
            s[n - i - 1] = 'a' + i;
        }
        if(m * 2 <= n){
            for(int i = m; i < n - m; i++){
                s[i] = 'a' + i;
            }
        }
        cout << s << endl;
    }
}

E 一起走很长的路！

RMQ、数据结构、贪心

如果从 1 开始推倒，那么每个位置之前的重量之和就是前缀和，记为 。

如果自身重量大于前面的前缀和，那我们就需要进行操作。

那么我们应该怎么操作呢？

一个比较显然的贪心想法是，将第 1 块多米诺骨牌的重量增加 。

那么对于整个数组需要给第 1 块多米诺骨牌增加多少重量呢？显然是数组中 的最大值。

那么现在如果是 子数组怎么办呢？

在子数组中应该这样更新： 。

这时我对子数组进行一次区间加，再查询最大值就行了，可以直接使用线段树暴力处理。

当然，我们再稍微思考一下可以发现，根本不需要进行区间加，直接查询最大值，然后将最大值加上 即可，可以使用ST表。

注意，最大值要从 开始取，因为第 1 块不需要靠前面的推倒。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

template <typename T>
class ST{
public:
    const int n;
    vector<vector<T>> st;
    ST(int n = 0, vector<T> &a = {}) : n(n){
        st = vector(n + 1, vector<T>(22 + 1));
        build(n, a);
    }

    inline T get(const T &x, const T &y){
        return max(x, y);
    }

    void build(int n, vector<T> &a){
        for(int i = 1; i <= n; i++){
            st[i][0] = a[i];
        }
        for(int j = 1, t = 2; t <= n; j++, t <<= 1){
            for(int i = 1; i <= n; i++){
                if(i + t - 1 > n) break;
                st[i][j] = get(st[i][j - 1], st[i + (t >> 1)][j - 1]);
            }
        }
    }

    inline T find(int l, int r){
        int t = log(r - l + 1) / log(2);
        return get(st[l][t], st[r - (1 << t) + 1][t]);
    }
};

int main(){
    int n, q;
    cin >> n >> q;
    vector f(n + 1, 0ll), d = f;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        f[i] = f[i - 1] + x;
        d[i] = x - f[i - 1];
    }
    ST<long long> st(n, d);
    while(q--){
        int l, r;
        cin >> l >> r;
        if(l == r){
            cout << 0 << endl;
            continue;
        }
        auto ma = st.find(l + 1, r);
        auto ans = max(ma + f[l - 1], 0ll);
        cout << ans << endl;
    }
}

H 一起画很大的圆！

构造、计算几何，贪心

三个不共线的点确定一个圆。

如果这三个点越接近一条直线，这个圆最大。

那么我们需要在边界上找三个点使得最接近一条直线，猜一下有一个点会在边角，那剩下的点就不难确定了。

横着可以找到一个答案是 ，但如果 的话，就应该竖着找。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vector<pair<int, int>> ans;
        int x = b - a;
        int y = d - c;
        if(x > y){
            ans.push_back({a, d - 1});
            ans.push_back({b, d});
            ans.push_back({b - 1, d});
        }
        else{
            ans.push_back({b, d});
            ans.push_back({b, d - 1});
            ans.push_back({b - 1, c});
        }
        for(auto &[x, y] : ans){
            cout << x << " " << y << endl;
        }
    }
}

M 那是我们的影子

计数、暴力

一个比较显然的结论：第 1、4、7... 列，第 2、5、8... 列，第 3、6、9... 列有的数字必须都是一样的。

也就是说如果第 列出现的数组种数大于 3 的话，一定无解，输出 0 。

如果某一列有至少两个相同的数字，也一定无解，输出 0 。

否则说明至少有一种解，我们可以将前 3 列进行全排列，看前 3 列是否满足条件。第 4 开始的每一列有哪些数字在提前预处理好之后可以直接进行判断，若都合法，那下来就是每一列填 '?' 字符的方案数了。

如果一列有 个 '?' ，那这一列就有 种填法，每一列的填法数量相乘就是所有 '?' 的填法方案数。由于前 3 列是通过全排列得到的，因此算方案数时只需要算第 4 列开始即可。

需要注意的是判断全排列是否有解时需要使用常数较小的方法。

时间复杂度 。

#include<bits/stdc++.h>

using namespace std;

const int M = 1e9 + 7;

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<string> s(3);
        for(auto &i : s){
            cin >> i;
        }
        int tar = 1;
        vector<set<int>> st(3);
        vector<int> a(n);
        for(int j = 0; j < n; j++){
            set<int> t;
            for(int i = 0; i < 3; i++){
                if(s[i][j] == '?'){
                    a[j]++;
                    continue;
                }
                s[i][j] -= '0';
                if(t.count(s[i][j])) tar = 0;
                t.insert(s[i][j]);
            }
            st[j % 3].merge(t);
        }
        vector<int> sst;
        for(auto &i : st){
            if(i.size() > 3) tar = 0;
            int x = 0;
            for(auto &j : i){
                x ^= 1 << j;
            }
            sst.push_back(x);
        }
        if(!tar){
            cout << 0 << endl;
            continue;
        }
        auto S = 1ll;
        for(int i = 3; i < n; i++){
            if(a[i] == 2) S = S * 2 % M;
            if(a[i] == 3) S = S * 6 % M;
        }
        vector<int> v(9);
        iota(v.begin(), v.end(), 1);
        int sum = 0;
        do{
            int tar = 1;
            for(int i = 0; i < 3; i++){
                for(int j = 0; j < 3; j++){
                    if(s[i][j] == '?') continue;
                    int x = i + j * 3;
                    if(s[i][j] != v[x]) tar = 0;
                }
            }
            int x;
            x = (1 << v[0]) + (1 << v[1]) + (1 << v[2]);
            if(x != (x | sst[0])) tar = 0;
            x = (1 << v[3]) + (1 << v[4]) + (1 << v[5]);
            if(x != (x | sst[1])) tar = 0;
            x = (1 << v[6]) + (1 << v[7]) + (1 << v[8]);
            if(x != (x | sst[2])) tar = 0;
            if(!tar) continue;
            sum = (sum + S) % M;
        }
        while(next_permutation(v.begin(), v.end()));
        cout << sum << endl;
    }
}

I 一起看很美的日落！

计数、树、DP

推了半天，推的很乱，而且不会换根，寄。

不过似乎换根不是很能做，是普通的DP，但是昨晚脑子不清醒推不出来（虽然清醒也推不出来）。

这题我写了两次，第一次是几个月前写了一会没过，第二次是昨晚凌晨写了几个小时，也没过，同时也导致了下一题没时间写了。

不会DP，呜呜

L 还会再见吗？

虚树、换根DP

这题最开始的思路是树剖加上一堆神秘的东西大力堆 s**t 的，整体复杂度非常高。

然后我想到了一个启发式合并后跑最短路的做法，并进行了实现，时限变成了常数较小的 ，而且启发式合并可以优化成 整体的复杂度将下降到 。

这份启发式合并也成了当时的 std ，并造了数据，后续几个验题人力大砖飞写了虚树，并通过了此题。但后续一个凑巧造出来的数据，两种代码跑的不同，之后对拍了挺久发现启发式合并寄了。

之后我也没有继续想启发式合并能不能修改，也没去写虚树，这题就暂时没动了。启发式合并被 hack 之后，这题就似乎就彻底变成了火箭头盔滑板毛毛虫，就变成了板子套板子，非常无趣。

虚树的做法是：对每一种颜色建一棵虚树，然后在虚树上DP跑每个点离最近的点的距离是多少（这个DP好像需要换根），最后再在原树上跑一下最短路即可。

时间复杂度 。

rk1 pyy的代码就是，而且也挺清楚的。