CF1879

写在前面： 的

A

签到题，注意读题，特判后直接输出答案

B

符合条件的摆法，一定满足每行都有或者每列都有

所以按行取一次最小值再按列取一次最小值，输出两次的最小值

C

小小计数题

预处理出 以及

如果有连续的一串 或 ，在 个里面取 个，最后再乘上操作数的阶乘

D

求全部区间的区间长度 元素异或和

先考虑 时的做法

求出来异或前缀和，对于一个选定的区间右端点，如果该点异或前缀和为 ，那么左端点的异或前缀和只能是 ，该区间才对答案有贡献，另外一种情况也一样，于是我们扫一遍序列，分别记录 和 的个数以及到右端点的距离之和，有点小技巧，每次扫到 时就加上 对应的距离和，每次扫到 时就加上 对应的距离和，细节处理一下就好

然后 就按位拆开分别处理即可

E

交互题，想假了

一开始的做法：

对于一个点，其连儿子的边都是一种颜色，连父亲的边是另一种颜色，当一个点有大于 个儿子时，可以通过数量判断父亲，一棵树都是这样的节点的话，就只需要两种颜色，当一个点只有一个儿子时，就是需要引入另一种颜色，所以我们只需要统计儿子个数之为 的点形成的链的最大长度即可，最小颜色就是

实际上，想复杂了

颜色最多 种

对于多个儿子的节点直接找 ，对于一个儿子的点，相邻边存在的颜色也最多只有 种，颜色对 取模后就完全可以确定边的优先级

还有一个点就是 连儿子的边的颜色可以不相同

贴个代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdlib>
#include<ctime>
#include<bitset>
#include<vector>
#include<climits>
#include<iomanip>
using namespace std;
#define N 100010
template<typename T>
inline void read(T &x){
    x=0;bool flg=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') flg=1;
    for(;isdigit(c);c=getchar()) x=x*10+(c^48);
    if(flg) x=-x;
}

int n,p[N];
vector<int> e[110];
int cl[N],mx[110],dmx=0;

void dfs1(int x,int c){
    cl[x]=c;dmx=max(dmx,c);
    for(auto i:e[x]){
        if(e[x].size()==1) dfs1(i,c%3+1);
        else{
            if(c!=1) dfs1(i,1);
            else dfs1(i,2);
        }
    }
}

int main(){

    read(n);
    for(int i=2;i<=n;i++) read(p[i]),e[p[i]].push_back(i);

    for(int i=0;i<e[1].size();i++){
        dmx=1;
        dfs1(e[1][i],1);
        if(dmx==1){mx[i]=1;continue;}
        else if(dmx==2){mx[i]=2;continue;}
        else{
            dmx=2;
            dfs1(e[1][i],2);
            if(dmx==2) mx[i]=2;
            else mx[i]=3;
        }
    }

    for(int i=0;i<e[1].size();i++) dmx=max(dmx,mx[i]);

    cout<<dmx<<endl;
    for(int i=2;i<=n;i++) cout<<cl[i]<<" ";
    cout<<endl;

    int op;
    read(op);
    while(op==0){
        int tmp=0;
        for(int i=1,o=1;i<=dmx;i++,o*=2){
            int a;
            read(a);
            if(a==1) tmp+=o;
        }
        if(tmp==1||tmp==3) cout<<1<<endl;
        else if(tmp==2||tmp==6) cout<<2<<endl;
        else cout<<3<<endl;
        read(op);
    }

    return 0;
}

F

问题转换：对于 从 枚举到 ，求出 第一大的下标和值以及第二大的值

数论分块+ST表

调死我了

对于每个 ，按 分块，由调和级数，遍历的复杂度也不会超过 ，于是只需对 处理

查询第一大的下标和值以及第二大的值， 表改改就行了，但是💩山代码

贴个代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstdlib>
#include<ctime>
#include<bitset>
#include<vector>
#include<climits>
#include<iomanip>
using namespace std;
#define N 400010
#define ll long long
template<typename T>
inline void read(T &x){
    x=0;bool flg=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') flg=1;
    for(;isdigit(c);c=getchar()) x=x*10+(c^48);
    if(flg) x=-x;
}

