前言：

此文章主要是记录每天的codeforces刷题，还有就是给其他打算法竞赛的人一点点点点小小的帮助（毕竟现在实力比较菜，题目比较简单，但我还是会认真写题解）。

之前忙学校事情，懈怠了一段时间，今天继续，看能坚持到几天！

开始先来点简单的复健吧，目前分数1449，但是一段时间没训cf，实力应该不到1200，争取20天后开始板刷1600。

每天坚持写三道题第四天：

Problem - D - Codeforces 1000

Problem - B - Codeforces 1100

Problem - C - Codeforces 1400

目录

题目一:

题目大意:

解题思路:

代码(C++):

题目二:

题目大意:

解题思路:

代码(C++):

题目三:

题目大意:

解题思路:

代码(C++):

---

题目一:

Problem - D - Codeforces

题目大意:

定义字符串中字符的价值为在字母表中的位置，比如a为1，b为2...z为26。

定义字符串的价值为包含的字符价值和。

现在你需要从给定的只有小写字母的字符串中删除若干个元素保证字符串的价值和不超过p。

现在你要保证尽可能少的删除字符。

输出删除字符后的字符串（可能为空）

解题思路:

从大到小的贪心。

我们每次删除价值最大的字符就可以了。

具体实现方案，我们可以用一个数组同时记录此处字符的价值和字符的下标。

然后根据价值从大到小排序，这样就可以保证每次删除的都是价值最大的字符了。

我们可以用一个set记录需要删除的下标，然后遍历字符串输出，遍历到需要删除的就跳过即可。

代码(C++):

void solve() {std::string s;int p;std::cin >> s >> p;int n = s.size();//建立数组,a[i].first表示此时字符的价值,a[i].second表示字符的下标std::vector<std::pair<int, int>> a(n);int total = 0;for (int i = 0; i < n; i++) {int v = s[i] - 'a' + 1;a[i].first = v;total += v;a[i].second = i;}//根据字符的价值从大到小进行排序//也可以直接std::sort(a.begin(), a.end(), std::greater<>());,因为默认是根据第一个元素排序//我这里为了可读性就这么写了std::sort(a.begin(), a.end(), [](auto& v, auto& u) {return v.first > u.first;});//用set存需要删除的下标std::set<int> index;for (int i = 0; i < n; i++) {if (total > p) {total -= a[i].first;index.insert(a[i].second);} else {break;}}for (int i = 0; i < n; i++) {//当set包含下标i,也就是说这个字符需要删除,跳过不输出即可if (index.count(i)) {continue;}std::cout << s[i];}std::cout << "\n";
}

题目二:

Problem - B - Codeforces

题目大意:

现在给你一个长度为n的数组a，现在询问你是否可以重新排列这个数组，使得

min([a1,a2,…,ai])= gcd([ai+1,ai+2,…,an]).（下标从1开始的）。

也就是说，数组前面一部分的最小值，等于数组后面一段所有数字的gcd。

如果可以输出Yes，否则输出No。

解题思路:

我们首先得注意一点：对于一段序列a，gcd(a) <= min(a)是恒成立的。

所以把数组的最小值放在数组开头，是最有可能满足题目条件的。

我们设此时的a[0] = x。

那么数组前面连续一部分的最小值，是绝对等于x的，也就是等式左边等于x

现在我们只需要：

1.在数组中找出是x的倍数的数（这些数组成的序列我设置成b）放在数组最后。

2.不断求序列b的gcd，也就是等式右边，当gcd(b) = x的时候即可表示存在这种情况。

代码(C++):

void solve() {int n;std::cin >> n;std::vector<i64> a(n);i64 mn = 1e18 + 7;for (int i = 0; i < n; i++) {std::cin >> a[i];mn = std::min(mn, a[i]);}//找出最小值放在开头for (int i = 0; i < n; i++) {if (a[i] == mn) {std::swap(a[i], a[0]);break;}}i64 g = 0;for (int i = 1; i < n; i++) {//是a[0]的倍数if (a[i] % a[0] == 0) {g = std::gcd(g, a[i]);if (g == a[0]) {std::cout << "Yes\n";return;}}}std::cout << "No\n";
}

题目三:

Problem - C - Codeforces

题目大意:

现在有一个n * m的矩阵，起初，这个矩阵满足，所有的行和列都满足相加的和相等。

也就是每一行的和都相等，每一列的和都相等，并且任意一行的和等于任意一列的和。

现在一个物体从矩阵的左上方(1, 1)移动到矩阵的右下方(n, m)。

已知这个矩阵的运动路径，D为向下移动，R为向右移动。

经过的方格都会变成0。

现在让你把方格复原，也就是复原这个物体运动路径上的数，使得矩阵的性质不变（行和列相等）。

输出最终复原后的矩阵。输出一种复原情况即可。

解题思路:

首先需要注意到并且理解两个点：

1.物体从左上角移动到右下角，不管怎么走，都会保证每一行每一列至少有一个经过的点（也就是说每行每列中至少存在一个0）。

2.根据1来推理得出，我们只需要修改“每行每列中的0”来调整每一行每一列的和，使其相等即可。

通过上述分析，问题可以转化成，我们需要找出一个和sum，使得方便调整。

注意到：这个和sum = 0的时候最容易调整。

代码实现的时候，可以这么实现：

用i,j表示此时的位置，我们重新走一遍“物体走过的路”：

如果是此时向下走，那么表示需要根据这一列的情况来修改(i, j)处的0。

既然我们要让行和列的和都为0，那么我们可以计算出整个列的和sum_col，然后把此处的0修改成-sum_col即可，这样就可以满足列的值为0了

如果是向右走，那么就表示这一行有一个多出的0，同理进行修改即可。

具体实现可以参考代码。我这里参考的是jiangly老师的写法。

注意可能错的点：给出的字符串长度是n + m - 2，我们实际走的路程是n + m - 2但是实际经过的位置数量是n + m - 1，所以实现的时候要么是开头位置特判，要是是结尾特判。

代码(C++):

void solve() {int n, m;std::string s;std::cin >> n >> m >> s;std::vector a(n, std::vector<i64> (m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {std::cin >> a[i][j];}}//用(i, j)表示此时的位置,我们重新走一遍这个路线int i = 0, j = 0;while (i + j < n + m - 1) {//如果此时是向下走//特判最后一个位置if (s[i + j] == 'D' || i + j == n + m - 2) {i64 res = 0;//计算这一列的和for (int x = 0; x < m; x++) {res += a[i][x];}a[i][j] = -res;i++;} else if (s[i + j] == 'R') {i64 res = 0;for (int y = 0; y < n; y++) {res += a[y][j];}a[i][j] = -res;j++;}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {std::cout << a[i][j] << " ";}std::cout << "\n";}
}