题解
国庆集训DAY3 题解
刘渊 LV11 玄仙 LV 4 @ 2024-10-4 15:20:56

国庆集训DAY3

T1

考试分数：0分（未提交）

正确思路

拆分成两个子问题。

减法

要想凑出最大的值，那么需要用数组里最大的值减去一个尽可能小的负数。拿样例举例，先凑一个最小的负数，需要用 1 去减一个较大的值，又需要留出最大值，所以负数为 $1-(2+3+4)=-8$ 。用最大值 $5$ 去减，得到 $5-(-8)=13$ 。

简化公式（样例）：

$$\begin{align*} &\quad\,\,5-[1-(2+3+4)]\\ &=5-(1-2-3-4)\\ &=5-1+2+3+4\\ &=5-1+2+2+3+4-2\\ &=5+1+2+3+4-2\\ &=1+2+3+4+5-1\times2 \end{align*}$$

最终，式子被简化为了 $\text{sum}(a)-\min(a)\times2$ ，其中， $\text{sum}(a)$ 为 $a$ 数组的总和， $\min(a)$ 表示 $a$ 中的最小值。

求余

根据余数的定理（和判断样例惊奇的巧合）可以发现：答案为 $a$ 里面最小的值。

注意：代码写到这里只有 90 分！有一个坑！ $n=1,a_1=1$ 的情况减法算出来是负数！！！

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	freopen("divmod.in", "r", stdin);    // freopen别忘了
	freopen("divmod.out", "w", stdout);
	int n, k;
	cin >> n >> k;
	
	if (n == 1) {      // 坑
		int x;
		cin >> x;
		cout << x;
		return 0;
	}
	
	long long sum = 0;         // 不开longlong见祖宗  10^5 * 10^6 = 10^11 > 2147483647
	int _min = 0x7fffffff;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		sum += x;            // 求和
		_min = min(_min, x); // 求最小
	}
	
	if (k == 1) cout << sum - 2*_min;
	else cout << _min;
	return 0;
}

T2

未完待续……

欧阳龙钰 LV11 玄仙 LV 4 @ 2024-10-4 15:49:49

T1

大意：

两种操作方式：

1：把n个数进行n-1次减法，要使得数最大

2：把n个数进行n-1次求余，要使得数最大

思路：

**k=1时，发现答案为：总和-最小值*2**

k=2时，发现答案为：最小值

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,k,ans=INT_MAX;
long long sum=0;
int main(){
	freopen("divmod.in","r",stdin);
	freopen("divmod.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		long long x;
		cin>>x;
		ans=min(x,ans);
		sum+=x;
	}
	sum-=2*ans;
	if(k==1) cout<<abs(sum);
	else cout<<ans;
	return 0;
}
//🈲抄袭
//🈲抄袭//🈲抄袭
//🈲抄袭//🈲抄袭//🈲抄袭
//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭
//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭
//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭

T2

大意：

把一个字符串改成回文字符串，且字典码最小

思路：

可以先找不同，再进行更改，如果本来就是回文字符串，就找最边上且不是a的字符，给他改成a

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("hw.in","r",stdin);
	freopen("hw.out","w",stdout);
	string s;
	cin>>s;
	int ans=0,x=-1,y=-1;
	for (int i=s.size()-1;i>=s.size()/2;i--){
		if(s[i]==s[s.size()-1-i]) continue;
		ans++;
		if(ans==1){
			x=s.size()-1-i;
		}else if(ans==2){
			y=s.size()-1-i;
		}
	}
	if(ans==2){
		char a=min(s[x],s[s.size()-1-x]);
		char b=min(s[y],s[s.size()-1-y]);
		s[x]=s[s.size()-1-x]=a;
		s[y]=s[s.size()-1-y]=b;
	}else if(ans==1){
		char a=min(s[x],s[s.size()-1-x]);
		s[x]=s[s.size()-1-x]='a';
		if(a=='a' && s.size()%2==1){
			s[s.size()/2]='a';
		}
	}else if(ans==0){
		for(int i=0;i<s.size();i++){
			if (s[i]!='a'){
				s[i]=s[s.size()-1-i]='a';
				break; 
			}
		}
	}
	cout<<s;
	return 0;
}
//🈲抄袭
//🈲抄袭//🈲抄袭
//🈲抄袭//🈲抄袭//🈲抄袭
//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭
//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭
//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭//🈲抄袭

刘渊 LV11 玄仙 LV 4 @ 2024-10-4 16:00:54

龙钰，快点告诉我你的洛谷号是什么？（或者告诉我你不知道洛谷是啥）

李睿泽 LV 7 @ 2024-10-4 15:45:26

emmm..................