也是当上监考了：D
题目其实出的比较navie,很多想出来比较有意思的题目考虑到难度因素都被扫出比赛了QAQ
应该会放在寒假的比赛里
湮灭
题意：给出两个点的坐标，求出欧几里得距离
思路：模拟即可
代码：
考察基本语法
void solve(){int x,y,z,a,b,c;cin>>x>>y>>z>>a>>b>>c;cout<<fixed<<setprecision(2)<<sqrt((a-x)*(a-x)+(b-y)*(b-y)+(c-z)*(c-z));
}
遗迹探险
题意：给出\(n\)个神器的价值，能拿走\(k\)个，求能拿走的最大价值之和
思路：贪心，选择前\(k\)大的神器是最优的方案
代码：
数据量很小，因此\(O(n^2)\)算法 即冒泡排序等朴素排序方法可以通过
当然你也可以使用桶排序实现\(O(n)\)复杂度
void solve(){int n,k;cin>>n>>k;int ans=0;vector<int>a(n+1);rep(i,1,n)cin>>a[i];sort(a.begin()+1,a.end(),greater<int>());rep(i,1,k)ans+=a[i];cout<<ans;
}
编码&解码
题意：
给出一个数字字符串\(s\)，按照\(ASCII\)码将其转译为字母字符串，其中大写字母转小写且倒序输出
(规定输入的字符串转译后一定是由英文字母组成的字符串)
思路：
如果你不清楚哪些数字表示哪些英文字母，有代码：
void solve(){
cout<<(int)'A'<<endl;
cout<<(int)'a'<<endl;
}
输出：
65
97
所以你明白了
\(A\)~\(Z\) :\(65\)~\(90\)
\(a\)$z$:$97$\(122\)
从左往右依次遍历：
- 遇到\(1\): 当前位和 后面两位 组成的数字计算一下
- 否则：当前位和 后面一位 组成的数字计算一下
代码：
模拟题
string s;
void solve(){cin>>s;string ans;for(int i=0;i<s.size();i++){if(s[i]=='1'){int x=s[i]-'0';int y=s[i+1]-'0';int z=s[i+2]-'0';int res=x*100+y*10+z;ans.pb((char)(res));i+=2;}else{int x=s[i]-'0';int y=s[i+1]-'0';int res=x*10+y;ans.pb((char)(res));i++;}}for(int i=0;i<ans.size();i++){if(ans[i]>='A' &&ans[i]<='Z'){ans[i] ='a' + (ans[i]-'A');}}for(int i=ans.size()-1;i>=0;i--){cout<<ans[i];}
}
在寒武纪很想你
题意：
\(n\)个人围一圈，依次报数，报到\(2\) 的人淘汰，后面人接着报\(1\)，求最后留下的人的编号
思路：
发现这是一个经典的约瑟夫环问题
观察得到：
- 第一轮淘汰的是\(n\)范围内所有的偶数编号
- 当\(n\)是\(2\)的幂时，最后留下的一定是编号\(1\)
因此当\(n\)不是\(2\)的幂时，不妨先淘汰掉若干人直到剩下的人数为\(2\)的幂时，当前报数的编号就是最后留下的编号
模拟一下可知\(ans = 2 \times (n-2^k) +1\) \((2^k \lt n \lt 2^{k+1})\)
代码：
时间复杂度\(O(logn)\)
void solve(){int n;cin>>n;int x=1;while(x*2<=n)x*=2;int res=n-x;cout<<2*res+1;
}
如果找不出规律，发现\(n \leq 1e6\)
不妨使用链表模拟报数的情况
用一个\(nxt\)数组表示当前编号的下一个编号是哪一个
淘汰时，将前一个编号的\(nxt\)指向下一个编号
时间复杂度\(O(n)\)
const int M=1e6+5;
int nxt[M];
void solve(){int n;cin>>n;for(int i=1;i<=n;i++){if(i<n)nxt[i]=i+1;else nxt[i]=1;}int p=1,cnt=0;int sz=n;while(true){cnt++;if(cnt==1){sz--;if(sz==1){cout<<p;return;}cnt=0;nxt[p]=nxt[nxt[p]];}p=nxt[p];}
}