520 钻石争霸赛 2022 题解

--------------------------------------------------------------------------------
更多详见>>

OJ题解系列 目录导航帖
--------------------------------------------------------------------------------

这里是 520 钻石争霸赛 2022 题解
该比赛会在每年的5月20日举办，比赛时间60分钟，一共8道题，分值为5 10 10 15 15 20 20 25，总体难度不大，与入门级难度相当，考察编程的速度能力
接下来是题解部分
--------------------------------------------------------------------------------

算法标签: 输入/输出
注意点: 输出格式

#include
using namespace std;

int main(){
	int N;
	cin >> N;
	printf("%d! 520!",N);
	
	return 0;
} 

算法标签: if…else…语句
注意点: 输出格式

#include
using namespace std;

int main(){
	int N,M,K;
	cin >> N >> M >> K;
	if(M == N*K){
		printf("zheng hao mei ren %d!",K);
	}else if(M > N*K){
		printf("hai sheng %d!",M-N*K);
	}else{
		printf("hai cha %d!",N*K-M);
	}
	
	return 0;
} 

算法标签: 循环
注意点: 按顺序输出

#include
using namespace std;

int main(){
	int sex;
	int a,b,c,d;
	cin >> sex >> a >> b >> c >> d;
	int N;
	cin >> N;
	sex = 1-sex;
	for(int i=1;i<=N;i++){
		int s,age,h;
		cin >> s >> age >> h;
		if(sex == s && age>=a && age<=b && h>=c && h<=d){
			printf("%d %d %dn",s,age,h);
		}
	}
	
	return 0;
} 

算法标签: 枚举
注意点: 根据题意上的等式： 3 n = 1 x + 1 y + 1 z frac{3}{n}=frac{1}{x}+frac{1}{y}+frac{1}{z} n3​=x1​+y1​+z1​
移项变形得： 3 ∗ x ∗ y ∗ z = n ∗ ( x ∗ y + y ∗ z + z ∗ x ) 3*x*y*z=n*(x*y+y*z+z*x) 3∗x∗y∗z=n∗(x∗y+y∗z+z∗x)
由于 n n n已知，因此，只需要枚举 x , y , z x,y,z x,y,z即可求出最小解，枚举的顺序应为 x − > y − > z x->y->z x−>y−>z
注意 x , y , z x,y,z x,y,z均为奇数，且满足 0 < x < y < z ≤ m 0 最后记得输出无解的情况No solution

#include
using namespace std;
typedef long long LL;
int main(){
	int n,m;
	cin >> n >> m;
	bool f = false;
	for(int x=1;x<=m;x+=2){
		for(int y=x+2;y<=m;y+=2){
			for(int z=y+2;z<=m;z+=2){
				LL ans1 = 3LL*x*y*z;
				LL ans2 = 1LL*n*(y*z+z*x+x*y);
				if(ans1 == ans2){
					cout << x << " " << y << " " << z << endl;
					f = true;
					break; 
				}
			}
			if(f){
				break;
			}
		}
		if(f){
			break;
		}
	}
	if(!f){
		printf("No solution in (%d, %d].",3,m);
	}
	return 0;
} 

算法标签: 字符串 + 哈希
注意点: 按字符串的方式读入 A A A和 B B B，先去除所有的前导 0，然后用哈希数组hashT1统计0-9的个数，作为基准
接着读入需要判断的数据 A ′ , B ′ A',B' A′,B′，先去除前导0，再统计0-9出现的个数，保存至hashT2，比较两个数组，相同输出Yes，不同输出No

#include
using namespace std;
int hashT1[15];
int hashT2[15];

int main(){
	string s1,s2;
	cin >> s1 >> s2;
	int len1 = s1.size();
	int len2 = s2.size();
	bool f1 = false;
	bool f2 = false;
	for(int i=0;i
		if(f1 == false && s1[i] == '0'){
			continue;
		}else{
			f1 = true;
			hashT1[s1[i]-'0']++;
		}
	}
	for(int i=0;i
		if(f2 == false && s2[i] == '0'){
			continue;
		}else{
			f2 = true;
			hashT1[s2[i]-'0']++;
		}
	}
	while(1){
		memset(hashT2,0,sizeof(hashT2));
		cin >> s1 >> s2;
		len1 = s1.size();
		len2 = s2.size();
		if(len1 == 1 && len2 == 1 && s1[0] == '0' && s2[0] == '0'){
			break;
		}
		f1 = false;
		f2 = false;
		for(int i=0;i
			if(f1 == false && s1[i] == '0'){
				continue;
			}else{
				f1 = true;
				hashT2[s1[i]-'0']++;
			}
		}
		for(int i=0;i
			if(f2 == false && s2[i] == '0'){
				continue;
			}else{
				f2 = true;
				hashT2[s2[i]-'0']++;
			}
		}
		bool f = false;
		for(int i=0;i<=9;i++){
			if(hashT1[i] == hashT2[i]){
				continue;
			}else{
				f = true;
				break;
			}
		}
		if(f){
			printf("Non");
		}else{
			printf("Yesn");
		}
	}
	return 0;
} 

