本文共 16755 字，大约阅读时间需要 55 分钟。

Problem A. Axis of Symmetry

留坑。

Problem B. Binary Tree

因为每次取出的满二叉树的节点个数是奇数，所以是奇数等价于先手必赢。

#include<bits/stdc++.h>using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    while(T --)    {        int n ;        cin >> n ;        for(int i = 0 ; i < n - 1 ; i ++)        {            int x , y ;            cin >> x >> y ;        }        if(n % 2 == 1)  cout << "Alice\n" ;        else  cout << "Bob\n" ;    }    return 0 ;}

Problem C. Constructing Ranches

多边形的最长边的二倍大于多边形的周长。点分治维护即可。

#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>#define fi first#define se secondusing namespace std;using namespace __gnu_pbds;using ll = long long;using pil = pair<int, ll>;using pli = pair<ll, int>;template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;const int N = 2e5 + 5;int n, a[N], tot;int rt, sz[N], dp[N], mxsz;pil mes[N];ll ans;vector<int> G[N];bool vis[N];void findroot(int u, int fa) {    dp[u] = 0, sz[u] = 1;    for(int v : G[u])    {        if(vis[v]||v==fa) continue;        findroot(v, u);        dp[u] = max(dp[u], sz[v]);        sz[u] += sz[v];    }    dp[u] = max(dp[u], mxsz-sz[u]);    if(dp[u]<dp[rt]) rt = u;}void getmes(int u, int fa, pil d){    pil nd = {max(a[u], d.fi), a[u]+d.se};    mes[++tot] = nd;    for(int v : G[u])    {        if(vis[v]||v==fa) continue;        getmes(v, u, nd);    }}ll calcu(int u, pil d, int ext){    ll ans = 0;    tot = 0;    getmes(u, 0, d);    sort(mes+1, mes+tot+1);    ordered_set<pli> tr;    for(int i=1; i<=tot; i++)    {        ans += i - 1 - tr.order_of_key({mes[i].fi*2-mes[i].se+1+ext, 0});        tr.insert({mes[i].se, i});    }    return ans; }void Divide(int u) {    vis[u] = 1;    ans += calcu(u, {0, 0}, a[u]);     for(int v : G[u])    {        if(vis[v]) continue;        ans -= calcu(v, {a[u], a[u]}, a[u]);         mxsz = sz[v], rt = 0;        findroot(v, u);        Divide(rt);    }}void solve(){    scanf("%d", &n);    for(int i=1; i<=n; i++) scanf("%d", a+i), G[i].clear(), vis[i] = 0;    for(int i=1; i<n; i++)    {        int u, v; scanf("%d%d", &u, &v);        G[u].push_back(v), G[v].push_back(u);    }    rt = 0, ans = 0;    dp[0] = mxsz = n;    findroot(1, 0);    Divide(rt);    printf("%lld\n", ans);}int main(){    int _; scanf("%d", &_);    while(_--) solve();    return 0;}

Problem D. Defining Labels

先固定答案的长度，再从高位到低位枚举每一位的数值。

#include<bits/stdc++.h>using namespace std ;int main(){    //std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    while(T --)    {        int k ;        long long x ;        cin >> k >> x ;        int d = 10 - k ;        int t = 9 - d + 1 ;        int len = 1 ;        long long res = 1 ;        //long long tk = k ;        while(1)        {            res *= t ;            //cout << k << ' ' << res << '\n' ;            if(x - res > 0)  x -= res , len ++ ;            else  break ;        }        //cout << len << '\n' ;        res = 1 ;        for(int i = 1 ; i <= len ; i ++)  res *= t ;        //cout << d << '\n' ;        for(int i = 1 ; i <= len ; i ++)        {            res /= t ;            for(int j = d ; j <= 9 ; j ++)            {                //cout << res << '\n' ;                if(x > res)  x -= res ;                else                {                    cout << j ;                    break ;                }            }        }        cout << '\n' ;    }    return 0 ;}

Problem E. Erasing Numbers

