补题报告4

Picecone-zzs / 2024-10-05 / 原文

背景

CSP-J模拟赛
考得最好的一次

得分

$T1$: $AC$
$T2$: $AC$
$T3$: $0$
$T4$: $20$
总分: $220$

致敬传奇$180$分以上就请吃饭的🐟老师

$T1$ 三个 ($Three$)

赛时$AC$

概述

$A,B,C$三种微生物，他们会繁殖,在每分钟：
每个 $A$ 可繁殖出一个$A$,一个$B$,一个$C$
每个 $B$ 可繁殖出两个$A$,两个$C$
每个 $C$ 可繁殖出一个$A$,一个$B$
注：三种繁殖同时进行
每种微生物现各有1个，求$n$秒后，$A$，$B$，$C$ 三种微生物数量的奇偶？

思路

奇偶？正常来讲，应输出数量，输出奇偶可能是有规律可循
先打个小表：

输出

i    a b c
1  : 5 3 4
2  : 20 12 15
3  : 79 47 59
4  : 311 185 232
5  : 1224 728 913
6  : 4817 2865 3593 
7  : 18957 11275 14140
8  : 74604 44372 55647
9  : 293599 174623 218995
10 : 1155439 687217 861840
11 : 4547152 2704496 3391713
12 : 17895009 10643361 13347857
13 : 70424597 41886227 52529588
14 : 277151236 164840412 206726639
15 : 1090709935 648718287 813558699

哇！有规律(狂喜
观察可得：
当$i=2,5,8,11,14……$时，$A$为偶数，否则为奇数
当$i=2,5,8,11,14……$时，$B$为偶数，否则为奇数
当$i=1,4,7,10,13……$时，$C$为偶数，否则为奇数

所以

若 $n\%3 == 2 $ ，$A$和$C$为偶数
否则为偶数

若 $n\%3 == 1 $ ，$B$为偶数
否则为偶数

$O(1)$做法出炉：

代码

Code

#include <cstdio>
using namespace std;
int n;
int main(){
	scanf("%d",&n);
	if(n % 3 == 2)  
            printf("even\neven\n");
	else
            printf("odd\nodd\n");
	if(n % 3 == 1) 
            printf("even");
	else
            printf("odd");
	return 0;
}

$T2$ 合体（$fit$）

赛时$AC$!!!!!!!!!!!!!!!!!!

概述

有一些整数：$a_1$ ~ $a_n$ ,它们范围在1~ $m$
你有魔法,可将2个一样的合成，变成1个原数+1
例：$2,2$ $\implies$ $3$
现有$q$次询问，每次给定一个$x$，问施完魔法后(可无限次使用~~太强了~~),最多能得到几个$x$？

思路

输入，用桶存储各数个数
输入$x$
合成
输出

Emmm……,一开始，我代码执行的顺序是 $1 \to 3 \to 2 \to 4$
做完，又想后输入$x$，结果合成的数很大，而$x$不需要那么大，不就浪费了时间？
~~纯属想多了~~
所以，我又改进了代码，运行顺序就变成了$1 \to 2 \to 3 \to 4$
还有还有，昨天老师说，数据过大要用 $scanf$ 和 $printf$ ,记着了，今天全用的它俩，今天这题不用 $TLE$ $70$ 分，用了$AC$

代码

最正确的一集

Code

#include <cstdio>
using namespace std;
const int maxn = 1e6+1111;
bool flag=1;
int n,m,q;
int maxx;//要求输出的数的最大值
int a[maxn];
//cnt[]存转换前个数
int cnt[maxn];//n,m最大都是1e6，maxn=maxm
int x[maxn];
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; ++i) {
		scanf("%d",&a[i]);
		++cnt[a[i]];
	}
	scanf("%d",&q);
	for(int i=1; i<=q; ++i) {
		scanf("%d",&x[i]);
		maxx = max(maxx,x[i]);
	} 
	//转换
	for(int i=2; i<=maxx; ++i) 
		cnt[i] += cnt[i-1]/2;
		
	for(int i=1;i<=q;++i){
		printf("%d",cnt[x[i]]);
		if(q) printf("\n");
	}
	return 0;
}

