CCSP

小蒟蒻前两天参加了CCSP2024

最终幸运蹭铜(蹭着本科的边边捞到了铜牌,没有遗憾了)。

评价感受

本来只是来打酱油(蹭吃蹭喝)的,因为自从推免结束后,已经正好一个月没碰代码了,上一次碰代码还是参加某学校的机考。但是编程这个东西很神奇,不管你多久没碰代码,一看到题目就突然会了,还是能比划比划的。于是上来20分钟直接贪心算法(我不会别的算法了),先AC了第一道题。之后又试了试贝壳统计,发现前10个点数据量很小,并且操作简单,完全可以暴力解决,故一番尝试之后先把这题拿了40分。

此时时间过去了一个半小时,我又看了看数树,发现这道题逻辑很清晰,三个层次的数据点,前两个层次只要把树模拟出来就可以很轻易地得分,故我就先拿到了这55分。此时已经12点过了,比赛过了3小时,拿到了195分。

正好吃一下午饭,收拾收拾心情。午饭没有拍照(没有手机),但感觉还是可以的,盒饭,还发了个香蕉。午饭结束后我感觉数树的后面45分有个旋转,当时潜意识里感觉没那么容易,于是就先放一放。开始开系统题(也就是超级大模拟),这一开不要紧,直接写了4个小时的bitTorent服务器,要求实现接受6个指令并做出反应,我感觉最低的得分门槛大概涵盖了70%的工作量,但只有30分,但一旦实现了这个最低门槛,再往上拿分就比较容易了。很遗憾,我写了四个小时没有写出来,没有通过这个最低门槛。后来看到似乎这个最低门槛还是与未要求的指令有关系,这个就不知道了。中途又对贝壳统计改进了又交了一发还是没有提升。此时已经到了晚上五点半,天黑了。等于是我一个下午一分都没有拿,心态有点炸。打开排行榜一看,发现自己已经掉出了铜奖线,遂没有什么别的想法,开始摆烂。正好又来了盒饭,故事已至此,先吃饭吧。

边吃饭边看前面的题目,想再捞点分。发现数树的最后一部分其实还好,没有想象的那么难。边吃边想,想的差不多了就看最后一道系统题,发现前两个得分点还是比较简单的。遂定下方针,先把数树拿到,再最后一道系统题捞20分,就是赚了。如果这个策略能成真,那估计就有260,可能有铜奖了。

饭后敲了半个小时,直接提交,数树AC了,此时已经六点半了,我AC了第二道题。这45分一加,效果很显著,直接跳到了铜奖中间的位置,240分。

然后做最后一道系统题,本来以为能捞20分的,结果只拿到10分,此时已经七点了,先尝试找bug,找了半个小时没找到,又试试别的题,之后就没有任何进展了。

临结束的时候交了一发贝壳统计,换了一种思路,当时没立刻出结果,后来看到还是TLE,那就没办法了,就这样吧。事后发现,如果这个拿满,还是可能银牌的,呵呵。

全过程跌宕起伏吧,从一开始的无所谓,到发现自己还是有点希望的,再到跌出铜奖线,开始摆烂,然后又绝处逢生,再到最后实在找不出bug了,就这样潦草画上句点。

总的来说我还是非常幸运的。感谢勇于尝试的自己。

金银铜奖情况

金奖靠前ranklist(全都是大佬)

第一名是在封榜前AK的,真的是非常厉害

金奖线(365)

银奖线(300)

铜奖线(240靠前)

只有时间较早拿到240的同学才有铜奖

题目与解答

部分题目不会,没答上来。

第1题

AC代码:

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
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;

int main()
{
int n;
priority_queue<int, vector<int>, greater<int>> q;
cin>>n;
for (int i=0;i<n;i++)
{
int temp;
cin>>temp;
q.push(temp);
}
int t1=0,t2=0;
bool flag1,flag2;
while(!q.empty())
{
// cout<<q.top();
// q.pop();
int now = q.top();
q.pop();
if (t2<t1)
{
if (now > t2) t2=now+10;
else t2+=10;
}
else{
if (now > t1) t1=now+10;
else t1+=10;
}
}
if (t1>t2) swap(t1,t2);
cout<<t1<<" "<<t2<<endl;
return 0;
}

