SMU Summer 2023 Contest Round 15

A. AB Balance

其实就只会更改一次

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
    	string s;
    	cin >> s;
    	int ba = 0, ab = 0;
    	int n = s.size();
    	for(int i = 0;i < n - 1;i ++){
    		if(s.substr(i,2) == "ab") ab ++;
    		else if(s.substr(i,2) == "ba") ba++;
    	}

    	if(ab == ba){
    		cout << s << '\n';
    	}else{
    		if(ba > ab){
    			s[0] = 'a';
    			cout << s << '\n';
    		}else{
    			s.back() = 'a';
    			cout << s << '\n';
    		}
    	}
    }

    return 0;
}

B. Update Files

模拟第一个样例\(1,2,4,7,8...\),其实前面就是\(1 \sim 2^{k-1}\),后面多出来的去除以\(k\)向上取整就可以了

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
    	int n,k;
    	cin >> n >> k ;    	
    	int ans = 0,m = 1;
    	while(m < k && m < n){
    		m *= 2;
    		ans ++;
    	}
        
    	cout << ans + (max(0ll, n - m) + k - 1) / k << '\n';
    }

    return 0;
}

C. Banknotes

如果小的凑不成,大的肯定也凑不成,所以我们要从小去枚举,枚举当前能进位的纸币数小于\(k\)张,否则的话就加上\(k+1\)张就行了.

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
    	int n,k;
    	cin >> n >> k;
    	vector<int> a(n);
    	for(auto &i : a) cin >> i;

    	vector<int> b(n);
    	for(int i = 0;i < n - 1;i ++){
    		b[i] = (int)pow(10,a[i + 1] - a[i]) - 1;
    	}

    	b[n - 1] = 1e10;
    	int ans = 0;
    	for(int i = 0;i < n;i ++){
    		if(b[i] > k){
    			ans += (k + 1) * (int)pow(10,a[i]);
    			break;
    		}else{
    			ans += b[i] * (int)pow(10,a[i]);
    			k -= b[i];
    		}
    	}

    	cout << ans << '\n';

    }

    return 0;
}