CF1878(div3)题解

B. Aleksa and Stack(奇偶性构造数组)

题意：
创建一个单调递增序列，使得 $ (3 \cdot a_{i+2}) mod(a_{i+1}+a_i) !=0 $ 思路：
直接全部奇数，3*奇数=奇数，奇数+奇数=偶数

C. Vasilije in Cacak

题意：
给定n,k,x,从1-n选择k个数能组成x
思路：
选择k个数的最小值为前k个数的和，最大值为倒数k个数的和，x满足[最小值,最大值]输出YES，否则NO

D. Reverse Madness

思路：
两个区间不互相影响，在同一个区间内标记经过多少次反转，最后再判断即可

E. Iva & Pav(按位计算)

题意：
定义 $ f(l,r)=a_{l} $ & $ a_{l+1} $ &…& $ a_r $ 给出q次询问，一个k，回答最长的r使得 $f(l,r)>=k $
思路：
考虑预处理每一位，l对应的最长连续1到达的r,每次询问将每一位的r拿出来，从大到小排序，然后累加直至大于等于k则输出r，否则输出-1

void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<vector<int>> pos(31,vector<int>(n+1,-1));
    for(int k=0;k<=30;k++){
        for(int i=n,j=n;i>=1;i--){
            if((a[i]>>k)&1){
                j=i;
                pos[k][j]=i;
                while(j-1>=1&&((a[j-1]>>k)&1)){
                    j--;
                    pos[k][j]=i;
                }
                i=j;
           }
        }
    }
    int q;
    cin>>q;
    while(q--){
        int l,k;
        cin>>l>>k;
        ll tmp=0;
        ll ans=INF;
        vector<pair<int,int>> B; 
        for(int i=0;i<=30;i++){
            if(pos[i][l]!=-1){
                B.pb({pos[i][l],i});
            }
        }
        sort(all(B));
        bool g=0;
        for(int i=B.size()-1;i>=0;i--){
            tmp+=(1ll<<B[i].second);
            if(tmp>=k){
                cout<<B[i].first<<" ";
                g=1;
                break;
            }
        }
        if(g)continue;
        cout<<"-1 ";
    }
    cout<<"\n";
}

F. Vasilije Loves Number Theory(数论)

题意：
给定一个整数n，每次进行下列操作，定义d(n)为n的约数

• 1 x，n*=x,然后找出一个a,满足 $ d(n \cdot a)=n,gcd(a,n)=1 $
• 2，重置n

思路：
定理： $n=a_1^{b_1} \cdot a_2^{b_2} \cdot a_3^{b_3}..$,约数个数= $ (b_1+1) \cdot (b_2+1) \cdot (b_3+1)…$
如果n能整除此时n的约数个数，则a可以是若干个质因数组成，使得d(na)=n,问题转换完成
注意：nx是个大数，每次计算要用比较质因数的次数来判断是否能被整除

void solve(){
    ll nn,q;
    cin>>nn>>q;
    map<ll,ll> cnt[1010];
    ll tmp=nn;
    vector<pll> pos;
    for(int i=2;i<=sqrt(tmp);i++){
        if(tmp%i==0){
            int a=i,b=0;
            while(tmp%i==0)tmp/=i,b++;
            pos.pb({a,b});
        }
    }
    if(tmp>1){
        pos.pb({tmp,1});
    }
    for(auto it:pos){
        for(int i=0;i<=q;i++){
            cnt[i][it.first]=it.second;
        }
    }
    ll v=0;
    __int128 N=nn;
    __int128 n=nn;
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            ll x;
            cin>>x;
            n*=x;
            for(int i=2;i<=sqrt(x);i++){
                if(x%i==0){
                    int a=i,b=0;
                    while(x%i==0)x/=i,b++;
                    cnt[v][a]+=b;
                }
            }
            if(x>1)cnt[v][x]++;
            ll A=1;
            map<int,int> P;
            for(auto it:cnt[v]){
                int H=it.second+1;
                for(int i=2;i<=sqrt(H);i++){
                    if(H%i==0){
                        int a=i,b=0;
                        while(H%i==0)H/=i,b++;
                        P[a]+=b;
                    }
                }
                if(H>1)P[H]++;
            }
            bool g=0;
            for(auto it:P){
                if(cnt[v][it.first]<P[it.first]){
                    g=1;
                    break;
                }
            }
            if(!g)cout<<"YES\n";
            else cout<<"NO\n";
        }
        else{
            v++;
            n=N;
        }
    }
    cout<<"\n";
}

G. wxhtzdy ORO Tree(LCA)

一棵树每次询问两个节点x,y,在两个点的最短路径中找出一个z，使g(x,z)+g(y,z)最大，g(u,v)表示a[u]一直或到a[v]，然后计算二进制1的数量
思路：
对于x的每一位考虑，找出离x最近的一个数且该位数为1，最多找 $ log2(max(a_i)) $ 位，位数为0的可以忽略因为对x和y都不会有贡献，全部找出来x和y的(还要判断最近的点是否在lca和自身之间)，然后再对每个数都跑一遍(用倍增跑)统计
复杂度： $ O(q \cdot (logn+log(max(a))) \cdot logn) $

const int M=200010;
int fa[M][30],sum[M][30],depth[M],a[M],bst[M][30];
vector<int> adj[M];
void dfs(int u,int p,vector<int> b){
    fa[u][0]=p;
    sum[u][0]=a[p];
    depth[u]=depth[p]+1;
    for(int i=0;i<30;i++){
        bst[u][i]=b[i];
        if(a[u]&(1ll<<i))b[i]=u;
    }
    for(int i=1;i<=log2(depth[u]);i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        sum[u][i]=sum[u][i-1]|sum[fa[u][i-1]][i-1];
    }
    for(auto v:adj[u]){
        if(v!=p){
            dfs(v,u,b);
        }
    }
}
int lca(int x,int y){
    if(depth[x]<depth[y])swap(x,y);
    while(depth[x]>depth[y]){
        x=fa[x][(int)log2(depth[x]-depth[y])];
    }
    if(x==y)return x;
    for(int k=log2(depth[x]);k>=0;k--){
        if(fa[x][k]!=fa[y][k])x=fa[x][k],y=fa[y][k];
    }
    return fa[x][0];
}
int getOR(int u,int dis){
    int res=a[u];
    for(int i=0;i<30;i++){
        if(dis&(1<<i)){
            res|=sum[u][i];
            u=fa[u][i];
        }
    }
    return res;
}
int query(int u,int v){
    int l=lca(u,v);
    return getOR(u,depth[u]-depth[l])|getOR(v,depth[v]-depth[l]);
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        adj[i].clear();
        depth[i]=0;
        for(int k=0;k<30;k++){
            fa[i][k]=sum[i][k]=bst[i][k]=0;
        }
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> temp(30,-1);
    dfs(1,0,temp);
    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        int LCA=lca(x,y);
        vector<int> t;
        t.push_back(x);
        t.push_back(y);
        for(int i=0;i<30;i++){
            if(bst[x][i]!=-1&&lca(LCA,bst[x][i])==LCA)t.push_back(bst[x][i]);
            if(bst[y][i]!=-1&&lca(LCA,bst[y][i])==LCA)t.push_back(bst[y][i]);
        }
        int ans=__builtin_popcount(a[x])+__builtin_popcount(a[y]);
        for(auto p:t){
            int x1=a[x]|query(x,p),x2=a[y]|query(y,p);
            ans=max(ans,__builtin_popcount(x1)+__builtin_popcount(x2));
        }
        cout<<ans<<" ";
    }
    cout<<"\n";
}