由于一次比賽被虐得太慘，，生發開始寫blog的想法，于是便有了這篇隨筆（找了個近期的cf比賽練練手(bushi)）第一次寫blog，多多包涵，
第二場cf比賽，第一場打的Div2，被虐太慘，所以第二場挑了個Div4...
比賽鏈接： https://codeforces.com/contest/1669
A. Division
翻譯（參考）：
t組樣例，每組樣例給出一個正整數，判斷該整數所在的范圍
題解：
簽到題，分類討論下即可
B.Trip
翻譯（參考）：
t組樣例，每組給出一個長度為n的陣列，對每組樣例輸出一個在該陣列中出現三次及三次以上的數字（可能有多個，輸出任意一個就好），若不存在則輸出-1.
題解：
簽到題，An<=2e5,值域范圍不大，開個陣列記錄即可（值域過大可以考慮用map記錄），
C. Odd/Even Increments
翻譯（參考）
t組樣例，對每組樣例給出一個長度為n的陣列（下標從1開始），有以下兩種操作，每種操作可進行任意次
1. 對所有奇數下標的元素+1
2. 對所有偶數下標的元素+1
問是否能進行以上兩種操作使得陣列所有元素都為奇數或都為偶數
題解：
思維題，很容易想到如果原陣列奇數和偶數分別對應的下標不滿足均為奇數或者均為偶數不可能經過操作滿足條件
故而，分別判斷奇數下標是否全為奇或全為偶，偶數下標是否全為奇或全為偶即可，
D. Colorful Stamp
翻譯（參考）：
t組樣例，每組給出一個僅由W R B組成的字串，問該字串能否經過操作（選擇相鄰的兩個字符，一個變為R另一個變為B）由全為W的等長字串得到，若可以輸出YES，否則輸出NO
題解：
樣例解釋：
（BRB）
WWW→WRB→BRB（YES）
（RRR）
不可能由WWW得到（NO）
思維題，我們很容易想到每次操作的結果都是一個R一個B，，操作變換有以下四種情況（對W不能進行操作，因為W改變了不可能再變回去）
1. RR ---> RB / BR（減少一個R）
2. BB ---> RB / WR（減少一個W）
3. RB ---> BR
4. BR ---> RB
可以得出結論，只要字串中既含B又含有R就可以得到目標字串
把W看成空格得到一堆字串，判斷這些字串中是否全為B或者全為B即可
代碼：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; string s; void solve() { int n, r = 0, b = 0, cnt = 0; // r記錄R的個數，b記錄B的個數 cin >> n; getline(cin, s); //消除換行符 getline(cin, s); //讀入目標字串 for (int i = 0; i < n; i++) { if (s[i] == 'R') { cnt++; r++; } else if (s[i] == 'B') { cnt++; b++; } else //遇到W標志已得到一個子串進行判斷該字串是否滿足條件 { if (r == 0 || b == 0) { cout << "NO\n"; return; } cnt = 0, r = 0, b = 0; } } if (r == 0 || b == 0) //最后的一個不以W分隔的子串 { cout << "NO\n"; return; } cout << "YES\n"; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int __; cin >> __; getline(cin, s); while (__--) { solve(); } }E.2-Letter Strings
翻譯（參考）：
t組樣例，對每組樣例給出n個長度為2的僅由abcdefghijk構成的字串，求有幾對字串滿足只有一個對應位置相同，
題解：
樣例解釋：
7 aa bb cc ac ca bb aa
("aa", "ac"), ("aa", "ca"), ("cc", "ac"), ("cc", "ca"), ("ac", "aa") and ("ca", "aa")
共計6種
可以由容斥原理想到，先分別統計對每種字符在多少個字串的第一個位置出現和對每種字符在多少個字串的第二個位置出現的數量減去2*相同的字串的個數（因為相同的字串在第一個字符相同和第二個字符相同都有被統計），利用組合數求出對應的每種情況的個數C2m
代碼：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; string s; void solve() { ll ans = 0; map<char, ll> mp1, mp2; // mp1統計在位置一（s[0])相同的字串個數，mp2統計在位置二（s[1])相同的字串個數 map<string, ll> mp; //統計相同的字串個數 int n; cin >> n; getline(cin, s); //吸識訓行符 for (int i = 0; i < n; i++) { string ss; getline(cin, ss); if (mp.find(ss) != mp.end()) { mp[ss]++; } else { mp[ss] = 1; } if (mp1.find(ss[0]) != mp1.end()) { mp1[ss[0]]++; } else { mp1[ss[0]] = 1; } if (mp2.find(ss[1]) != mp2.end()) { mp2[ss[1]]++; } else { mp2[ss[1]] = 1; } } for (auto it : mp1) //統計每種字符在位置一相同的字串的貢獻 { if (it.second != 1) { int t = it.second; ans += (t * (t - 1) / 2); } } for (auto it : mp2) //統計每種字符在位置二相同的字串的貢獻 { if (it.second != 1) { int t = it.second; ans += (t * (t - 1) / 2); } } for (auto it : mp) //統計每種相同字串的貢獻 { if (it.second > 1) { int t = it.second; string te = it.first; ans -= 2 * (t * (t - 1) / 2); } } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int __; cin >> __; getline(cin, s); while (__--) { solve(); } }F. Eating Candies
翻譯（參考）：
t組樣例，對每組樣例給出n個數分別為糖果的價值，Alice從左開始吃糖果，Bob從右往左開始吃糖果，每次只能有一個人吃到糖果，問是否能有一種方案使得兩人在中途吃到的糖果總數量相同，輸出最大糖果數量
題解：
樣例解釋：
9
7 3 20 5 15 1 11 8 10
Alice : [7,3,20]
Bob : [10,8,11,1]
兩人吃的總價值均為30
可以吃的最多的糖果數量為7個
筆者認為此題考查了前綴和，后綴和，二分，前綴和維護Alice吃的糖果總價值，后綴和維護Bob吃的糖果的總價值，二分查找前綴和對應的元素在后綴和陣列中的位置，若出現可更新結果（Alice和Bob的總價值相同），對結果取max輸出即可
代碼：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; ll w[200009], a[200009], b[200009]; //記得開long long，因為前綴和或后綴和可能很大會爆int void solve() { int n, ans = 0; cin >> n; for (int i = 1; i <= n; i++) { cin >> w[i]; a[i] = a[i - 1] + w[i]; //前綴和->Alice的總價值 } b[n + 1] = 0; for (int i = n; i >= 1; i--) { b[i] = b[i + 1] + w[i]; //后綴和->Bob的總價值 } for (int r = n; r > 1; r--) { int p = lower_bound(a + 1, a + 1 + r - 1, b[r]) - a; //二分查找 if (p != r && a[p] == b[r]) //找到的位置值相同，更新答案 { ans = max(ans, p + n - r + 1); // Alice:p個 Bob:n-r+1個 } } cout << ans << "\n"; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int __; cin >> __; while (__--) { solve(); } }G. Fall Down
翻譯（參考）：
t組樣例，對每組樣例給出n*m的地圖，‘*’代表石頭，‘.’代表空地，‘o’代表障礙，對每個石頭可以進行下落直到遇到障礙或到達底部，輸出最終的地圖，
樣例：
6 10
.*.*....*.
.*.......*
...o....o.
.*.*....*.
..........
.o......o*
輸出：
..........
...*....*.
.*.o....o.
.*........
.*......**
.o.*....o*
題解：
對每個*（石頭）往下找第一個不為.（空地）的位置或已到達底部，將二者進行交換即可
代碼：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9 + 7; void solve() { int n, m; cin >> n >> m; char s[60][60]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> s[i][j]; //讀入 } } for (int i = n - 2; i >= 0; i--) { for (int j = 0; j < m; j++) { if (s[i][j] == '*') //石頭 { int k = i + 1; while (k < n && s[k][j] == '.') //找第一個不為空地的位置或已到達底部 { k++; } swap(s[i][j], s[k - 1][j]); //交換 } } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cout << s[i][j]; } cout << "\n"; } cout << "\n"; } signed main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int __; cin >> __; while (__--) { solve(); } }H. Maximal AND 咳咳，鄙人不才，此題賽時沒寫出來，賽后也沒去補題..... ending: 第一次寫blog，有什么錯誤之處歡迎指正！鄙人不勝感激！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/465995.html
標籤：其他