Codeforces Round 707(div 2)

A. Alexey and Train

链接：https://codeforces.com/problemset/problem/1501/A

题目大意

有一列火车，要从站台1开往站台n，现在给你预期到达时间$a_i$和预期发车时间$b_i$，以及列车在从i-1站驶向i站时的延误时间$tm_i$，求火车到达站台n的时间。

当延误时，列车在站台i停靠的时长T应满足：

$T\geq \lceil\frac {b_i - a_i} 2\rceil$
使实际发车时间$\geq$预期发车时间

分析

简单模拟，计算出到达每一站的时间和从每一站出发的时间即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
int a[N], b[N], t[N];
int aa[N], bb[N];
int n;

int main() {
    int T; cin >> T;
    while (T--) {
        memset(aa, 0, sizeof aa);
        memset(bb, 0, sizeof bb);
        cin >> n;
        
        for (int i = 1; i <= n; i++) scanf("%d%d", a + i, b + i);
        for (int i = 1; i <= n; i++) scanf("%d", t + i);
        for (int i = 1; i <= n; i++) {
            aa[i] = a[i] - b[i - 1] + t[i] + bb[i - 1];
            bb[i] = max(aa[i] + (int)ceil((b[i] - a[i] + 0.0) / 2), b[i]);
        }

        cout << aa[n] << endl;
    }
}

B. Napoleon Cake

链接：https://codeforces.com/problemset/problem/1501/B

题目大意

一个长度为n数组，初始值都是0，有n次操作，操作i给定$a_i$，让你给区间$[i-a_i+1,i]$都加上1，最后问你哪些位大于0，哪些位等于0。

分析

因为可以很显然的转化为区间维护问题，没多想就直接上树状数组了，就ac了（幸好没卡$n\log n$）。

但是，fzh大佬指出，差分前缀和可以在$o(n)$的复杂度内解决问题，是我菜了

AC代码(树状数组)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;

ll n, a[N], t[N << 2];

void init() {
    memset(t, 0, sizeof(int) * (n << 2));
}

int lowb(int x) {
    return x & (-x);
}

void update(int x, ll k) {
    for (; x <= n; x += lowb(x)) t[x] += k;
}

int query(int x) {
    ll res = 0;
    for (; x > 0; x -= lowb(x)) res += t[x];
    return res;
}

void modlify(int l, int r) {
    if (l > r) return;
    l = max(l, 1);
    update(l, 1);
    update(r + 1, -1);
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        init();

        for (int i = n; i > 0; i--) {
            if (a[i] > 0) modlify(i - a[i] + 1, i);
        }
        
        for (int i = 1; i <= n; i++) {
            if (query(i) > 0) printf("1 ");
            else printf("0 ");
        }
        puts("");
    }
}

C. Going Home

链接：https://codeforces.com/problemset/problem/1501/C

题目大意

给定n个数（$n\leq 2e5$）$a_1,a_2……a_n$（$a_i\leq2.5e6$），找出四个不同的整数x，y，z，w，使得$a_x+a_y=a_z+a_w$。

分析

看到题目你是不是想到了meeting in the middle？如果是，那么你答对了$\sqrt{max(n)}$。

如果只看n的范围，不难猜测，我们需要在$O(n\log n)$的时间内解决这个问题，显然这几乎是不可能（是我能解决）的。但是$a_i$的值域给了一个非常奇怪的数2.5e6，这让我们有了操作空间。

首先，如果同一个数出现超过三次，那么可以很显然的得到答案，所以，我们考虑所有数出现的次数都小于等于3的情况。

此时，就算序列a中的每一个数都出现了3次，我们依然有超过5e4个不同的数。

我们先把序列a从小到大排列，再把重复的数去掉，得到新的序列$A_1,A_2……A_m$。再对序列A做差分，得到序列$b1,b2……bm-1$，其中$b_i=a_{i+1}-a_i$。

此时，我们可以得到结论：$若i-j\geq 2 \ 且\ b_i=b_j $，那么i+1，j，i，j+1就是所求解。

那么我们假设出题者非常恶毒，他想使所有的$b_i$都尽量不相等！那么在最严苛的条件下，就有:

