姓名：王胤皓，校区：和谐校区，考试时间：$2024$ 年 $10$ 月 $4$ 日 $9:00:00$~$12:30:00$，学号：$S07738$

请关注作者的 B 站，谢谢~链接

CSP-J Day $4$ 模拟赛补题报告

前言

考了我们班 Rank $1$。

分数

T1 three: $Accepeted100$
T2 fit: $Accepeted100$
T3 matrix: $TLE20$
T4 pair: $TLE20$

T1

题面

思路

打标找规律。

赛时 $Accepeted$ 代码

#include<bits/stdc++.h>
using namespace std;
int main(){freopen("three.in","r",stdin);freopen("three.out","w",stdout);int n;cin>>n;n%=3;if(n==0){printf("odd\nodd\nodd\n");}else if(n==1){printf("odd\nodd\neven\n");}else{printf("even\neven\nodd\n");}return 0;
}

T2

题面

思路

开桶数组，然后利用递推，预处理。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,tong[1000005],q,x;
int main(){freopen("fit.in","r",stdin);freopen("fit.out","w",stdout);cin.tie(0);ios::sync_with_stdio(false);cin>>n>>m;for(int i=1; i<=n; i++){int x;cin>>x;tong[x]++;}for(int i=1; i<=m; i++) tong[i]+=tong[i-1]/2;cin>>q;while(q--){cin>>x;cout<<tong[x]<<"\n";}return 0;
}

T3

题面

思路

枚举完起始行和终止行之后，还需要去计算结果，这一部分可以考虑优化。
可以按位去考虑，对于某个区间，按位异或之后的值，的某一位，是否为 $1$。只需要考虑这个区间内的这一位的 $1$ 的个数是奇数个还是偶数个。
也可以考虑 $xor$ 数组 $ans+(xo{r}_r\oplus xo{r}_{l-1})$ ，按位考虑，某一位如果想被累计到答案里，那么 $xo{r}_r$ 的这一位和 $xo{r}_{l-1}$ 的这一位，不相同。所以可以考虑把 $xor$ 拆位，如果当前这一位是 $1$，那么就考虑它前面这一位是 $0$ 的情况有多少个，反之同理。

代码

#include<bits/stdc++.h>
using namespace std;
int b[305][305],c[305],sum[305];
int main(){cin.tie(0);ios::sync_with_stdio(false);int n,m;cin>>n>>m; long long cnt=0ll;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){cin>>b[i][j];}}long long ans=0;for(int u=1; u<=n; u++){memset(c,0,sizeof c);memset(sum,0,sizeof sum);for(int d=u;d<=n; d++){for(int j=1; j<=m; j++){c[j]^=b[d][j];sum[j]=c[j]^sum[j-1];}for(int p=0;p<10;p++){int 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]++;}    }}}cout<<ans<<"\n";return 0;
}

T4

题面

思路

具体看代码中的注释

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000005],b[1000005],cntb[15];
__int128 res[15],vis[15],cnt;
void print(__int128 ans){if(ans==0) return;print(ans/10);putchar(ans%10+'0');
}
int main(){cin.tie(0);ios::sync_with_stdio(false);int n,m,p;cin>>n>>m>>p;for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i<=m; i++) cin>>b[i],cntb[b[i]]++;if(p==1){cout<<0<<"\n";return 0;}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-1; j++){res[k]+=vis[j];//$res_k$ 表示 $b$ 数组加上 $k$ 后，逆序对的数量}vis[b[i]]++;b[i]=(b[i]+1)%p;}}memset(vis,0,sizeof vis);//$vis$ 数组统计之前块中，每个数的出现次数for(int i=1; i<=n; i++){cnt+=res[a[i]];//统计块内逆序对的数量for(int k=0;k<p;k++){//遍历 $b$ 中所有数字的取值for(int j=(a[i]+k)%p+1; j<p;j++){cnt+=cntb[k]*vis[j];//$b$ 序列中，$k$ 的数量，乘以之前块中比 $(a_i+k)\bmod p$ 大的数字个数}}for(int k=0;k<p;k++){//遍历 $b$ 中所有数字的取值vis[(a[i]+k)%p]+=cntb[k];//记录数量。}}print(cnt);return 0;
}

请关注作者的 B 站，谢谢~链接