2022河南财金算法协会新生赛题解

比赛链接：https://ac.nowcoder.com/acm/contest/35213#question

出题小剧场

A. 3509(对于转义字符的考察)

对于特殊字符的输出需要在符号前加 \ 来转义

#include<stdio.h>
#include<math.h>

int main(){
    
	
	printf("(lll￢ω￢) (\\\"ω\\\") wmxNP!!!");
	
	return 0;
}

B. 金牌选手的训练方式(字符串匹配)

#include<stdio.h>
#include<math.h>
#include<string.h>

char s[1000005], t[1000005];

int main(){
    
	
	scanf("%s %s", s, t);
	
	int lens = strlen(s), lent = strlen(t), res = 0;
	
	for(int i = 0; i < lens; i++){
    
		int flag = 1;
		for(int j = 0; j < lent; j++){
    
			if(i+j < lens && s[i+j] == t[j]) continue;
			else flag = 0;
		}
		if(flag) res++;
	}
	
	printf("%d", res);
	
	return 0;
}

C. ACM金牌选手的做题顺序(数组计数)

由题得：把用时短的题面放在前边，再依次统计即可。
对于 1e6 的数据，使用 sort 函数可以不超时实现排序。
但是，这不是考察重点，浅浅的提供一个C语言版的解题思路：

如图所示，现在我们有五个写有编号的球和五个有编号的桶:

把每个小球放到对应编号的桶中：

把小球依次拿出来：

此时，小球就按编号依次排好序了~~

ps：$10^6\ast 10^6=10^{12}>2147483647$

#include<stdio.h>
#include<math.h>
#include<string.h>

int a[1000005], v[1000005];

int main(){
    
	
	int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) v[a[i]]++;
    
    long long res = 0, sum = 0;
    for(int i = 1; i <= 1e6; i++){
    
        while(v[i]){
    
            sum += i;
            res += sum;
            v[i]--;
        }
    }
	
	printf("%lld", res);
	
	return 0;
}

D. 六合数(循环)

循环判断即可。只有一个六合数：548834

#include<stdio.h>
#include<math.h>
#include<string.h>

int main(){
    
	
	for(int i = 1e5; i < 1e6-1; i++){
    
        int num = 0, x = i;
        while(x){
    
            num += pow(x%10, 6);
            x /= 10;
        }
        if(num == i) printf("%d\n", i);
	}

	return 0;
}

E. 倒背圆周率(循环)

细节一：处理负数和前导零。
细节二：2147483647 -> 7463847412
细节三：int 的范围为：-2147483648 ~ 2147483647

展开讲讲细节三，如图(亿点点小细节)

#include<stdio.h>
#include<math.h>
#include<string.h>

int main(){
    
	
	long long m;
    scanf("%lld", &m);
    
    if(m < 0){
    
        m = -m;
        printf("-");
    }
    
    long long res = 0;
    while(m){
    
        res = res * 10 + m % 10;
        m /= 10;
    }
    printf("%lld", res);
	
	return 0;
}

F. 倒背圆周率再续(字符串模拟)

字符串模拟加法。

#include<stdio.h>
#include<math.h>
#include<string.h>

char a[1000005], b[1000005];

int main(){
    
    
    scanf("%s %s", a, b);
    
    int lena = strlen(a), lenb = strlen(b);
    
    for(int i = 0; i < lena/2; i++){
     // 逆转
        char x = a[i];
        a[i] = a[lena-1-i];
        a[lena-1-i] = x;
    }
    for(int i = 0; i < lenb/2; i++){
     // 逆转
        char x = b[i];
        b[i] = b[lenb-1-i];
        b[lenb-1-i] = x;
    }
    
    for(int i = lena; i < lenb; i++) a[i] = '0'; // 补零
    for(int i = lenb; i < lena; i++) b[i] = '0'; // 补零
    
    int len = (lena < lenb ? lenb : lena);
    a[len] = b[len] = '0';
    for(int i = 0; i < len; i++){
    
        int x = a[i] - '0' + b[i] - '0';
        if(x > 9) a[i+1]++, x -= 10; // 进位
        a[i] = x + '0';
    }
    if(a[len] != '0') printf("%c", a[len]); // 判断最高位是否进位
    for(int i = len-1; i >= 0; i--) printf("%c", a[i]);
    
	return 0;
}

G. 所谓的签到题

本场的防AK题。
贪心，分析可得只会重复购买一种奶茶。
枚举购买那些奶茶，再处理亿点点细节。

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1000010;

ll sum[N],a[N],b[N],c[N];


void Test() {
    
	ll n,m;
	ll res=0;
	cin>>m>>n;
	for(int i=1; i<=n; i++) cin>>a[i]>>b[i];
	for(int i=1; i<=n; i++) c[i]=a[i];
	sort(c+1,c+1+n);
	
	for(int i=1; i<=n; i++) sum[i]=sum[i-1]+c[i];
	c[n+1]=0x3f3f3f3f;
	
	for(int i=1; i<=n; i++) {
    
		int x=lower_bound(c+1,c+2+n,b[i])-c;
		if(x==n+1){
    
			res=max(res,a[i]+(m-1)*b[i]);
			continue;
		}
		if(n-x+1>=m) {
    
			res=max(res,sum[n]-sum[n-m]);
			continue;
		}
		ll num=x;
		ll tmp=sum[n]-sum[num-1];
		
		int ans=m-(n-num+1);
		if(a[i]<b[i]) tmp+=a[i],ans--;
		if(ans<0) continue; 
		tmp+=b[i]*ans;
		res=max(tmp,res);
	}
	cout<<res<<"\n";
}

int main() {
    
	ios::sync_with_stdio(false);

	int t;
	cin>>t;
	while(t--)
		Test();
    
    return 0;
}

H. Wsc的魔盒(数学题)

对于有缘人最初的选择：无上智慧的概率为 $\frac{1}{3}$ ，无尽财富的概率为 $\frac{2}{3}$。
根据规则，

• 如果有缘人第一次选择到无尽财富，改变选择一定会选到无上智慧。
• 如果有缘人第一次选择到无上智慧，改变选择一定会选到无尽财富。
• 综上，有缘人改变选择后，得到无上智慧的概率为 $\frac{2}{3}$ ，无尽财富的概率为 $\frac{1}{3}$。

ps：要注意浮点误差和四舍五入。

#include<stdio.h>
#include<math.h>
#include<string.h>

void f(char x, int y){
    
    while(y--) printf("%c", x);
}

int main(){
    
    
    f('0', 1);  f('.', 1);  f('3', 20);  f('\n', 1);  
    f('0', 1);  f('.', 1);  f('6', 19);  f('7', 1);  
    
	return 0;
}