2016-2017 ACM-ICPC CHINA-Final 部分题解-白红宇的个人博客

2016-2017 ACM-ICPC CHINA-Final 部分题解

发布日期：2021-05-06 15:23:49 浏览次数：22 分类：原创文章

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

Problem A. Number Theory Problem

温暖的签到题。

#include<bits/stdc++.h>using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    for(int cas = 1 ; cas <= T ; cas ++)    {        int n ;        cin >> n ;        cout << "Case #" << cas << ": " << n / 3 << '\n' ;    }    return 0 ;}

Problem B. Hemi Palindrome

用数位 $dp$ 的思想写即可。容斥计算前 $i-1$ 位确定，第 $i$ 位是 $0$ ，后 $n-i$ 位不确定的半回文串个数。

容斥计算的方法是奇回文+偶回文-奇偶回文。

细节太多，写的我欲仙欲死。

#include<bits/stdc++.h>using namespace std ;const int maxn = 1e5 + 10 ;const long long inf = 3e18 ;int n ;long long k ;bool flag ;int a[maxn] ;long long p[105] ;bool flag1 , flag0 ;long long qpow(int y){    if(y >= 60)  return 1e18 + 10 ;    return p[y] ;}long long cal1(int i) //所有奇数对称{    if(!flag1)  return 0 ;    int len1 = (i + 1) / 2 ;    int len2 = (n + 1) / 2 ;    if(len1 * 2 >= len2) //奇数没有自由位    {        int len = n / 2 - i / 2 ; //偶数自由位        len = max(len , 0) ;        return qpow(len) ;    }    else    {        int len = n / 2 - i / 2 ; //偶数自由位        len = max(len , 0) ;        int len3 = (len2 - len1 * 2 + 1) / 2 ; //奇数自由位        len3 = max(len3 , 0) ;        return qpow(len3 + len) ;    }}long long cal0(int i) //所有偶数对称{    if(!flag0)  return 0 ;    int len1 = i / 2 ;    int len2 = n / 2 ;    if(len1 * 2 >= len2) //偶数没有自由位    {        int len = (n + 1) / 2 - (i + 1) / 2 ; //奇数自由位        len = max(len , 0) ;        return qpow(len) ;    }    else    {        int len = (n + 1) / 2 - ((i + 1) / 2) ; //奇数自由位        len = max(len , 0) ;        int len3 = (len2 - len1 * 2 + 1) / 2 ; //偶数自由位        len3 = max(len3 , 0) ;        return qpow(len3 + len) ;    }}long long cal10(int i){    if(!flag1 || !flag0)  return 0 ;    int num = 0 ;    int len1 = (i + 1) / 2 ;    int len2 = (n + 1) / 2 ;    if(len1 * 2 < len2)  num += (len2 - len1 * 2 + 1) / 2 ; //奇数自由位    int len3 = i / 2 ;    int len4 = n / 2 ;    if(len3 * 2 < len4)  num += (len4 - len3 * 2 + 1) / 2 ; //偶数自由位    // cout << num << '\n' ;    return qpow(num) ;}long long cal(int i){    long long sum = 0 ;    sum += cal1(i) ;    if(sum >= 3 * k)  return k ;    sum += cal0(i) ;    if(sum >= 3 * k)  return k ;    sum -= cal10(i) ;    // if(i == 3)    // {    //     cout << "!!!" << ' ' << i << ' ' << cal1(i) << ' ' << cal0(i) << ' ' << cal10(i) << '\n' ;    // }    //if(sum < 0)  cout << "!!!" << ' ' << i << ' ' << cal1(i) << ' ' << cal0(i) << ' ' << cal10(i) << '\n' ;    return sum ;}int id1(int i){    return (i - 1) * 2 + 1 ;}int id0(int i){    return i * 2 ;}bool check(int i){    if(i % 2 == 1)    {        int len = (n + 1) / 2 ;        int nxt = id1(len + 1 - (i + 1) / 2) ;        // if(i == 3)        // {        //     cout << "???" << nxt << ' ' << a[nxt] << ' ' << a[i] << '\n' ;        // }        if(nxt < i && nxt >= 1 && a[nxt] != a[i])          {            flag1 = false ;            return false ;        }    }    else    {        int len = n / 2 ;        int nxt = id0(len + 1 - i / 2) ;        if(nxt < i && nxt >= 1 && a[nxt] != a[i])          {            flag0 = false ;            return false ;        }    }    return true ;}void solve(){    if(cal(0) < k)    {        flag = false ;        return ;    }    //cal10(1) ;    //cout << cal1(3) << ' ' << cal0(3) << ' ' << cal10(3) << '\n' ;    for(int i = 1 ; i <= n ; i ++)    {        bool t1 = flag1 ;        bool t0 = flag0 ;        a[i] = 0 ;        check(i) ;        // if(i == 3)        // {        //     cout << a[1] << ' ' << a[3] << ' ' << flag1 << '\n' ;        // }        long long tmp = cal(i) ;        flag1 = t1 ;        flag0 = t0 ;        //cout << i << ' ' << tmp << '\n' ;        if(tmp < k)  k -= tmp , a[i] = 1 , check(i) ;        else  a[i] = 0 , check(i) ;      }}int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    p[0] = 1 ;    for(int i = 1 ; i <= 60 ; i ++)  p[i] = p[i - 1] * 2 ;    int T ;    cin >> T ;    for(int cas = 1 ; cas <= T ; cas ++)    {        cout << "Case #" << cas << ": " ;        cin >> n >> k ;        flag = true ;        flag1 = true ;        flag0 = true ;        solve() ;        if(flag)          {            for(int i = 1 ; i <= n ; i ++)  cout << a[i] ;            cout << '\n' ;        }        else  cout << "NOT FOUND!\n" ;    }    return 0;}