算法标签: 模拟
注意点: 按题意，先确定 R R R， R = ⌊ N e ⌋ R=lfloor frac{N}{e} rfloor R=⌊eN​⌋，然后统计 1 − R 1-R 1−R中的最大值，保存记录为a[num1]，然后遍历 R + 1 − N R+1-N R+1−N，按顺序找到大于等于a[num1]的第一个数，记录为输出的第一个编号，若找不到，该编号为0，接着遍历 1 − N 1-N 1−N找到最大数，记录其为输出的第二个编号，最后输出结果

#include
using namespace std;
double E = 2.718;
const int maxn = 1e4+5;
int a[maxn];

int main(){
	int N;
	cin >> N;
	for(int i=1;i<=N;i++){
		cin >> a[i];
	}
	double res = 1.0*N/E;
	int T = (int)(res);
	int site = -1;
	int num1 = -1;
	int maxm = -1;
	for(int i=1;i<=T;i++){
		if(a[i]>maxm){
			maxm = a[i];
			num1 = i;
		}
	} 
	int num2 = -1;
	maxm = a[num1];
	for(int i=T+1;i<=N;i++){
		if(a[i]>=maxm){
			maxm = a[i];
			num2 = i;
			break;
		}
	}
	int num3 = -1;
	maxm = -1;
	for(int i=1;i<=N;i++){
		if(a[i]>maxm){
			maxm = a[i];
			num3 = i;
 		}
	}	
	if(num2 == -1){
		cout << "0 " << num3 << endl;
	}else{
		
		cout << num2 << " " << num3 << endl;
	}
	return 0;
} 

算法标签: 二维数组
注意点: 先确定指定行/列的 m i n ( a b s ( a [ x ] [ y ] − A ) ) min(abs(a[x][y]-A)) min(abs(a[x][y]−A))，其中 A A A为开奖号码，然后按照先行后列的顺序输出所有满足上述等式的坐标

#include
using namespace std;
const int maxn = 1e3+5;
int a[maxn][maxn];
int main(){
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> a[i][j];
		}
	}
	int r,c;
	cin >> r >> c;
	int res;
	cin >> res;
	int maxm = 1e7;
	for(int i=1;i<=m;i++){
		if(a[r][i]!=-1 && abs(a[r][i]-res)
			maxm = abs(a[r][i]-res);
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i][c]!=-1 && abs(a[i][c]-res)
			maxm = abs(a[i][c]-res);
		}
	}
	for(int i=1;i<=m;i++){
		if(a[r][i]!=-1 && abs(a[r][i]-res) == maxm){
			printf("(%d:%d)n",r,i);
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i][c]!=-1 && i!=r && abs(a[i][c]-res) == maxm){
			printf("(%d:%d)n",i,c);
		}
	}
	return 0;
} 

算法标签: 哈希
注意点: 我们将数列分成两部分， ≥ 0 , < 0 ≥0,<0 ≥0,<0
（1）先统计 ≥ 0 ≥0 ≥0的部分，遍历输入数据，凡是遇到 ≥ 0 ≥0 ≥0的数，哈希桶对应位置+1
（2）接着处理哈希桶内的数据，按照从大到小的顺序枚举哈希桶，每枚举一个数t，就将t/5加入521序列中，并将t/5,t,t/5*2三个位置桶上的数-1
（3）如此循环，直至整个哈希桶为空，那么就得到了 ≥ 0 ≥0 ≥0的521序列
同理，可按照此操作步骤得到 < 0 <0 <0的521序列，最后直接输出即可（已满足非递增）

#include
using namespace std;
const int maxn = 5e5+5;
int a[maxn];
int hashT1[maxn];
int hashT2[maxn];
int ans[maxn];
int cnt = 0;

int main(){
	int N;
	cin >> N;
	for(int i=1;i<=N;i++){
		cin >> a[i];
	}
	int maxm1 = -1;
	for(int i=1;i<=N;i++){
		if(a[i]>=0){
			hashT1[a[i]]++;
			maxm1 = max(maxm1,a[i]);
		}
	}
	for(int j=maxm1;j>=0;){
		if(hashT1[j]){
			int t = j;
			t /= 5;
			ans[cnt++] = t;
			hashT1[t]--;
			t*=2;
			hashT1[t]--;
			hashT1[j]--;
		}else{
			j--;
		}
	}

	int maxm2 = -1;
	for(int i=1;i<=N;i++){
		if(a[i]<0){
			hashT2[abs(a[i])]++;
			maxm2 = max(maxm2,abs(a[i]));
		}
	}
	for(int j=0;j<=maxm2;){
		if(hashT2[j]){
			int t = j;
			ans[cnt++] = -t;
			t*=5;
			hashT2[t]--;
			t/=5;
			t*=2;
			hashT2[t]--;
			hashT2[j]--;
		}else{
			j++;
		}
	}

	for(int i=0;i
		if(i==0){
			printf("%d",ans[i]);
		}else{
			printf(" %d",ans[i]);
		}
	}
	return 0;
} 

最后，祝大家520快乐，AC每一天