【CF】Day139——杂题 (绝对值变换 | 异或 + 二分 | 随机数据 + 图论)

B. Meeting on the Line

题目：

思路：

数形结合

首先考虑如果没有 t 的影响该怎么写

显然我们就是让最大时间最小化，那么显然选择最左端点和最右端点的中间值即可，即 (mi + mx) / 2，那么现在有了 t 该怎么办

我们不妨考虑拆开绝对值，由 |a - b| = max(a-b, b-a) 可得原式 t - |x - x0| 拆解为

max(t - (x - x0), t - (x0 - x)) = max(t - x + x0, t + x - x0) = max(x0 - (x - t), (t + x) - x0)

我们令 x-t 和 t+x 为两个新点，那么显然 x-t 在 x0 左边，t+x 在 x0 右边，所以我们找到最大的右端点和最小的左端点即可，这就是我们上面的普通情况

除此之外，我们可以还能使用二分or三分

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), t(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> t[i];
    int mx = -1e18, mi = 1e18;
    for (int i = 1; i <= n; i++)
    {
        mx = max(mx, a[i] + t[i]);
        mi = min(mi, a[i] - t[i]);
    }
    double res = (mx + mi) * 1.0 / 2.0;
    printf("%.6lf\n", res);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

C1. Sheikh (Easy version)

题目：

思路：

异或性质

这题看似无从下手，但是我们关键点在于发现异或的性质，不难发现一个特点，异或是不带进位的加法，那么对于任意 x,y，我们都有 x+y >= x ^ y，这是显然的

那么我们就豁然开朗了，既然 x+y >= x ^ y，那么对于一个区间我们肯定是多加数的，因为 x+y - x^y >= 0 恒成立，所以多加显然是不劣的

那么最大值显然就是选取整个区间，但是题目让我们输出最小的长度，所以考虑如何最小

显然由上诉结论可知，我们区间长度越长，那么值就越大，这是单调的，所以我们考虑二分区间长度，我们枚举每一个左端点，然后二分最大长度即可

特别注意预处理前缀和即可，还有越界问题

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve()
{
    int n,q;
    cin >> n >> q;
    vector<int> a(n+1),sum(n+1,0),sumxor(n+1,0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
        sumxor[i] = sumxor[i-1] ^ a[i];
    }
    cin >> q >> q;
    int mx = sum[n] - sumxor[n];
    auto check = [&](int l,int len)->int{
        int r = min(l + len - 1,n);
        int nmx = (sum[r] - sum[l-1]) - (sumxor[r] ^ sumxor[l-1]);
        return nmx >= mx;
    };
    int le = 1e18;
    int mxl = 0;
    for (int i = 1; i <= n; i++)
    {
        int l = 1,r = 1e18;
        while (l+1 < r)
        {
            int mid = l+r >> 1;
            if(check(i,mid))
            {
                r = mid;
            }
            else
            {
                l = mid;
            }
        }
        int templen = 0;
        if(check(i,l)) templen = l;
        else templen = r;
        if(templen < le)
        {
            le = templen;
            mxl = i;
        }
    }
    cout << mxl << " " << mxl + le - 1 << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E. Guess the Cycle Size

题目：

思路：

随机数据的特征

注意到题目数据随机，那么可以考虑稍微暴力的做法

我们假设对于 a,b 点对进行询问，如果 a,b 和 b,a 的询问结果不同，那么显然二者相加就是答案

但是由于 a,b 和 b,a 的询问结果不同，因此我们要多次判断，可以发现 50 次内基本上不可能会错，如果担心错的话可以在代码结尾加上 while(1) 使得其超时，因为TLE 会重测 3 次，3 次全错肯定不可能

最后特别注意特判 -1 情况即可

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define yes cout << "YES\n"
#define no cout << "NO\n"
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve()
{
    int ans1, ans2;
    for (int i = 2; i <= 1e18; i++)
    {
        cout << "? " << 1 << " " << i << endl;
        cin >> ans1;
        if (ans1 == -1)
        {
            cout << "! " << i - 1 << endl;
            return;
        }
        cout << "? " << i << " " << 1 << endl;
        cin >> ans2;       
        if(ans1 != ans2)
        {
            cout << "! " << ans1 + ans2 << endl;
            return;
        } 
    }
    while (1);
}

signed main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}