前言

做的时候昏昏的，每题一个rz错误，比如读入没读完，减一写错位置，传vector做函数参数切记要引用，要不然每次拷贝一次，直接T麻了

题解

A.面包店故事

如果 $c \leqslant a$ + $b$ ，就输出 $YES$ ，否则输出 $NO$

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int a, b, c;
    std::cin >> a >> b >> c;
    if  (c >= a + b) {
        std::cout << "YES" << '\n';
    }
    else {
        std::cout << "NO" << '\n';
    }
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

B.放课后故事

这东西大家是不是一眼就出答案，那不就是所有的纸张加一起除以折一个飞机需要的纸张数和留下来的人数 $m$ 取个最小值就完了，诶，我也是这么想的，交上去喜提 $WA$ ，我们再读题发现有 $m$ 个人留下来，和小 $S$ 一起飞纸飞机，所以一共有 $m$ + $1$ 个人，诶过了

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n, m, k;
    std::cin >> n >> m >> k;

    i64 num = 0;
    for (int i = 1; i <= n; i++) {
        int a;
        std::cin >> a;
        num += a;
    }

    std::cout << std::min(num / k, m);
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

C.异或故事

根据异或的性质我们得出，用 $1$ 去异或上一个数 $n$ ，如果 $n$ 为奇数则得到 $n - 1$ ，否则我们会得到 $n$ + $1$ ，由此，们发现，直接用 $1$ 去异或就好了嘛，但考虑特殊的两个数，输入为 $1$ 或 $1e9$ 时，我们发现，用 $1$ 去异或得到的两个数为 $0$ 和 $1e9$ + $1$ ，不在我们要求的范围内，所以我们特判一下这两个数即可

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int a;
    std::cin >> a;
    if (a == 1) {
        std::cout << "2 3" << '\n';
    }
    else if (a == 1e9) {
        std::cout << 999999999 << ' ' << 1023 << '\n';
    }
    else {
        std::cout << 1 << ' ' << (1 ^ a) << '\n';
    }
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

D.构造故事

我们的目标是得到周长最大的三角形，那我们肯定考虑拿最长的对吧，我们对所有火柴排序后，直接枚举！第一维直接从最大的往后枚举，第二维从比上一个小的第一个开始枚举，由于数组有序我们会发现，如果比我当前选了的两个小的最大那个数都不能和前两个构成三角形，那我们直接break就好了，往后再枚举没意义了，后面不能再出现可以和前两条边构成三角形的边。这样的复杂度可以做到nlog

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 n;
    std::cin >> n;

    std::vector<i64> a(n + 1);
    for (i64 i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    
    std::sort(a.begin() + 1, a.end(), std::greater<i64> ());
    i64 ans = -1;
    for (i64 i = 1; i <= n - 2; i++) {
        for (i64 j = i + 1; j <= n - 1; j++) {
            if (a[i] >= a[j] + a[j + 1]) {
                break;
            }
            ans = std::max(ans, a[i] + a[j] + a[j + 1]);
        }
    }

    std::cout << ans << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

E.约会故事

这个就小模拟嘛，没别的说的，由于有效区间只有 $00:00 - 1:59$ ，我们直接把时间用分钟表示就好了，开个标记数组记录每一分钟是否可以作为快乐时间，唯一的小坑点就是如果起始时间大于结束时间，那说明这东西跨了一天，在一天中的有效区间就变成了 $00:00 - 结束时间$ 和 $起始时间-23:59$ 的并集，我们每次跟120做一次比较即可。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n, m;
    std::cin >> n >> m;

    auto cal = [&] (std::string s) -> int {
        int h = 0, m = 0;
        h = (s[0] - '0') * 10 + (s[1] - '0');
        m = (s[3] - '0') * 10 + (s[4] - '0');
        return h * 60 + m;
    };

    std::vector<int> vis(200, 0);
    for (int i = 1; i <= n; i++) {
        std::string s1, s2;
        std::cin >> s1 >> s2;
        
        int tmp1 = cal(s1), tmp2 = cal(s2);
        if (tmp1 >= tmp2) {
            for (int i = 0; i <= std::min(120, tmp2); i++) {
                vis[i] = 1;
            }
            for (int i = tmp1; i <= 120; i++) {
                vis[i] = 1;
            }
        }
        else {
            for (int i = tmp1; i <= std::min(120, tmp2); i++) {
                vis[i] = 1;
            }
        }
    }

    std::map<std::string, int> mp;
    for (int i = 1; i <= m; i++) {
        std::string s;
        std::cin >> s;
        mp[s] = 1;
    }

    int q;
    std::cin >> q;
    while(q--) {
        std::string s;
        std::cin >> s;
        int tmp = cal(s);
        std::string s1, s2, s3;
        std::cin >> s1 >> s2 >> s3;

        if (tmp >= 120 || !vis[tmp]) {
            std::cout << "Loser xqq" << '\n';
            continue;
        }

        int tmp1 = cal(s1), tmp2 = cal(s2);
        if (tmp1 > tmp2 || !mp.count(s3)) {
            std::cout << "Joker xqq" << '\n';
            continue;
        }

        std::cout << "Winner xqq" << '\n';
    }
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

F.不是烤串故事

二分+哈希，我们直接枚举在每个位置翻转就好了，每次翻转时二分查询一下最长的匹配前缀即可，唯一的小细节就是由于字符串开头翻转了一段，我们需要特殊处理一下，就是拼接嘛，比如你要在字符串s前面拼一个字符串 $t$ ，那我们就可以用 $t$ 的哈希值乘上 $p[s.size()]$ ，再加上 $s$ 的哈希值就好了，想不通的同学我们可以想想十进制下的 $12345$ ，哈希就是一个你设置 $base$ 进制下的数嘛。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

const int P=13331;
const i64 hash_mod = 1610612741;

void solve() {
    int n;
    std::cin >> n;

    std::string s, t;
    std::cin >> s >> t;
    s = ' ' + s, t = ' ' + t;
    std::vector<i64> h1(n + 1), h2(n + 1), h3(n + 1), p(n + 1); 

    p[0] = 1, h1[0] = 0, h3[0] = 0;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * P % hash_mod;	
        h1[i] = (h1[i - 1] * P + s[i]) % hash_mod; 
        h3[i] = (h3[i - 1] * P + t[i]) % hash_mod;
    }
    h2[0] = 0;
    std::reverse(s.begin() + 1, s.end());
    for (int i = 1; i <= n; i++) {
        h2[i] = (h2[i - 1] * P + s[i]) % hash_mod; 
    }

    auto get = [&] (int l, int r, std::vector<i64>& h) -> i64 {
        return ((h[r] - h[l - 1] * p[r - l + 1]) % hash_mod + hash_mod) % hash_mod;
    };

    int mx = 0, pos = 1;
    for (int i = 1; i <= n; i++) {
        int l = 1, r = n;
        int ans = -1;
        while(l <= r) {
            int mid = l + r >> 1;
            i64 tar = get(1, mid, h3);
            i64 num = 0;
            if (mid > i) {
                num = get(i + 1, mid, h1);
                num = (num + get(n - i + 1, n, h2) * p[mid - i]) % hash_mod;
            }
            else {
                num = get(n - i + 1, n - i + mid, h2);
            }

            if (tar == num) {
                l = mid + 1;
                ans = mid;
                if (mid > mx) {
                    mx = mid;
                    pos = i;
                }
            }
            else {
                r = mid - 1;
            }
        }
    }

    std::cout << mx << ' ' << pos << '\n'; 
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

题解 | #牛客周赛56题解#