whvp 1 - Codeforces Round #763 (Div. 2)

whvp 1 - Codeforces Round #763 (Div. 2) whvp 1 - Codeforces Round #763 (Div. 2)

Codeforces Round #763 (Div. 2)

确实好久没打了都快不会打代码了

A. Robot Cleaner

题意：给一个 n × m n times m n×m的地图，有一个机器人，起始（x， y）, 他每一秒会将当前位置x轴y轴方向的十字交叉上的格子全部清理干净，移动方向刚开始是x轴+1，y轴+1，如果碰到边界+1会变-1，-1会变+1，请问多少秒之后他能清理到目标位置（a，b）

注意到数据范围不大，直接按题意暴力

#include 

using namespace std;

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m, x, y, a, b;
        cin >> n >> m >> x >> y >> a >> b;

        int cnt = 0;
        int dx = 1, dy = 1;
        while (1) {
            if (x == a || y == b) {
                break;
            }
            cnt++;
            if (x + dx > n) {
                dx = -dx;
                x = x + dx;
            } else {
                x = x + dx;
            }
            if (y + dy > m) {
                dy = -dy;
                y = y + dy;
            } else {
                y = y + dy;
            }

        }
        cout << cnt << endl;
    }


}

B. Game on Ranges

题意：给一个数字n，刚开始区间是[1, n]， A每次给出一个区间，B选取一个区间中的数字，然后从区间中拿走这个数字，区间变成两个区间或长度-1（[a, b] , 拿走c, a ≤ c ≤ b a leq c leq b a≤c≤b， 区间变成[a, c-1], [c +1, b]），直到所有数都被拿完位置，给出A每次给出的区间（顺序可能打乱），问B每次选的数字是多少。

对于区间[a,b ],拿走c后的[a, c-1], [c +1, b]必然也会出现，暴力枚举[a, b]中的数字判断是否存在对应的[a, c-1], [c +1, b]

#include 

using namespace std;

const int N = 1010;

struct node {
    int l, r;
};

node mp[N];
map, int> exist;

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        exist.clear();
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> mp[i].l >> mp[i].r;
            exist[{mp[i].l, mp[i].r}] = 1;
        }
        for (int i = 1; i <= n; ++i) {
            int l = mp[i].l;
            int r = mp[i].r;
            if (l == r) {
                cout << l << " " << r <<" "<< l << endl;
                continue;
            }
            for (int j = l; j <= r; ++j) {
                if ((j == l || exist[{l, j - 1}]) && (j == r || exist[{j + 1, r}])) {
                    cout << l << " " << r << " " << j << endl;
                    break;
                }
            }
        }
    }
    return 0;
}

C .Balanced Stone Heaps

题意：有n堆石头，一次 *** 作定义为从第i堆取出不超过该堆石子数的 3 × d 3 times d 3×d个石头，将d个给i-1堆， 2 × d 2times d 2×d个给i-2堆， 以3到n的顺序依次 *** 作，问每堆石子最小值最大是多少

经典二分答案，但在判断的时候注意倒着，取原先石子数和能从后续石子中得到的石子减去当前二分答案中的较小者。(倒着是为了得到后续石子堆中能过来的石子数，）

#include 

using namespace std;

typedef long long ll;
const ll N = 2e5 + 10;
ll h[N], tmp[N];
ll n;

bool check(ll x) {
    for (ll i = 1; i <= n; ++i) {
        tmp[i] = h[i];
    }
    for (ll i = n; i >= 3; --i) {
        if (tmp[i] < x) return false;
        ll d = min(h[i], tmp[i] - x) / 3;
        tmp[i - 1] += d;
        tmp[i - 2] += d * 2;
    }
    return (tmp[2] >= x && tmp[1] >= x);
}

signed main() {
    ll T;
    cin >> T;

    while (T--) {
        cin >> n;
        for (ll i = 1; i <= n; ++i) {
            cin >> h[i];
        }
        ll l = 0, r = 1e9 + 10, ans = 0;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            //            cerr << mid << endl;
            if (check(mid)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << ans << endl;
    }
}

D. Robot Cleaner Revisit

题意 ：在A题的基础上加上了每一步清理的概率P，要求精确值对1e9+7取模

看了题解非常妙，就是说机器人走的状态（位置和朝向）其实会成环，对于每一个状态设一个变量表示从这个状态开始最后的答案，每个变量其实是由上一个状态的变量值+1乘上没有触发清理的概率，如果当前位置与目标位置不在一条直线上这个概率就是1，否则就是1-P，然后就可以变成一个方程。解方程就可。

最后一层层展开，将方程化为 x = u + vx 的形式

#include 

using namespace std;

typedef long long ll;
const ll mod = 1e9 + 7;

ll qpow(ll x, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

signed main() {
    ll T;
    cin >> T;
    while (T--) {
        ll n, m, x, y, a, b, P;
        ll v = 1, u = 0;
        cin >> n >> m >> x >> y >> a >> b >> P;
        ll p = (ll) (100 - P) * qpow(100, mod - 2) % mod;
        ll tt = 4ll * (n - 1) * (m - 1);
        ll dx = -1, dy = -1;
        for (ll i = 0; i < tt; ++i) {
            if (x + dx > n || x + dx < 1) dx = -dx;
            if (y + dy > m || y + dy < 1) dy = -dy;
            x = x + dx;
            y = y + dy;
            //cerr << "(" << x <<" , " << y << ")" << endl;
            u = (u + 1) % mod;
            if (x == a || y == b) {
                v = v * p % mod;
                u = u * p % mod;
            }
        }
        //cerr << u << " " << v << endl;
        cout << u * qpow((1 - v + mod) % mod, mod - 2) % mod << endl;
    }
}