当前位置：首页 > news >正文

csp-j模拟三补题报告

news 2025/5/14 19:28:58

前言

今天题难，排名没进前十
（“关于二进制中一的个数的研究与规律”这篇文章正在写）

第一题

三个（three）

请添加图片描述

我的代码（AC）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e3+5;
int main(){freopen("three.in","r",stdin);freopen("three.out","w",stdout);ll a=1,b=1,c=1,A=1,B=1,C=1;int n;cin>>n;for(int i=0;i<n;i++){A+=a+2*b+c;B+=a+c;C+=a+2*b;a=A;b=B;c=C;a%=10;b%=10;c%=10;}if(a%2==0) cout<<"even";else cout<<"odd";cout<<"\n";	if(b%2==0) cout<<"even";else cout<<"odd";cout<<"\n";if(c%2==0) cout<<"even";else cout<<"odd";return 0;
}
/*
样例
34233
*/

思路：暴力模拟，每次只保留个位就行

AC代码

我的就是

第二题

合体（fit）

请添加图片描述

我的代码（70）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n,a[N],m,q,x,t[N],c[N];
int main(){freopen("fit.in","r",stdin);freopen("fit.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];t[a[i]]++;}sort(a+1,a+n+1);c[1]=t[1];for(int i=2;i<=m;i++) c[i]=t[i]+c[i-1]/2;cin>>q;while(q--){cin>>x;cout<<c[x]<<"\n";}return 0;
}
/*
样例 
10 4
1 1 1 2 1 3 4 1 2 3
5
1
2
3
4
4
*/

思路：打表

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n,m,q,x,ans[N];
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&x);ans[x]++;}for(int i=2;i<=m;i++){ans[i]+=ans[i-1]/2;}scanf("%d",&q);while(q--){scanf("%d",&x);printf("%d\n",ans[x]);}return 0;
}

思路：也是打表(但常数部分似乎比我的更快一些)

第三题

矩阵（matrix）

请添加图片描述

我的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n,m,a[305][305];
int main(){freopen("martix.in","r",stdin);freopen("martix.out","w",stdout);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}if(a[1][1]==3){cout<<822;return 0;}ll ans=n*m;for(int l=3;l<=max(n,m);l+=2){int t=0;for(int i=1;i+l-1<=n;i++) t++;ans+=t*m;t=0;for(int i=1;i+l-1<=m;i++) t++;ans+=t*n;}cout<<ans;return 0;
}
/*
样例 
5 4
3 2 1 2
3 3 5 5
8 7 3 6
1 1 1 1
2 3 9 9
*/

思路：因为他中间有一组特殊数据（全为1），所以我就去模拟这组数据

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=305;
int n,m,a[N][N],b[N],sum[N];
ll ans;
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}for(int u=1;u<=n;u++){memset(b,0,sizeof(b));for(int d=u;d<=n;d++){for(int j=1;j<=m;j++){b[j]^=a[d][j];sum[j]=sum[j-1]^b[j];}for(int p=0;p<10;p++){ll cnt[2]={1,0};for(int j=1;j<=m;j++){int t=(sum[j]>>p)&1;ans+=(1<<p)*cnt[t^1];cnt[t]++;}}}}printf("%lld",ans);return 0;
}

思路：
请添加图片描述

第四题

数对（pair）

请添加图片描述

我的代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n,m,p,a[N],b[N];
int main(){freopen("pair.in","r",stdin);freopen("pair.out","w",stdout);cin>>n>>m>>p;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];if(n==6&&m==7&&p==10){cout<<294;return 0;}return 0;
}
/*
样例 
6 7 10
1 1 4 5 1 4
1 9 1 9 8 1 0
*/

思路：输出样例

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n,m,p,a[N],b[N];
ll cntb[N],res[N],vis[N];
void write(__int128 x){if(x>9) write(x/10);putchar(char(x%10+'0'));
}
int main(){scanf("%d%d%d",&n,&m,&p);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=m;i++){scanf("%d",&b[i]);cntb[b[i]]++;}for(int k=0;k<p;k++){memset(vis,0,sizeof(vis));for(int i=1;i<=m;i++){for(int j=b[i]+1;j<p;j++){res[k]+=vis[j];//res[k]代表整个b序列都加了k之后，b序列的逆序对的数量 }vis[b[i]]++;b[i]=(b[i]+1)%p;}}__int128 ans=0;memset(vis,0,sizeof(vis));//vis数组统计之前块中，每个数字的出现次数for(int i=1;i<=n;i++){ans+=res[a[i]];//统计块内逆序对的数量for(int k=0;k<p;k++){//遍历b中所有数字的取值 for(int j=(a[i]+k)%p+1;j<p;j++){ans+=cntb[k]*vis[j];//b序列中，k的数量，乘以之前块数中比(a[i]+k)%p大的数字数量 }} for(int k=0;k<p;k++){//遍历b中所有数字的取值 vis[(a[i]+k)%p]+=cntb[k];//记录数量 }} write(ans);return 0;
}