int t;
int mx=0;
ll ans[N];
int n,f1[30][N],f2[30][N],g[30][N],lg[N]={-1};
int a[N];

struct inp{
    int h,a;
    int num;
}p[N];

struct node{
    ll idx,k1,k2;
};

bool cmp(inp a,inp b){
    return a.a<b.a;
}

void init(){
    for(int i=1;i<=n;i++) f1[0][i]=p[i].h,f2[0][i]=0,lg[i]=lg[i/2]+1,g[0][i]=p[i].num;
    for(int i=1;i<=lg[n];i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            if(f1[i-1][j]<f1[i-1][j+(1<<(i-1))]){
                f1[i][j]=f1[i-1][j+(1<<(i-1))];
                g[i][j]=g[i-1][j+(1<<(i-1))];
                f2[i][j]=max(f1[i-1][j],f2[i-1][j+(1<<(i-1))]);
            }else if(f1[i-1][j]>f1[i-1][j+(1<<(i-1))]){
                f1[i][j]=f1[i-1][j];
                g[i][j]=g[i-1][j];
                f2[i][j]=max(f2[i-1][j],f1[i-1][j+(1<<(i-1))]);
            }else{
                f1[i][j]=f1[i-1][j];
                g[i][j]=-1;
                f2[i][j]=max(f2[i-1][j],f2[i-1][j+(1<<(i-1))]);
            }
        }
    }
}

node query(int l,int r){
    node ans;
    int len=lg[r-l+1];
    if(f1[len][l]>f1[len][r-(1<<len)+1]){
        ans.k1=f1[len][l];
        ans.idx=g[len][l];
        ans.k2=max(f1[len][r-(1<<len)+1],f2[len][l]);
    }else if(f1[len][l]<f1[len][r-(1<<len)+1]){
        ans.k1=f1[len][r-(1<<len)+1];
        ans.idx=g[len][r-(1<<len)+1];
        ans.k2=max(f2[len][r-(1<<len)+1],f1[len][l]);
    }else{
        ans.k1=f1[len][l];
        ans.k2=max(f2[len][l],f2[len][r-(1<<len)+1]);
        if(g[len][l]==g[len][r-(1<<len)+1]) ans.idx=g[len][l];
        else ans.idx=-1;
    }
    return ans;
}

int main(){

    read(t);
    while(t--){
        read(n);mx=0;
        for(int i=1;i<=n;i++) read(p[i].h),p[i].num=i,ans[i]=0;
        for(int i=1;i<=n;i++) read(p[i].a),mx=max(mx,p[i].a);

        sort(p+1,p+1+n,cmp);

        for(int i=1;i<=n;i++) a[i]=p[i].a;

        init();

        for(int i=1;i<=mx;i++){
            node tmp,ad;
            ad.idx=0,ad.k1=0,ad.k2=0;
            // cout<<i<<" "<<ceil((1.0*mx)/(1.0*i))<<endl;
            for(int c=1;c<=ceil((1.0*mx)/(1.0*i));c++){
                int l=lower_bound(a+1,a+n+1,i*(c-1)+1)-a;
                int r=upper_bound(a+1,a+n+1,i*c)-a-1;
                // cout<<i*(c-1)+1<<" "<<i*c<<" "<<l<<" "<<r<<endl;
                if(l>r) continue;
                tmp=query(l,r);
                // cout<<l<<" "<<r<<" "<<tmp.k1<<" "<<tmp.idx<<" "<<tmp.k2<<endl;
                if(tmp.k1*c>ad.k1){
                    ad.k2=max(ad.k1,tmp.k2*c);
                    ad.k1=tmp.k1*c;
                    ad.idx=tmp.idx;
                }else if(tmp.k1*c<ad.k1){
                    ad.k2=max(ad.k2,tmp.k1*c);
                }else{
                    ad.idx=-1;
                    ad.k2=max(ad.k2,tmp.k2*c);
                }
            }
            // cout<<ad.k1<<" "<<ad.idx<<" "<<ad.k2<<endl;
            if(ad.idx==-1) continue;
            ans[ad.idx]=max(ans[ad.idx],ad.k1-ad.k2);
        }

        for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
        cout<<endl;
    }
    

    return 0;
}