「SRM786」题解

Author： RainAir
发布时间：May 16, 2020
1291views
2 comments
581 words
Categories：题解

昨天打完牛客挑战赛意识模糊忘记 register 了...一看题目发现血亏。

250pts

我们将下标按照 $\bmod k$ 分组发现每个组之间的交换互不影响。每次交换相当于至少要减少一对顺序对。我们肯定是想每次只减少一个顺序对（这样这一组的答案就是顺序对个数了）。发现我们每次交换相邻两个顺序对就满足条件。所以答案就是每组的顺序对个数加起来。

一开始 zz 了想错了但是感觉 10 min是能做完的？

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
const int MAXM = 233;

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXM];

    inline void add(int pos,int x){
        while(pos < MAXM){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
}bit;

class SwapTheString {
    int A[MAXN];
    int f[MAXN][26];
    std::string str;
    public:
    long long findNumberOfSwaps(std::string P, int A0, int X, int Y, int N, int K) {
        A[0] = A0;
        FOR(i,1,N-1) A[i] = (1ll*A[i-1]*X+Y)%1812447359;
        str = P;str.resize(N);
        FOR(i,P.length(),N-1) str[i] = (char)(A[i]%26+'a');
        if(K >= N) return 0;
        LL ans = 0;
        FOR(i,0,K-1){
            CLR(bit.tree,0);
            for(int t=0,j = i;j < N;j += K,++t){
                ans += bit.query(str[j]-1);
                bit.add(str[j],1);
            }
        }
        return ans;
    }
};

500pts

题目

这种题目数字种类数不多可以用期望线性性拆成计算每个数字对答案的贡献的期望

设 $f[i][j]$ 表示经过了 $i$ 轮数组 $j$ 的期望出现次数。第二维是在 $\bmod 512$ 意义下定义的。

显然有转移 $f[i][j] = \frac{n-1}{n}f[i-1][j]+\frac{1}{n}f[i-1][j-1]$

就是有 $\frac{f[i][j-1]}{n}$ 的概率让出现次数 $+1$，有$\frac{f[i-1][j]}{n}$ 的概率让出现次数 $-1$。直接做的时间复杂度是 $O(512*K)$ 看起来就不太行。

于是我们考虑使用矩阵快速幂可以做到 $O(512^3 \log K)$ 然而还是过不去。

继续观察：发现转移矩阵是一个循环矩阵矩阵乘法改成暴力循环卷积/FFT优化到 $O(512^2\log K)/ O(512\log512\log K)$。

如果这个题是输出小数的话或许可以代入单位根插值（个人感觉精度会丢的很厉害）

这个题被搞了原因是我不知道 class 里的变量初始化在 Linux 下是随机值（也不知道 Mac 到底是随 Win 还是随 Linux）。否则估计花 20min 就可以。（归根结底还是自己菜）

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
//#define P stdd::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
// f[i][j] i 时刻 期望多少个=j 的数字
// f[i][j] = f[i-1][j] + f[i-1][j-1]/n - f[i-1][j]/n
const int ha = 1000000007;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}
int A[2000005];
int a[512],b[512],res[512],t[512];
class ModCounters {
    std::vector<int> S;
    inline void mul(int c[],int a[],int b[]){
        FOR(i,0,511){
            FOR(j,0,511){
                (c[(i+j)%512] += 1ll*a[i]*b[j]%ha)%=ha;
            }
        }
    }

    public:
    int findExpectedSum(std::vector<int> P, int A0, int X, int Y, int N, int K) {
        A[0] = A0;FOR(i,1,N-1) A[i] = (1ll*A[i-1]*X%1812447359+Y)%1812447359;
        S = P;S.resize(N);FOR(i,P.size(),N-1) S[i] = A[i]%512;
        FOR(i,0,N-1) b[S[i]]++;
        a[0] = 1ll*(N-1)*qpow(N)%ha;a[511] = qpow(N);res[0] = 1;
        while(K){
            if(K & 1){
                mul(t,res,a);
                FOR(i,0,511) res[i] = t[i],t[i] = 0;
            }
            mul(t,a,a);FOR(i,0,511) a[i] = t[i],t[i] = 0;
            K >>= 1;
        }
        LL ans = 0;
        FOR(i,0,511){
            LL t = 0;
            FOR(k,0,511){
                (t += 1ll*res[(k-i+512)%512]*b[k]%ha)%=ha;
            }
            (ans += 1ll*t*i%ha)%=ha;
        }
        return ans;
    }
};

