这场比赛不是CF的周赛，但因为自我感觉做的还不错，做出来5题！于是写下此文，以示纪念
A： AB Balance
题意如下，进行最少次数的修改，使得一个只包含'a'和'b'的字符串中，"ab"和“ba”出现的次数相同，其中每次修改指将一位的a替换成b或者将b替换成a，输出修改后的字符串。
签到题，只要判断第一个和最后一个字符是否相同，如果相同，直接输出该字符串，如果不同，进行一次替换，输出该字符串。
一串a或者一串b如果没有出现在两端，那么他们会各自提供一个“ab”和一个“ba”，如果出现在两端，比如开头是a，那么它只会提供一个"ab"，出现在结尾，会提供一个"ba"，所以只要考虑开头和结尾的字符就可以了。
点击查看代码
#include<string>
#include<iostream>
using namespace std;
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
string s;
cin >> s;
if (s[0] != s[s.length() - 1]) {
s[s.length() - 1] = s[0];
}
cout << s << endl;
}
} B：Update Files
题意如下，有一台机器有资料，我们可以花一个小时将从有资料的机器上将资料传输到另一个机器，一个有资料的机器只能同时给一台机器传输，且同时传输的机器数目有上限，给出机器数目n和同时传输的机器数目的上限k，求最少需要花费多少小时使得所有机器都有资料，其中初始仅仅只有1台机器有资料。(表达能力匮乏，可以看原题)
我们记录当前有资料的机器个数为x，可以把这个过程看成两段，第一段是倍增阶段，x<=k的时候，这时传输资料受到x的限制，第二阶段是平稳阶段，x>k，这时传输资料受到k的限制。
于是我们就要计算倍增阶段和平稳阶段花费（如果有的话）的时间，这个很容易得出。
#include<iostream>
using namespace std;
int main() {
int t;
cin >> t;
here:for (; t > 0; t--) {
long long n, k;
cin >> n >> k;
int hour = 0;
long long num = 1;
if (n == 1) {
cout << 0 << endl;
continue;
}
while (num <= k) {
num *= 2;
hour++;
if (num >= n) {
cout << hour << endl;
t--;
goto here;
}
}
n -= num;
cout << hour + (n + k - 1) / k<<endl;
}
} C：Banknotes
题目就不翻译了，有点儿麻烦...
题目既然要找到至少要用k+1张纸币表示的最小数值，那么就贪心一点，用k+1张尽可能小的纸币去表示这个值。
那么什么样的情况，满足用不能用更少的纸币表示呢？很容易想到，因为题目中的纸币都是10的幂，所以用10^ak+1/10^ak-1及以下个第k个纸币时，一定不能用更高面额的纸币代替。而最高面额的纸币则没有这样的限制，如果用的纸币数量小于k+1,那么多出来的数目都可以放最高面额的纸币。
于是代码如下:
#include<iostream>
#include<vector>
using namespace std;
int main() {
int T;
cin >> T;
for (; T > 0; T--) {
long long n, k;
cin >> n >> k;
k++;
vector<long long>arr(n,1);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
while (a) {
a--;
arr[i] *= 10;
}
}
long long res = 0;
for (int i = 0; i < n-1; i++) {
if (k >= arr[i+1]/arr[i]-1) {
k -= arr[i + 1] / arr[i] - 1;
res += arr[i + 1] - arr[i];
}
else {
res += k * arr[i];
k = 0;
}
}
if (k) {
res += k * arr[n - 1];
}
cout << res << endl;
}
} D Red-Blue Matrix
这一题很有意思，因为乍一看很难想到如何处理，因为红蓝色分配会有2^n种可能，而分割线也有m-1种可能，如果暴力破解一定会失败
但是有一个很重要的特质，第一列一定在分割线的左边，且如果存在分割线，那么它的位置一定是唯一的。
第一条性质是显然的
由此，我们可以得到
Lemma 4.1: 第一列中最小元素所在行一定为蓝色，最大元素所在行一定为红色。
反证法，假设最小元素所在行为红色，那么一定有一行是蓝色，在分割线左边，蓝色那一行的元素不小于最小元素，与题干矛盾，所以得证。最大元素为红色同理。
Theorem 4.2: 如果存在合理的解，那么分割线的位置是唯一的。
借助Lemma 4.1 我们可以确定一个蓝色行以及一个红色行，如果满足题目中的两个限制，那么对于已经确定颜色的这两行的要求就是，split左边的部分，蓝色行中元素小于对应红色行中元素，split右边部分蓝色行中元素大于对应红色行中元素。
又因为不等关系具有反对称性，因此分割线的位置一定是唯一的。
因此在这里借助Lemma 4.1和Th 4.2，我们可以判断某些矩阵是无法进行合理的涂色和分割的
这些矩阵包括
1.对于所有列，都有蓝色行元素小于红色行元素的
2.存在某一列，蓝色行元素等于红色行元素
3.对于某一列，蓝色行元素大于红色行元素，且存在它后面的某一列，蓝色行元素小于红色行元素。
因此我们可以进行初步判断，一些不合理的矩阵
int n, m;
cin >> n >> m;
vector<vector<int>>mat(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
}
}
int minpl = 0, maxpl = 0;
for (int i = 0; i < n; i++) {
if (mat[i][0] < mat[minpl][0]) {
minpl = i;
}
if (mat[i][0] > mat[maxpl][0]) {
maxpl = i;
}
}
//找到一对点，minpl一行一定是蓝，maxpl一定是红。
//开始判断split的位置
bool check = 0;
int split = m-1;
for (int j = 1; j < m; j++) {
if (mat[minpl][j] == mat[maxpl][j]) {
//情况二，存在一列使得蓝色行和红色行元素相同
cout <<"NO" << endl;
T--;
goto here;
}
else if (mat[minpl][j] < mat[maxpl][j]) {
if (check) {
//情况三，在之前有一列出现蓝色行元素大于红色行元素之后，该列蓝色行元素小于红色行元素。
cout << "NO" << endl;
T--;
goto here;
}
}
else {
if (!check) {
check = 1;
split = j;
}
}
}
if (!check) {
//情况一，所有列的蓝色行元素都小于红色行元素
cout << "NO" << endl;
T--;
goto here;
} 在得到split的位置之后，下一步是判断哪些行为蓝色，哪些行为红色
Lemma 4.3 如果在split之前，有元素小于split左边蓝色行元素的最小值，那么该元素所在行一定是蓝色，如果大于左边红色行元素的最大值，那么该元素所在行一定是红色。
Proof： 类似于Lemma 4.1的证明，利用反证法即可。
Lemma 4.4 在split之后，如果有元素大于split右边蓝色行元素的最大值，那么该元素所在行一定是蓝色，如果小于右边红色行元素的最小值，那么该元素所在行一定是红色。
Proof：略过。
在有了Lemma 4.3,4.4之后，我们可以进一步对矩阵进行涂色，通过不断将某一行涂色，然后更新蓝色行元素的最小（大）值，以及红色行元素的最大（小）值，直到无法继续，如果存在合理涂色的方法，那么这样涂色一定是正确的。
但也存在一些不合理的涂色，因此我们仅仅只对同一行元素进行一次涂色，就算它同时满足Lemma 4.3的前后两个性质。我们最后根据蓝色行元素和红色行元素的相对大小判断涂色是否合理。
这里我的代码的顺序有一点点问题，但是影响不大，就是在遍历的时候，应该先按照行遍历，如果遇到涂色行，跳过，我这里先按照列遍历，则需要额外执行很多次continue.
vector<int>color(n, -1);
color[minpl] = 0;
color[maxpl] = 1;
int bluel = mat[minpl][0];
int bluer = mat[minpl][m - 1];
int redl = mat[maxpl][0];
int redr = mat[maxpl][m - 1];
for (int i = 0; i < split; i++) {
bluel = max(bluel, mat[minpl][i]);
redl = min(mat[maxpl][i], redl);
}
for (int i = split; i < m; i++) {
bluer = min(bluer, mat[minpl][i]);
redr = max(mat[maxpl][i], redr);
}
while (1) {
bool isadd = 0;
for (int i = 0; i < split; i++) {
for (int j = 0; j < n; j++) {
if (color[j] != -1) {
continue;
}
if (mat[j][i] <= bluel) {
isadd = 1;
color[j] = 0;
for (int k = 0; k < split; k++) {
bluel = max(mat[j][k], bluel);
}
for (int k = split; k < m; k++) {
bluer = min(mat[j][k], bluer);
}
}
else if (mat[j][i] >= redl) {
isadd = 1;
color[j] = 1;
for (int k = 0; k < split; k++) {
redl = min(mat[j][k], redl);
}
for (int k = split; k < m; k++) {
redr = max(mat[j][k], redr);
}
}
}
}
for (int i = split; i < m; i++) {
for (int j = 0; j < n; j++) {
if (color[j] != -1) {
continue;
}
if (mat[j][i] >= bluer) {
isadd = 1;
color[j] = 0;
for (int k = 0; k < split; k++) {
bluel = max(mat[j][k], bluel);
}
for (int k = split; k < m; k++) {
bluer = min(mat[j][k], bluer);
}
}
else if (mat[j][i] <= redr) {
isadd = 1;
color[j] = 1;
for (int k = 0; k < split; k++) {
redl = min(mat[j][k], redl);
}
for (int k = split; k < m; k++) {
redr = max(mat[j][k], redr);
}
}
}
}
if (!isadd) {
break;
}
} 最后，如果存在一些没有涂色的行，那么统一把它们涂色为红色或者蓝色均可，证明略。
加上一段判断涂色结果是否合理的代码
if (bluel >= redl || bluer <= redr) {
cout << "NO" << endl;
T--;
goto here;
}
cout << "YES" << endl;
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
cout << "B";
}
else {
cout << "R";
}
}
cout << " " << split << endl; 完整代码如下
完整代码
#include<vector>
#include<iostream>
using namespace std;
int main() {
int T;
cin >> T;
here:for (; T > 0; T--) {
int n, m;
cin >> n >> m;
vector<vector<int>>mat(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
}
}
int minpl = 0, maxpl = 0;
for (int i = 0; i < n; i++) {
if (mat[i][0] < mat[minpl][0]) {
minpl = i;
}
if (mat[i][0] > mat[maxpl][0]) {
maxpl = i;
}
}
//找到一对点，minpl一行一定是蓝，maxpl一定是红。
//开始判断split的位置
bool check = 0;
int split = m - 1;
for (int j = 1; j < m; j++) {
if (mat[minpl][j] == mat[maxpl][j]) {
cout << "NO" << endl;
T--;
goto here;
}
else if (mat[minpl][j] < mat[maxpl][j]) {
if (check) {
cout << "NO" << endl;
T--;
goto here;
}
}
else {
if (!check) {
check = 1;
split = j;
}
}
}
if (!check) {
cout << "NO" << endl;
T--;
goto here;
}
//接下来划分红蓝
//首先能确定的是，在split左边的点，val<=蓝色点的最大值的点一定是蓝色，val>=红色点的最小值的点一定是红色。
//其次能确定的是，在split右边的点，val>=蓝色点的最大值的点一定是蓝色，val<=红色点最小值的点一定是红色。
//对于剩余点，全部划分为红色。
vector<int>color(n, -1);
color[minpl] = 0;
color[maxpl] = 1;
int bluel = mat[minpl][0];
int bluer = mat[minpl][m - 1];
int redl = mat[maxpl][0];
int redr = mat[maxpl][m - 1];
for (int i = 0; i < split; i++) {
bluel = max(bluel, mat[minpl][i]);
redl = min(mat[maxpl][i], redl);
}
for (int i = split; i < m; i++) {
bluer = min(bluer, mat[minpl][i]);
redr = max(mat[maxpl][i], redr);
}
while (1) {
bool isadd = 0;
for (int i = 0; i < split; i++) {
for (int j = 0; j < n; j++) {
if (color[j] != -1) {
continue;
}
if (mat[j][i] <= bluel) {
isadd = 1;
color[j] = 0;
for (int k = 0; k < split; k++) {
bluel = max(mat[j][k], bluel);
}
for (int k = split; k < m; k++) {
bluer = min(mat[j][k], bluer);
}
}
else if (mat[j][i] >= redl) {
isadd = 1;
color[j] = 1;
for (int k = 0; k < split; k++) {
redl = min(mat[j][k], redl);
}
for (int k = split; k < m; k++) {
redr = max(mat[j][k], redr);
}
}
}
}
for (int i = split; i < m; i++) {
for (int j = 0; j < n; j++) {
if (color[j] != -1) {
continue;
}
if (mat[j][i] >= bluer) {
isadd = 1;
color[j] = 0;
for (int k = 0; k < split; k++) {
bluel = max(mat[j][k], bluel);
}
for (int k = split; k < m; k++) {
bluer = min(mat[j][k], bluer);
}
}
else if (mat[j][i] <= redr) {
isadd = 1;
color[j] = 1;
for (int k = 0; k < split; k++) {
redl = min(mat[j][k], redl);
}
for (int k = split; k < m; k++) {
redr = max(mat[j][k], redr);
}
}
}
}
if (!isadd) {
break;
}
}
if (bluel >= redl || bluer <= redr) {
cout << "NO" << endl;
T--;
goto here;
}
cout << "YES" << endl;
for (int i = 0; i < n; i++) {
if (color[i] == 0) {
cout << "B";
}
else {
cout << "R";
}
}
cout << " " << split << endl;
}
} E：Arena
Ps：Arena是竞技场的意思，MOBA游戏里的A就是这个单词，（MOBA--multiplayer online battle arena）
首先看到这样的数据范围应该有一个敏感性，可能要用到dp了
这题确实可以通过记忆化搜索来实现。
我们假设剩余n个人，且每个人剩余血量不超过m时，能达到平局的可能次数为f(n,m)；
显然，当n=1时，f(1,m)=0;
那么如果m<=n-1时，在第一轮，所有人都死亡，那么每个人的血量可以任取1-m的值，也就是说，f(n,m)=m^n
接着考虑m>=n时
如果有i个人此时血量<=n-1, n-i个人血量>=n，那么第一轮结束后，将会剩下n-i个人，他们将继续决斗，且此时，他们的剩余血量不超过m-(n-1)，在这种情况下，对答案的贡献为C(i,n)*(m^i)*f(n-i,m-n+1)
#include<vector>
#include<iostream>
using namespace std;
const int mod = 998244353;
long long ksm(long long b, long long e) {
long long res = 1, tmp = b;
while (e) {
if (e & 1) {
res *= tmp;
res %= mod;
}
tmp *= tmp;
tmp %= mod;
e >>= 1;
}
return res;
}
vector<vector<long long>>c(501, vector<long long>(501, 0));
vector<vector<long long>>dp(501, vector<long long>(501, -1));
void initial() {
for (int i = 1; i < 501; i++) {
c[i][0] = c[i][i] = 1;
}
for (int i = 1; i < 501; i++) {
for (int j = 1; j < i; j++) {
c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
c[i][j] %= mod;
}
}
}
long long cal(long long n, long long x) {
if (dp[n][x] != -1) {
return dp[n][x];
}
else if (x <= n-1) {
return dp[n][x]=ksm(x, n);
}
else {
long long res = 0;
for (int i = 0; i <= n; i++) {
//死了i个的情况,选i个死
res += ((cal(n - i, x - n + 1) * ksm(n-1, i))%mod)*c[n][i];
res %= mod;
}
return dp[n][x] = res;
}
}
int main() {
//dp[n][x]代表剩余n个人，每个人的最高血量为x.
//dp[1][]=0;
//dp[n][x]=x^n;x<=n;
initial();
for (int i = 1; i < 501; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < 501; i++) {
dp[1][i] = 0;
}
int n, x;
cin >> n >> x;
cout << cal(n, x);
//3 3
//第一轮一个没死
//3 1
//第一轮死了一个
//f(2 1) *(2)*C(3,1)
}