枚举判断第个数能不能保留，大于的数看作，小于的数看作。能保留第个数的局面是个数相等。

首先发现跨越并保留的删除操作不能改变个数的相对大小。那就可以把左右两边分开考虑。

可以发现如果一个子序列的个数的差值大于等于，那就可以使这个差值减小。所以扫一遍就好了，具体实现看代码。

#include<bits/stdc++.h>using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    while(T --)    {        int n ;        cin >> n ;        vector<int> p(n + 1) ;        for(int i = 1 ; i <= n ; i ++)  cin >> p[i] ;        function<int(int)> check = [&](int id)        {            int cnt0 = 0 , cnt1 = 0 ;            vector<int> b(n + 1) ;            for(int i = 1 ; i <= n ; i ++)                if(p[i] < p[id])  b[i] = 0 , cnt0 ++ ;                else if(p[i] > p[id])  b[i] = 1 , cnt1 ++ ;            int res = abs(cnt0 - cnt1) ;            if(res == 0)  return 1 ;            int cnt = 0 ;            for(int i = 1 ; i <= id - 1 ; i ++)            {                if(cnt0 > cnt1)                {                    if(b[i] == 0)  cnt ++ ;                    else  cnt -- ;                    cnt = max(cnt , 0) ;                    if(cnt == 3)  cnt -= 2 , res -= 2 ;                }                else                {                    if(b[i] == 1)  cnt ++ ;                    else  cnt -- ;                    cnt = max(cnt , 0) ;                    if(cnt == 3)  cnt -= 2 , res -= 2 ;                }            }            cnt = 0 ;            for(int i = id + 1 ; i <= n ; i ++)            {                if(cnt0 > cnt1)                {                    if(b[i] == 0)  cnt ++ ;                    else  cnt -- ;                    cnt = max(cnt , 0) ;                    if(cnt == 3)  cnt -= 2 , res -= 2 ;                }                else                {                    if(b[i] == 1)  cnt ++ ;                    else  cnt -- ;                    cnt = max(cnt , 0) ;                    if(cnt == 3)  cnt -= 2 , res -= 2 ;                }            }            if(res <= 0)  return 1 ;            else return 0 ;        } ;        for(int i = 1 ; i <= n ; i ++)  cout << check(i) ;        cout << '\n' ;    }    return 0 ;}

Problem F. Falling Objects

留坑。

Problem G. Game Design

考虑用二叉树构造。

设表示以为根的二叉树的方案数，是的左右儿子，容易发现。

考虑从根节点逐步到叶子节点构造。

当前是奇数，左儿子的方案数设置为，右儿子的方案数设置为。

当前是偶数，左儿子的方案数设置为，右儿子的方案数设置为，这样就转成了奇数做。

根节点初始权值设置为，每个儿子的权值是父亲的一半。假如当前权值是，儿子不再具有权值了，那么直接挂一个长度是的链就好了。

#include<bits/stdc++.h>using namespace std ;const int maxn = 1e5 + 10 ;int cnt = 0 ;int fa[maxn] ;int c[maxn] ;void dfs(int u , int val , int k){    c[u] = val ;    if(val == 1)    {        for(int i = 1 ; i <= k - 1 ; i ++)        {            cnt ++ ;            fa[cnt] = cnt - 1 ;            c[cnt] = 1 ;        }        return ;    }    if(k == 1)  return ;    if(k % 2 == 1)    {        cnt ++ ;        fa[cnt] = u ;        dfs(cnt , val / 2 , 2) ;        cnt ++ ;        fa[cnt] = u ;        dfs(cnt , val / 2 , k / 2) ;    }    else    {        if(k == 2)        {            cnt ++ ;            fa[cnt] = u ;            dfs(cnt , val / 2 , 1) ;            cnt ++ ;            fa[cnt] = u ;            dfs(cnt , val / 2 , 1) ;        }        else        {            cnt ++ ;            fa[cnt] = u ;            dfs(cnt , val / 2 , 1) ;            cnt ++ ;            fa[cnt] = u ;            dfs(cnt , val / 2 , k - 1) ;        }    }}int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int k ;    cin >> k ;    if(k == 1)    {        cout << "2\n" ;        cout << "1\n" ;        cout << "2 1\n" ;    }    else if(k == 2)    {        cout << "2\n" ;        cout << "1\n" ;        cout << "1 1\n" ;    }    else    {        cnt = 1 ;        dfs(1 , 1 << 29 , k) ;        cout << cnt << '\n' ;        for(int i = 2 ; i <= cnt ; i ++)  cout << fa[i] << " \n"[i == cnt] ;        for(int i = 1 ; i <= cnt ; i ++)  cout << c[i] << " \n"[i == cnt] ;    }    return 0 ;}