1000pts

题目

首先可以用两个 $\text{multiset}$ 支持插入删除询问绝对值最小值。一个维护值一个维护值域上相邻的两个数的差即可。

暴力是对于每个点插入它的孙子，爷爷和兄弟。一个菊花图就没了。

我们针对菊花图考虑去枚举父亲 $p$ 每次先把所有儿子和自己的父亲插入。然后对于每一个儿子 $v$ 先把 $v$ 删除再插入 $v$ 的所有孙子然后撤销这两步操作。

发现每个点只会被作为父亲孙子被插入（也就是只被插入两次）总复杂度 $O(n\log n)$

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;

class TwoDistance {
    struct Data_Structure{
        std::multiset<int> S1,S2;
        inline void clear(){
            S1.clear();S2.clear();
        }
    
        inline void insert(int x){
            auto p = S1.insert(x);
            auto pre = p,suf = p;--pre;++suf;
            if(p != S1.begin()) S2.insert(x-*pre);
            if(suf != S1.end()) S2.insert(*suf-x);
            if(p != S1.begin() && suf != S1.end()) S2.erase(S2.find(*suf-*pre));
        }

        inline void del(int x){
            auto p = S1.find(x);
            auto pre = p,suf = p;--pre;++suf;
            if(p != S1.begin()) S2.erase(S2.find(x-*pre));
            if(suf != S1.end()) S2.erase(S2.find(*suf-x));
            if(p != S1.begin() && suf != S1.end()) S2.insert(*suf-*pre);
            S1.erase(p);
        }
    
        inline int query(){
            if(S2.empty()) return 0;
            return *S2.begin();
        }
    }DS;

    struct Edge{
        int to,nxt;
    }e[MAXN<<1];
    int head[MAXN],cnt;

    inline void add(int u,int v){
        e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
        e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
    }

    int A[MAXN<<1];LL ans;
    std::vector<int> V,E;
    int f[MAXN];
    std::vector<int> son[MAXN],sson[MAXN];

    inline void pdfs(int v,int fa=0){
        f[v] = fa;
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].to == fa) continue;
            pdfs(e[i].to,v);
        }
    }

    inline void dfs(int v,int fa=0){
        DS.clear();
        if(fa) DS.insert(V[fa-1]);
        for(auto x:son[v]) DS.insert(V[x-1]);
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].to == fa) continue;
            DS.del(V[e[i].to-1]);
            for(auto x:sson[e[i].to]) DS.insert(V[x-1]);
            ans += DS.query();
            DS.insert(V[e[i].to-1]);
            for(auto x:sson[e[i].to]) DS.del(V[x-1]);
        }
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].to == fa) continue;
            dfs(e[i].to,v);
        }
    }

    public:
    long long findMinValue(int N, std::vector<int> edge, std::vector<int> val, int D, int seed) {
        cnt = 0;FOR(i,1,N) head[i] = 0;cnt = 0;
        A[0] = seed;FOR(i,1,2*N-1)  A[i] = (LL)(A[i-1] * 1103515245ll + 12345) % 2147483648;
        V = val;V.resize(N);FOR(i,val.size(),N-1) V[i] = A[i];
        E = edge;E.resize(N);FOR(i,edge.size(),N-1) E[i] = A[N+i]%std::min(i,D);
        FOR(i,1,N-1) add(i+1,E[i]+1);ans = 0;
        pdfs(1);
        FOR(i,1,N){
            if(f[i]) son[f[i]].pb(i);
            if(f[f[i]]) sson[f[f[i]]].pb(i);
        }
        dfs(1);DS.clear();
        for(auto x:sson[1]) DS.insert(V[x-1]);
        ans += DS.query();
        return ans;
    }
};

Last modification：May 16th, 2020 at 11:36 am

