Codeforces ラウンド #149 (ディビジョン 2)_html/css_WEB-ITnose

このラウンドはとてもシンプルです。 。
A と B については話しません


C 質問では、有効なポイントの数が 10^5 を超えないと言っています
それから、それを直接離散化し、その後 bfs を実行するだけです

D のボタンを押していることに注意してください。この質問は、間接的ではなく、直接隣接する点に変化を引き起こします

そこで、アイデアがあります。

状態の場合、いくつかの点の値が配列の対応する値と同じである場合。

その後、これらのポイントを押した後、これらのポイントは、必ずキューに入れてください。押す必要がある新しいポイントが表示されたら、それをキューの最後に追加します

最後に、すべてのポイントが押された場合でも、a の対応する値と同じ状況が表示されます

それ-1 が出力されます

なぜこれが機能するのでしょうか? 考えてみればわかります

ある状態の場合、違法なポイントを押すと、その周りに押された人がいる場合、これらが合法になります。押されたものは合法である必要があり、それを再度変更することは合法になります、

周囲の変更が違法になっている場合、これらの違法なものは依然として押される必要があります。 そう考えると、-1 の状況は実際には存在しません。 (データには-1はないようです)

押すと隣接リストが直結します シミュレーションするだけですが、各点は1回しかクリックできないので、各エッジは最大2回訪問できます

#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <ctime>#include <set>#include <vector>#include <map>#define MAXN 111#define MAXM 55555#define INF 1000000007using namespace std;int xa, ya, xb, yb;int n;struct node {    int r, x, y;}p[111111];struct P {    int x, y;}f[111111];bool cmp(node x, node y) {    if(x.r != y.r) return x.r < y.r;    if(x.x != y.x) return x.x < y.x;    return x.y < y.y;}map<long long, int> mp;long long getnum(long long x, long long y) {    return x * (long long)INF + y;}int xx[] = {0, 0, 1, -1, 1, 1, -1, -1};int yy[] = {1, -1, 0, 0, -1, 1, -1, 1};int vis[111111];int q[111111];int ans[111111];bool ok(int mv) {    if(!mv) return false;    if(vis[mv]) return false;    return true;}void bfs() {    int h = 0, t = 0;    vis[1] = 1;    q[t++] = 1;    while(h < t) {        int u = q[h++];        for(int i = 0; i < 8; i++) {            int tx = f[u].x + xx[i];            int ty = f[u].y + yy[i];            int mv = mp[getnum(tx, ty)];            if(ok(mv)) {                ans[mv] = ans[u] + 1;                q[t++] = mv;                vis[mv] = 1;            }        }    }    if(!ans[2]) printf("-1\n");    else printf("%d\n", ans[2]);}int main(){    scanf("%d%d%d%d", &xa, &ya, &xb, &yb);    int idx = 2;    mp[getnum(xa, ya)] = 1;    mp[getnum(xb, yb)] = 2;    f[1].x = xa;    f[1].y = ya;    f[2].x = xb;    f[2].y = yb;    scanf("%d", &n);    for(int i = 0; i < n; i++) {        scanf("%d%d%d", &p[i].r, &p[i].x, &p[i].y);    }    sort(p, p + n, cmp);    for(int i = 0; i < n; i++) {        for(int j = p[i].x; j <= p[i].y; j++) {            long long tmp = getnum(p[i].r, j);            if(!mp[tmp]) {                mp[tmp] = ++idx;                f[idx].x = p[i].r;                f[idx].y = j;            }        }    }    if(xa == xb && ya == yb) {        printf("0\n");        return 0;    }    bfs();    return 0;}

E 非常に古い質問、ある USACO の質問
のバリエーション
線分ツリーを少しずつ構築することが問題です

りー