2009(971div4)

A. Minimize!

cout << b - a << '\n';

B. osu! mania

钢琴块落下

void solve() {
    int n;cin >> n;
    vector<int> ans;
    for (int i = 0;i < n;i++) {
        string s;cin >> s;
        for (int j = 0;j < s.size();j++) {
            if (s[j] == '#') {
                ans.push_back(j + 1);
            }
        }
    }
    reverse(ans.begin(), ans.end());
    for (auto x : ans)cout << x << ' ';cout << '\n';
}

C. The Legend of Freya the Frog

青蛙弗莱娅正在二维坐标平面上旅行。她目前在点 $(0, 0)$ ，想去点 $(x, y)$ 。在一次移动中，她选择了一个整数 $d$ ，即 $0 \leq d \leq k$ ，并沿着她面对的方向向前跳跃了 $d$ 个点。

最初，她面向的是 $x$ 正方向。每次移动后，她将交替朝向正 $x$ 方向和正 $y$ 方向（即第二次移动时朝向正 $y$ 方向，第三次移动时朝向正 $x$ 方向，以此类推）。

她最少要走多少步才能到达点 $(x, y)$ ？

初步很容易想到答案是 $⌈ \frac{max (x, y)}{k} ⌉ \times 2$ ，但不容易想到要减去 1 的情况，当 $x$ 需要比 $y$ 多走一步时，最后一步只需要将 $x$ 方向走完即可，不需要再走 $y$ 方向。

void solve() {
    int x, y, k;cin >> x >> y >> k;
    if ((x + k - 1) / k <= (y + k - 1) / k) {
        cout << (max(x, y) + k - 1) / k * 2 << '\n';
    } else {
        cout << (max(x, y) + k - 1) / k * 2 - 1 << '\n';
    }
}

D. Satyam and Counting

给出了 $n$ 个不同的点。对于所有给定点 $(x_{i}, y_{i})$ ，保证 $0 \leq y_{i} \leq 1$ 。选择三个不同的点作为顶点，可以形成多少个不同的直角三角形 $^{∗}$ ？

如果有一个点 $v$ 使得 $v$ 是 $a$ 的顶点而不是 $b$ 的顶点，那么两个三角形 $a$ 和 $b$ 是不同的。

只有两种情况能组成直角三角形：

当两个点横坐标相同时

当横坐标为 $x, x + 1, x + 2$ 且满足构成直角三角形时

#define int long long
void solve() {
    int n;cin >> n;
    vector<int> vis(n + 1);
    map<pair<int, int>, int>mp;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        int x, y;cin >> x >> y;mp[{x, y}] = 1;
        vis[x]++;
        if (vis[x] == 2) {
            cnt++;
        }
    }
    int ans = cnt * (n - 2);
    for (int i = 0;i <= n - 2;i++) {
        if (mp.count({i,0}) && mp.count({i + 1,1}) && mp.count({i + 2,0}))ans++;
        if (mp.count({i,1}) && mp.count({i + 1,0}) && mp.count({i + 2,1}))ans++;
    }
    cout << ans << '\n';
}

E. Klee's SUPER DUPER LARGE Array!!!

Klee 有一个长度为 $n$ 的数组 $a$ ，其中按顺序包含整数 $[k, k + 1, . . ., k + n - 1]$ 。克利希望选择一个索引 $i$ ( $1 \leq i \leq n$ )，使得 $x = | a_{1} + a_{2} + \dots + a_{i} - a_{i + 1} - \dots - a_{n} |$ 最小。请注意，对于任意整数 $z$ ， $| z |$ 表示 $z$ 的绝对值。

输出 $x$ 的最小可能值。

二分出正负数的边界即可

Q: 可不可以不使用二分而通过数学的方式 $O (1)$ 解决呢？A: 可以(在官方题解)

#define int long long
void solve() {
    int n, k;cin >> n >> k;

    auto cal = [&](int i) {
        return 2 * i * k + i * (i - 1) - n * k - n * (n - 1) / 2;
        };
    int l = 1, r = n + 1;
    while (l < r) {
        int i = l + r >> 1;
        int ans = cal(i);
        if (ans >= 0) {
            r = i;
        } else {
            l = i + 1;
        }
    }
    cout << min(cal(l), -cal(l - 1)) << '\n';
}

F. Firefly's Queries

给定长度为 $n$ 的数组 $a$ 为萤火虫。让 $c_{i}$ 表示 $a$ 的 $i$ 'th 循环移动 $^{∗}$ 。她创建了一个新数组 $b$ ，使得 $b = c_{1} + c_{2} + \dots + c_{n}$ 其中 $+$ 表示连接 $^{†}$ 。

然后，她会向你提出 $q$ 个查询。对于每一个查询，输出 $b$ 子数组中从 $l$ （第三个元素）开始到 $r$ （第三个元素）结束的所有元素的总和，包括两端的元素。

$^{∗}$ 数组 $a$ 的 $x$ （ $1 \leq x \leq n$ ）循环位移是 $a_{x}, a_{x + 1} \dots a_{n}, a_{1}, a_{2} \dots a_{x - 1}$ 。请注意， $1$ 次移位是初始的 $a$ 。

将区间分为三个部分： $[0, l - 1], [l, r], [r + 1, n^{2}]$ ,拆开做将两边多余的部分删除即可 (大模拟做法)