Problem H. Hold the Line

直接的做法是线段树套，常数巨大过不去。

然后考虑通过离线优化常数。具体实现是线段树套单调栈。

离线时候对于修改和询问按照输入的顺序都打上时间戳。

修改操作记为，表示在时间戳为把位置放上高度是的物品。

询问操作记为，表示在时间戳为，询问区间是，询问高度是。

对于修改和询问，按照右端点升序排列。

对于询问，需要找到满足且最接近的修改操作。

考虑以为下标建造权值线段树，最接近可以分成两半做，最靠右的满足要求的操作的权值，最靠左的满足要求的操作的权值。

在权值线段树上二分至叶子节点即可找到答案，下面分析如何当前节点是否存在符合要求的操作。

对于当前权值范围是的节点，每个节点存一个二元组，因为每个节点判断的是合法性，不考虑是否最优，所以省去了权值，合法性持续至叶子节点即可找到最优权值。

下面分析如何判断合法性，满足，分析对于两个二元组。如果，那么没有存在的必要，可以被覆盖。

因此单调栈性质很明显了，对于每个节点维护一个随着递增，递增的单调栈即可。

对于询问可以在单调栈上二分判定是否存在满足的二元组。

正确性保证：如果一个节点合法，那么它的所有祖先节点都合法。

这题真难，写了个小时。

