牛客周赛round56

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

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

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

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.   $n$ 根火柴，想知道从这 $n$ 根火柴中任选 $3$ 根，能否组成一个周长最大的三角形。 求周长最大

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

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.按题意模拟即可，注意给出的时间段可能跨越零点，注意判断

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.  小红有两个长度为 $n$ 的字符串 $s$ 和 $t$ ，我们定义下标从 $1$ 开始，现在你可以选取字符串 $s$ 的前 $i$ 个字符 $s_1 s_2\cdots s_i$，然后将这一部分反转后与剩余部分拼接，得到 $s_i’$。

         $,,,,,,,,,$请你找到每一个翻转前缀 $s_i’$ 与字符串 $t$ 的 $\displaystyle \max_{i=1}^n{\rm_len} {{\rm lcp}(s_i’,t) }$ ，即长度最长的 ${\rm lcp}(s_i’,t)$ 。在这里，$\rm lcp$ 代表最长公共前缀。

         $,,,,,,,,,$好吧，这其实并不难，作为神秘的 $\mathcal F$ 题，你同时需要输出满足上述条件的最小的 $i$

Sol:正解是纯线性的，把z函数忘了直接写的二分+哈希。考虑这个过程，我们直接枚举反转点，我们需要判断反向字符串和t的匹配长度，如果拉满了，再去二分右端点找最长lcp。

正解：考虑这个lcp每次都是从t开头开始匹配的，这非常适合z函数。对于反转部分采用z函数，反转s后拼接到t然后跑z函数。对于剩余正着的匹配部分，我们可以直接dp，为什么？

这其实是个最长最大公共段问题,$dp_{i}$是以i结尾的最长公共端，只不过本题也是需要倒过来dp

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;
}