烟尘墨

2024-09-10 19:31 已编辑嘉应学院 Web前端发布于广东

关注

题解 | 牛客周赛 Round 56

久违的 $ak$ 场, $qwq$

A. 面包店故事

思路

判断 $n$ 与 $x y$ 的大小关系即可， $n$ 不小于 $x y$ 输出 $YES$ ，否则为 $NO$ 。

代码实现

// Problem: 面包店故事
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88392/A
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int x, y, n;
    cin >> x >> y >> n;
    cout << (n >= x + y ? "YES" : "NO");
}

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

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

B. 放课后故事

思路

若纸的总数为 $s$ ,那么折出来的纸飞机最多有 $\lfloor \frac{s}{k} \rfloor$ 个。

因为 $m$ 个人留下与小 $S$ 一起放飞机，所以放飞机人数为 $m 1$ 人。

能分到纸飞机的最多人数即为上述两个值的较小值。

代码实现

// Problem: 放课后故事
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88392/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n, m, k, s = 0;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        s += x;
    }
    int ans = min(m + 1, s / k);
    cout << ans;
}

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

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

C. 异或故事

思路

因为 $0 \oplus x = x$ ，所以 $a = c \oplus b$ 的一组非负整数解可以为 $b = a,c = 0$ 。

因为题目要求的是正整数解，所以考虑从低到高枚举二进制位，把 $c$ 某个二进制位从 $0$ 修改为 $1$ ，然后 $b$ 该二进制位对应的进行修改，使得异或后仍为 $a$ ，此时就是一组正整数解了。

如果 $a$ 的第 $i$ 位二进制位为 $0$ ，若 $c$ 的该位为 $1$ ，因为 $1 \oplus 1 = 0$ ，则 $b$ 的该位也需要为 $1$ 。因为 $b$ 初始值等于 $a$ ，该位置初始为 $0$ ，变成 $1$ 后增加了 $2^i$ , 判断是否超过 $1e9$ ，如果不超过则该情况为可行解。
如果 $a$ 的第 $i$ 位二进制位为 $1$ ，若 $c$ 的该位为 $1$ ，因为 $1 \oplus 0 = 1$ ，则 $b$ 的该位也需要为 $0$ 。因为 $b$ 初始值等于 $a$ ，该位置初始为 $0$ ，变成 $0$ 后减少了 $2^i$ , 判断是否不小于 $1$ ，如果不小于 $1$ 则该情况为可行解。

代码实现

// Problem: 异或故事
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88392/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int a;
    cin >> a;
    int b = a, c = 0, inf = 1e9;
    for (int i = 0; i <= 31; i++) {
        int x = (a >> i) & 1;
        int w = 1 << i;
        if (x == 0) {
            if (b + w <= inf) {
                c += w;
                b += w;
                break;
            }
        } else {
            if (b - w >= 1) {
                b -= w;
                c += w;
                break;
            }
        }
    }
    cout << b << ' ' << c << '\n';
}

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

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

D. 构造故事

思路

如果选择的三条边从小到大分别为 $x,y,z$ ，那么当 $x y>z$ 时构成三角形。

从小到大对 $a$ 进行排序，然后枚举 $y=a_i$ ，因为要周长最大，所以 $x$ 取不超过 $y$ 的最大值，即为 $a_{i-1}$ ， $z$ 即为数组 $a$ 中小于 $a_i a_{i-1}$ 的最大值。因为数组已经升序，所以可以二分查找 $z$ 。取 $x y z$ 的最大值即为答案。

代码实现

// Problem: 构造故事
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88392/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e4 + 5;

int n;
int a[N];

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);

    int ans = -1;
    for (int i = 2; i < n; i++) {
        int l = i + 1, r = n;
        // 因为升序排列,所以最大边一定在 i 的右边
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (a[i - 1] + a[i] > a[mid])
                l = mid;
            else
                r = mid - 1;
        }
        // 判断是否构成三角形
        if (a[i - 1] + a[i] > a[r]) {
            ans = max(ans, a[i - 1] + a[i] + a[r]);
        }
    }
    cout << ans << '\n';
}

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

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

E. 约会故事

思路