#include<bits/stdc++.h>using namespace std ;const int maxn = 1e6 + 10 ;vector<pair<int , int>> p[maxn << 2] ;int lson(int x){    return x << 1 ;}int rson(int x){    return x << 1 | 1 ;}void build(int id , int l , int r){    p[id].clear() ;    if(l == r)  return ;    int mid = (l + r) / 2 ;    build(lson(id) , l , mid) ;    build(rson(id) , mid + 1 , r) ;}void push(int id , int h , int pos , int v){    while(p[id].size() > 0 && p[id].back().second > v)  p[id].pop_back() ;    p[id].push_back({pos , v}) ;}void update(int id , int l , int r , int h , int pos , int v){    push(id , h , pos , v) ;    if(l == r)      {        //cout << v << ' ' << h << ' ' << l << ' ' << r << ' ' << p[id].size() << '\n' ;        return ;    }    int mid = (l + r) / 2 ;    if(h <= mid)  update(lson(id) , l , mid , h , pos , v) ;    else  update(rson(id) , mid + 1 , r , h , pos , v) ;    //cout << v << ' ' << h << ' ' << l << ' ' << r << ' ' << p[id].size() << '\n' ;}bool ok(int id , int L , int id2){    pair<int , int> pp = {L , 0} ;    //cout << "??? " << id << ' ' << L << ' ' << id2 << '\n' ;    //cout << "!!! " << p[id][0].first << ' ' << p[id][0].second << '\n' ;    auto it = lower_bound(p[id].begin() , p[id].end() , pp) ;    //cout << "!!! " << (*it).second << '\n' ;    if(it != p[id].end())  return (*it).second < id2 ;    else  return false ;}int query_r(int id , int l , int r , int x , int y , int L , int id2){    int mid = (l + r) / 2 ;    int res = -1 ;    if(r < x)  return -1 ;    if(y < l)  return -1 ;    if(l == r)    {        if(ok(id , L , id2))  return l ;        else  return -1 ;    }    if(x <= l && r <= y && !ok(id , L , id2))  return -1 ;    res = max(res , query_r(rson(id) , mid + 1 , r , x , y , L , id2)) ;    if(res == -1)  res = max(res , query_r(lson(id) , l , mid , x , y , L , id2)) ;    return res ;}int query_l(int id , int l , int r , int x , int y , int L , int id2){    int mid = (l + r) / 2 ;    int res = 1e9 + 1e8 ;    //cout << "*** " << id2 << '\n' ;    if(r < x)  return 1e9 + 1e8 ;    if(y < l)  return 1e9 + 1e8 ;    if(l == r)    {        if(ok(id , L , id2))  return l ;        else  return 1e9 + 1e8 ;    }    if(x <= l && r <= y && !ok(id , L , id2))  return 1e9 + 1e8 ;    res = min(res , query_l(lson(id) , l , mid , x , y , L , id2)) ;    if(res > 1e9 + 1e7)  res = min(res , query_l(rson(id) , mid + 1 , r , x , y , L , id2)) ;    return res ;}int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    while(T --)    {        int n , m ;        cin >> n >> m ;        vector<vector<pair<int , int>>> v1(n + 1) ; //change        vector<vector<array<int , 3>>> v2(n + 1) ; //query        vector<int> val ;        for(int i = 1 ; i <= m ; i ++)        {            int op ;            cin >> op ;            if(op == 0)            {                int x , h ;                cin >> x >> h ;                v1[x].push_back({h , i}) ;                val.push_back(h) ;            }            else            {                int l , r , h ;                cin >> l >> r >> h ;                v2[r].push_back({l , h , i}) ;                val.push_back(h) ;            }        }        sort(val.begin() , val.end()) ;        val.erase(unique(val.begin() , val.end()) , val.end()) ;        int siz = val.size() ;        build(1 , 0 , siz - 1) ;        function<int(int , int , int)> ask = [&](int l , int id , int h)        {            int t1 = query_r(1 , 0 , siz - 1 , 0 , h , l , id) ; //right first            int t2 = query_l(1 , 0 , siz - 1 , h + 1 , siz - 1 , l , id) ; //left first            //cout << t1 << ' ' << t2 << '\n' ;            int res = 1e9 + 1e8 ;            //cout << "^^^ " << id << '\n' ;            if(t1 >= 0)  res = min(res , val[h] - val[t1]) ;            if(t2 < 1e9 + 1e7)  res = min(res , val[t2] - val[h]) ;            if(res < 1e9 + 1e7)  return res ;            else  return -1 ;        } ;        vector<pair<int , int>> ans ;        for(int i = 1 ; i <= n ; i ++)        {            for(auto u : v1[i])            {                int h = lower_bound(val.begin() , val.end() , u.first) - val.begin() ;                int v = u.second ;                int pos = i ;                //cout << "$$$ " << h << ' ' << pos << ' ' << v << '\n' ;                update(1 , 0 , siz - 1 , h , pos , v) ;            }            for(auto u : v2[i])            {                int l = u[0] ;                int h = u[1] ;                int id = u[2] ;                //cout << "^^^ " << id << '\n' ;                ans.push_back({id , ask(l , id , lower_bound(val.begin() , val.end() , h) - val.begin())}) ;            }        }        sort(ans.begin() , ans.end()) ;        for(auto u : ans)  cout << u.second << '\n' ;    }    return 0 ;}

Problem I. Incoming Asteroids

每个人的每个观测点全部设置一个阈值，假如某个观测点超过阈值，我就把这个人对应的每个观测点的阈值都更新。

具体实现可以用优先队列或者维护。压着时限过的，建议优先队列，不过我更喜欢用。