Solution

#define int long long
void solve() {
    int n, q;cin >> n >> q;
    vector<int> a(n + 1), pre(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++) {
        pre[i] = pre[i - 1] + a[i];
    }
    int sum = accumulate(a.begin() + 1, a.end(), 0ll);

    while (q--) {
        int l, r;cin >> l >> r;
        int ans = sum * n;
        int x = (l - 1) / n;
        int yu = (l - 1) % n;
        
        ans -= sum * x;
        if (yu <= n - x) {
            ans -= pre[x + yu] - pre[x];
        } else {
            ans -= pre[n] - pre[x];
            yu -= n - x;
            ans -= pre[yu];
        }

        x = (n * n - r) / n;
        yu = (n * n - r) % n;

        ans -= sum * x;
        if (yu <= n - x - 1) {
            ans -= pre[n - x - 1] - pre[n - x - 1 - yu];
        } else {
            ans -= pre[n - x - 1];
            yu -= n - x - 1;
            ans -= pre[n] - pre[n - yu];
        }
        cout << ans << '\n';
    }
}

法二：(官方题解)
复制数组 $a$ 并将其与自身连接。现在， $a$ 的长度应为 $2 n$ ， $n < i \leq 2 n$ 的长度应为 $a_{i} = a_{i - n}$ 。现在， $i$ 'th 旋转中的 $j$ 'th 元素是 $a_{i + j - 1}$ 。

可以证明，对于任意整数 $x$ ，它属于 $⌊ \frac{x - 1}{n} ⌋ + 1$ 的旋转轴，位于位置 $(x - 1) \mod n + 1$ 。让 $r l$ 表示 $l$ 的旋转， $r r$ 表示 $r$ 的旋转。如果是 $r r - r l > 1$ ，那么我们的答案中就增加了 $r r - r l - 1$ 个完整数组。剩下的只是从位置 $l$ 开始的旋转 $r l$ 的后缀和从位置 $r$ 开始的旋转 $r r$ 的前缀。这可以通过前缀和来实现。您可能需要单独处理 $r l = r r$ 。

void solve() {
	ll n, q;
	cin >> n >> q;
	vector<ll> a(n), ps(1);
	for (ll &r : a) {
		cin >> r;
		ps.push_back(ps.back() + r);
	}
	for (ll &r : a) {
		ps.push_back(ps.back() + r);
	}
	while (q--) {
		ll l, r;
		cin >> l >> r;
		l--; r--;
		ll i = l / n, j = r / n;
		l %= n; r %= n;
		cout << ps[n] * (j - i + 1) - (ps[i + l] - ps[i]) - (ps[j + n] - ps[j + r + 1]) << "\n";
	}
}

G1. Yunli's Subarray Queries (easy version)

这是问题的简单版本。在这个版本中，保证所有查询都是 $r = l + k - 1$ 。

对于任意数组 $b$ ，云里可以执行任意多次下面的操作：

选择索引 $i$ 。设置 $b_{i} = x$ ，其中 $x$ 是她想要的任意整数（ $x$ 不限于区间 $[1, n]$ ）。

将 $f (b)$ 记为她需要执行的最小操作次数，直到 $b$ 中存在一个长度至少为 $k$ 的连续子数组 $^{∗}$ 。

给云莉一个大小为 $n$ 的数组 $a$ ，并向你提出 $q$ 个查询。在每个查询中，你必须输出 $\sum_{j = l + k - 1}^{r} f ([a_{l}, a_{l + 1}, \dots, a_{j}])$ 。请注意，在这个版本中，您只需要输出 $f ([a_{l}, a_{l + 1}, \dots, a_{l + k - 1}])$ 。

$^{∗}$ 如果存在一个长度为 $k$ ，从索引 $i$ （ $1 \leq i \leq | b | - k + 1$ ）开始的连续子数组，那么对于所有的 $i < j \leq i + k - 1$ ，都是 $b_{j} = b_{j - 1} + 1$ 。

Solution

滑动窗口

所有区间长度都是 $k$ ，则只需要处理出所有区间大小为 $k$ 的区间即可， $O (1)$ 查询

对于一个区间， $a_{i} \to a_{i} - i$ ，处理后若这个区间每个数大小都相等则满足 连续子数组 的要求，否则只需要查看区间内出现次数最多的元素即可，需要操作的次数则为 $k - max ()$

每次是从区间 $[i, i + k - 1] \to [i + 1, i + k]$ ，需要将下标为 $i$ 位置的删除，添加 $i + k$ 位置

void solve() {
    int n, k, q;cin >> n >> k >> q;
    vector<int> a(n + 1);
    multiset<int>s;
    map<int, int>mp;
    for (int i = 1;i <= n;i++)cin >> a[i], s.insert(0);

    auto op = [&](int i, int x) {
        s.erase(s.find(mp[a[i] - i]));
        mp[a[i] - i] += x;
        s.insert(mp[a[i] - i]);
        };

    for (int i = 1;i < k;i++) {
        op(i, 1);
    }
    vector<int> ans(n + 1);

    for (int i = k;i <= n;i++) {
        op(i, 1);
        ans[i] = k - *s.rbegin();
        op(i - k + 1, -1);
    }

    while (q--) {
        int l, r;cin >> l >> r;
        cout << ans[r] << '\n';
    }
}

G2,G3 暂且不补