CZSC 2023 第二次 题解

T1 乘积

10pts

很多人10分都没有拿到，这是不应该的。有一个部分分是x=0，这意味着两两相乘有几种情况最终答案就是多少。所以我们只需要输出 $n*(n-1)/2$ 即可得到10分

100pts

每次枚举两个数，计算出两个数的乘积，满足条件的话最后答案就+1

解法一

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int arr[10004];
int main(){
	int n,x,ans=0;
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>arr[i];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){//注意，第二层的循环要从i+1开始。这样可以保证不重复
			int s=arr[i]*arr[j];
			int t=0;//末尾有几个零
          //下面的代码是常见的把数字每一位都分割出来的操作
			while(s){//这句话的意思是，如果s不为0的话就继续分割
              //s%10可以把最后一位数字取出来，s/=10可以把最后一位数字删除
				if(s%10==0) t++,s/=10;
				else break;
			}
			if(t>=x) ans++;
		}
	}
	cout<<ans;
	return 0;
}

解法二

这个解法是赛时很多同学想到的。思路是判断乘积能否被 $10^x$ 整除。这里给出袁浩宇同学的赛时代码：

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<cmath>
using namespace std;
int a[10010];

int main(void){
	int n,x,ans = 0,c,d,e;
	cin>>n>>x;
	d=pow(10,x);
	for(int m = 0;m<n;m++){
		cin>>a[m];
	}
	for(int i = 0;i<n;i++){
		for(int j = i + 1;j<n;j++){
			c = a[i] * a[j];
			e = c%d;
		
			if(e == 0){
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

T2 命题

n和m都要取100，这样才能尽可能消耗时间。

对于Code1和Code2，我们不难发现，如果给出的数据是从大到小排序的若干个数字，那么最后消耗的时间会很长。

对于Code3，我们可以进行100次从1到100的染色过程。

对于Code5，我们可以让100个操作都是给[100,100]涂色。这样代码最后枚举从1到99这些格子的时候，都会把这100个操作给过一遍，增加了消耗的时间。

对于Code4，我们构造形如给[1,1]涂色、再给[1,2]涂色、再给[1,3]涂色...，这样的数据。这样代码设置的跳跃点并没有跳过很多的格子，换句话说，设置的跳跃点基本上是废掉了，因为到后面的操作，程序会从1，根据跳跃点跳到2，根据2的跳跃点再跳到3...

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;

int main(){
	int t;cin>>t;
	if(t==1||t==2){
		cout<<100<<endl;
		for(int i=100;i>=1;i--){
			cout<<i<<' ';
		} 
	}
	if(t==3){
		cout<<100<<' '<<100<<endl;
		for(int i=1;i<=100;i++){
			cout<<"1 100 1"<<endl;
		} 
	}
	if(t==4){
		cout<<100<<' '<<100<<endl;
		for(int i=1;i<=100;i++){
			cout<<"1 "<<i<<" 1"<<endl;
		} 
	}
	if(t==5){
		cout<<100<<' '<<100<<endl;
		for(int i=1;i<=100;i++){
			cout<<"100 100 1"<<endl;
		} 
	}
	return 0;
}

T3 报数

根据第一题的解法一一样的思路，对每个数字进行拆分。对于一个不能被报出的数组，我们枚举这个数字的倍数。用数组记录下来那些数字是不能被报出来的。

下面是吴海同同学的赛时代码

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
bool a[10001000];//记录一个数能否被报出，0为可以报出，1为不能被报出
bool x(int i){//判断一个数是否含有7。返回0为存在，1为不存在
	while(i){
		if(i%10==7){
			return 0;
		}
		i/=10;
	}
	return 1;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<10001000;i++){//先对10001000以内的数字全部进行判断
		if(a[i]==0 && x(i)==0){//如果枚举到的数字含有7，且没有被标记过
			a[i]=1;//进行标记
			for(int j=1;i*j<=10001000;j++){//枚举倍数，其倍数也标记上
				a[i*j]=1;
			}
		}
	}
  //然后从n+1开始，逐个判断
	for(int i=n+1;i<10001000;i++){
		if(a[i]==0){
			cout<<i;
			return 0;
		}
	}
	return 0;
}

T4 数组

首先有个性质，对于一个数组，无论这个数组的数字有多少个，只有最小值和次小值是有用的。因为只有最小值才影响最后的答案，如果把最小值移走了，那么次小值影响最后答案。而且一个数组只能移走数字一次。

还有一个性质，对于所有数组出现的所有的数字中最小的那个，无论这个数字有没有被移动，或者移动到了哪里，最后的答案一定会算上这个最小的数字。我们记这个最小的数字为 $minn$。

假设 $minn$ 在数组 $i$ 中，那么最优的方案就是，除了数组 $i$ 以外的所有数组，都把它的最小值移动到数组 $i$ 中。这样他们的次小值就会被暴露出来，对答案产生贡献。而由于数组 $i$ 中有 $minn$，所以有数字移进来之后，不会对答案产生影响。

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#define int long long
using namespace std;

int arr[2][1003],n;

signed main(){
	cin>>n;
	int minn=10004;//最小值，因为题目中所有数字小于 10 的三次方，所以我们初始值设为比 10 的的三次方大的数字
	for(int i=1;i<=n;i++){
		int m;
		cin>>m;
		int x1=10004,x2=10004;//x1为当前数组的最小值，x2为次小值 
		for(int j=1;j<=m;j++){
			int x;
			cin>>x; 
			if(x<=x1) x2=x1,x1=x;
			else if(x<=x2) x2=x;
			if(x<minn) minn=x;
		}
      //arr[0][]里面存的是最小值，1里面存的是次小值
		arr[0][i]=x1;
		arr[1][i]=x2;
	}
	int sum=0;
	for(int i=1;i<=n;i++) sum+=arr[1][i];
	//sum为所有数组的次小值的加和 
	int ans=0; 
	for(int i=1;i<=n;i++){//枚举minn出现在那个数组中，找出一个最大情况
		ans=max(ans,sum-arr[1][i]+minn);//如果出现在i数组中，那么i数组对答案的贡献是minn，而不是arr[1][i]
	}
	cout<<ans; 
	return 0;
}