【XJTU 2020暑期集训】Day18 - 2019 XX Open Cup GP of Warsaw

传送门：Gym 102341

A - Alakazam

对于shuffle操作，相当于将区间 [l,r] 内的所有值设置成该区间的平均值，每次询问即为单点查值，线段树维护即可。

C - Cloyster

首先由题目条件「所有格子的值互不相同，且非最大值格子的周围8个格子中一定存在比它更大的值」，显然有结论：从任何一个格子出发，不断走向周围的最大值，最终一定能到达全局最大值的格子。

对于最中间的一行，询问其上每一个格子的值并找出最大的那个格子 (x,y)，然后询问它周围的8个格子，此时有三种情况：当它比周围的格子都大时，那么它一定是全局最大值；当另一个比它大的格子 (x',y') 在中间行的上方时，由上述结论可知，从 (x,y) 出发经 (x',y') 到达全局最大值的路径一定不可能穿过中间行到达中间行的下方区域，所以此时全局最大值只能在中间行上方；当另一个比它大的格子在中间行的下方时，同理可知全局最大值一定在中间行下方。

需要注意的是，当我们第一次切去一半的区域后，上述做法的正确性会失效，因为有可能存在递增路径从 (x',y') 出发，先穿出边界后再穿入边界到达分界线的另一边。但是注意到穿入点的值一定比 (x',y') 更大，所以我们可以维护所有已询问格子的最大值及其位置，并以此最大值判断全局最大值的位置即可。

因此我们不断地横竖切分原始区域，可以在 \log_2 n 次切分后得到 1\times 1 的区域，即为答案所在位置。计算可得总询问次数约为 2n+6\log_2 n，显然小于询问次数限制。

J - Jigglypuff

对于一个格子，如果它右边和下面和它相邻的两个格子的字母相同，则称这个格子为好格子。存在三条不同路径满足构成的字符串均相同的充要条件为，存在两个好格子 (x_1,y_1) 和 (x_2,y_2)，满足 x_1\lt x_2,y_1\lt y_2 或 (x_1+1,y_1)=(x_2,y_2) 或 (x_1,y_1+1)=(x_2,y_2)。所以 O(nm) 判断即可。

Code

A - Alakazam

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <iomanip>
#define MAX_N 250005
#define MAX_T 1000005

using namespace std;

int n, q;
double w[MAX_T];
double tag[MAX_T];

void pushdown(int k, int l, int m, int r) {
    if (tag[k] >= 0) {
        w[k << 1] = (m - l + 1) * tag[k];
        w[k << 1 | 1] = (r - m) * tag[k];
        tag[k << 1] = tag[k];
        tag[k << 1 | 1] = tag[k];
        tag[k] = -1;
    }
}

void pushup(int k) {
    w[k] = w[k << 1] + w[k << 1 | 1];
}

void upd(int a, int b, int k, int l, int r, double x) {
    if (a <= l && r <= b) {
        w[k] = (r - l + 1) * x;
        tag[k] = x;
        return;
    }
    int m = (l + r) >> 1;
    pushdown(k, l, m, r);
    if (a <= m) {
        upd(a, b, k << 1, l, m, x);
    }
    if (b > m) {
        upd(a, b, k << 1 | 1, m + 1, r, x);
    }
    pushup(k);
}

double ask(int a, int b, int k, int l, int r) {
    if (a <= l && r <= b) {
        return w[k];
    }
    int m = (l + r) >> 1;
    double ans = 0;
    pushdown(k, l, m, r);
    if (a <= m) {
        ans += ask(a, b, k << 1, l, m);
    }
    if (b > m) {
        ans += ask(a, b, k << 1 | 1, m + 1, r);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 0; i < MAX_T; i++) {
        tag[i] = -1;
    }
    int x, y;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        upd(i, i, 1, 1, n, x);
    }
    string s;
    while (q--) {
        cin >> s >> x;
        if (s == "get") {
            cout << fixed << setprecision(12) << ask(x, x, 1, 1, n) << endl;
        } else {
            cin >> y;
            double sum = ask(x, y, 1, 1, n);
            upd(x, y, 1, 1, n, sum / (y - x + 1));
        }
    }
}

C - Cloyster

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 2005
#define pii pair<int, int>

using namespace std;

const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n, mx = 0;
int a[MAX_N][MAX_N];
pii pmx(-1, -1);

int ask(int x, int y) {
    if (a[x][y]) {
        return a[x][y];
    }
    cout << "? " << x << " " << y << endl;
    cin >> a[x][y];
    if (a[x][y] > mx) {
        mx = a[x][y], pmx = pii(x, y);
    }
    return a[x][y];
}

void print(int x, int y) {
    cout << "! " << x << " " << y << endl;
}

bool ok(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= n;
}

bool check(int x, int y) {
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (ok(nx, ny) && ask(x, y) < ask(nx, ny)) {
            return false;
        }
    }
    return true;
}

void solve(int x1, int y1, int x2, int y2, bool stp) {
    if (x1 == x2 && y1 == y2) {
        print(x1, y1);
        return;
    }
    if (stp) {
        int xm = (x1 + x2) >> 1;
        int pos = y1, mx = ask(xm, y1);
        for (int i = y1 + 1; i <= y2; i++) {
            int t = ask(xm, i);
            if (t > mx) {
                mx = t, pos = i;
            }
        }
        if (check(xm, pos)) {
            print(xm, pos);
            return;
        }
        if (pmx.first < xm) {
            solve(x1, y1, xm - 1, y2, !stp);
        } else {
            solve(xm + 1, y1, x2, y2, !stp);
        }
    } else {
        int ym = (y1 + y2) >> 1;
        int pos = x1, mx = ask(x1, ym);
        for (int i = x1 + 1; i <= x2; i++) {
            int t = ask(i, ym);
            if (t > mx) {
                mx = t, pos = i;
            }
        }
        if (check(pos, ym)) {
            print(pos, ym);
            return;
        }
        if (pmx.second < ym) {
            solve(x1, y1, x2, ym - 1, !stp);
        } else {
            solve(x1, ym + 1, x2, y2, !stp);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    solve(1, 1, n, n, true);
}

J - Jigglypuff

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 3005

using namespace std;

int n, m;
int ok[MAX_N][MAX_N];
int a[MAX_N][MAX_N];
char s[MAX_N][MAX_N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (s[i + 1][j] == s[i][j + 1]) {
                ok[i][j] = 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = ok[i][j] + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (ok[i][j]) {
                if (a[i - 1][j - 1] || ok[i - 1][j] || ok[i][j - 1]) {
                    printf("YES\n");
                    return 0;
                }
            }
        }
    }
    printf("NO\n");
}