CSP2025模拟赛5

用户头像 发布于 2025-08-19 81 次阅读 OI

S+CSP2025模拟赛5

A. 逆转

按时间模拟即可，
懒得一个一个加分数，所以把连续的得分合并了一下，
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
struct node{
	int t,id;
}f[N];
int a,b,x,idx;
int s1,s2,ans1,ans2;
vector<node> v;
bool cmp(node x,node y){return x.t<y.t;}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	cin>>a;
	while(a--){
		cin>>x,v.push_back({x,1});
		if(x<=1440) ans1++;
	} 
	cin>>b;
	while(b--){
		cin>>x,v.push_back({x,2});
		if(x<=1440) ans1++;
	}
	sort(v.begin(),v.end(),cmp);
	for(int i=0;i<v.size();i++){
		int cnt=1;
		while(v[i+1].id==v[i].id) i++,cnt++;
		f[++idx]={cnt,v[i].id};
	}
	for(int i=1;i<=idx;i++){
		if(f[i].id==1){
			if(s1<s2&&s1+f[i].t>s2) ans2++;
			s1+=f[i].t;
		}
		if(f[i].id==2){
			if(s1>s2&&s1<s2+f[i].t) ans2++;
			s2+=f[i].t;
		}
	}
	cout<<ans1<<endl<<ans2;
	return 0;
}
C++

B. 约数计数

观察到 $m$ 比较小，考虑对数组进行操作。
可以先用map存下每个因数出现了多少次，
再按次数统计因数的个数即可，
最后直接输出答案。
（$0$ 的情况就是 $n$ 减去所有范围内的因数的种类数）
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,cnt;
int a[N],ans[N];
unordered_map<int,int> m1;
void f(int x){
	for(int i=1;i*i<=x;i++) if(x%i==0&&i<=n){
		if(i!=x/i) m1[i]++,m1[x/i]++;
		else m1[i]++;
	}
}
int main(){
	freopen("div.in","r",stdin);
	freopen("div.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		f(a[i]);
	}
	for(auto u:m1){
		int x=u.first,y=u.second;
        if(x>=1&&x<=n&&y<=m){
            ans[y]++;
            cnt++;
        }
	}
    cout<<n-cnt<<endl;
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
	return 0;
}
C++

C. 集合查找

对于操作一，我们统计每个因数的倍数，方便在操作二中找gcd。
而对于操作二，我们贪心的从二进制最高位到最低位二分查找亦或后某一位是 $1$ 的方案是否可行，
统计答案输出即可。
代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
set<int> v[N];
int q;
main() {
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    cin>>q;
    while(q--) {
        int t;
        cin>>t;
        if(t==1) {
            int u;
            cin>>u;
            for(int i=1;i*i<=u;i++){
                if (u%i==0) {
                    v[i].insert(u);
                    if(i!=u/i) v[u/i].insert(u);
                }
            }
        }
        else{
            int x,k,s;
            cin>>x>>k>>s;
            s-=x;
            if(x%k||s<0){
                cout<<"-1\n";
                continue;
            }
            bool y=1;
            int ans=0;
            for(int i=(!s?0:log2(s));i>=0;i--){
                if(!y) break;
                auto it=v[k].lower_bound(ans+(1<<i));
                bool f1=(it!=v[k].end()&&*it<=min(s,ans+(1<<(i+1))-1));
                bool f2=(it!=v[k].begin()&&*prev(it)>=ans);
                if(!f1&&!f2){
                    cout<<"-1\n";
                    y=0;
                } 
                else if(f1&&!f2) ans+=(1<<i);
                else if(f1&&f2&&!((x>>i)&1)) ans+=(1<<i);
            }
            if(y) cout<<ans<<"\n";
        }
    }
    return 0;
}
C++