比赛传送门

做出来五道题。

A. AB Balance

{% note info no-icon problem %}

给你一个只含有 a 和 b 的字符串，问怎样通过修改尽可能少的字符，使得 ab 的数量和 ba 的数量相等。

{% endnote %}

显然，ab 的数量和 ba 的数量最多差 \(1\)，而当开头字母和结尾字母相同时，ab 的数量等于 ba 的数量。如果不同，修改开头或结尾字母使它们相同即可。

B. Update Files

{% note info no-icon problem %}

有 \(n\) 个电脑和 \(k\) 个数据线，其中一个电脑上有一个文件，每次可以通过数据线将文件从一个电脑传到另一个电脑上，耗时 \(1\) 小时。问至少需要几个小时才能让所有电脑都有文件。

{% endnote %}

设当前有 \(x\) 个电脑有文件：若 \(x<=k\)，则通过 \(x\) 条数据线将 \(x\) 翻倍；若 \(x>k\)，则通过 \(k\) 条数据线将 \(x+=k\)。暴力跑第一种情况（\(\log(k)\)），剩下的情况算一下就行了。

C. Banknotes

{% note info no-icon problem %}

有 \(n\) 中不同面值的货币，每种货币的面值为 \(10^{a_i}\)，问至少需要 \(x+1\) 个货币才能组成的价值最小的货币是多少。

{% endnote %}

暴力贪心模拟。先尽可能多地用面值最小的货币，再用面值第二小的货币，以此类推。具体实现细节比较多，在这里放个代码。

{% note success code %}

#include <bits/stdc++.h>
using namespace std;
int n,k,a[10];
int main() {
	int t;
	cin>>t;
	while(t--) {
		cin>>n>>k;
		k++;
		for(int i=0;i<n;i++) {
			cin>>a[i];
			int cur=1;
			while(x--)
				cur*=10;
			a[i]=cur;
		}
		long long res=0;
		for(int i=0;i<n;i++) {
			int cnt=k;
			if(i<=n)
				cnt=min(cnt,a[i+1]/a[i]-1);
			res+=1ll*a[i]*cnt;
			k-=cnt;
		}
		cout<<res<<endl;
	}
}

{% endnote %}

D. Red-Blue Matrix

{% note info no-icon problem %}

有一个 \(n\times m\) 的矩阵，每个格子有一个正整数，你需要对每一行染成红色或蓝色，使得能够找到竖线，让左边所有红格子都大于所有蓝格子的值，右边相反。输出染色方案以及竖线位置。

\(\sum n\times m\le 10^6\)

{% endnote %}

假设我们已经知道了竖线的位置，如何分配红蓝呢？考虑以行为单位，以每一行的第一个元素为关键字进行从大到小的排序，则我们发现，一定是上面几行为红色，下面几行为蓝色，而这个两条分界线，一横一竖，左上、右上为红，左下、右下为蓝，则必须满足左上的最小值大于左下的最大值，右上的最大值小于右下的最小值。我们可以对矩阵分别求从左上、右下开始的前缀最小值和从左下、右上开始的前缀最大值。枚举横、竖线，然后就可以 \(O(1)\) 判断了。总复杂度为 \(O(n\times m)\)。

E. Arena

待更新......