点击并拖拽以移动

第2题

40分代码(仅完成1-10数据点):

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
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
vector<int> v;
for (int i=0;i<n;i++)
{
int temp;
cin>>temp;
v.push_back(temp);
}
if (n<=10000 && m<=10000)
{
while(m--)
{
int op,a,b;
cin>>op>>a>>b;
if (op==1)
{
int sum = 0;
// set<int> s;
// for (int i=a-1; i<=b-1; i++)
// {
// int now = v[i];
// if (s.find(now) == s.end())
// {
// sum++;
// s.insert(now);
// }
// }
bool ntemp[20000];
memset(ntemp,0,sizeof(ntemp));
for (int i=a-1; i<=b-1; i++)
{
int now = v[i];
if (ntemp[now] == 0)
{
sum++;
ntemp[now] = 1;
}
}
cout<<sum<<endl;
}
else if (op==2)
{
v[a-1] = b;
}
else
{
v.insert(v.begin()+a, b);
}
}
}
else{
map<int,vector<int>> mp;
bool ntemp[200000];
memset(ntemp,0,sizeof(ntemp));
for (int i=0; i<n; i++)
{
if (ntemp[v[i]] == 0)
{
ntemp[v[i]] = 1;
}
else{
vector<int> temp;
for (int j=0; j<mp[v[i]].size(); j++) {
temp.push_back(mp[v[i]][j]);
mp[v[i]].push_back(mp[v[i]][j]);}
for (auto x : temp) mp[x].push_back(v[i]);
}
}
while(m--)
{
int op,a,b;
cin>>op>>a>>b;
if (op==1)
{
int sum = 0;
for (auto x : mp)
{
int count = 0;
if (x.first>=a && x.first<=b)
{
for (auto y : x.second)
{
if (y>=a && y<=b) count++;
}
}
count /= 2;
count --;
sum+=count;
}
cout<<b-a+1-sum<<endl;
}
else if (op==2)
{
v[a-1] = b;
}
else
{
v.insert(v.begin()+a, b);
}
}
}
return 0;
}

点击并拖拽以移动

第3题

AC代码:

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

struct node
{
int data;
int parent;
vector<int> child;
};

int findnum(vector<node> &list, int u, int v)
{
int ret = 0;
if (list[u].child.empty())
{
if (list[u].data > v) ret = 1;
return ret;
}
else{
for(int i=0; i<list[u].child.size(); i++)
{
ret += findnum(list,list[u].child[i],v);
}
if (list[u].data > v) ret += 1;
return ret;
}
}

int findmax(vector<node> &list, int u)
{
int maxnum = 0;
if (list[u].child.empty())
{
maxnum = max(list[u].data, maxnum);
return maxnum;
}
else{
for(int i=0; i<list[u].child.size(); i++)
{
maxnum = max(maxnum, findmax(list,list[u].child[i]));
}
return max(maxnum, list[u].data);
}
}

void findmin(vector<node> &list, int u, int& minvalue, int& minnum)
{
if (!list[u].child.empty())
{
for(int i=0; i<list[u].child.size(); i++)
{
findmin(list, list[u].child[i], minvalue, minnum);
}
}
if (list[u].data < minvalue)
{
minnum = u;
minvalue = list[u].data;
}
else if (list[u].data == minvalue && u<minnum)
{
minnum = u;
minvalue = list[u].data;
}
return;
}

void rotate(vector<node> &list, int u)
{
if (list[u].parent == -1) return;
rotate(list, list[u].parent);
int parentnum = list[u].parent;
auto childpos = find(list[parentnum].child.begin(), list[parentnum].child.end(), u);
list[parentnum].child.erase(childpos);
list[parentnum].parent = u;
list[u].parent = -1;
list[u].child.push_back(parentnum);
return;
}

