XCPC wiki - 双指针

和$\geqslant s$ 的最短子区间

void eachT() {
    int n = read(), s = read();

    vector<ll> pre(n + 1);
    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + read();
    }

    int ans = inf;
    for (int l = 1, r = 1; l <= n; l++) {
        while (r < n && pre[r] - pre[l - 1] < s) {  // 当前不满足
            r++;
        }
        if (pre[r] - pre[l - 1] >= s) {
            ans = min(ans, r - l + 1);
        }
    }
    printf("%d\n", ans == inf ? -1 : ans);
}

和最接近$t$ 的子区间

给定一个序列，多次查询，每次给出$t$，求一个子区间使得其和的绝对值与$t$ 的差值最小。(2566 – Bound Found (poj.org))

即是最小化$|s_{r}-s_{l}-t|$。存储所有前缀和并排序，排序是为了产生单调性，其合理性基于贪心。

struct node {
    ll x;
    int id;
    bool operator<(const node& o) const {
        return x < o.x;
    }
};

void beforeT() {}
void eachT() {
    int n = read(), q = read();

    vector<node> pre(n + 1);
    for (int i = 1; i <= n; ++i) {
        pre[i].x = pre[i - 1].x + read();
        pre[i].id = i;
    }
    sort(pre.begin(), pre.end());

    while (q--) {
        int t = read();

        ll res = 8e18;
        int resl = 0, resr = 0;
        for (int l = 0, r = 1; r <= n; r++) {
            while (l + 1 < r && abs(pre[r].x - pre[l].x - t) > abs(pre[r].x - pre[l + 1].x - t)) {
                l++;
            }
            if (abs(pre[r].x - pre[l].x - t) < abs(res - t)) {
                res = pre[r].x - pre[l].x;
                resl = pre[l].id;
                resr = pre[r].id;
            }
        }
        if (resl > resr) swap(resl, resr);
        printf("%lld %d %d\n", res, resl + 1, resr);
    }
}

A-B problem

给定序列及一个正整数$C$，计算所有满足$A - B = C$ 的数对的个数。

void eachT() {
    int n = read(), c = read();

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = read();
    }
    sort(a.begin(), a.end());

    ll res = 0;
    for (int l = 0, r1 = 1, r2 = 1; l < n; l++) {
        while (r2 < n && a[l] + c >= a[r2]) {
            r2++;
        }
        while (r1 < n && a[l] + c > a[r1]) {
            r1++;
        }
        res += r2 - r1;
    }
    printf("%lld\n", res);
}

连续自然数和

给定正整数$n$，求出所有的连续的正整数段，这些连续的自然数段中的全部数之和为$n$。

Input	Output
10000	18 142 297 328 388 412 1998 2002

void eachT() {
    int n = read();

    for (int l = 0, r = 0; l < n; l++) {
        while ((r - l + 1ll) * (l + r) / 2 < n) {
            r++;
        }
        if ((r - l + 1ll) * (l + r) / 2 == n) {
            printf("%d %d\n", l, r);
        }
    }
}

例题

2024 牛客多校 10K - Doremy’s IQ 2

[[…/contests/2024牛客多校/2024-08-15：2024牛客暑期多校训练营10|2024-08-15：2024牛客暑期多校训练营10]]

题意 给定数轴上$n$ 个整点，你初始在原点。每次你选择一个点，向它的方向移动一格；但如果选择的点与你当前重合，则加一分。选择后该点消失。最大化分数。

思路 移动的方向最多改变一次，双指针找折返点和终点。时间复杂度$\Theta(n)$。

void eachT() {
    int n = read();

    int L = 1e9, R = -1e9;  // 能吃到的左右界
    int p1 = n;   // 第一个非负数的位置
    int p2 = -1;  // 最后一个非正数的位置

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = read();
        if (a[i] >= 0) p1 = min(p1, i);  // 第一个非负数的位置
        if (a[i] <= 0) p2 = i;           // 最后一个非正数的位置
        if (a[i] < 0 && a[i] + i >= 0 || a[i] == 0 || a[i] > 0 && a[i] <= n - 1 - i) {
            L = min(L, i);
            R = i;  // 能吃到的左右界
        }
    }

    int ans = 0;
    for (int l = L, r = p1; l <= R; l++) {
        while (r <= R && a[r] - a[l] <= l) {
            r++;
        }
        ans = max(ans, r - l);
    }
    for (int l = p2, r = R; r >= L; r--) {
        while (l >= L && a[r] - a[l] <= n - 1 - r) {
            l--;
        }
        ans = max(ans, r - l);
    }
    printf("%d\n", ans);
}