$b_1=1, \\ b_2=1, \\ b_3=2, \\ b_4=2, \\ …… \\ b_n=\lceil \frac n 2 \rceil$

这时就恰好无解了（很烦）。

我们在这个条件下我们对序列b求和:

$\sum{b_i}\approx 2*\frac {(1+\frac n 2)*\frac n 2} 2\\ =(1+\frac n 2)*\frac n 2 \\ \approx \frac {n^2} 4$

$又\because \ \ \ \ \ \sum b_i=max\{a_i\}-min\{a_i\}=2.5e6=A_m-A_1$（因为是差分）

$\therefore\ \ \ A_m-A_1=\frac {n^2} 4$

如果此时，我们将某个$b_i（i>2）$减少1，那么就变成了：

$\therefore\ \ \ A_m-A_1=\frac {n^2} 4-1<\frac {n^2} 4$

注意，序列b是对序列A差分得到，因此b的和永远是$A_m-A_1(等式左边)$，但是，$\frac {n^2} 4$是由等差数列求和算的。当$b_i$发生变化时，序列b就不再是等差数列，因此求和也不可以再直接由等差数列求和得到（但是可以通过补全为等差数列求和得到）。

不难发现某个$b_i（i>2）$减少1后，就必然会出现元素相同的情况，此时满足$i-j\geq 2 \ 且\ b_i=b_j $，因此一定有解。

同理，如果继续减小$b_i（i>2）$，也必然会有解的，

因此，当$\therefore\ \ \ A_m-A_1<\frac {n^2} 4$时，我们一定能找到解。

由于，$A_m-A_1<2.5e6$，所以只要$n>1000\sqrt 10\approx3162.27$，就必然有解，且必然有一组解是在序列A中两对不相交的相邻的两个数。

如果不满足这个条件，由于数据很小，暴力就好了，~~芜湖！~~

另外如果你足够有耐心，也可以精确算出必然有解的条件（注意上述过程只是估算，实际上n的取值最好大于3200）。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;

struct node {
    // val = x - y (n>3e3)
    // val = x + y (else)
    int val, x, y;

    node(int v, int xx, int yy) : val(v), x(xx), y(yy) {}

    bool operator<(const node &rhs) const {
        return val < rhs.val;
    }
};

int a[N], b[N], n;


int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        b[i] = a[i];
    }

    set<node> s;
    if (n > 3e3) {
        int ans[4];

        sort(a, a + n);
        node t(0, 0, 0);
        for (int i = 1; i < n; i++) {
            if (i > 1 && s.count(node(a[i] - a[i - 1], 0, 0))) {
                auto x = s.find(node(a[i] - a[i - 1], 0, 0));
                printf("YES\n");
                ans[0] = x->x;
                ans[1] = i - 1;
                ans[2] = x->y;
                ans[3] = i;
                break;
            }
            if (i > 1) s.insert(t); // 注意这里的细节，不能直接插入
            t = node(a[i] - a[i - 1], i, i - 1);
        }

        for (int k = 0; k < 4; k++) {
            int i = ans[k];
            for (int j = 0; j < n; j++)
                if (a[i] == b[j]) {
                    int ok = 1;
                    for (int kk = 0; kk < k; kk++)
                        if (ans[kk] == j) {
                            ok = 0;
                            break;
                        }
                    if (ok) ans[k] = j;
                }
        }

        for (int an : ans) printf("%d ", an + 1);
        puts("");
    } else {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++)
                    if (i != j && !s.count(node(a[i] + a[j], 0, 0)))
                        s.insert(node(a[i] + a[j], i, j));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < i; j++) if (i != j) {
                    if (s.count(node(a[i] + a[j], 0, 0))) {
                        auto p = s.find(node(a[i] + a[j], 0, 0));
                        if (p->x != i && p->y != j && p->x != j && p->y != i) {
                            printf("YES\n");
                            printf("%d %d %d %d\n", i + 1, j + 1, p->x + 1, p->y + 1);
                            return 0;
                        }
                    }
                }
        printf("NO\n");
    }
}