写在前面： 的

A

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

B

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

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

C

小小计数题

预处理出 以及

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

D

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

先考虑 时的做法

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

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

E

交互题，想假了

一开始的做法：

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

实际上，想复杂了

颜色最多 种

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

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

贴个代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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表

调死我了

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

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

贴个代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#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;
}

本文采用CC-BY-SA-3.0协议，转载请注明出处
作者: wsy_jim