CSP-J模拟赛(4)补题报告

前言：

          1.三个（three）：100

           2.合体（fit）：10

           3,矩阵（matrix）：0

           4.数对（pair）：0

总结一下，这个成绩对于我来说还是不错的，第二题差一点就A掉了，如果保持的好的话复赛有望一奖（下次加油！）

三个

题意：

现在科学家在培养 A,B,C 三种微生物，这三种微生物每一秒都会繁殖出新的微生物，具体规则为：

A 类微生物每一秒会繁殖出 1 个 A类微生物，1个 B 类微生物，1 个 C 类微生物。
B类微生物每一秒会繁殖出 2 个 A 类微生物，2 个 C 类微生物。
C 类微生物每一秒会繁殖出 1 个 A 类微生物，1 个 B 类微生物。

假设所有的微生物都不会死亡，一开始培养皿中有 A,B,C 三种微生物各 1 个，现在问你 n 秒后 A,B,C 三种微生物分别有奇数个还是偶数个。

考试回顾：

题目简单，一会儿就A了。

题解：

用三个数组计算n秒后微生物的个数（类似于前缀和），再进行奇偶判断。（数据量较大，注意取模）

AC: 

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N],b[N],c[N]; 
int main() {
    //freopen("three.in","r",stdin);
    //freopen("three.out","w",stdout);
    scanf("%d",&n);
    a[0]=1;
    b[0]=1;
    c[0]=1;
    for(int i=1;i<=n;i++){
       a[i]=(a[i-1]*1+b[i-1]*2+c[i-1]*1+a[i-1])%2;
       b[i]=(a[i-1]*1+c[i-1]*1+b[i-1])%2;
       c[i]=(a[i-1]*1+b[i-1]*2+c[i-1])%2;
	}
	if(a[n]%2!=0){
		printf("odd\n");
	}
	else{
		printf("even\n");
	}
	
	if(b[n]%2!=0){
		printf("odd\n");
	}
	else{
		printf("even\n");
	}
	
	if(c[n]%2!=0){
		printf("odd\n");
	}
	else{
		printf("even\n");
	}
		return 0;
}

合体

题意：

现在有 n 个大小范围在 1∼m 中的整数 a​1​​∼a​n​​，并且你获得了一项魔法能力。
施加一次魔法能力后，可以将两个相同的数字合并成一个数字，并且这个数字为原来的数字 +1，例如：

有 2,2 这两个数字，施加一次魔法能力后可以将这两个数字合并成一个数字 3。

现在有 q 次询问，每次询问给你一个整数 x，你可以施加任意次数魔法能力，问你这 n 个整数最多能得到多少个整数 x？

考试回顾：

大部分时间都花到这一道题上了，最后虽然分不高，但是我的代码距离正解就差了一个if（开心~）

题解：

桶标记打标，计算出数组中每一个数能得到的数量的最大值，再根据输入的x进行输出（这样能减少时间复杂度，我就是因为if时超了）

AC: 

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
map<int,int>mp;
int n,m,a,q,x;
int main() {
   //freopen("fit.in","r",stdin);
   //freopen("fit.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++){
   	scanf("%d",&a);
   	mp[a]++;
   }
   	for(int i=2;i<=m;i++){
   			 mp[i]+=mp[i-1]/2;
	   }
	  scanf("%d",&q);
   while(q--){
   	scanf("%d",&x);
    printf("%d\n",mp[x]);
	}
		return 0;
}

矩阵

题意：

现在给你一个 n 行 mm列的矩阵，矩阵上每个格子有一个整数，其中第 i行第 j 列对应的格子上的整数为 gi，j​​。
现在定义该矩阵的一个子矩阵的快乐值为该子矩阵上的所有数字的异或和。

一组数字 a​1​​,a​2​​,...,a​n​​ 的异或和为 a​1​​ xor a​2​​ xor ... xor a​n​​。（其中 xor 表示按位异或运算）

现在问你，该矩阵的所有子矩阵的快乐值之和为多少？

考试回顾：

回顾不了一点~（压维和拆位是我能会的？）

题解：

考虑将二维数组压成一维的；
枚举起始行 i 和终止行 j ，这个范围内的每一列都求异或值 x[k] ；即 x[k] 为 a[i][k] ~ a[j][k] 的异或值。
之后对于x数组，求前缀异或值，然后枚举其左右端点，计算区间异或值。再按位去考虑，对于某个区间，按位异或之后的值，的某一位，是否为1。只需要考虑这个区间内的这一位的1的个数是奇数个还是偶数个。
也可以考虑xo数组 ans += (xo[r] ^ xo[l - 1]); ，按位考虑，某一位如果想被累计到答案里，那么xo[r]的这一位和xo[l-1]的这一位，不相同。所以可以考虑把xo拆位，如果当前这一位是1，那么就考虑它前面这一位是0的情况有多少个，反之同理。

AC: 

#include<bits/stdc++.h>
using namespace std;
const int N=310;
int a[N][N],n,m,b[N];
long long ans=0,sum[N];
int main() {
   //freopen("matrix.in","r",stdin);
   //freopen("matrix.out","w",stdout);
   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]=b[j]^a[d][j];
  				sum[j]=sum[j-1]^b[j];
		  }
		  for(int p=0;p<10;p++){
		     long long 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;
}

数对

题意：

给你一个长度为 n的数列 a1,a2,...,an。
再给你一个长度为 m 的数列 b1,b2,...,bm​​。
现在再再再给你一个正整数 p，让你生成一个长度为 n×m 的数列 c1,c2,...,cn×m。
其中满足 c(i−1)×m+j=(ai+bj) mod p。
现在问你数列 c  中有多少个数对 (i,j) 满足 i<j 且 ci>cj？

考试回顾：

O(n^3)暴力，不得，遂0分（压位高精害人不浅）

题解：

我们观察到 数组是可以分成n 块，每一块有m 个数字。 然后我们求逆序对可以块内求，然后再块与块之间求。
对于块内
观察到值域非常小，我们可以对 b 数组记录数字出现次数num。
枚举到当前数字x，计算逆序数时，可以枚举比x大的数字的出现次数即可。也就是记录 num[b[i]+1]~num[p-1] 的和。
考虑b后续需要变化(+a[j]) 。所有我们记录一个数组nixu[k]。表示为对于b数组所有数组都加k之后，逆序数为多少。
对于块与块
我们可以记录之前所有数字的出现次数，当前块一定是在之前块的后面，所以直接枚举值域，统计逆序数即可。

（想必以上语言有点抽象，看不懂的可以结合AC代码加注释来理解）

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[11],res[11],vis[11];
void write(__int128 x){
	if(x>9) write(x/10);
	putchar(char(x%10+'0'));
}
int main() {
    //freopen("pair.in","r",stdin);
    //freopen("pair.out","w",stdout);
   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;
}