牛客多校4

G Horse Drinks Water

已知将军的马在点 $(x_{G}, y_{G})$ 处，帐篷在点 $(x_{T}, y_{T})$ 处，河流位于 x 轴的正半轴和 y 轴的正半轴上，求马从河边喝水返回帐篷所需的最短距离。

小学问题。

#define int long long
void solve() {
    int xg, yg, xt, yt;cin >> xg >> yg >> xt >> yt;
    auto dis = [&](int xg, int yt) ->double {
        return sqrt((xg - xt) * (xg - xt) + (yg - yt) * (yg - yt));
        };

    cout << fixed << setprecision(15) << min(dis(-xg, yt), dis(xg, -yt)) << '\n';
}

I Friends

有 $n$ 个人站成一排，从左到右依次为 $1$ 到 $n$ 。在这些人中，有 $m$ 对朋友。

当且仅当区间内的每一对人都是朋友时，定义区间 $[l, r]$ （ $1 \leq l \leq r \leq n$ ）为友好区间。

有多少个友好区间？

代码的具体细节等会再写

void solve() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n, m;cin >> n >> m;
    map<int, int> mp[n + 1];
    int ans = 0;
    for (int i = 1;i <= m;i++) {
        int u, v;cin >> u >> v;mp[v][u] = 1;
    }
    int now = 1;
    for (int i = 1;i <= n;i++) {
        int tmp = i - 1;
        while (tmp && mp[i][tmp]) tmp--;
        tmp++;now = max(now, tmp);
        ans += i - now + 1;
    }
    cout << ans << '\n';
}

H Yet Another Origami Problem

炸鸡讨厌折纸问题！别人能轻松解决的折纸问题（例如 CF 1966 E 和 HDU 6822），他总是解决不了。不过，今天炸鸡是出题人！轮到他给参赛者出一道非常难的折纸题了！

给定一个长度为 $n$ 的数组 $a$ ，你可以执行以下任意次数（可能为零）的操作：

选择一个索引 $p$ ，然后执行以下两种操作之一：

对于所有 $i$ ，如 $a_{i} \leq a_{p}$ ，让 $a_{i} \leftarrow a_{i} + 2 (a_{p} - a_{i})$ 。
对于所有 $i$ ，如 $a_{i} \geq a_{p}$ ，让 $a_{i} \leftarrow a_{i} - 2 (a_{i} - a_{p})$ 。

现在，你想通过这些操作最小化数组的范围。回想一下，数组的范围是数组中最大元素和最小元素之差。

每次两个数的操作本质上两个数之间的差值并不会改变。每次都以第二大的数和最大的数来操作，每次都让最大的数变到前面去，直到最后只剩下两个数为止。这两个数字的差值即为答案。

直接用差分数组所有数的 gcd 即可。

至于证明...

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), suf(n);
    for (int i = 1;i <= n;i++)cin >> a[i];
    sort(a.begin() + 1, a.end());
    if (n <= 2) {
        if (n == 1) {
            cout << "0\n";return;
        } else {
            cout << abs(a[1] - a[0]) << '\n';return;
        }
    }
    for (int i = 1;i < n;i++)suf[i] = a[i + 1] - a[i];
    int g = suf[1];
    for (int i = 2;i < n;i++) {
        g = __gcd(g, suf[i]);
    }
    cout << g << '\n';
}

C Sort 4

给定一个长度为 $n$ 的排列 $^{†}$ 。在一次操作中，你可以从排列中选择不超过 4个元素，并任意交换它们的位置。按升序排列该排列所需的最少操作次数是多少？

根据题意可以知道：每次在没有还原的对应位置一定有环。

即在这个排列中有若干个环，对于每个环都是相互独立的。

对于这些环，有的可以拼接，有的环较大，需要多次操作且每次需要花费 4 次操作来使得 3 个元素被还原。

void solve() {
    int n;cin >> n;
    vector<int> p(n + 1);
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++) {
        cin >> a[i];p[a[i]] = i;
    }
    vector<int>vis(n + 1), ans;
    int cnt = 0;

    auto dfs = [&](auto self, int x, int y)->void {
        if (vis[x]) {
            return;
        }
        cnt++;vis[x] = 1;
        self(self, y, p[y]);
        };
    for (int i = 1;i <= n;i++)if (p[i] == i)vis[i] = 1;
    for (int i = 1;i <= n;i++) {
        if (!vis[a[i]]) {
            cnt = 0;
            dfs(dfs, a[i], p[a[i]]);
            ans.push_back(cnt);
        }
    }
    int res = 0;
    int c[4] = {};
    for (auto x : ans) {
        res += x / 3;x %= 3;
        c[x]++;
    }
    cout << c[3] + (c[2] + 1) / 2 + res << '\n';
}