S+CSP2025模拟赛5
A. 逆转
模拟即可
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=3000;
int a,b,ta[N],tb[N];
struct point {
int t;
bool A;
bool operator<(const point &p) const {
return t<p.t;
}
};
vector<point> v;
vector<int> di;
signed main(){
freopen("game.in" ,"r",stdin);
freopen("game.out","w",stdout);
cin>>a;
for (int i=1;i<=a;i++) {
cin>>ta[i];
v.push_back({ta[i],1});
}
cin>>b;
for (int i=1;i<=b;i++) {
cin>>tb[i];
v.push_back({tb[i],0});
}
sort(v.begin(),v.end());
int la=0,lb=0;
for (point p:v) {
if (p.t>24*60) break;
if (p.A) la++;
else lb++;
}
cout<<la+lb<<endl;
la=0;
lb=0;
int sum=0,dis=0;
for (point p:v) {
if (p.A) la++,dis++;
else lb++,dis--;
di.push_back(dis);
}
for (int i=0;i<di.size();i++) {
if (di[i]==1) {
if (di[i+1]==0&&di[i+2]==-1) sum++;
}
else if (di[i]==-1) {
if (di[i+1]==0&&di[i+2]==1) sum++;
}
}
cout<<sum<<endl;
return 0;
}B. 约数计数
容易想出去枚举 $a_i$ 的每个因数，并使用map计数。
分析复杂度，因为 $a_i\le 10^9$ ， 设 $a_i$ 共有 $s_i$ 个因数，则 $s_i\le 2\sqrt{a_i}$。
则总时间复杂度为 $O(n\sqrt{n})$，空间复杂度为 $O(2n+2\sqrt{n})$
#include<bits/stdc++.h>
using namespace std;
#define intc const int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=205;
int n,m,a[N],res[N];
map<int,int> cntmap;
signed main(){
freopen("div.in" ,"r",stdin );
freopen("div.out","w",stdout);
Cios;
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=m;i++){
int x=a[i];
for(int d=1;d*d<=x;d++){
if(x
if(d<=n) cntmap[d]++;
int d2=x/d;
if(d2==d||d2>n) continue;
cntmap[d2]++;
}
}
int tot=cntmap.size();
res[0]=n-tot;
for(auto &kv:cntmap){
int c=kv.second;
if(c<=m) res[c]++;
}
for(int k=0;k<=m;k++) cout<<res[k]<<'\n';
return 0;
}
评论（0）
暂无评论