Codeforces Round 984 (Div. 3)
题目链接
A. Quintomania
题意
思路
模拟即可
示例代码
void solve() {int n;cin >> n;vector<int>arr(n);fer(i, 0 ,n) cin >> arr[i];fer(i, 1, n){if(abs(arr[i] - arr[i - 1]) != 5 && abs(arr[i] - arr[i - 1]) != 7){cout << "NO" << '\n';return;}}cout << "YES" << '\n';
}
B. Startup
题意
输入
输出
思路
哈希表（数组哈希或者map)，需要注意计算ans时的边界（计算多少个）
示例代码
void solve() {int n, k;cin >> n >> k;int *arr = new int[max(n, k) + 2]{};fer(i, 0, k){int b, c;cin >> b >> c;arr[b] += c;}sort(arr, arr + max(n, k) + 2, [&](int a, int b){return a > b;});int ans = 0;fer(i, 0, n) ans += arr[i];cout << ans << '\n';
}
void solve() {int n, k;cin >> n >> k;map<int, int>mp;fer(i, 0, k){int b, c;cin >> b >> c;mp[b] += c;}vector<pii>arr(all(mp));sort(all(arr), [&](pii a, pii b){return a.second > b.second;});int ans = 0;fer(i, 0, min((int)arr.size(), n))ans += arr[i].second;cout << ans << '\n';
}
C. Anya and 1100
题意
输入
输出
思路
先预处理包含的1100的个数，然后计算在改变位置改变后对改变前的影响（可以分别计算在改变位置处1100的个数，计算差值），注意遍历的边界范围
示例代码
void solve() {string s;cin >> s;int q;cin >> q;int cnt = 0;fer(i, 0, s.size() - 3){if(s.substr(i, 4) == "1100") cnt++;}while(q--){int ind, v;cin >> ind >> v;ind--;int cnt1 = 0, cnt2 = 0;// 改变前fer(i, max(0, ind - 3), min((int)s.size() - 3, ind + 1)){if(s.substr(i, 4) == "1100") cnt1++;}// 改变后s[ind] = char(v + '0');fer(i, max(0, ind - 3), min((int)s.size() - 3, ind + 1)){if(s.substr(i, 4) == "1100") cnt2++;}cnt += cnt2 - cnt1;if(cnt >= 1) cout << "YES" << '\n';else cout << "NO" << '\n';}
}
D. I Love 1543
题意
输入
输出
样例输入及输出
思路
与蛇形填数思路一致，用偏移量法求取每一个外围的字符串，统计这个字符串在循环移位后包含1543子串的最大个数，加到res中输出。注意边界的判断。
示例代码
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};int finds(string s){int cnt = 0;fer(i, 0, s.size() - 3){if(s.substr(i, 4) == "1543")cnt++;}return cnt;
}void solve() {int n, m;cin >> n >> m;vector<vector<int>>arr(n, vector<int>(m));fer(i, 0, n){string s;cin >> s;fer(j, 0, s.size())arr[i][j] = (int)(s[j] - '0');}int c = 0;int res = 0;int nn = n, mm = m;while(n && m){string s;int x = c, y = c, d = 0;fer(i, 0, 2 * (n + m - 2)){s += to_string(arr[x][y]);int a = x + dx[d], b = y + dy[d];if(a < c || a >= nn - c || b < c || b >= mm - c){d = (d + 1) % 4;a = x + dx[d], b = y + dy[d];}x = a, y = b;}n -= 2, m -= 2;c ++;string s1 = s.substr(1) + s[0];string s2 = s1.substr(1) + s1[0];string s3 = s2.substr(1) + s2[0];res += max(finds(s), max(finds(s1), max(finds(s2), finds(s3))));}cout << res << '\n';
}