$\dpi{150} jyf$ 写的就很小清新。

#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 1e5 + 5;int kas;int n, ans[N], dif[2], oddmid, evenmid;ll k;int count0(int l, int r){    if(l>r) return 0;    if(l&1) ++l;    if(r&1) --r;    return (r-l+2)>>1;}int count1(int l, int r){    if(l>r) return 0;    if(l%2==0) ++l;    if(r%2==0) --r;    return (r-l+2)>>1;}ll Pow2(int x) { return 1ll<<(min(62, x)); }void upd(int p, int v){    if(p%2==1 && p>oddmid)    {        int rev = 2*oddmid - p;        if(count1(1, n)%2==0) rev += 2;        dif[1] = dif[1] + v*(ans[rev]!=ans[p]);    }    else if(p%2==0 && p>evenmid)    {        int rev = 2*evenmid - p;        if(count0(1, n)%2==0) rev += 2;        dif[0] = dif[0] + v*(ans[rev]!=ans[p]);    }}void solve(){    scanf("%d%lld", &n, &k);    dif[0] = dif[1] = 0;    if(n&1) oddmid = (n+(n%4==1))>>1;    else oddmid = (n>>1) - (n%4==0);    if(n&1) evenmid = (n+(n%4==3))>>1;    else evenmid = (n>>1) + (n%4!=0);    for(int i=1; i<=n; i++)    {        ans[i] = 0;        upd(i, 1);        ll oddcnt = 0, evencnt = 0, allcnt = 0;        if(i<=oddmid) oddcnt = Pow2(n-i-count1(oddmid+2, n));        else if(!dif[1]) oddcnt = Pow2(n-i-count1(i+1, n));        if(i<=evenmid) evencnt = Pow2(n-i-count0(evenmid+2, n));        else if(!dif[0]) evencnt = Pow2(n-i-count0(i+1, n));        if(i<=max(oddmid, evenmid)) allcnt = Pow2(max(oddmid, evenmid)-i);        else if(!dif[0]&&!dif[1]) allcnt = 1;        //cout << oddcnt << ' ' << evencnt << ' ' << allcnt << '\n';        if(oddcnt+evencnt-allcnt<k)         {            k -= oddcnt + evencnt - allcnt;            upd(i, -1);            ans[i] = 1;            upd(i, 1);        }    }    printf("Case #%d: ", ++kas);    if(k==1)    {        for(int i=1; i<=n; i++) printf("%d", ans[i]);        puts("");    }    else puts("NOT FOUND!");}int main(){    int _; scanf("%d", &_);    while(_--) solve();    return 0;}