如果觉得我的文章对你有用，请随意赞赏

2 comments

yzclink
June 12th, 2020 at 07:49 am

t1其实可以不用带logqwq

Reply
1. RainAir
  June 13th, 2020 at 06:44 pm
  
  @yzclink
  
  怎么做啊 QAQ
  
  Reply

「SRM786」题解

RainAir • 2020 年 05 月 16 日

昨天打完牛客挑战赛意识模糊忘记 register 了...一看题目发现血亏。

250pts

题目

一开始 zz 了想错了但是感觉 10 min是能做完的？

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;
const int MAXM = 233;

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXM];

    inline void add(int pos,int x){
        while(pos < MAXM){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }

    inline int query(int pos){
        int res = 0;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
}bit;

class SwapTheString {
    int A[MAXN];
    int f[MAXN][26];
    std::string str;
    public:
    long long findNumberOfSwaps(std::string P, int A0, int X, int Y, int N, int K) {
        A[0] = A0;
        FOR(i,1,N-1) A[i] = (1ll*A[i-1]*X+Y)%1812447359;
        str = P;str.resize(N);
        FOR(i,P.length(),N-1) str[i] = (char)(A[i]%26+'a');
        if(K >= N) return 0;
        LL ans = 0;
        FOR(i,0,K-1){
            CLR(bit.tree,0);
            for(int t=0,j = i;j < N;j += K,++t){
                ans += bit.query(str[j]-1);
                bit.add(str[j],1);
            }
        }
        return ans;
    }
};

500pts

题目

这种题目数字种类数不多可以用期望线性性拆成计算每个数字对答案的贡献的期望

设 $f[i][j]$ 表示经过了 $i$ 轮数组 $j$ 的期望出现次数。第二维是在 $\bmod 512$ 意义下定义的。

显然有转移 $f[i][j] = \frac{n-1}{n}f[i-1][j]+\frac{1}{n}f[i-1][j-1]$

就是有 $\frac{f[i][j-1]}{n}$ 的概率让出现次数 $+1$，有$\frac{f[i-1][j]}{n}$ 的概率让出现次数 $-1$。直接做的时间复杂度是 $O(512*K)$ 看起来就不太行。

于是我们考虑使用矩阵快速幂可以做到 $O(512^3 \log K)$ 然而还是过不去。

继续观察：发现转移矩阵是一个循环矩阵矩阵乘法改成暴力循环卷积/FFT优化到 $O(512^2\log K)/ O(512\log512\log K)$。

如果这个题是输出小数的话或许可以代入单位根插值（个人感觉精度会丢的很厉害）

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
//#define P stdd::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
// f[i][j] i 时刻 期望多少个=j 的数字
// f[i][j] = f[i-1][j] + f[i-1][j-1]/n - f[i-1][j]/n
const int ha = 1000000007;

inline int qpow(int a,int n=ha-2){
    int res = 1;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}
int A[2000005];
int a[512],b[512],res[512],t[512];
class ModCounters {
    std::vector<int> S;
    inline void mul(int c[],int a[],int b[]){
        FOR(i,0,511){
            FOR(j,0,511){
                (c[(i+j)%512] += 1ll*a[i]*b[j]%ha)%=ha;
            }
        }
    }

    public:
    int findExpectedSum(std::vector<int> P, int A0, int X, int Y, int N, int K) {
        A[0] = A0;FOR(i,1,N-1) A[i] = (1ll*A[i-1]*X%1812447359+Y)%1812447359;
        S = P;S.resize(N);FOR(i,P.size(),N-1) S[i] = A[i]%512;
        FOR(i,0,N-1) b[S[i]]++;
        a[0] = 1ll*(N-1)*qpow(N)%ha;a[511] = qpow(N);res[0] = 1;
        while(K){
            if(K & 1){
                mul(t,res,a);
                FOR(i,0,511) res[i] = t[i],t[i] = 0;
            }
            mul(t,a,a);FOR(i,0,511) a[i] = t[i],t[i] = 0;
            K >>= 1;
        }
        LL ans = 0;
        FOR(i,0,511){
            LL t = 0;
            FOR(k,0,511){
                (t += 1ll*res[(k-i+512)%512]*b[k]%ha)%=ha;
            }
            (ans += 1ll*t*i%ha)%=ha;
        }
        return ans;
    }
};

1000pts

题目

首先可以用两个 $\text{multiset}$ 支持插入删除询问绝对值最小值。一个维护值一个维护值域上相邻的两个数的差即可。

暴力是对于每个点插入它的孙子，爷爷和兄弟。一个菊花图就没了。

发现每个点只会被作为父亲孙子被插入（也就是只被插入两次）总复杂度 $O(n\log n)$

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2e5 + 5;

class TwoDistance {
    struct Data_Structure{
        std::multiset<int> S1,S2;
        inline void clear(){
            S1.clear();S2.clear();
        }
    
        inline void insert(int x){
            auto p = S1.insert(x);
            auto pre = p,suf = p;--pre;++suf;
            if(p != S1.begin()) S2.insert(x-*pre);
            if(suf != S1.end()) S2.insert(*suf-x);
            if(p != S1.begin() && suf != S1.end()) S2.erase(S2.find(*suf-*pre));
        }

        inline void del(int x){
            auto p = S1.find(x);
            auto pre = p,suf = p;--pre;++suf;
            if(p != S1.begin()) S2.erase(S2.find(x-*pre));
            if(suf != S1.end()) S2.erase(S2.find(*suf-x));
            if(p != S1.begin() && suf != S1.end()) S2.insert(*suf-*pre);
            S1.erase(p);
        }
    
        inline int query(){
            if(S2.empty()) return 0;
            return *S2.begin();
        }
    }DS;

    struct Edge{
        int to,nxt;
    }e[MAXN<<1];
    int head[MAXN],cnt;

    inline void add(int u,int v){
        e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
        e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
    }

    int A[MAXN<<1];LL ans;
    std::vector<int> V,E;
    int f[MAXN];
    std::vector<int> son[MAXN],sson[MAXN];

    inline void pdfs(int v,int fa=0){
        f[v] = fa;
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].to == fa) continue;
            pdfs(e[i].to,v);
        }
    }

    inline void dfs(int v,int fa=0){
        DS.clear();
        if(fa) DS.insert(V[fa-1]);
        for(auto x:son[v]) DS.insert(V[x-1]);
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].to == fa) continue;
            DS.del(V[e[i].to-1]);
            for(auto x:sson[e[i].to]) DS.insert(V[x-1]);
            ans += DS.query();
            DS.insert(V[e[i].to-1]);
            for(auto x:sson[e[i].to]) DS.del(V[x-1]);
        }
        for(int i = head[v];i;i = e[i].nxt){
            if(e[i].to == fa) continue;
            dfs(e[i].to,v);
        }
    }

    public:
    long long findMinValue(int N, std::vector<int> edge, std::vector<int> val, int D, int seed) {
        cnt = 0;FOR(i,1,N) head[i] = 0;cnt = 0;
        A[0] = seed;FOR(i,1,2*N-1)  A[i] = (LL)(A[i-1] * 1103515245ll + 12345) % 2147483648;
        V = val;V.resize(N);FOR(i,val.size(),N-1) V[i] = A[i];
        E = edge;E.resize(N);FOR(i,edge.size(),N-1) E[i] = A[N+i]%std::min(i,D);
        FOR(i,1,N-1) add(i+1,E[i]+1);ans = 0;
        pdfs(1);
        FOR(i,1,N){
            if(f[i]) son[f[i]].pb(i);
            if(f[f[i]]) sson[f[f[i]]].pb(i);
        }
        dfs(1);DS.clear();
        for(auto x:sson[1]) DS.insert(V[x-1]);
        ans += DS.query();
        return ans;
    }
};

「SRM786」题解

250pts

500pts

1000pts

2 comments

Leave a Comment Cancel reply

NOI2021 退役记

SDOI2020 退役记

I'm back

点双连通分量 & 圆方树学习笔记

CSP2019 游记

单次询问的最长瓶颈路

「NOIP2016」换教室

平衡树学习笔记

CF1381 题解

CF 1202 题解

「SRM786」题解

250pts

500pts

1000pts