对于时间，可以都转换成分钟，这样方便比较大小，用于比较是否到电影院时间晚，比较是否在 $01:59$ 前发送。

然后开心的时间段直接开个数组对时间段内的时间标记，这样在查询的时候就可以直接判断某个时间点是否开心。

注意时间段不一定是开始时间不一定小于结束时间，如果开始时间小于结束时间则直接从开始时间标记到结束时间即可，否则就是跨天的情况，要从开始时间标记到 $23:59$ ，再从 $00:00$ 标记到结束时间。

快速查询奶茶名字是否是给出的奶茶名字，可以用 $c$ 中的 $set$ 或者 $unordered\_set$ 存储然后用 $.count()$ 方法查询。

对各个条件判断后综合起来输出即可。

代码实现

// Problem: 约会故事
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88392/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, m, q;
int a[4000];
set<string> st;

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s1, s2;
        cin >> s1 >> s2;
        int h1 = stoi(s1.substr(0, 2));
        int m1 = stoi(s1.substr(3, 2));
        int t1 = h1 * 60 + m1;
        int h2 = stoi(s2.substr(0, 2));
        int m2 = stoi(s2.substr(3, 2));
        int t2 = h2 * 60 + m2;
        if (t1 < t2) {
            for (int j = t1; j <= t2; j++)
                a[j] = 1;
        } else {
            for (int j = t1; j <= 3600; j++) {
                a[j] = 1;
            }
            for (int j = 0; j <= t2; j++) {
                a[j] = 1;
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        st.insert(s);
    }
    cin >> q;
    while (q--) {
        string s, s1, s2, s3;
        cin >> s >> s1 >> s2 >> s3;
        int h = stoi(s.substr(0, 2));
        int m = stoi(s.substr(3, 2));
        int t = h * 60 + m;
        int h1 = stoi(s1.substr(0, 2));
        int m1 = stoi(s1.substr(3, 2));
        int t1 = h1 * 60 + m1;
        int h2 = stoi(s2.substr(0, 2));
        int m2 = stoi(s2.substr(3, 2));
        int t2 = h2 * 60 + m2;

        if (t > 60 + 59) {
            cout << "Loser xqq\n";
            continue;
        }
        if (a[t] && t1 <= t2 && st.count(s3)) {
            cout << "Winner xqq\n";
        } else if (a[t] && (t1 > t2 || !st.count(s3))) {
            cout << "Joker xqq\n";
        } else {
            cout << "Loser xqq\n";
        }
    }
}

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

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

F. 不是烤串故事

思路

枚举反转区间的右端点 $i$ ，如果反转区间 $[1,i]$ 得到的 $ss$ 与 $t$ 公共前缀的最大长度为 $lcp_i$ ，那么 $ss$ 长度不超过 $lcp_i$ 的前缀也是与 $t$ 的公共前缀，具有二段性，可以考虑二分 $lcp_i$ ，取 $lcp_i$ 最大的最小下标 $i$ 即为答案。

如果将 $s$ 区间为 $[1,i]$ 的前缀进行反转，得到字符串 $ss$ ，那么 $ss$ 的前缀有两种情况。

令 $ss$ 前缀的右边界下标为 $j$ 。

$j \le i$ ，此时 $ss_1 ss_2 ... ss_j = s_j s_{j 1} ... s_i 的反转$ 。
$j >i$ ，此时 $ss_1 ss_2 ... ss_j = (s_1 s_{2} ... s_i 的反转) (s_{i 1} s_{i 2} ... s_j)$

因为要取未反转和反转后的 $s$ 的子串，且可以发现，子串反转后是整个父串反转后的子串，所以可以处理 $s$ 未反转和 $s$ 整体反转的前缀哈希值，这样就可以直接查询某一段子串未反转或反转后的哈希值。

根据上面讨论的情况对计算拼接后的哈希值，就可以得到反转区间 $[1..i]$ 之后的 $s$ （即 $ss$ ）某个前缀的哈希值，与 $t$ 相同长度的前缀哈希值进行比较，即可判断出该前缀是否为公共前缀，从而确定二分时移动左边界还是右边界，最后二分出来的结果即为 $lcp_i$ 。