Problem C. Mr. Panda and Strips

预处理 $dp[l][r]$ 表示 $[l,r]$ 内最长不重复连续子序列长度。

考虑固定左区间的左端点，滑动左区间的右端点。左区间内的数不能在右区间出现，因此滑动左区间右端点时，右边合法区间在逐渐分裂成小区间。 $set$ 维护右边合法区间即可。

时间复杂度 $O(n^2logn)$ 。

#include<bits/stdc++.h>using namespace std ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    vector<bool> c(100000 + 10 , false) ;    vector<vector<int>> pos(100000 + 10) ;    for(int cas = 1 ; cas <= T ; cas ++)    {        cout << "Case #" << cas << ": " ;        int n ;        cin >> n ;        vector<int> a(n + 1) ;        vector<vector<int>> dp(n + 1) ;        for(int i = 1 ; i <= n ; i ++)  cin >> a[i] , pos[a[i]].push_back(i) ;        for(int i = 1 ; i <= n ; i ++)  dp[i].resize(n + 1 , 0) ;        for(int i = 1 ; i <= n ; i ++)        {            for(int j = i ; j <= n ; j ++)            {                if(c[a[j]])  break ;                c[a[j]] = true ;                dp[i][j] = j - i + 1 ;            }            for(int j = 1 ; j <= n ; j ++)  c[a[j]] = false ;        }        for(int len = 2 ; len <= n ; len ++)            for(int i = 1 ; i + len - 1 <= n ; i ++)            {                int j = i + len - 1 ;                dp[i][j] = max({dp[i][j] , dp[i + 1][j] , dp[i][j - 1]}) ;            }        int ans = 0 ;        set<pair<int , int>> s ;        multiset<int> t ;        for(int i = 1 ; i <= n ; i ++)        {            s.clear() ;            s.insert({i , n}) ;            t.clear() ;            t.insert(dp[i][n]) ;            for(int j = i ; j <= n ; j ++)            {                if(c[a[j]])  break ;                c[a[j]] = true ;                ans = max(ans , j - i + 1) ;                for(auto u : pos[a[j]])                {                    if(u < i)  continue ;                    auto it = s.lower_bound({u , n + 1}) ;                    it -- ;                    int l = (*it).first ;                    int r = (*it).second ;                    s.erase(it) ;                    auto it2 = t.lower_bound(dp[l][r]) ;                    t.erase(it2) ;                    if(l < u)  s.insert({l , u - 1}) , t.insert(dp[l][u - 1]) ;                    if(u < r)  s.insert({u + 1 , r}) , t.insert(dp[u + 1][r]) ;                }                int tmp = 0 ;                if(t.size() > 0)  tmp = (*t.rbegin()) ;                ans = max(ans , j - i + 1 + tmp) ;            }            for(int j = 1 ; j <= n ; j ++)  c[a[j]] = false ;        }        cout << ans << '\n' ;        for(int i = 1 ; i <= n ; i ++)  pos[a[i]].clear() ;    }    return 0 ;}

Problem D. Ice Cream Tower

二分答案 $x$ 。check时用前 $x$ 个数作为 $x$ 个序列的首元素。

