巅峰赛#17全题解！
2025-02-06 17:31:57
发布于：广东
151阅读
0回复
0点赞
先报个人难度：红，红/橙，黄，黄/绿，橙，黄，橙/黄，蓝。
T1 - 纪念品商店
如果他在商店区左边，就往右边移至商店区最左边的商店。
如果他在商店区右边，就往右边移至商店区最右边的商店。
#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int a, b, c, d;
cin >> a >> b >> c >> d;
if(c < a) d -= (a - c);
if(c > b) d -= (c - b);//移动
if(d < 0) cout << "No";//判断步数是否大于D
else cout << "Yes";
return 0;
}
时间复杂度 。
思考，如果要小码君恰好移动 步，还要特判哪种情况？
T2 - 删除元素使数组去重
这题数据范围不算太大，可以直接用桶模拟。
#include <iostream>
#include <cstdio>
using namespace std;
int a[105], n;
int bucket[105], ct;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i], bucket[a[i]]++;//用桶记录出现的次数
for(int i = 1; i <= 100; i++){
if(bucket[i] > 1) ct++;//如果出现次数大于1，就记录下来
}
if(ct == 0){//注意特判没有重复元素的情况
cout << 0;
return 0;
}
for(int i = 1; i <= n; i++){
if((--bucket[a[i]]) == 1) ct--;//删除元素
if(ct == 0){//如果没有重复元素直接输出
cout << i;
return 0;
}
}
}
时间复杂度 。
T3 - 摩天轮
超难数学题。
本题分为两步：
- 计算出当他们登上摩天轮 分钟后的坐标。
- 通过坐标计算出角度。
由于摩天轮关于 轴平行，所以此时的旋转坐标公式应为：
，
.
并且因为摩天轮是平行于 轴的，所以 .
最终的公式为 ，.
我们知道仰角和俯角实际上就是两个点构成的直角三角形的角度，如图所示：
就是 看向 的仰角度数。
我们只需要知道 的长度即可套公式 求出。
显然，在本题 就是小码君和小码酱在 平面上的距离， 就是两人的高度差。
说完了，上代码！
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#define int long long
#define float long double
using namespace std;
int n, t;
int xa, ya, xb, yb;
int la, lb;
const float tau = 6.283185307179586;
pair <float, float> get_coord(float len, float theta){//计算移动距离
return {-(len / 2) * sinl(theta), (len / 2) * (1 - cosl(theta))};
}
void solve(){
int time;
cin >> time;
time %= n;
float theta = tau * time / n;
auto cha = get_coord(la, theta), chb = get_coord(lb, theta);
float curya = cha.first + ya, curza = cha.second;//移动距离和原来的坐标加起来就是旋转后的坐标
float curyb = chb.first + yb, curzb = chb.second;
float dx = abs(xa - xb), dy = abs(curya - curyb), dz = abs(curza - curzb);
float dis = sqrtl(dx * dx + dy * dy);//计算AB距离
float ans = atan2l(dz, dis) * (360 / tau);//套公式
cout << setprecision(9) << fixed << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> xa >> ya >> la >> xb >> yb >> lb >> t;
while(t--) solve();
return 0;
}
时间复杂度 。
T4 - 线性探查法
这道题目考的是哈希，那肯定会卡哈希，所以我就不用 unordered_map 做了
本题插入的意思就是找到第一个内容为空的单元，如果直接暴力会被卡到 。
但是，众所又周知，线段树可以 找到第一个符合条件的点！
那么，模拟，秒了。
诶等等，在样例的第 次操作中，由于前面没有空位，它探测到后面去了！
没事，像合并石子一样，再复制一个拼接到后面就能当循环空间用了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
#define int long long
#define double pair <int, int>
using namespace std;
int a[100005];
bool tree[524293];//线段树
int size;
int n, m;
map <int, int> mp;
int get_first(int idx){//O(logN)寻找第一个符合条件的
if(idx == 0){//线段树不能处理idx=0的情况，得特判
if(!tree[size]) return 0;
return get_first(1);
}
idx += size;
do{
while(~idx & 1) idx >>= 1;
if(!tree[idx]){
for(; idx <= size;){
idx <<= 1;
if(tree[idx]) idx++;
}
return idx - size;
}
idx++;
}while((idx & -idx) != idx);
return size * 2;
}
void modify(int idx){//O(logN)单点改
for(tree[idx += size] = 1, idx >>= 1; idx; idx >>= 1){
tree[idx] = (tree[idx * 2] && tree[idx * 2 + 1]);
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
size = 1 << (int)(ceil(log2(n)) + 1e-5) + 1;
for(int i = 1; i <= m; i++){
cin >> a[i];
if(mp[a[i]]){//如果已经有了就不用修改了
cout << mp[a[i]] << '\n';
continue;
}
int idx = get_first(a[i] % n);
if(idx >= n) idx -= n;//循环空间
modify(idx), modify(idx + n);//修改
mp[a[i]] = idx;//记录
cout << idx << '\n';
}
return 0;
}
时间复杂度 。
T5 - 统计 acgo 的出现次数
先看这题：P2646 数数zzy - 洛谷 | 计算机科学教育新生态
如果字符串出现了 y ，那么在它之前的 z 任意挑两个和这个 y 都可以组成一个 zzy 的子序列。
所以核心代码如下：
for(char c:s){
if(c == 'z') ctz++;//记录z的数量
if(c == 'y') ans += ctz * (ctz - 1) / 2;//挑两个z的组合数
}
这题同理，只不过复杂一些。
我们先记录 a 的数量。
如果一个字符是 c，那么在它之前所有的 a 与这个 c 都能组成一个 ac 的子序列，记录下来。
如果一个字符是 g，那么在它之前所有的 ac 与这个 g 都能组成一个 acg 的子序列，记录下来。
如果一个字符是 o，那么在它之前所有的 acg 与这个 o 都能组成一个 acgo 的子序列，记录下来。
答案就出来了！
#include <iostream>
#include <cstdio>
using namespace std;
int n;
string s;
struct modInt{//还是这个用着爽
int val;
void operator ++(int){
val++;
if(val == 998244353) val = 0;
}
void operator += (modInt b){
val += b.val;
if(val >= 998244353) val -= 998244353;
}
}ct1, ct2, ct3, ct4;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> s;
for(char i:s){
if(i == 'a') ct1++;
if(i == 'c') ct2 += ct1;
if(i == 'g') ct3 += ct2;
if(i == 'o') ct4 += ct3;//计算
}
cout << ct4.val;
return 0;
}
时间复杂度：。
T6 - 美丽数 II
解法：我们从 开始，枚举不超过 的质因子，然后判断即可。
注意一定得遍历质数，不然单次查询时间复杂度就会退化至 。
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
#pragma GCC optimize(2)
using namespace std;
bool vis[100005];
vector <int> v;
void solve(){
int n, ct = 0;
cin >> n;
for(int i:v){
if(i * i > n) break;
while(n % i == 0) n /= i, ct++;//记录下有多少个质因子
}
if(ct > 3) cout << "No\n";
else if(ct == 3 && n == 1 || ct == 2 && n != 1) cout << "Yes\n";//如果n不为1就说明还有一个质因子（就是当前的n）
else cout << "No\n";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
vis[0] = vis[1] = 1;
for(int i = 2; i <= 400; i++){//提前筛一遍
if(!vis[i]){
for(int j = i * 2; j <= 100000; j += i) vis[j] = 1;
}
}
for(int i = 2; i <= 100000; i++) if(!vis[i]) v.push_back(i);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度：。
T7 - 数的集合
分类讨论：
这个数是不是质数？是？那就没得操作了，直接输出 。
如果不是质数，那他有没有为 的质因子？
有：那就能把所有 的数都给加进这个集合内，然后所有 也都进去了。
没有：那就把其中一个质因子 放进集合内，可以证明它必定小于 。然后就和上面的一样了。
当 足够大时（ 就行），显然不能进入集合的只有所有 的质数。显然这可以前缀和秒掉。
#include <iostream>
#include <cstdio>
using namespace std;
bool vis[3000005];
int qzh[3000005];
int dabiao[10]{0, 0, 0, 0, 1, 0, 3, 0, 4, 5};
void solve(){
int n;
cin >> n;
if(n < 10){
cout << dabiao[n] << '\n';//小数据打表，以免出现特殊情况
return;
}
if(!vis[n]) cout << "0\n";//是质数，操作次数为0
else cout << n - qzh[n] + qzh[n / 2] - 2 << '\n';//否则就按题意模拟
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
vis[0] = vis[1] = 1;
for(int i = 2; i <= 1800; i++){//筛
if(!vis[i]){
for(int j = i * 2; j <= 3000000; j += i) vis[j] = 1;
}
}
for(int i = 2; i <= 3000000; i++){
qzh[i] = qzh[i - 1] + 1 - vis[i];//记录前缀和
}
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度 。
T8 - 巨大的表格
这道题可以发现 很小，但也没小到那种程度，注意到这题刚刚好能通过 的算法。
而且 又这么大……还是递推题……
这就需要矩阵快速幂了。
我们可以构造如下的神秘矩阵：
这个矩阵乘上
就可以得到
然后就可以快速幂了。
构造矩阵的办法在这题的题解里详细介绍，可以去看看。
#include <iostream>
#include <cstdio>
#include <memory.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n, m, s, t;
int b[35];
int mtx[40][40];
struct martix{//应该没人发现我拼错了吧（
int a[40][40];
martix(){
memset(a, 0, sizeof(a));
}
void _1(){
for(int i = 0; i < n - 1; i++) a[n - i - 2][0] = b[i];//初始化，A_{i,0}
a[n][0] = 1;
}
void _2(){
for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) a[i][j] = mtx[i][j];//乘数
}
martix operator * (const martix &b) const{//矩阵乘法
martix tmp;
for(int i = 0; i < 35; i++){
for(int j = 0; j < 35; j++){
for(int k = 0; k < 35; k++){
tmp.a[i][j] += a[i][k] * b.a[k][j] % mod;
tmp.a[i][j] %= mod;
}
}
}
return tmp;
}
};
martix pow(int time){//快速幂
martix tmp, a;
tmp._1();
a._2();
while(time){
if(time & 1) tmp = a * tmp;
a = a * a, time >>= 1;
}
return tmp;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> s >> t;
for(int i = 0; i < n - 1; i++) cin >> b[i];
mtx[n][n] = 1;//构造乘法矩阵
mtx[n - 1][n - 1] = mtx[n - 1][n] = 1;
for(int i = n - 2; i >= 0; i--){
mtx[i][i] = t;
for(int j = i + 1; j <= n; j++){
mtx[i][j] = mtx[i + 1][j] * s % mod;
}
}
int q;
cin >> q;
while(q--){
int x, y;
cin >> x >> y;
cout << pow(y).a[n - x - 1][0] << '\n';
}
return 0;
}
时间复杂度 。
初次推矩阵耗时可能长一些，但熟练之后两三分钟就可以完成了。加油！
有帮助，赞一个