牛客周赛round56

C.给定一个c，要求在给定范围内构造a,b满足a⊕b=ca\oplus b=c.要求值域在1-1e9

Sol:本题的范围比较宽松，只需要构造1，c^1.注意到1e9情况有些特殊，我们特判即可。

思考：如果范围限定到[l,r][l,r]如何寻找b和c，考虑从二进制位考虑？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    cin >> n;
    if (n == 1)
        cout << 2 << " " << 3 << endl;
    else if (n == 1e9) {
        for (int i = 30; i >= 0; i--) {
            if ((n >> i) & 1) {
                int tmp = 1 << i;
                cout << tmp << " " << (n ^ tmp) << endl;
                return ;
            }
        }
    } else
        cout << 1 << " " << (n ^ 1) << endl;
}

D.   nn 根火柴，想知道从这 nn 根火柴中任选 33 根，能否组成一个周长最大的三角形。 求周长最大

Sol:考虑固定最大边，那需要两边之和大于第三边，我们希望满足条件需要两个小边尽可能大，且这符合最终周长最大的答案方向。所以我们排序即可。

1
2
3
4
5
6
7
8
9
10
void solve() {
   cin>>n;
   for(int i=1;i<=n;i++)cin>>a[i];
   int ans=-1;
   sort(a+1,a+1+n);
   for(int i=3;i<=n;i++){
    if(a[i-2]+a[i-1]>a[i])ans=max(ans,a[i-2]+a[i-1]+a[i]);
   }
   cout<<ans<<endl;
}

E.按题意模拟即可，注意给出的时间段可能跨越零点，注意判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
int cal(string s) {
    int h1 = stoi(s.substr(0, 2)), m1 = stoi(s.substr(3, 2));
    return h1 * 60 + m1;
}
void solve() {
    cin >> n >> m;
    vector<int> vis(1500);
    for (int i = 1; i <= n; i++) {
        string st, ed;
        cin >> st >> ed;
        int t1 = cal(st), t2 = cal(ed);
        if (t1 == t2) {
            vis[0]++;
            vis[1440]--;
        } else if (t1 < t2) {
            vis[t1]++;
            vis[t2 + 1]--;
        } else {
            vis[t2]++;
            vis[1440]--;
            vis[0]++;
            vis[t1 + 1]--;
        }
    }
    // int res = cal("23:59");
    // deb(res);
    unordered_map<string, bool> mp;
    for (int i = 1; i <= m; i++) {
        string s;
        cin >> s;
        mp[s] = 1;
    }
    for (int i = 1; i <= 120; i++) vis[i] += vis[i - 1];
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        string st;
        cin >> st;
        string d1, d2;
        cin >> d1 >> d2;
        string name;
        cin >> name;
        int tmp = cal(st);
        int flag = 0;
        if (tmp >= 0 && tmp <= 119 && vis[tmp]) {
            flag = 1;
            if (d1 <= d2 && mp.count(name)) {
                flag = 2;
            }
        }
        if (flag == 2)
            cout << "Winner xqq" << endl;
        else if (flag == 1)
            cout << "Joker xqq" << endl;
        else
            cout << "Loser xqq" << endl;
    }
}

F. 小红有两个长度为 nn 的字符串 ss 和 tt

我们定义下标从 11 开始。你可以选取字符串 ss 的前 ii 个字符 s1s2⋯sis_1 s_2 \cdots s_i，将其反转后与剩余部分拼接，得到 si′s_i'。

请你找到每一个翻转前缀 si′s_i' 与字符串 tt 的最长公共前缀长度：

max⁡i=1nlcp(si′,t)\max_{i=1}^n \text{lcp}(s_i', t)

并输出满足该最大长度的最小 ii。

当然，这其实并不难。作为神秘的 F\mathcal{F} 题，你还需要输出满足条件的最小的 ii。

Sol:

正解是纯线性的，但比赛中忘了 Z 函数，直接写了二分 + 哈希。

考虑过程：我们枚举反转点 ii，先判断反转部分与 tt 的匹配长度。如果完全匹配，再二分正向部分的最长公共前缀（LCP）。

正解思路：LCP 始终从 tt 开头开始匹配，非常适合 Z 函数。

  • 对于反转部分：将 ss 反转后拼接到 tt 后面，运行 Z 函数。
  • 对于正向部分：可以用 DP 预处理。因为这是典型的“最长公共子段”问题，dpidp_i 表示以 ii 结尾的最长公共段长度，本题需倒序 DP。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
void solve() {
    cin >> n;
    string s, t;
    cin >> s >> t;
    Hash hst(t), hs1(s), hs2(s, 1);
    s = " " + s;
    t = " " + t;
    int mx = 0, pos = 1;
    for (int i = 1; i <= n; i++) {
        deb(s);
        deb(t);
        deb(i);
        if (s[i] != t[1])
            continue;
        int l = 1, r = i;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (hs2.getsuf(i - mid + 1, i) == hst.getpre(1, mid))
                l = mid;
            else
                r = mid - 1;
        }
        if (l < i) {
            if (mx < l) {
                mx = l;
                pos = i;
            }
            continue;
        }

        deb(l);
        if (mx < l) {
            mx = l;
            pos = i;
        }
        if (i + 1 > n || s[i + 1] != t[i + 1]) {
            continue;
        }
        int ql = 1, qr = n - (i + 1) + 1;
        while (ql < qr) {
            int mid = (ql + qr + 1) >> 1;
            if (hs1.getpre(i + 1, i + 1 + mid - 1) == hst.getpre(i + 1, i + 1 + mid - 1))
                ql = mid;
            else
                qr = mid - 1;
        }
        deb(ql);

        int res = ql + i;
        if (mx < res) {
            mx = res;
            pos = i;
        }
    }
    cout << mx << " " << pos << endl;
}