#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 3e5 + 5;int kas;int n, k, cnt[N];ll a[N], ed[N];bool check(int x){    int j = x+1;    for(int i=1; i<=x; i++) ed[i] = a[i], cnt[i] = 1;    while(j<=n&&cnt[x]<k)    {        for(int i=1; i<=x; i++)        {            while(j<=n && a[j]<2*ed[i]) ++j;            if(j<=n) ++cnt[i], ed[i] = a[j], ++j;        }    }    return cnt[x]>=k;}void solve(){    scanf("%d%d", &n, &k);    for(int i=1; i<=n; i++) scanf("%lld", a+i);    sort(a+1, a+n+1);    int l = 1, r = n/k, ans = 0;    while(l<=r)    {        int mid = (l+r)>>1;        if(check(mid)) ans = mid, l = mid + 1;        else r = mid - 1;    }    printf("Case #%d: %d\n", ++kas, ans);}int main(){    int _; scanf("%d", &_);    while(_--) solve();    return 0;}

Problem E. Bet

对 $\frac{a_i}{b_i}$ 升序排列，挑选满足 $\sum \frac{a_i}{b_i} < 1$ 的最大个数的前缀即可。

卡精度，需要使用 $long \; double$ 。

#include <bits/stdc++.h>#define fi first#define se secondusing namespace std;using db = long double;using pdd = pair<db, db>;const int N = 105;int n, kas;pdd p[N];void solve(){    scanf("%d", &n);    for(int i=1; i<=n; i++) scanf("%Lf:%Lf", &p[i].fi, &p[i].se);    sort(p+1, p+n+1, [](pdd x, pdd y) { return x.fi*(y.fi+y.se) < y.fi*(x.fi+x.se); });    int ans = 0;    db cur = 0;    for(int i=1; i<=n; i++)    {        cur += 1.0*p[i].fi/(p[i].fi+p[i].se);        if(cur<1.0) ans = i;    }    printf("Case #%d: %d\n", ++kas, ans);}int main(){    int _; scanf("%d", &_);    while(_--) solve();    return 0;}/*131:1.11:0.21.5:1.7*/

Problem F. Mr. Panda and Fantastic Beasts

将 $n$ 个字符串用分隔符连接起来 $s = s_1 + \$ + s_2 + \# + s3 + \# + \cdots + \# + s_n$ 。

对 $s$ 做后缀排序。使用 $height$ 数组找到以 $s_1$ 中元素开头的后缀和非 $s_1$ 中元素开头的后缀的最大 $lcp$ ，记作 $ans$ 。

$min(ans)+1$ 即为答案子串的长度，后缀数组保证了字典序最小，对应位置输出子串即可。如果对应 $min(ans)+1$ 长度的子串不存在，即为无解。

