题解：CF479D Long Jumps

FiraCode · 2024-06-09 11:56:32 · 题解

显然的，答案至多为 2，所以可以考虑分类讨论。

当差有 x,y 时直接输出 0。

若只有 x,y 中的一个，那么最优就是在没有这个点的地方标记一下，次数为 1。

否则 x,y 都没有，那么只需要考虑此时只需要标记一次的情况。若要标记两次，那么直接在 x,y 对应位置标记即可。

考虑是否有间隔长度为 x+y 的区间，若有此时只需要在中间标记一下。

否则就是类似这种（红色为原有点，蓝色为新加的点）：

此时就是判断有没有长度为 x-y 的区间，然后看在区间的左/右放一个点是否越界，若越界则不行，否则可以。

#include <bits/stdc++.h>

using namespace std;

int n, l, x, y;
int a[100010];
map<int, int> ma;

int main() {
    scanf("%d%d%d%d", &n, &l, &x, &y);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ma[a[i]] = 1;
    int cntx = 0, cnty = 0;
    for (int i = 1; i <= n; ++i) {
        if (ma[a[i] + x]) ++cntx;
        if (ma[a[i] + y]) ++cnty;
    }

    cntx = min(cntx, 1);
    cnty = min(cnty, 1);

    if (cntx + cnty == 2) puts("0");
    else if (cntx + cnty == 1) {
        if (cntx == 1) {
            puts("1");
            printf("%d\n", y);
        } else {
            puts("1");
            printf("%d\n", x);
        }
    }
    else {
        for (int i = 1; i <= n; ++i) if (ma[a[i] + x + y]) {
            puts("1");
            printf("%d\n", a[i] + x);
            return 0;
        } else if (ma[a[i] + y - x] && a[i] + y <= l) {
            puts("1");
            printf("%d\n", a[i] + y);
            return 0;
        } else if (ma[a[i] + y - x] && a[i] - x >= 0) {
            puts("1");
            printf("%d\n", a[i] - x);
            return 0;
        }

        puts("2");
        printf("%d %d\n", x, y);
    }

    return 0;
}