昨晚原题大赛A-D题解
2025-12-07 09:14:44
发布于：广东
14阅读
0回复
0点赞
A
题目大意：给出正整数 ，求 。
由于 很小，可以直接解。显然也有 解
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
int sum = 0;
for(int i = 1;i<=n;++i) sum+=i;
cout<<sum;
}
时间复杂度：
B
模拟即可，由于我想少写一点加了前缀和
#include<bits/stdc++.h>
using namespace std;
int n,ans;
int s[59],a[59];
int main(){
cin>>n;
for(int i = 1;i<=n;++i){
cin>>a[i];
s[i] = s[i-1]+a[i];
}
for(int l = 1;l<=n;++l){
for(int r = l;r<=n;++r){
bool flag = 0;
for(int i = l;i<=r;++i){
if((s[r]-s[l-1])%a[i] == 0) flag = 1;
}
if(!flag) ans++;
}
}
cout<<ans;
}
时间复杂度：
C
注意到第 个骨牌在数轴上第 个位置，也就是说最右边的骨牌也仅仅在 的位置，所以我们可以定义 表示当前能达到的最右的位置。而只有 有骨牌，所以枚举最多做到 ，每次 。答案即为
#include<bits/stdc++.h>
using namespace std;
int n,r;
int a[500009];
int main(){
cin>>n;
for(int i = 1;i<=n;++i){
cin>>a[i];
}
r = 1;
for(int i = 1;i<=min(n,r);++i){
r = max(r,i+a[i]-1);
}
cout<<min(n,r);
}
时间复杂度：
D
D最水的一级，C好歹还让我想了一会。
直接反图，对于每个操作 BFS记录答案，操作二直接 查询。
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int> g[300009];
bool vis[300009];
bool ans[300009];
int main(){
cin>>n>>m;
for(int i = 1;i<=m;++i){
int x,y;
cin>>x>>y;
g[y].push_back(x);
}
cin>>q;
while(q--){
int opt,v;
cin>>opt>>v;
if(opt == 1){
vis[v] = 1;
queue<int> q;
q.push(v);
while(q.size()){
int u = q.front();
q.pop();
if(ans[u]) continue;
ans[u] = 1;
for(auto p:g[u]){
if(!ans[p]) q.push(p);
}
}
}else{
if(ans[v]) cout<<"Yes\n";
else cout<<"No\n";
}
}
}
时间复杂度：（或者 ）
有帮助，赞一个