#include<bits/stdc++.h>using namespace std ;const int maxn = 5e5 + 10 ;const int base = 131 ;typedef unsigned long long ull ;#include <ext/pb_ds/assoc_container.hpp>using namespace __gnu_pbds ;const ull mod1 = 68861641 ;const ull mod2 = 91815541 ;const int kk = 1e9 ;struct Sa //如果是多个测例，记得清空 s{    int rk[maxn << 1] , sa[maxn << 1] , height[maxn << 1] ;    int tmp[maxn << 1] , cnt[maxn] ;    char s[maxn] ;    void cal(int n , int m)    {       n ++ ;       for(int i = 0 ; i < n * 2 + 5 ; i ++)         rk[i] = sa[i] = height[i] = tmp[i] = 0 ;//开2 倍空间       for(int i = 0 ; i < m ; i ++)  cnt[i] = 0 ;       for(int i = 0 ; i < n ; i ++)  cnt[rk[i] = s[i]] ++ ;       for(int i = 1 ; i < m ; i ++)  cnt[i] += cnt[i - 1] ;       for(int i = 0 ; i < n ; i ++)  sa[-- cnt[rk[i]]] = i ;       for(int k = 1 ; k <= n ; k <<= 1)       {         int j = 0 ;         for(int i = 0 ; i < n ; i ++)         {           j = sa[i] - k ;           if(j < 0)  j += n ;           tmp[cnt[rk[j]] ++] = j ;         }         sa[tmp[cnt[0] = 0]] = j = 0 ;         for(int i = 1 ; i < n ; i ++)         {           if(rk[tmp[i]] != rk[tmp[i - 1]]           || rk[tmp[i] + k] != rk[tmp[i - 1] + k])             cnt[++ j] = i ;           sa[tmp[i]] = j ;         }         memcpy(rk , sa , n * sizeof(int)) ;         memcpy(sa , tmp , n * sizeof(int)) ;         if(j >= n - 1)  break ;       }       height[0] = 0 ;       for(int i = 0 , k = 0 , j = rk[0] ; i < n - 1 ; i ++ , k ++)         while(~k && s[i] != s[sa[j - 1] + k])           height[j] = k -- , j = rk[sa[j] + 1] ;    }    char t[maxn] ;    int len ;    int c ;    void init()    {        int n ;        cin >> n ;        cin >> s ;        len = strlen(s) ;        c = len ;        s[len ++] = '$' ;        for(int i = 2 ; i <= n ; i ++)        {            cin >> t ;            int len2 = strlen(t) ;            for(int j = 0 ; j < len2 ; j ++)  s[len ++] = t[j] ;            s[len ++] = '#' ;        }        cal(len , 200) ;    }    int mx[maxn] ;    int l[maxn] ;    int r[maxn] ;    bool vis[maxn] ;    int id , ans ;    void solve()    {        ans = 1e9 ;        for(int i = 0 ; i < len ; i ++)  mx[i] = l[i] = r[i] = 1e9 ;        int now = 1e9 ;        bool flag = false ;              for(int i = 2 ; i <= len ; i ++)        {            if(sa[i - 1] > c)  now = height[i] , flag = true ;            else  now = min(now , height[i]) ;            if(flag)  l[sa[i]] = now ;        }        now = 1e9 ;        flag = false ;        for(int i = len - 1 ; i >= 1 ; i --)        {            if(sa[i + 1] > c)  now = height[i + 1] , flag = true ;            else now = min(now , height[i + 1]) ;            if(flag)  r[sa[i]] = now ;        }        for(int i = 0 ; i < len ; i ++)  mx[i] = max(l[i] , r[i]) ;        // for(int i = 1 ; i <= len ; i ++)  cout << i << ' ' << height[i] << '\n' ;        // for(int i = 1 ; i <= len ; i ++)  cout << i << ' ' << l[sa[i]] << ' ' << r[sa[i]] << '\n' ;        for(int i = 1 ; i <= len ; i ++)              if(sa[i] < c && sa[i] + mx[sa[i]] < c && mx[sa[i]] + 1 < ans)                ans = mx[sa[i]] + 1 , id = sa[i] ;        for(int i = 0 ; i < len ; i ++)  mx[i] = l[i] = r[i] = 1e9 ;    }    void print()    {        if(ans > 1e8)  cout << "Impossible\n" ;        else        {            for(int i = id ; i <= id + ans - 1 ; i ++)  cout << s[i] ;            cout << '\n' ;        }    }} sa ;int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    for(int cas = 1 ; cas <= T ; cas ++)    {        cout << "Case #" << cas << ": " ;        sa.init() ;        sa.solve() ;        sa.print() ;        //for(int i = 0 ; i < len ; i ++)  sa.s[i] = 0 ;    }    return 0 ;}

Problem G. Pandaria

考虑 $kruskal$ 的过程，在添加边 $(u,v,w)$ 时，新建一个虚点 $t$ ，点权赋为 $w$ 。 $u,v$ 所在连通块的祖先的父亲都是 $t$ 。

在每次询问 $x,w$ 时， $x$ 向上倍增找到点权不超过 $w$ 的祖先 $y$ ，对 $y$ 的子树进行众数查询。

众数查询可以用线段树合并、树上启发式合并。

我写了 $200$ 行，是 $jyf$ 的两倍多。谁的码力强已经很显然了。

我写的树上启发式合并。