int main()
{
int n,m;
cin>>n;
vector<node> list;
for (int i=0;i<n; i++)
{
node newnode;
newnode.parent = -1;
list.push_back(newnode);
}
for (int i=0;i<n-1;i++)
{
int u,v;
cin>>u>>v;
u--;
v--;
list[u].child.push_back(v);
list[v].parent = u;
}
for (int i=0; i<n; i++)
{
int temp;
cin>>temp;
list[i].data = temp;
}

cin>>m;
int last = 0;
while(m--)
{
int DEBUG =0;
if (DEBUG)
{
cout<<endl;
for (int i=0; i<list.size(); i++)
{
cout<<"index = "<<i<<" value = "<<list[i].data<<" | ";
for (int j=0; j<list[i].child.size(); j++) cout<<list[i].child[j]<<" ";
cout<<endl;
}
}
int op;
cin>>op;
if (op == 1)
{
int u,v;
cin>>u>>v;
u ^= last;
v ^= last;
u--;
last = findnum(list,u,v);
cout<<last<<endl;
}
else if (op == 2)
{
int u,v;
cin>>u>>v;
u ^= last;
v ^= last;
u--;
list[u].data = v;
}
else if (op == 3)
{
int u,v;
cin>>u>>v;
u ^= last;
v ^= last;
u--;
int now = list.size();
node newnode;
list.push_back(newnode);
list[now].data = v;
list[u].child.push_back(now);
list[now].parent = u;
}
else if (op == 4)
{
int u,v;
cin>>u;
u ^= last;
u--;
int parent = list[u].parent;
list[parent].child.erase(find(list[parent].child.begin(),list[parent].child.end(),u));
list[u].parent = -1;
last = findmax(list,u);
cout<<last<<endl;
}
else if (op == 5)
{
int u,v;
cin>>u;
u ^= last;
u--;
int minvalue = 9999999;
int minnum = 99999;
findmin(list, u, minvalue, minnum);
last = minnum + 1;
cout<<last<<endl;
}
else if (op == 6)
{
int u,v;
cin>>u;
u ^= last;
u--;
rotate(list,u);
}

}

return 0;
}

点击并拖拽以移动

第4题

10分代码(只完成数据点1):

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
#include<bits/stdc++.h>
#include<cstring>
#include<string>
using namespace std;

// CREATE_Proc pid load
// DESTROY_Thread tid
// CREATE_Thread pid tid load
// SCHEDULE_OPT

map<int,int> tidref;

struct pnode
{
int pid;
int load;
map<int,int> threadlist;
};

map<int,pnode> plist;

int main()
{
int n;
cin>>n;

getchar();
while (n--)
{
string str;
getline(cin,str);
stringstream ss;
ss << str;
string op;
vector<string> envlist;
ss >> op;
string temp;
while(ss >> temp)
{
envlist.push_back(temp);
}

if (op == "CREATE_Proc")
{
// CREATE_Proc pid load
int pid = stoi(envlist[0]);
int load = stoi(envlist[1]);

if (plist.find(pid) != plist.end()) continue;
pnode newnode;
newnode.pid = pid;
newnode.load = load;
newnode.threadlist.insert(make_pair(pid,load));
tidref.insert(make_pair(pid,pid));
plist.insert(make_pair(pid,newnode));
}
else if (op == "CREATE_Thread")
{
// CREATE_Thread pid tid load
int pid = stoi(envlist[0]);
int tid = stoi(envlist[1]);
int load = stoi(envlist[2]);

if (plist.find(tid) != plist.end()) continue;
auto pos = plist.find(pid);
if (pos != plist.end())
{
pos->second.threadlist.insert(make_pair(tid,load));
tidref.insert(make_pair(tid,pid));
}
}
else if (op == "DESTROY_Thread")
{
// DESTROY_Thread tid
int tid = stoi(envlist[0]);

if (tidref.find(tid) == tidref.end()) continue;
int pid = tidref[tid];
plist[pid].threadlist.erase(tid);
tidref.erase(tid);
if (plist[pid].threadlist.empty())
{
plist.erase(pid);
}
}
else if (op == "SCHEDULE_OPT")
{
// SCHEDULE_OPT
for (auto x : plist)
{
for (auto y : x.second.threadlist)
{
cout<<"Process (PID): "<<x.first<<" Thread(Tid): "<<y.first<<" Load: "<<y.second<<endl;
}
}
cout<<"Contention Cost: 0"<<endl;
}
}
return 0;
}