$T3$ 矩阵（$matrix$）

赛时全 WA (

概述

给定一个矩阵，定义一个矩阵的快乐值为该矩阵中所有数字的异或和，求该矩阵的所有子矩阵的快乐值之和是多少？

赛时思路

四重循环，枚举该矩阵的左上顶点与右下顶点
写完了
写炸了

难评

#include <cstdio>
using namespace std;
const int maxn = 310;
int n,m;
int a[maxn][maxn];
long long sum[maxn][maxn];
long long 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]);
			sum[i][j] = a[i][j];
			if(i!=1) sum[i][j] ^= sum[i-1][j];
			if(j!=1) sum[i][j] ^= sum[i][j-1];
			if(i!=1&&j!=1) sum[i][j] ^= sum[i-1][j-1];
		}
	}
	sum[1][1] = 0;
	for(int a=1; a<=n; ++a) {
		for(int b=1; b<=m; ++b) {
			for(int c=a+1; c<=n; ++c) {
				for(int d=b+1; d<=m; ++d) {
					long long h = sum[c][d];
					if(b != 1) h ^= sum[c][b-1];
					if(a != 1) h ^= sum[a-1][d];
					if(a != 1 && b != 1) h ^= sum[a-1][b-1];
					ans += h;
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;


}

歪解(bushi

考虑将二维数组压成一维的；
枚举起始行 i 和终止行 j ，这个范围内的每一列都求异或值 x[k] ；即 x[k] 为 a[i][k] ~ a[j][k] 的异或值。
之后再对于x数组，求前缀异或值，然后枚举其左右端点，计算区间异或值即可。
时间复杂度$O(n^4)$,能拿个20分(原因在于最后统计)

20分

#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=305;
int n, m, a[maxn][maxn], x[maxn], xo[maxn];
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		//枚举起始行
		memset(x, 0,sizeof(x));
		for (int j = i; j <= n; j++) {
			//枚举终止行
			for (int k = 1; k <= m; k++) {
				x[k] ^= a[j][k];
				// i到j行压成一行
				xo[k] = xo[k - 1] ^ x[k]; //求前缀异或值
			}
			for (int l = 1; l <= m; l++)
				for (int r = l; r <= m; r++) //枚举区间
					ans += (xo[r] ^ xo[l - 1]); //计算区间异或
		}
	}
	cout << ans << endl;
	return 0;
}

优化

对于上述代码，枚举完起始行和终止行之后，还需要$O(m^2)$去计算结果，这一部分可以考虑优化。

可以按位去考虑，对于某个区间，按位异或之后的值，的某一位，是否为1。只需要考虑这个区间内的这一位的1的个数是奇数个还是偶数个。

也可以考虑$xo$数组 ans += (xo[r] ^ xo[l - 1]); ，按位考虑，某一位如果想被累计到答案里，那么$xo[r]$的这一位和$xo[l-1]的这一位$不相同。

所以可以考虑把$xo$拆位，如果当前这一位是$1$，那么就考虑它前面这一位是$0$的情况有多少个，反之同理。

正确的

int n, m, a[N][N], x[N], xo[N];
int main() {
	freopen("matrix.in", "r", stdin);
	freopen("matrix.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		//枚举起始行
		mem(x, 0);
		for (int j = i; j <= n; j++) {
			//枚举终止行
			for (int k = 1; k <= m; k++) {
				x[k] ^= a[j][k];
				xo[k] = xo[k - 1] ^ x[k];
			}//求前缀异或值
			for (int p = 0; p < 10; p++) {
				//按位枚举
				int cnt0 = 1; //记录第p位为0的个数
				int cnt1 = 0; //记录第p位为1的个数
				for (int k = 1; k <= m; k++) {
					if (xo[k] & (1 << p)) {
						//如果当前数字，第p位是1，那么要考虑前面有多少0
						ans += 1ll * (1 << p) * cnt0;
						cnt1++;
					} else {
						//如果当前数字，第p位是0，那么要考虑前面有多少1
						ans += 1ll * (1 << p) * cnt1;
						cnt0++;
					}
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

$T4$ 数对（$pair$)

赛时20

概述

给$a_1,……a_n$
给$b_1,……b_m$，
再给一正整数$p$，要求生成$c_1,……,c_{m \times n }$
且满足$c_{i-1 \times m + j} = (a_i + b_j) $ $mod$ $p$
求$c$中逆序对

思路

暴力求解
喜得20

暴力

#include <cstdio>
using namespace std;
const int maxn = 1e3+1111;
int a[maxn];
int b[maxn];
long long c[maxn*maxn];
int n,m,p;
long long cnt;
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]);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			c[(i-1) * m + j] = (a[i] + b[j]) % p;
		}
	}
	for(int i=1;i<=n*m;++i){
		for(int j=i+1;j<=n*m;++j){
			if(c[i] > c[j]) 
				++cnt;
		}
	}
	printf("%lld",cnt);
	return 0;
}

正解

可将$c$数组拆成$n$,每块有$m$个
再用逆序对在块内求，块间求

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

30分long long

int n, m, p, a[M], b[M];
ll num[10], numb[10], nixu[10]; // nixu[i]表示b数组+i之后的逆序数。
int main() {
	freopen("pair.in", "r", stdin);
	freopen("pair.out", "w", stdout);
	CLOSE
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
		numb[b[i]]++;
	}
	for (int j = 0; j < p; j++) {
		mem(num, 0);
		for (int i = 1; i <= m; i++) {
			for (int k = b[i] + 1; k < p; k++)
				nixu[j] += num[k];
			num[b[i]]++;
			b[i] = (b[i] + 1) % p;
		}
	}
	mem(num, 0);
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += nixu[a[i]];
		for (int j = 0; j < p; j++) {
			int x = (j + a[i]) % p;
			for (int k = x + 1; k < p; k++)
				ans += 1ll * numb[j] * num[k];
		}
		for (int j = 0; j < p; j++)
			num[(j + a[i]) % p] += numb[j];
	}
	cout << ans << endl;
	return 0;
}