#include<bits/stdc++.h>using namespace std ;typedef long long ll ;const int maxn = 2e5 + 10 ;const int maxm = 1e6 + 10 ;int n , m , q , c[maxn] ;int d[maxn] ;int fa[maxn][25] ;struct Link{    int num , head[maxn] ;    struct Edge    {        int v , next ;    } edge[maxn << 1] ;    void init()    {        num = 0 ;        memset(head , -1 , sizeof(head)) ;    }    void add_edge(int u , int v)    {        edge[num].v = v ;        edge[num].next = head[u] ;        head[u] = num ++ ;      }     void dfs1(int f , int u)    {       for(int i = 1 ; i <= 20 ; i ++)       {         int nxt = fa[u][i - 1] ;         fa[u][i] = fa[nxt][i - 1] ;       }       for(int i = head[u] ; i != -1 ; i = edge[i].next)       {         int v = edge[i].v ;         if(v == f)  continue ;         fa[v][0] = u ;         dfs1(u , v) ;       }    }} link ;struct Dsu_on_tree{    int siz[maxn] , son[maxn] ;    int flag ;    int ans[maxn] , cnt[maxm] ;    int res , max1 ;    void init()     {        res = 1e9 ;        max1 = flag = 0 ;        memset(siz , 0 , sizeof(siz)) ;        memset(son , 0 , sizeof(son)) ;        memset(ans , 0 , sizeof(ans)) ;        memset(cnt , 0 , sizeof(cnt)) ;       }    void dfs1(int f , int u)    {        siz[u] = 1 ;         for(int i = link.head[u] ; i != -1 ; i = link.edge[i].next)        {            int v = link.edge[i].v ;            if(v == f) continue ;            dfs1(u , v) ;             siz[u] += siz[v] ;            if(siz[v] > siz[son[u]]) son[u] = v ;        }    }    void add(int f , int u , int x)    {        cnt[c[u]] += x ;        if(x > 0 && c[u] > 0 && cnt[c[u]] >= max1)        {            if(cnt[c[u]] > max1)  res = c[u] , max1 = cnt[c[u]] ;            else  res = min(res , c[u]) ;                 }        for(int i = link.head[u] ; i != -1 ; i = link.edge[i].next)        {            int v = link.edge[i].v ;            if(v == f || v == flag) continue ;            add(u , v , x) ;        }    }    void dfs2(int f , int u , int keep)    {        for(int i = link.head[u] ; i != -1 ; i = link.edge[i].next)        {            int v = link.edge[i].v ;            if(v == f || v == son[u]) continue ;            dfs2(u , v , 0) ;        }        if(son[u])  dfs2(u , son[u] , 1) , flag = son[u] ;        add(f , u , 1) ;        ans[u] = res ;        if(son[u]) flag = 0 ;        if(!keep)  add(f , u , -1) , res = 1e9 , max1 = 0 ;    }    int cal(int x , int w)    {        // for(int i = 1 ; i <= n ; i ++)        // {        //     for(int j = 0 ; j <= 2 ; j ++)        //         cout << i << ' ' << j << ' ' << fa[i][j] << '\n' ;        // }        for(int i = 20 ; i >= 0 ; i --)        {            if(fa[x][i] > 0 && d[fa[x][i]] <= w)                x = fa[x][i] ;        }        return ans[x] ;    }} dsu_on_tree ;struct Dsu{    int pre[maxn] ;    void init(int n)    {        for(int i = 1 ; i <= n ; i ++)  pre[i] = i ;    }    int find(int u)     {        if(pre[u] == u)  return u ;        return pre[u] = find(pre[u]) ;    }    void add(int u , int v , int w)    {        int fu = find(u) ;        int fv = find(v) ;        if(fu != fv)        {            n ++ ;            d[n] = w ;            pre[fu] = n ;            pre[fv] = n ;            link.add_edge(n , fv) , link.add_edge(fv , n) ;            link.add_edge(n , fu) , link.add_edge(fu , n) ;            fa[fv][0] = n ;            fa[fu][0] = n ;            //cout << n << ' ' << fv << ' ' << w << '\n' ;            //cout << n << ' ' << fu << ' ' << w << '\n' ;            //if(fu == 5 || fv == 5)  cout << "$$$ " << n << ' ' << fa[5][0] << '\n' ;        }    }} dsu ;void init(){    cin >> n >> m ;    memset(c , 0 , sizeof(c)) ;    memset(d , 0 , sizeof(d)) ;    memset(fa , 0 , sizeof(fa)) ;    for(int i = 1 ; i <= n ; i ++)  cin >> c[i] ;    vector<array<int , 3>> g ;    dsu.init(n * 2) ;    for(int i = 1 ; i <= m ; i ++)    {        int u , v , w ;        cin >> u >> v >> w ;        g.push_back({w , u , v}) ;    }    sort(g.begin() , g.end()) ;    link.init() ;    for(auto now : g)    {        int u = now[1] ;        int v = now[2] ;        int w = now[0] ;        dsu.add(u , v , w) ;    }}void solve(){    link.dfs1(n , n) ;    dsu_on_tree.init() ;    dsu_on_tree.dfs1(n , n) ;     dsu_on_tree.dfs2(n , n , 0) ;    int lst = 0 ;    int q ;    cin >> q ;    while(q --)    {        int x , w ;        cin >> x >> w ;        x ^= lst , w ^= lst ;        int res = dsu_on_tree.cal(x , w) ;        cout << res << '\n' ;        lst = res ;    }}int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    for(int cas = 1 ; cas <= T ; cas ++)    {        cout << "Case #" << cas << ":\n" ;        init() ;        solve() ;    }    return 0;}