点击并拖拽以移动

第5题

题面太长,不放了。这道题足足写了4个小时,但还是0分,很难受。

0分代码

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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
#include<bits/stdc++.h>
#define my_leecher pos->second.leecher
#define my_seeder pos->second.seeder
using namespace std;
const int DEBUG = 0;

struct usernode
{
string peer_id;
string ip;
string port;
int uploaded;
int downloaded;
usernode(string peer_id, string ip, string port, int uploaded, int downloaded)
{
this->peer_id = peer_id;
this->ip = ip;
this->port = port;
this->uploaded = uploaded;
this->downloaded = downloaded;
}
};

struct seednode
{
string info_hash;
string status;
map<string,usernode> seeder;
map<string,usernode> leecher;
int complete;
int incomplete;
};

map<string,seednode> seedlist;


bool cmp_seeder(usernode& a, usernode& b)
{
if (a.uploaded > b.uploaded) return true;
else if (a.uploaded < b.uploaded) return false;
else{
return a.peer_id < b.peer_id;
}
}

bool cmp_leecher(usernode& a, usernode& b)
{
if (a.downloaded > b.downloaded) return true;
else if (a.downloaded < b.downloaded) return false;
else{
return a.peer_id < b.peer_id;
}
}

string add(map<string,seednode>& seedlist, vector<string>& envlist)
{
string info_hash = envlist[0].substr(10,20);
if (seedlist.find(info_hash) == seedlist.end())
{
seednode newseed;
newseed.info_hash = info_hash;
seedlist.insert({info_hash,newseed});
return "OK";
}
else{
return "ERROR: Torrent already exists";
}
}

string del(map<string,seednode>& seedlist, vector<string>& envlist)
{
string info_hash = envlist[0].substr(10,20);
map<string,seednode>::iterator now = seedlist.find(info_hash);
if (now != seedlist.end())
{
// TODO
// if () in use
if (now->second.status == "FROZEN") return "FROZEN";
else{
seedlist.erase(now);
return "OK";
}
}
else{
return "ERROR: Invalid info_hash";
}

}