优化后的

参考代码(仅供参考)

int n, m, p, a[M], b[M];
ll num[10], numb[10], nixu[10]; // nixu[i]表示b数组+i之后的逆序数。ll ans[200], cnt = 0;void jia(ll k)
{
	ans[0] += k;
	int pos = 0;
	while (true) {
		if (ans[pos] >= 1000000) {
			ans[pos + 1] += ans[pos] / 1000000;
			ans[pos] %= 1000000;
			if (++pos > cnt)cnt++;
		} else
			break;
	}
}
int main() {
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++)cin >> a[i];
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
		numb[b[i]]++;
	}
	for (int j = 0; j < p; j++) {
		mem(num, 0);
		for (int i = 1; i <= m; i++) {
			for (int k = b[i] + 1; k < p; k++)nixu[j] += num[k];
			num[b[i]]++;
			b[i] = (b[i] + 1) % p;
		}
	}
	mem(num, 0);
	for (int i = 1; i <= n; i++) {
		// ans += nixu[a[i]];
		jia(nixu[a[i]]);//优化32行加法 
		for (int j = 0; j < p; j++) {
			int x = (j + a[i]) % p;
			for (int k = x + 1; k < p; k++)
				jia(1ll * numb[j] * num[k]);//优化38行加法 
				// ans += 1ll * numb[j] * num[k];
		}
		for (int j = 0; j < p; j++)
			num[(j + a[i]) % p] += numb[j];
	}
	cout<<ans[cnt];//最前面一定不用补0，单独输出 
	for (int i = cnt-1; i >= 0; i--)
		printf("%06lld",ans[i]);//有可能要补0 
		// cout << ans[i];
	return 0;
}

官方题解