2021-11-07 【第八届算法大赛部分题解】

7-1 选举

让我们解决第一个候选人的问题，为了赢得选举，他需要比其他候选人至少多获得1张选票。因此，第一个候选人至少需要获得 $m a x (b, c) + 1$ 票。如果 $a$ 已经大于这个值，那么你不需要添加任何投票，否则你需要添加 $m a x (b, c) + 1 - a$ 票。所以第一个候选的答案是 $m a x (0, m a x (b, c) + 1 - a)$ 。

类似地，第二个候选人的答案是 $m a x (0, m a x (a, c) + 1 - b)$ ，第三个候选人的答案是 $m a x (0, m a x (a, b) + 1 - c)$ 。

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

int solveSingle(int best, int other1, int other2){
   
	return max(0, max(other1, other2) + 1 - best);
}

int main(){
   
	int t;
	cin >> t;
	while (t--){
   
		int a, b, c;
		cin >> a >> b >> c;
		cout<<solveSingle(a, b, c)<<' '<<solveSingle(b, a, c) <<' '<<solveSingle(c, a, b) << '\n';
	}
	return 0;
}

7-3 Dividing candy

由于侄子清空了他所选择的盒子 $i$ ，并希望使其他 $n - 1$ 个盒子相等，那么这意味着至少所有数组a的总和应该被 $(n - 1)$ 整除，而且其他每个盒子里的块数应该至少是 $⌈\frac{sum}{n-1}⌉$ （上限函数）。

另一方面，由于侄子选择了 $i$ ，那么他可以选择一个不是最大值的盒子，而且由于他使唯一的盒子 $i$ 为空，那么其他每个盒子中的最终数量应该至少是最大值。

总的来说，所产生的 $n - 1$ 个其他盒子中的每个块的数量应该至少是 $k=max(⌈\frac{sum}{n-1}⌉,max)$ ，我们需要在初始数组中添加至少 $(n - 1) \cdot k - s u m$ 元素。

#include <bits/stdc++.h>
using namespace std;
 
int a[100000+5];
int n;
long long sum, ans;
 
void solve(){
   
    cin>>n;
    for(int i = 0; i < n; i++){
   
        cin>>a[i];
    }
    if(n == 2){
   
    	cout<<"0\n";
    	return;
    }
    int mx = *max_element(a, a + n);
    sum = 0;
    for(int i = 0; i < n; i++){
   
        sum += (mx - a[i]);
    }
    sum -= mx;//本身被分了
    if(sum == 0) ans = 0;		//0
    else if(sum > 0) ans = sum;	//需要补齐的糖果数
    else{
   
        sum = abs(sum);			//可以给其他的n-1堆分配
        sum %= (n - 1);			//取余
        if(sum){
   				//未分配完
        	ans = n - 1 - sum;	//sum余数可以分配，ans为sum分配完剩下的个数
        }
        else{
   
        	ans = 0;
        }
    }
    cout<<ans<<endl;
}
int main(){
   
    int TC;
    cin>>TC;
    while(TC--){
   
        solve();
    }
    return 0;
}

7-9 Strings

在这个问题中，您可以迭代每种类型的操作删除了多少个字符。如果从字符串 $s$ 中删除了开头的 $l$ 个字符和结尾的 $x$ 个字符，则子字符串 $s [l + 1 ， n - x]$ 保留，其中 $n$ 是字符串 $s$ 的长度。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
   
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    int ans = 0;
    for (int len = 1; len <= min(n, m); len++) {
   
        for (int i = 0; i + len <= n; i++) {
   
            for (int j = 0; j + len <= m; j++) {
   
                if (a.substr(i, len) == b.substr(j, len)) {
   
                    ans = max(ans, len);
                }
            }
        }
    }
    cout << a.size() + b.size() - 2 * ans << "\n";
}

int main() {
   
    int n;
    cin >> n;
    while (n--) {
   
        solve();
    }
    return 0;
}