2024 牛客多校 4I - Friends

[[…/contests/2024牛客多校/2024-07-25：2024牛客暑期多校训练营4#I - Friends (24)|2024-07-25：2024牛客暑期多校训练营4]]

题意 有$n$ 个人排成一列，编号分别为$1\sim n$。 其中有$m$ 对是好朋友。一个编号区间$[l,r]$ 被称为好区间当且仅当所有编号在内的人彼此之间都是好朋友。求好区间的数量。

思路 时间复杂度$\Theta(m\log m+n)$，主要时间在排序。

void eachT() {
    int n = read(), m = read();

    vector<vector<int>> vec(n + 1);
    while (m--) {
        int u = read(), v = read();
        vec[v].push_back(u);
    }

    vector<int> L(n + 1);
    for (int i = 1; i <= n; i++) {
        sort(vec[i].begin(), vec[i].end(), greater<>());
        L[i] = i;
        for (auto& x : vec[i]) {
            if (x == L[i] - 1) L[i]--;
            else break;
        }
    }

    ll ans = 0;
    for (int l = 1, r = 1; l <= n; l++) {
        while (r <= n && L[r] <= l) {
            r++;
        }
        ans += r - l;
    }
    printf("%lld\n", ans);
}

CF1994C - Hungry Games

题意 给定序列$a$ 和一个阈值$x$，对于$1 \leqslant l \leqslant r \leqslant n$，定义$f(l,r)$：

1. 最初$f(l,r)=0$；
2. 依次遍历$a_{l},a_{l+1},\dots,a_{r}$，每遍历一个数$a_{i}$，置

$$f(l,r)\leftarrow \begin{cases} f(l,r)+a_{i},&f(l,r)+a_{i} \leqslant x \\ 0,&f(l,r)+a_{i} > x \end{cases}$$

3. 遍历这些数最后的结果即是$f(l,r)$。

求满足$f(l,r) \neq 0$ 的$(l,r)$ 对数。

思路 倒着 DP 并注意到$p$ 具有单调性，用双指针优化。时间复杂度$\Theta(n)$。

void eachT() {
    int n = read(), x = read();

    vector<ll> pre(n + 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + read();
    }

    ll ans = n * (n + 1ll) >> 1;
    vector<int> f(n + 2);
    f[n] = 1;
    for (int l = n, r = n; l >= 0; l--) {
        while (pre[r] - pre[l] > x) {
            r--;
        }
        f[l] = f[r + 1] + 1;
        ans -= f[l] - 1;
    }
    printf("%lld\n", ans);
}

CF1941F. Rudolf and Imbalance

给定长度分别为$n,m,k$ 的数组$a,d,f$，其中保证$a$ 升序。现在你要在$d,f$ 两个数组中分别选出一个数，相加后加入到$a$ 数组中，再按升序排序。求怎样操作能使最终的$a$ 数组相邻的两个数之差最大值最小。

据说比单调队列优化 DP 难 250 分……

int n, m, k;
cin >> n >> m >> k;

vector<ll> a(n), d(m), f(k);
for (auto& i : a) cin >> i;
for (auto& i : d) cin >> i;
for (auto& i : f) cin >> i;
sort(d.begin(), d.end(), greater<>());
sort(f.begin(), f.end());

ll max1 = 0, max2 = 0, imax = 0;
for (int i = 1; i < n; i++) {
	int now = a[i] - a[i - 1];
	if (now >= max1) {
		max2 = max1;
		max1 = now;
		imax = i;
	}
	else if (now >= max2) {
		max2 = now;
	}
}

ll lo = a[imax - 1], hi = a[imax];
ll need = lo + hi;
for (int i = 0, p = 0; i < m; i++) {
	while (p + 1 < k && abs(2 * (f[p + 1] + d[i]) - need) <= abs(2 * (f[p] + d[i]) - need)) {
		p++;
	}
	int now = f[p] + d[i];
	if (lo < now && now < hi) {
		max1 = min(max1, max(hi - now, now - lo));
	}
}
cout << max(max1, max2) << "\n";