2025 CSP-J

Koei · 2025-11-22 14:23:11 · 个人记录

CSP-J 2025

T1 [CSP-J 2025] 拼数 / number

题意：

在一个字符串中提取出所有数字并任意组合使其组成的数最大

思路：

桶：求出每个数字出现的个数，再从 9 至 0 依次输出数字

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N(1e5+10); 
string s;
int t[10];
int main(){
    cin>>s;
    for(int i(0);i<s.size();i++){
        if(s[i]>='0'&&s[i]<='9'){
            t[s[i]-'0']++;
        }
    }
    for(int i(9);i>=0;i--){
        while(t[i]){
            t[i]--;
            cout<<i;
        }
    }
    cout<<'\n';
    return 0;
}

T2 [CSP-J 2025] 座位 / seat

题意：

按照成绩高低给考生排位置，求第一个输入的人该坐什么位置

思路：

模拟：再排序后找到第一个输入的人是第几大的，枚举到第一个输入的人后结束

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N(1e5+10);
int n,m;
struct node{
    int x,id;
};
node a[N];
bool cmp(node a,node b){
    return a.x>b.x;
}
int main(){
    cin>>n>>m;
    for(int i(1);i<=n*m;i++){
        cin>>a[i].x;
        a[i].id=i;
    }
    sort(a+1,a+n*m+1,cmp);
    int r_id(0);
    for(int i(1);i<=n*m;i++){
        if(a[i].id==1){
            r_id=i;break;
        }
    }
    int x(1),y(0);
    int flag(1),k(0);
    for(int i(1);i<=r_id;i++){
        y+=flag;
        if(y==n+1||(y==0&&i!=1)){
            flag*=-1;
            x++;y+=flag;
        }
    }
    cout<<x<<' '<<y<<'\n';
    return 0;
}

T3 [CSP-J 2025] 异或和 / xor

题意：

在 n 个数中求一段连续的区间的异或和为 k 的区间个数

思路：

异或+前缀和

异或：

由此我们可以发现异或有自逆性，所以可以使用前缀和快速求区间异或和

定义上一个区间的右端点位置为 lst，于是，我们就可以通过枚举右端点r，如果存在一个 l(lst\le l<r) 使得 s_r\oplus k=s_l ，那么就存在区间 (l,r] 符合条件了

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N(5e5+10);
ll n,k;
ll a[N],s[N];
ll id[2005000],lst;
int main(){
    cin>>n>>k;
    for(int i(1);i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]^a[i];
    }
    memset(id,-1,sizeof id);
    id[0]=0;
    ll ans=0;
    for(int r(1);r<=n;r++){
        ll x(s[r]^k);
        if(id[x]>=lst){
            ans++;
            lst=r;
        }
        id[s[r]]=r;
    }
    cout<<ans<<'\n';
    return 0;
}

T4 [CSP-J 2025] 多边形 / polygon

题意：

求用一些小木棍能拼出多边形的方案数

思路：

从使用的木棍长度最大值入手，使用01背包求出有多少种看情况使不使用大于最长木棍也使和大于最长木棍

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N(5e3+10);
const int mod(998244353);
int n,a[N],f[N]={1},ans;
int main(){
    cin>>n;
    for(int i(1);i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i(1);i<=n;i++){
        for(int j(5001);j>a[i];j--){
            (ans+=f[j])%=mod;
        }
        for(int j(5001);j>=5001-a[i];j--){
            (f[5001]+=f[j])%=mod;
        }
        for(int j(5000);j>=a[i];j--){
            (f[j]+=f[j-a[i]])%=mod;
        }
    }
    cout<<ans<<'\n';
    return 0;
}