2020牛客暑期多校训练营（第四场）题解

部分题题解，剩余部分待补
A：Ancient Distance
这道题写了个根号的复杂度的，没有被卡
我们只需要做到O(1)判断就好了！
然后我们可以写一个有关于单调性的解法，然后我们可以类似于整除分块可能更好理解！
nlogn的代码和思路以后会补，先放上根号的代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e5+5;
struct Edge{int to,nxt;}e[N];
int fst[N],tote,n,dep[N],a[N],ma,fa[N],ans[N],id[N],dfc;
void adde(int u,int v){e[++tote]=(Edge){v,fst[u]};fst[u]=tote;}
void dfs(int u){
    id[++dfc]=u;ma=max(ma,dep[u]);
    for(int i=fst[u],v;i;i=e[i].nxt)v=e[i].to,dep[v]=dep[u]+1,dfs(v);
}
void solve(int L,int R,int l,int r){
    if(L>R||l>r)return;
    if(l==r){for(int i=L;i<=R;i++)ans[i]=l;return;}
    int mid=(L+R)>>1;ans[mid]=0;
    for(int i=1;i<=n;i++)a[i]=dep[i];
    for(int i=n,x;i>=1;i--){
        x=id[i];
        if(x==1||a[x]==dep[x]+mid)a[x]=-1,ans[mid]++;
        a[fa[x]]=max(a[fa[x]],a[x]);
    }
    solve(L,mid-1,ans[mid],r);solve(mid+1,R,l,ans[mid]);
}
int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=1;i<=n;i++)fst[i]=0;tote=ma=dfc=0;
        for(int i=2;i<=n;i++)scanf("%d",&fa[i]),adde(fa[i],i);
        dfs(1);solve(0,ma,1,n);
        LL res=0;
        for(int i=1;i<=ma;i++)res+=(LL)i*(ans[i-1]-ans[i]);
        printf("%lld\n",res);
    }
    return 0;
}

B: Basic Gcd Problem
这题算是这场的签到题了吧，我们只需要转化下，然后发现可以通过算一个数因数的次幂和，然后我们要O(logn)完成这个操作，线性筛一波就好了！
C: Count New String
这题我们要注意首先一个转化，就是把最外围的那个函数拆掉，然后直接统计不同子串个数扫一遍就好了
这是一个重要的思路，然后我们考虑这个字符集是10是一个隐士条件
这意识着我们不同的子串会很多，但是大部分都是一段很长的区间都是一个字母这样的条件很多
然后我们可以的得出一个基于字符集的hash做法，分别考虑每一个字母出现了多少次
但是这个hash用了unordered_map以后还是会tle
于是换成了广义sam，注意这里的广义sam我们不是每次把节点重***们采用记录一下上次的节点，由于已经插入过了，我们直接把这个节点接着记录的节点插一下就好了，可能写法还需要维护一个trie，然后我们bfs来完成这个过程！
这题感觉可能首先还是和普通的广义sam有一定的区别，是一种新的方式，我们可以拓宽一下
然后就是字符集小的情况我们可以想想奇怪的处理方法来通过字符集降低复杂度！

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=2e5+5;
char str[N];int n,st[N],tp,now,nd[N];LL ans;
struct SAM{
    int ch[N*10][10],slink[N*10],len[N*10],tot,lst,Root;
    int newnode(int l){len[tot]=l;return tot++;}
    void init(){lst=Root=newnode(0);}
    int extend(int p,int c){
        //printf("extend:%d %d\n",p,c);
        int np=newnode(len[p]+1);
        while(!ch[p][c])ch[p][c]=np,p=slink[p];
        if(p==Root&&ch[p][c]==np)slink[np]=Root;
        else{
            int q=ch[p][c];
            if(len[q]==len[p]+1)slink[np]=q;
            else{
                int nq=newnode(len[p]+1);
                slink[nq]=slink[q];slink[q]=slink[np]=nq;
                memcpy(ch[nq],ch[q],sizeof(ch[nq]));
                while(ch[p][c]==q)ch[p][c]=nq,p=slink[p];
            }
        }
        return np;
    }
}sam;
struct Trie{
    int ch[N*10][10],tot,sd[N*10];
    int insert(int u,int c){return (!ch[u][c]?ch[u][c]=++tot:ch[u][c]);}
    void build(){
        queue<int>que;while(!que.empty())que.pop();
        sam.init();que.push(0);
        while(!que.empty()){
            int u=que.front();que.pop();
            for(int i=0;i<10;i++)if(ch[u][i])
                que.push(ch[u][i]),sd[ch[u][i]]=sam.extend(sd[u],i);
        }
    }
}trie;
int main(){
    scanf("%s",str+1);n=strlen(str+1);
    for(int i=n;i>=1;i--){
        if(!tp||str[i]<=str[st[tp]]){now=trie.insert(now,str[i]-'a');st[++tp]=i;nd[tp]=now;continue;}
        while(tp&&str[i]>str[st[tp]])tp--;
        for(int j=tp+1;j<=n-i+1;j++){
            str[n-j+1]=str[i];now=trie.insert(nd[tp],str[n-j+1]-'a');
            st[++tp]=n-j+1;nd[tp]=now;
        }
    }
    trie.build();
    for(int i=1;i<sam.tot;i++)ans+=(LL)sam.len[i]-sam.len[sam.slink[i]];
    printf("%lld\n",ans);
    return 0;
}

