CCSP2024 赛后回忆

这次是在浙江金华的浙江师范大学，虽然说这里可能有一点点偏僻，但是店铺什么的基本都有，奶茶店，肯德基什么的甚至开在了校内。

这应该是我大学最后一次参加国家级的赛事了吧。

题目

I/O 任务调度队列

按来的时间排个序，奇数放第一个队列，偶数放第二个队列，保证每个任务等待的时间最小就可以了，签到题。

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
#include<bits/stdc++.h>
using namespace std;
const int mxlen = 1e3+5;

int t[mxlen];
int n;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>t[i];
        }        
        sort(t+1,t+n+1);
        int ans1=0,ans2=0;
        for(int i=1;i<=n;i++){
            if(i%2){
                if(t[i]>=ans1){
                    ans1 = t[i]+10;
                }else {
                    ans1 += 10;
                }
            }else {
                if(t[i]>=ans2){
                    ans2 = t[i]+10;
                }else ans2 +=10;
            }
        }
        if(ans1>ans2) swap(ans1,ans2);
        cout<<ans1<<" "<<ans2;
    }
    return 0;
}

数树

模拟题？直接按照他说的把功能都写了就行了，记录一下每个节点的父节点是什么。一开始只用了一位数组来记录点和父节点断开，改来改去只有45分。后来突然想到他可能和好多节点都断开，直接用vector存一下就过了。

第二天听颁奖典礼上讲题解说的是分快树，LCT做。。。

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
135
136
137
138
139
140
141
142
143
144
#include<bits/stdc++.h>
using namespace std;
const int mxlen = 4e5+5;
int n;
int pre_ans;
int w[mxlen];
int father[mxlen];
int now_root = 1;
vector<int> broken[mxlen];
vector<int> g[mxlen];
struct node{
    int weight;
    int index;
};

bool check_relation(int u,int v){
    for(int i=0;i<broken[u].size();i++){
        if(broken[u][i]==v) return 0;
    }
    return 1;
}
void find_father(int u,int fa){
    father[u] = fa;
    for(int i=0;i<g[u].size();i++){
        if(g[u][i]==fa) continue;
        if(!check_relation(u,g[u][i])) continue;
        find_father(g[u][i],u);
    }
}
int change(int v){
    if(!pre_ans) return v;
    return v^pre_ans;
} 

int dfs_weight(int u,int fa,int x){
    int ans = 0;
    for(int i=0;i<g[u].size();i++){
        if(g[u][i]==fa) continue;
        if(!check_relation(u,g[u][i])) continue;
        ans+=dfs_weight(g[u][i],u,x);
    }
    if(w[u]>x) ans++;
    return ans;
}
int find_heaviest(int u,int fa){
    int ans = w[u];
    for(int i=0;i<g[u].size();i++){
        if(g[u][i]==fa) continue;
        if(!check_relation(u,g[u][i])) continue;
        ans = max(ans,find_heaviest(g[u][i],u));
    }
    return ans;
}

