Codeforces Round 991 (Div. 3)

补题连接

A. Line Breaks

思路：从头开始累加单词个数，超过m就退出。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long longvoid solve()
{int n, m, k;cin >> n >> m;vector<string> a(n);int cnt = 0;for (int i = 0; i<n; i++){cin >> a[i];}int ans = 0;for (int i = 0; i<n; i++){if (cnt+a[i].size() <= m){cnt += a[i].size();ans++;}else break;}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

B. Transfusion

思路：分析得出，应该对奇数和偶数分开讨论。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_backvoid solve()
{int n, m, k;cin >> n;int sum1= 0, sum2=0;vi a, b;for (int i = 1;i<=n; i++){int x; cin >> x;if (i % 2 == 1){a.pb(x);sum1 += x;}else{b.pb(x);sum2 += x;}}if (sum1%a.size() == 0 && sum2%b.size() == 0 && sum1/a.size() == sum2/b.size()){cout << "YES" << endl;}else{cout << "NO" << endl;}}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

C. Uninteresting Number

思路：回想起了初中还是小学知识，一个是9的倍数的数，各个位数上的和也是9的倍数。

在这里我们遍历累加n的位数，又由题可以推出我们只可能当遇到2，3的时候才能用它的平方数替代，但是我们不知道该替代哪些，所以先分别记录下2，3的个数。

分别嵌套循环遍历2，3从0取到完为止的数是否满足要求。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long longvoid solve()
{int n, m, k;string s;cin >> s;int a = 0, b = 0, sum = 0;for (char c : s){if (c == '2') a++;else if (c == '3') b++;sum += c - '0';}for (int i = 0; i <= a; i++){for (int j = 0; j <= b; j++){if ((sum + i * 2 + j * 6) % 9 == 0){cout << "YES" << endl;return;}}}cout << "NO" << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

D. Digital string maximization

思路：感觉就像是冒泡排序一样的思路，不过改一点点东西而已。(一开始完全没想到这样会过，想半天才试了以下居然能过)。在排序的思路上对要往上的-1进行比较和替换。看代码比较好理解。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long longvoid solve()
{int n, m, k;string s;cin >> s;int num = s.size();for (int i = 0; i < num; i++){for (int j = i; j>=1; j--){if (s[j]-1 > s[j-1]){char temp = s[j]-1;s[j] = s[j-1];s[j-1] = temp;}else break;}}cout << s << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

E. Three Strings

思路：一道dp题，思路很像编辑距离和最长公共子序列，可以去刷刷这两题。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define pb push_back
#define endl '\n'void solve() {string a, b, c;cin >> a >> b >> c;int n = a.size(), m = b.size(), k = c.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, LLONG_MAX));dp[0][0] = 0; for (int i = 0; i <= n; ++i) {for (int j = 0; j <= m; ++j) {if (i + j <= k) {if (i > 0) {dp[i][j] = min(dp[i][j], dp[i - 1][j] + (c[i + j - 1] != a[i - 1]));}if (j > 0) {dp[i][j] = min(dp[i][j], dp[i][j - 1] + (c[i + j - 1] != b[j - 1]));}}}}int result = LLONG_MAX;for (int i = 0; i <= n; ++i) {if (i <= k) {result = min(result, dp[i][m] + (k - (i + m))); }}cout << result << endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--) {solve();}return 0;
}

F. Maximum modulo equality

思路：看到求区间类的题应该要很快想到线段树，这题应该最大公因数满足结合律，也可以用ST表来做比较快。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>void solve()
{int n, m, k, q;cin >> n >> q;vi a(n);vector<vector<int>> b(n, vi(20));for (int i = 0; i<n; i++) {cin >> a[i];if (i) b[i][0] = abs(a[i]-a[i-1]);}for (int j = 1; j<20; j++){for (int i = 0; i+(1ll<<j)-1<n; i++){b[i][j] = __gcd(b[i][j-1], b[i+(1ll<<j-1)][j-1]);}}auto query = [&](int l, int r)->int{if (l > r) return 0;int k = log2(r-l+1);return __gcd(b[l][k], b[r-(1ll<<k)+1][k]);};while (q--){int l, r;cin >> l >> r;l--, r--;cout << abs(query(l+1, r)) << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}

---

(如果有帮助请点赞或评论支持，有问题请指正，其他问题请评论交流...) 

都看到这里了真不点个赞吗