$jyf$ 写的线段树合并。

#include <bits/stdc++.h>using namespace std;using pii = pair<int, int>;const int N = 1e5 + 5, LOG = 18;int kas;int n, m, q, c[N];vector<int> G[N<<1];struct edge{    int u, v, w;    bool operator < (const edge& oth) { return w < oth.w; }}e[N<<1];int fa[N<<1], val[N<<1], tot;int anc[N<<1][20];pii ans[N<<1];map<int, int> cnt[N<<1];int find(int x) { return x==fa[x] ? x : fa[x] = find(fa[x]); }void build(){    for(int i=1; i<=2*n; i++) fa[i] = i, G[i].clear();    sort(e+1, e+m+1);    tot = 0;    for(int i=1; tot<n-1; i++)    {        int u = find(e[i].u), v = find(e[i].v);        if(u!=v)        {            ++tot;            fa[u] = fa[v] = n+tot;            val[n+tot] = e[i].w;            G[n+tot].push_back(u), G[n+tot].push_back(v);        }    }}inline void upd(pii &x, pii y){    if(x.first<y.first) x = y;    else if(x.first==y.first&&x.second>y.second) x.second = y.second; }void merge(int u, int v){    if(cnt[u].size()<cnt[v].size()) swap(cnt[u], cnt[v]);    upd(ans[u], ans[v]);    for(auto it : cnt[v])    {        cnt[u][it.first] += it.second;        upd(ans[u], {cnt[u][it.first], it.first});    }}void dfs(int u){    for(int i=1; i<=LOG; i++) anc[u][i] = anc[anc[u][i-1]][i-1];    cnt[u].clear();    if(u<=n) cnt[u][c[u]]++, ans[u] = {1, c[u]};    else ans[u] = {0, 0};    for(int v : G[u])    {        anc[v][0] = u;        dfs(v);        merge(u, v);    }} void go(int &u, int w){    for(int i=LOG; ~i; i--)        if(anc[u][i] && val[anc[u][i]]<=w) u = anc[u][i];}void solve(){    scanf("%d%d", &n, &m);    for(int i=1; i<=n; i++) scanf("%d", c+i);    for(int i=1; i<=m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);    build();    dfs(n+tot);    scanf("%d", &q);    int lst = 0;    printf("Case #%d:\n", ++kas);    while(q--)    {        int u, w; scanf("%d%d", &u, &w);        u ^= lst, w ^= lst;        go(u, w);        printf("%d\n", lst=ans[u].second);    }}int main(){    int _; scanf("%d", &_);    while(_--) solve();    return 0;}

Problem H. Great Cells

如果直接推 $A_g$ 是什么容易把人推没了。