node find_minw_minindex(int u,int fa){
    node tmp = {w[u],u};
    for(int i=0;i<g[u].size();i++){
        if(g[u][i]==fa) continue;
        if(!check_relation(u,g[u][i])) continue;
        node son = find_minw_minindex(g[u][i],u);
        if(son.weight<tmp.weight){
            tmp.weight = son.weight;
            tmp.index = son.index;
        }else if(son.weight==tmp.weight){
            if(son.index<tmp.index){
                tmp.weight = son.weight;
                tmp.index = son.index;
            }
        }
    }
    return tmp;
}
void solve(int op){
    int u,x;
    // ask how many points' weight more than v in u subtree
    if(op==1){
        cin>>u>>x;
        u = change(u);
        x = change(x);
        pre_ans = dfs_weight(u,father[u],x);
        cout<<pre_ans<<endl;
    }else if(op==2){
        cin>>u>>x;
        u = change(u);
        x = change(x);
        w[u] = x;
    }else if(op==3){
        cin>>u>>x;
        u = change(u);
        x = change(x);
        n++;
        g[n].push_back(u);
        g[u].push_back(n);
        father[n] = u;
        w[n] = x;
    }else if(op==4){
        cin>>u;
        u = change(u);
        broken[u].push_back(father[u]);
        broken[father[u]].push_back(u);
        find_father(u,-1);
        pre_ans = find_heaviest(u,father[u]);
        cout<<pre_ans<<endl;
    }else if(op==5){
        cin>>u;
        u = change(u);
        node temp = find_minw_minindex(u,father[u]);
        pre_ans = temp.index;
        cout<<pre_ans<<endl;
    }else if(op==6){
        cin>>u;
        u = change(u);
        find_father(u,-1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while(T--){
        int m;
        cin>>n;
        int x,y;
        for(int i=1;i<n;i++){
            cin>>x>>y;
            g[x].push_back(y);
            g[y].push_back(x);
        }     
        for(int i=1;i<=n;i++){
            cin>>w[i];
        }

        find_father(now_root,-1);
        cin>>m;
        int op;
        pre_ans = 0;
        for(int i=1;i<=m;i++){
            cin>>op;
            solve(op);
        }
    }
    return 0;
}

贝壳统计（shell）

这题。。。。80分带修莫队板子题。后面插入元素的改了半天都会超时，不懂怎么改。只拿了80分。

一开始直接暴力做能拿40分。我看这1e5的数据，两维数组都开不了，也没办法记忆化，就想起来了之前看过的快慢指针，我拿两个指针来回记录时间应该会小一点，很遗憾还是40分。我看着我写的pre_l--和pre_r++越看越熟悉，，，这不就是莫队吗？？？？！！！还好这比赛让带U盘，然后我点开里面的模版（赛前都没看过，不知道从哪里下的了都），直接目录直达带修莫队，ubuntu里复制pdf里代码到vscode里缩进都没了，我也没管，粘过来改改变量名称直接就拿了80分。

第二天题解讲的是线段树什么的维护增加位置的个数，把添加的数改为负数，还没插入的为负数不用管，好像有点道理。

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include<bits/stdc++.h>
using namespace std;
const int mxlen = 1e5+1e4+15;
int n;

vector<int> a;

bool vis[mxlen*2];
int block = 2589;
struct Query{
    int id,l,r,t;
}q[mxlen];
struct Modify{
    int pos,col,lst;
}c[mxlen];
int cnt[mxlen];
int bi[mxlen];

bool cmp(const Query &a, const Query &b){
int al = bi[a.l], ar = bi[a.r];
int bl = bi[b.l], br = bi[b.r];
if(al != bl)return a.l < b.l;
if(ar != br)return a.r < b.r;
return a.t < b.t;
}
void add(int x, int& res){
if(cnt[x] == 0)res ++ ;
cnt[x] ++ ;
}
void del(int x, int& res){
cnt[x] -- ;
if(cnt[x] == 0)res -- ;
}
int mq = 0,mc = 0;
int ans[mxlen];
inline void write(int res){
if(res<0){
putchar('-');
res=-res;
}
if(res>9)
write(res/10);
putchar(res%10+'0');
}
void modui(){
        for(int i = 1; i <= n; ++ i){
    bi[i] = (i - 1) / block;
    }
    sort(q + 1, q + 1 + mq, cmp);
    for(register int k = 1, i = 0, j = 1, t = 0, res = 0; k <= mq; ++ k){
        int id = q[k].id, l = q[k].l, r = q[k].r, tim = q[k].t;
        while(i < r)res += ++ cnt[a[ ++ i]] == 1;
    while(i > r)res -= -- cnt[a[i -- ]] == 0;
    while(j < l)res -= -- cnt[a[j ++ ]] == 0;
    while(j > l)res += ++ cnt[a[ -- j]] == 1;
    //再处理y轴
    while(t < tim){
    t ++ ;
    if(c[t].pos >= j && c[t].pos <= i){
    del(a[c[t].pos], res);
    add(c[t].col, res);
    //res -= !--cnt[w[c[t].pos]] - !cnt[c[t].col]++;
    }
    swap(a[c[t].pos], c[t].col);
    }
    while(t > tim){
    if(c[t].pos >= j && c[t].pos <= i){
    del(a[c[t].pos], res);
    add(c[t].col, res);
    //res -= !--cnt[w[c[t].pos]] - !cnt[c[t].col]++;
    }
    swap(a[c[t].pos], c[t].col);
    t -- ;
    }
    ans[id] = res;
    }

    for(int i=1;i<=mq;i++){
        write(ans[i]), puts("");
    }
}
void solve_large(int op){
    
    if(op==1){
        int L,R;
        cin>>L>>R;
        q[++mq] = (Query){mq,L,R,mc};        
    }else if(op==2){
        int P,V;
        cin>>P>>V;
        c[++mc] = (Modify){P,V};
    }else {
        modui();
        memset(cnt,0,sizeof(cnt));
        mq = 0;
        mc = 0;
        int P,V;
        cin>>P>>V;
        n++;
       a.insert(a.begin()+P,V);
    }
}
void solve(int op){
    if(n>1e4){
        solve_large(op);
        return ;
    }
    if(op==1){
        int L,R;
        cin>>L>>R;
        int ans = 0;
        memset(vis,0,sizeof(vis));
        for(int i=L;i<=R;i++){
            if(!vis[a[i]]){
                ans++;
                vis[a[i]]=1;
            }
        }
        cout<<ans<<endl;
    }else if(op==2){
        int P,V;
        cin>>P>>V;
        a[P] = V;
    }else {
        int P,V;
        cin>>P>>V;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    while(T--){
        int m;
        cin>>n>>m;
        int x;
        a.push_back(0);
        for(int i=1;i<=n;i++){
            cin>>x;
            a.push_back(x);
        }
        int op;
        while(m--){
            cin>>op;
            solve(op);
        }

        if(n>1e4&&op!=3) modui();

    }
    return 0;
}

其他

后两题真的折磨，光输入都差不多写了100多行，然而就只拿到了10分，这里就不贴代码了。我觉得要是平时写过系统相关的代码应该很快能写出来，我看有人很快就写完了。我调了半天真的有点崩溃了，看了看排行榜感觉再努力也进不了金牌了，还是早早收场就提前出来了。

总结

最后是拿了290分，差十分银。这次可以说是大意失荆州——骄兵必败了。六点半的时候还排在银奖队伍中前部位，因为七点后就封傍了，我觉得就算有人后面写出来后两题也不至于把我退到铜吧（请不要学我。。。）。