void annoounce(vector<string>& envlist)
{
// announce
// INFO_HASH=INFO-000000000000002
// PEER_ID=PEER-00000000000000D
// IP=192.168.3.4
// PORT=5204
// UPLOADED=1200
// DOWNLOADED=300
// NUMWANT=3
// EVENT=completed
string info_hash = envlist[0].substr(10,20);
string peer_id = envlist[1].substr(8,20);
string ip = envlist[2].substr(3);
string port = envlist[3].substr(5);
int uploaded = stoi(envlist[4].substr(9));
int downloaded = stoi(envlist[5].substr(11));
string temp = envlist[6].substr(8);
int numwant;
if (temp=="") numwant = 50;
else numwant = stoi(envlist[6].substr(8));
string event = envlist[7].substr(6);

//if (DEBUG) cout<<"DEBUG*****"<<endl<<info_hash<<endl<<peer_id<<endl<<ip<<endl<<port<<endl<<uploaded<<endl<<downloaded<<endl<<numwant<<endl<<event<<endl<<"*****DEBUG"<<endl;

auto pos = seedlist.find(info_hash);
if (pos != seedlist.end())
{
//auto my_seeder = pos->second.seeder;
auto seeder_pos = my_seeder.find(peer_id);
//auto my_leecher = pos->second.leecher;
auto leecher_pos = my_leecher.find(peer_id);
string user_status = "";
usernode newnode(peer_id, ip, port, uploaded, downloaded);
if (DEBUG) cout<<"AAAAA"<<endl;
if (DEBUG) cout<<"now info_hash:"<<info_hash<<endl;
if (DEBUG) {cout<<"leecher:"; for (auto x : my_leecher) cout<<x.first<<" "; cout<<endl;}
if (DEBUG) {cout<<"seed:"; for (auto x : my_seeder) cout<<x.first<<" "; cout<<endl;}

if (event == "started")
{
if (seeder_pos != my_seeder.end()) my_seeder.erase(seeder_pos);
if (leecher_pos == my_leecher.end()) my_leecher.insert({peer_id,newnode});
else
{
leecher_pos->second.downloaded = downloaded;
leecher_pos->second.uploaded = uploaded;
}
user_status = "leecher";
}
else if (event == "completed")
{
if (leecher_pos != my_leecher.end()) my_leecher.erase(leecher_pos);
if (seeder_pos == my_seeder.end()) my_seeder.insert({peer_id,newnode});
else
{
seeder_pos->second.downloaded = downloaded;
seeder_pos->second.uploaded = uploaded;
}
user_status = "seeder";
}
else if (event == "stopped")
{
if (seeder_pos != my_seeder.end()) my_seeder.erase(seeder_pos);
if (leecher_pos != my_leecher.end()) my_leecher.erase(leecher_pos);
}
else if (event == "empty")
{

}

int complete = my_seeder.size();
int incomplete = my_leecher.size();
if (DEBUG) cout<<"now info_hash:"<<info_hash<<endl;
if (DEBUG) cout<<"complete:"<<complete<<endl<<"incomplete:"<<incomplete<<endl;
if (DEBUG) {cout<<"leecher:"; for (auto x : my_leecher) cout<<x.first<<" "; cout<<endl;}
if (DEBUG) {cout<<"seed:"; for (auto x : my_seeder) cout<<x.first<<" "; cout<<endl;}

vector<usernode> peers;
if (user_status == "seeder")
{
numwant = min(numwant, incomplete);
vector<usernode> seedervec,leechervec;
for (auto x : my_leecher) leechervec.push_back(x.second);
sort(leechervec.begin(),leechervec.end(),cmp_leecher);
for(int i=0; i<numwant; i++) peers.push_back(leechervec[i]);
}
else if (user_status == "leecher")
{
vector<usernode> seedervec,leechervec;
for (auto x : my_seeder) seedervec.push_back(x.second);
sort(seedervec.begin(),seedervec.end(),cmp_seeder);
int count = 0;
for(int i=0; i<seedervec.size(); i++)
{
peers.push_back(seedervec[i]);
count++;
if (count == numwant) break;
}
if (count < numwant)
{
for (auto x : my_leecher) leechervec.push_back(x.second);
sort(leechervec.begin(),leechervec.end(),cmp_leecher);
for(int i=0; i<leechervec.size(); i++)
{
peers.push_back(leechervec[i]);
count++;
if (count == numwant) break;
}
}
}

// return
cout<<"OK: ";
cout<<"COMPLETE="<<complete<<" ";
cout<<"INCOMPLETE="<<incomplete<<" ";
cout<<"PEERS=[";
for (int i=0; i<peers.size(); i++)
{
cout<<"("<<peers[i].peer_id<<","<<peers[i].ip<<","<<peers[i].port<<")";
if (i != peers.size()-1) cout<<",";
}
cout<<"]"<<endl;
return;
}
else{
cout<<"ERROR: Invalid info_hash"<<endl;
return;
}


}


int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
string str;
while(getline(cin,str))
{
stringstream ss;
ss << str;
string op;
vector<string> envlist;
ss >> op;
string temp;
while(ss >> temp)
{
envlist.push_back(temp);
}
// cout<<op<<endl;
// for (auto x : envlist) cout<<x<<endl;
// cout<<endl;
if (op == "announce")
{
annoounce(envlist);
}
else if (op == "add")
{
cout<<add(seedlist, envlist)<<endl;
}
else if (op == "del")
{
cout<<del(seedlist, envlist)<<endl;
}
// 30
else if (op == "scrape")
{

}
// 50
else if (op == "run")
{

}
// 70
else if (op == "report")
{

}
// 100
}
return 0;
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

扫一扫,分享到微信

微信分享二维码
  • Copyrights © 2022-2025 wolf void
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信