非官方题解|挑战赛 #26 全题解
2025-12-29 20:08:59
发布于：广东
80阅读
0回复
0点赞
水
已完成今日后面忘了挑战赛#26难度红橙橙橙橙橙大学习。
T1
把一个 double 数用 int() 括起来相当于向下取整，据此如果 n>=int(n+0.5) 就是该向下取整，反之向上取整。
当然也可以使用 round 函数。
#include<bits/stdc++.h>
using namespace std;
int main(){
double n;
cin>>n;
if(n>=int(n+0.5)) cout<<int(n);
else cout<<int(n)+1;
}
时间复杂度：。
T2
贪心，如果这个数 升序排序后的 显然可以，反之不行。实现方式多样。
#include<bits/stdc++.h>
using namespace std;
int a[100009],b[100009];
bool cmp(int x,int y){return x>y;}
int main(){
int n,k;
cin>>n>>k;
for(int i = 1;i<=n;++i){
int x,y,z;
cin>>x>>y>>z;
a[i]+=x;a[i]+=y;a[i]+=z;b[i] = a[i];
}
sort(a+1,a+n+1,cmp);
for(int i = 1;i<=n;++i){
if(b[i]+300>=a[k]) cout<<"Yes\n";
else cout<<"No\n";
}
}
时间复杂度：
T3
看到这种需要不停合并/分离连通块，单个连通块内有前后顺序的问题就要想到链表！
具体的，维护 分别表示当前 的前车和尾车。操作 就是 来做，操作 一直往前跑到这个连通块的头部，然后往后跑即可。
#include<bits/stdc++.h>
using namespace std;
int n,q;
int l[100009],r[1000009];
int find(int x){return l[x]?find(l[x]):x;}
int main(){
cin>>n>>q;
while(q--){
int opt;
cin>>opt;
if(opt == 1){
int x,y;
cin>>x>>y;
l[y] = x;
r[x] = y;
}else if(opt == 2){
int x,y;
cin>>x>>y;
l[y] = r[x] = 0;
}else{
int x;
cin>>x;
int fx = find(x);
vector<int> ans;
for(int i = fx;i;i = r[i]) ans.push_back(i);
cout<<ans.size()<<" ";
for(int i = 0;i<ans.size();++i) cout<<ans[i]<<" ";
cout<<'\n';
}
}
}
时间复杂度：平均 。
T4
全场非语法题最水，二分板子。
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[200009];
int main(){
cin>>n>>q;
for(int i = 1;i<=n;++i){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i = 1;i<=q;++i){
int x;
cin>>x;
int p = lower_bound(a+1,a+n+1,x)-a;
cout<<n-p+1<<'\n';
}
}
时间复杂度：
T5
问题本质是在有向无环图（DAG）中，从目标技能 出发，找出所有必须的前置技能。
所以栈反向搜就可以了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,ans;
int t[200009];
vector<int> a[200009];
bool vis[200009];
stack<int> s;
signed main(){
cin>>n;
for(int i = 1,l,x;i<=n;++i){
cin>>t[i]>>l;
for(int j = 1;j<=l;++j){
cin>>x;
a[i].push_back(x);
}
}
s.push(n);
while(s.size()){
int p = s.top();s.pop();
if(vis[p]) continue;
ans+=t[p];
vis[p] = 1;
for(auto v:a[p])
if(!vis[v]) s.push(v);
}
cout<<ans;
}
时间复杂度：
T6
如果跑广搜的话还要回来求每个格子，感觉不如 。
转移易得。但要注意这个点满足能走、他上面或者左边能到达才能转移。
还有要特判起点为 # 以及和 的情况。
算上这么多细节，容易吃罚时。
#include<bits/stdc++.h>
using namespace std;
int n,m,ans = 1;
char mp[109][109];
int dp[109][109];
int main(){
cin>>n>>m;
memset(mp,'#',sizeof mp);
for(int i = 1;i<=n;++i){
for(int j = 1;j<=m;++j){
cin>>mp[i][j];
}
}
if(mp[1][1] == '#'){cout<<0;return 0;}
dp[1][1] = 1;
for(int i = 1;i<=n;++i){
for(int j = 1;j<=m;++j){
if(i == 1&&j == 1) continue;
if(mp[i][j] == '#') continue;
if(dp[i-1][j]||dp[i][j-1]) dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
ans = max(ans,dp[i][j]);
}
}
cout<<ans;
}
时间复杂度：
有帮助，赞一个