代码实现

// Problem: 不是烤串故事
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/88392/F
// Memory Limit: 1048576 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

// 宏定义
#define fs first
#define sc second

typedef long long ll;
// hashv为双哈希值
typedef pair<ll, ll> hashv;

// 进制和模数
const ll base = 13331;
const ll mod1 = 1e9 + 7, mod2 = 1e9 + 9;

// 下面四个函数重载了两个hashv间的 +,-,*,==
hashv operator+(hashv a, hashv b)
{
    ll c1 = a.fs + b.fs, c2 = a.sc + b.sc;
    if (c1 >= mod1)
        c1 -= mod1;
    if (c2 >= mod2)
        c2 -= mod2;
    return make_pair(c1, c2);
}

hashv operator-(hashv a, hashv b)
{
    ll c1 = a.fs - b.fs, c2 = a.sc - b.sc;
    if (c1 < 0)
        c1 += mod1;
    if (c2 < 0)
        c2 += mod2;
    return make_pair(c1, c2);
}

hashv operator*(hashv a, hashv b)
{
    ll c1 = a.fs * b.fs, c2 = a.sc * b.sc;
    if (c1 >= mod1)
        c1 %= mod1;
    if (c2 >= mod2)
        c2 %= mod2;
    return make_pair(c1, c2);
}

bool operator==(hashv a, hashv b)
{
    return (a.fs == b.fs) && (a.sc == b.sc);
}

// 下面三个函数重载了 hashv 与 ll 间的 +,-,*
// 单个整数会与hashv的两个值都进行运算
hashv operator+(hashv a, ll b)
{
    ll c1 = a.fs + b, c2 = a.sc + b;
    if (c1 >= mod1)
        c1 -= mod1;
    if (c2 >= mod2)
        c2 -= mod2;
    return make_pair(c1, c2);
}

hashv operator-(hashv a, ll b)
{
    ll c1 = a.fs - b, c2 = a.sc - b;
    if (c1 < 0)
        c1 += mod1;
    if (c2 < 0)
        c2 += mod2;
    return make_pair(c1, c2);
}

hashv operator*(hashv a, ll b)
{
    return make_pair(a.fs * b % mod1, a.sc * b % mod2);
}

const int N = 3e6 + 5;

int n;
int val[N];
char str[N], str1[N];
// 预处理的n次方
hashv p[N];

// h1为字符串从左到右的哈希值，h2为字符串从右到左的哈希值
hashv h1[N], h2[N], h3[N];

// op表示方向,op=0表示从左到右,op=1表示从右到左
// 该函数用于得到[l,r]的哈希值
hashv gethash(int l, int r, int op)
{
    if (!op)
        return h1[r] - h1[l - 1] * p[r - l + 1];
    return h2[l] - h2[r + 1] * p[r - l + 1];
}

int check(int id, int id1)
{
    if (!id)
        return 1;
    if (id <= id1) {
        return gethash(id1 - id + 1, id1, 1) == h3[id];
    } else {
        hashv v = gethash(1, id1, 1);
        hashv v1 = gethash(id1 + 1, id, 0);
        hashv v2 = v * p[id - id1] + v1;
        return v2 == h3[id];
    }
}

void solve()
{
    cin >> n >> str + 1 >> str1 + 1;
    for (int i = 1; i <= n; i++) {
        h1[i] = h1[i - 1] * base + (str[i] - 'a' + 1);
    }
    for (int i = n; i >= 1; i--) {
        h2[i] = h2[i + 1] * base + (str[i] - 'a' + 1);
    }
    for (int i = 1; i <= n; i++) {
        h3[i] = h3[i - 1] * base + (str1[i] - 'a' + 1);
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        int l = 0, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid, i))
                l = mid;
            else
                r = mid - 1;
        }
        val[i] = l;
        if (val[ans] < val[i])
            ans = i;
    }
    cout << val[ans] << ' ' << ans << '\n';
}

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

    // 预处理幂次
    for (int i = 0; i < N; i++) {
        if (!i)
            p[i] = { 1ll, 1ll };
        else
            p[i] = p[i - 1] * base;
    }

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}