杭电多校9补题记录

1007: Game

还剩一个小时的时候，打算用Splay码一发。码代码20分钟，剩下的时间全在debug

结果

赛后过题

#include <bits/stdc++.h>
#define ll long long
#define int long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_inputlarge freopen("./input_large.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<int, int>
#define sqr(x) ((x)*(x))
using namespace std;

const int maxn = 2e5 + 1000;

const int _bfsz = 7e6 + 1000;
char _buffer[_bfsz], *_head, *_tail;
char Getchar(){
    if(_head == _tail){
        _tail = (_head = _buffer) + fread(_buffer, 1, _bfsz, stdin);
        if(_tail == _head) return -1;
    }
    return *(_head++);
}

int read(){
    int ret = 0, op = 1;
    char c = Getchar();
    while(!isdigit(c)) {if(c == '-') op *= -1; c = Getchar();}
    while(isdigit(c)) ret = ret * 10 + c - '0', c = Getchar();
    return ret * op;
}

int b[maxn], n, q;

int child[maxn][2], par[maxn], sz[maxn]={0};
ll sum[maxn], val[maxn], mn[maxn];
int root, nrof_node, empty_node, padding_node;

#define lc child[rt][0]
#define rc child[rt][1]

inline void push_up(int rt){
    sz[rt] = sz[lc] + sz[rc] + 1;
    sum[rt] = sum[lc] + sum[rc] + val[rt];
    mn[rt] = val[rt];
    if(lc) mn[rt] = min(mn[rt], mn[lc]);
    if(rc) mn[rt] = min(mn[rt], mn[rc]);
}

int build_tree(int l, int r, int p){
    if(l > r) return 0;
    int idx = ++nrof_node;
    int mid = (l + r)>>1;
    mn[idx] = val[idx] = b[mid], par[idx] = p;
    if(mid == 0) empty_node = idx;
    if(mid == n + 1) padding_node = idx;
    child[idx][0] = build_tree(l, mid-1, idx);
    child[idx][1] = build_tree(mid+1, r, idx);
    push_up(idx);
    return idx;
}

#define chk(x) (child[par[x]][1] == x)

void rotate(int rt){
    int p = par[rt], g = par[p];
    int k = chk(rt), op = child[rt][k^1];
    child[g][chk(p)] = rt, par[rt] = g;
    child[p][k] = op, par[op] = p;
    child[rt][k^1] = p, par[p] = rt;
    push_up(p); push_up(rt);
}

void splay(int rt, int goal = 0){
    while(par[rt] != goal){
        if(par[par[rt]] != goal){
            if(chk(rt) == chk(par[rt])) rotate(par[rt]);
            else rotate(rt);
        }
        rotate(rt);
    }
    if(!goal) root = rt;
}

int find(int pos){
    int cur = root;
    while(cur){
        if(sz[child[cur][0]] + 1 == pos) return cur;
        if(sz[child[cur][0]] >= pos){
            cur = child[cur][0];
        }else{
            pos -= sz[child[cur][0]] + 1;
            cur = child[cur][1];
        }
    }
    assert(false);
    return -1;
}

int find_fst_less(int rt, int lim){
    while(true){
        if(rc != 0 && mn[rc] < lim) {
            rt = rc;
        }else if(val[rt] < lim){
            return rt;
        }else{
            rt = lc;
        }
    }
    return rt;
}

int find_rmst(int rt){
    while(child[rt][1] != 0) rt = child[rt][1];
    return rt;
}

int find_lmst(int rt){
    while(child[rt][0] != 0) rt = child[rt][0];
    return rt;
}

void chain_upd(int rt){
    while(rt != 0){
        push_up(rt);
        rt = par[rt];
    }
}

bool begining;

void dfs(int rt){
    if(child[rt][0]) dfs(child[rt][0]);
    if(rt != empty_node && rt != padding_node) {
        if(!begining) cout << ' ';
        begining = false;
        cout << val[rt];
    }
    if(child[rt][1]) dfs(child[rt][1]);
}

void solve(){
    begining = true;
    nrof_node = 0;

    n = read(), q = read();
    for(int i=1; i<=n; i++) b[i] = read();
    root = build_tree(0, n+1, 0);
    
    int left, right, l1, len;
    for(int i=0, op, x, y; i<q; i++){
        op = read();
        if(op == 1){
            x = read(), y = read();
            splay(find(x + 2));

            left = find_fst_less(child[root][0], y);
            if(left == empty_node){
                cout << "0\n";
                continue;
            }
            splay(left, root);

            right = find_rmst(child[root][0]);
            if(left == right){
                cout << "0\n";
                continue;
            }
            
            len = sz[child[left][1]];
            cout << sum[child[left][1]] - 1ll * len * (y - 1) << '\n';

            l1 = find_lmst(child[left][1]);
            val[left] += val[l1] - y + 1;

            child[par[l1]][chk(l1)] = child[l1][1];
            if(child[l1][1]) par[child[l1][1]] = par[l1];
            child[l1][1] = 0;
            chain_upd(par[l1]);

            val[l1] = y - 1;
            if(l1 != right){
                child[right][1] = l1;
                par[l1] = right;
            }else{
                child[par[l1]][1] = l1;
            }
            chain_upd(l1);

        }else{
            splay(find(read() + 1));
            cout << val[root] << '\n';
        }
    }

    dfs(root);
    cout << '\n';
}

signed main(){
    int t = read();
    while(t--) solve();
}

1003: Slime and Stones (HDU 6869)

威佐夫博弈变形

观察奇异局势$(a,b)$，可以得到$b_n=a_n+n(k+1)$

求得Betty定理对应的两个无理数为

$$\begin{aligned}p&=\frac{1-k+\sqrt{k^2+2k+5} }{2}\\q&=\frac{3+k+\sqrt{k^2+2k+5} }{2} \end{aligned}$$

最后判断一下$a=\lfloor\frac{b-a}{k+1}p\rfloor$（或$b=\lfloor\frac{b-a}{k+1}q\rfloor$）是否成立即可，不需要二分

AC代码

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

int solve(){
    ll a, b, k, n;
    cin >> a >> b >> k;
    if(a == 0 && b == 0) return 0;
    
    if(a > b) swap(a, b);
    if((b - a) % (k + 1) != 0) return 1;

    double factor = (1 - k + sqrt(k * k + 2 * k + 5)) / 2.0;
    n = (b - a) / (k + 1);
    return (int)(n * factor) != a;
}

signed main(){
    Android;
    int t; cin >> t;
    while(t--){
        cout << solve() << '\n';
    }
}