#include<bits/stdc++.h>using namespace std ;const int maxn = 2e5 + 10 ;set<array<long long , 3>> s[maxn] ;long long tag[maxn] ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int n , m ;    cin >> n >> m ;    int id = 0 ;    vector<vector<pair<long long , int>>> p(m + 1) ;    vector<int> val(m + 1 , 0) ;    int lst = 0 ;    while(m --)    {        int op ;        cin >> op ;        if(op == 1)        {            int y , k ;            cin >> y >> k ;            y ^= lst ;            id ++ ;            for(int i = 0 ; i < k ; i ++)            {                int x ;                cin >> x ;                x ^= lst ;                p[id].push_back({(y + k - 1) / k + tag[x] , x}) ;                val[id] = y ;                s[x].insert({(y + k - 1) / k + tag[x] , id , tag[x]}) ;            }        }        else        {            int x , y ;            cin >> x >> y ;            x ^= lst ;            y ^= lst ;            tag[x] += y ;            vector<int> ans ;            while(!s[x].empty())            {                auto it = s[x].begin() ;                long long t = (*it)[0] ;                int id = (*it)[1] ;                //cout << t << ' ' << tag[x] << '\n' ;                if(t <= tag[x])                {                    long long sum = 0 ;                    for(auto u : p[id])                    {                        long long val2 = u.first ;                        int id2 = u.second ;                        auto it2 = s[id2].lower_bound({val2 , id , 0}) ;                        sum += tag[id2] - (*it2)[2] ;                        s[id2].erase(it2) ;                    }                    // cout << sum << '\n' ;                    if(val[id] <= sum)  ans.push_back(id) ;                    else                    {                        val[id] -= sum ;                        vector<pair<long long , int>> tmp ;                        int k = p[id].size() ;                        for(auto u : p[id])                        {                            int id2 = u.second ;                            s[id2].insert({tag[id2] + (val[id] + k - 1) / k , id , tag[id2]}) ;                            tmp.push_back({tag[id2] + (val[id] + k - 1) / k , id2}) ;                        }                        swap(tmp , p[id]) ;                    }                }                else  break ;            }            lst = ans.size() ;            sort(ans.begin() , ans.end()) ;            cout << ans.size() ;            for(auto u : ans)  cout << ' ' << u ;            cout << '\n' ;        }    }        return 0 ;}

Problem J. Junior Mathematician

显然有一个N*61*61*61的做法，只需要记录前缀%m的值，前缀的f(x)%m的值，以及前缀各个数字和%m的值（用于递推f(x))，容易发现可以只记录第一维和第二维的差值

#include <bits/stdc++.h>using namespace std;const int N = 5005, mod = 1e9 + 7;char L[N], R[N];int t[N];int m, dp[N][61][61], dm[N];inline void Add(int &x, int y) { x += y; if(x>=mod) x -= mod; }int DP(int b, int lim, int x, int y){    if(b==-1) return !x;    int &v = dp[b][x][y];    if(~v && !lim) return v;    int ans = 0, up = (lim ? t[b] : 9);    for(int i=0; i<=up; i++)    {        int nx = (x + i*dm[b] - i*y)%m;        nx = (nx + m)%m;        int ny = (y + i)%m;        Add(ans, DP(b-1, lim&&i==up, nx, ny));    }    if(!lim) v = ans;    return ans;}int cal(char *s, int n){    reverse(s, s+n);    for(int i=0; i<n; i++) t[i] = s[i] - '0';    return DP(n-1, 1, 0, 0);}bool check(char *s, int n){    int a = 0, b = 0;    for(int i=n-1; i>=0; i--)    {        int d = s[i] - '0';        a = (a + d*dm[i] - d*b);        a = (a + m)%m;        b = (b + d)%m;    }    return !a;}void solve(){    scanf("%s%s", L, R);    scanf("%d", &m);    int up = strlen(R);    dm[0] = 1;    for(int i=1; i<up; i++) dm[i] = dm[i-1]*10%m;    for(int i=0; i<up; i++)         for(int j=0; j<m; j++) memset(dp[i][j], -1, m<<2);    int ans = (cal(R, strlen(R)) - cal(L, strlen(L)) + check(L, strlen(L)) + mod)%mod;    printf("%d\n", ans);}int main(){    int _; scanf("%d", &_);    while(_--) solve();    return 0;}

Problem K. Key Project

模拟费用流

可以O(n)的模拟每次找费用最小的增广路经，并更新反向边的流量