前言：

此文章主要是記錄每天的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";}
}