小蒟蒻前两天参加了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代码：
#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数据点）：
#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代码：
#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）：
#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分代码
#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;
}