D: Dividing Strings
这题感觉就是思路就是枚举长度，然后log判断，结果细节一大堆...
我们可以预处理出哈希的值，然后我们哈希判断可能更方便！
代码还没写完，待补见谅！
F: Finding the Order
类似于四边形不等式判断就好了，其实也就多画画图就可以猜个结论！
也可以设一个值然后来大力特判...大家可以自行选择方法！
注意画图的重要性！
H: Harder Gcd Problem
这题考试的时候用了一个奇怪的结论过题额，还是一个有关于sort的排序，然后关键字大小比较尤为繁琐！
用一个堆来判断然后不断细节特判两两匹配...
然后我们这题的妙处有一个结论是是去掉大于n/2的质数和1，然后剩下都可以两两匹配
然后我们从大到小枚举这个质数，然后发现这个质数的倍数尚未匹配的个数是多少？
我们分两类讨论：
如果是奇数：我们把2*i单独提出来，其他两两匹配就好了！
否则直接两两匹配就好了，因为我们注意到2是一个奇怪的数，可以当做gcd这方便了我们的构造，这样就可以很方便的构造出一组解了，需要注意的是我们可以用vector和一个pair<int,int>这样可能能好实现一些！
这题启发大概是我们首先需要搞出一个结论，就是要给出答案，我们要先求出这个组数通常能让我们更好地得出方案！然后就是我们配对的最后策略通常是倒序，然后这样有一个问题就是我们要把难以匹配的先搞，然后在匹配其他的，还有一个这里有关于这个2的思路甚为精妙
代码：

#include<bits/stdc++.h>
#define LL long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
int pri[N],len;bool np[N],usd[N];
void init(){
    for(int i=2;i<N;i++){
        if(!np[i])pri[++len]=i;
        for(int j=1;j<=len&&i*pri[j]<N;j++){
            np[i*pri[j]]=true;
            if(i%pri[j]==0)break;
        }
    }
}
int main(){
    init();int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);usd[1]=true;
        for(int i=2;i<=n;i++)if(i<=n/2||np[i])usd[i]=false;else usd[i]=true;
        vector<pii>ans;ans.clear();
        for(int i=(n>>1),res,lst;i>=2;i--)if(!np[i]){
            res=lst=0;for(int j=i;j<=n;j+=i)if(!usd[j])res++;
            if(res&1){
                if(!usd[i])usd[i]=true,lst=i;
                for(int j=3*i;j<=n;j+=i)if(!usd[j]){
                    usd[j]=true;
                    if(lst)ans.pb(pii(lst,j)),lst=0;else lst=j;
                }
            }else{
                for(int j=i;j<=n;j+=i)if(!usd[j]){
                    usd[j]=true;
                    if(lst)ans.pb(pii(lst,j)),lst=0;else lst=j;
                }
            }
        }
        printf("%d\n",(int)ans.size());
        for(auto x:ans)printf("%d %d\n",x.first,x.second);
    }
    return 0;
}

I: Investigating Legions
这题大概给出了一个随机方式，然后我们可以直接根据这个本机调参就可以了！
这题的思路很多，我们可以随机调整，也可以网络流匹配（这个作者不太懂）
这里最简单的是这个概率做法，我们可以利用三元环的思路构造就可以了，然后本机调参到最优就好了！
这题首先是我们有一个概率算法，而且这个给出的随机方式可以有利于我们本机调参！
代码：

2020牛客暑期多校训练营（第四场）题解

全站热榜