$\sum (g+1) \cdot A_g = \sum g \cdot A_g + \sum A_g$

容易发现 $\sum A_g = k^{n*m}$ 。

其次 $\sum g \cdot A_g$ 相当于把$g$个极大值独立开，分别计算贡献。

因此 $ans=k^{n*m}+n*m*\sum_{i=1}^{k} (i-1)^{n-1+m-1}$ 。

#include<bits/stdc++.h>using namespace std ;const int mod = 1e9 + 7 ;typedef long long ll ;ll qpow(ll a , ll b) //快速幂{    if(b < 0)  return 0 ;    ll ans = 1 ;     a %= mod ;    while(b)    {        if(b & 1)  ans = (ans * a) % mod ;        b >>= 1 , a = (a * a) % mod ;    }    return ans % mod ;}int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    int T ;    cin >> T ;    for(int cas = 1 ; cas <= T ; cas ++)    {        cout << "Case #" << cas << ": " ;        int n , m , k ;        cin >> n >> m >> k ;        ll ans = 0 ;        ans += qpow(k , n * m) ; //g = 0        for(int i = 1 ; i <= k ; i ++)  //g >= 1            ans += n * m * qpow(i - 1 , n - 1 + m - 1) % mod * qpow(k , n * m - n - m + 1) % mod , ans %= mod ;        cout << ans << '\n' ;    }    return 0 ;}

Problem I. Cherry Pick

留坑。

Problem J. Mr.Panda and TubeMaster

留坑。

Problem K. Justice Rains From Above

留坑。

Problem L. World Cup

温暖的签到题。

#include<bits/stdc++.h>using namespace std ;int ans[15][15][15][15] ;int f[15] ;void dfs(int now){    if(now > 6)    {        int a = 0 ;        int b = 0 ;        int c = 0 ;        int d = 0 ;        if(f[1] == 2) //a win b        {            a += 3 ;        }        else if(f[1] == 1) // a tie b        {            a ++ ;            b ++ ;        }        else //a lose b        {            b += 3 ;        }        if(f[2] == 2) //a win c        {            a += 3 ;        }        else if(f[2] == 1) // a tie c        {            a ++ ;            c ++ ;        }        else //a lose c        {            c += 3 ;        }        if(f[3] == 2) //a win d        {            a += 3 ;        }        else if(f[3] == 1) // a tie d        {            a ++ ;            d ++ ;        }        else //a lose d        {            d += 3 ;        }        if(f[4] == 2) //b win c        {            b += 3 ;        }        else if(f[4] == 1) // b tie c        {            b ++ ;            c ++ ;        }        else //b lose c        {            c += 3 ;        }        if(f[5] == 2) //b win d        {            b += 3 ;        }        else if(f[5] == 1) // b tie d        {            b ++ ;            d ++ ;        }        else //b lose d        {            d += 3 ;        }        if(f[6] == 2) //c win d        {            c += 3 ;        }        else if(f[6] == 1) // c tie d        {            c ++ ;            d ++ ;        }        else //c lose d        {            d += 3 ;        }        ans[a][b][c][d] ++ ;        return ;    }    for(int i = 0 ; i < 3 ; i ++)  f[now] = i , dfs(now + 1) ;}void init(){    dfs(1) ;}int main(){    std::ios::sync_with_stdio(false) , cin.tie(0) ;    init() ;    int T ;    cin >> T ;    for(int cas = 1 ; cas <= T ; cas ++)    {        cout << "Case #" << cas << ": " ;        int a , b , c , d ;        cin >> a >> b >> c >> d ;        if(max({a , b , c , d}) > 9)  cout << "Wrong Scoreboard\n" ;        else        {            if(ans[a][b][c][d] == 1)  cout << "Yes\n" ;            else if(ans[a][b][c][d] > 1) cout << "No\n" ;            else  cout << "Wrong Scoreboard\n" ;        }    }    return 0 ;}

上一篇：Codeforces Round #703 (Div. 2) 题解

下一篇：炼金术士（2020-2021）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！