A. Question Marks
题目大意
有4n道题，每道题有4个选项，且正确答案中每个选项各占有n个。给定一个字符串s，s中ABCD分别代表4个选项，？代表放弃这道题，求可能的最大正确数
解题思路
统计每个选项的出现次数，假设每次选的都对，即ans += min(x, n)
点击查看代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> a(4, 0);
for (int i = 0; i < 4 * n; i++) {
if (s[i] != '?') {
a[s[i] - 'A']++;
}
}
int ans = 0;
for (auto x : a) {
ans += min(x, n);
}
cout << ans << endl;
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B. Parity and Sum
题目大意
给定一个数组，每次选择一个奇数和偶数，将两者中较小者修改为两者之和，直到无法进行操作，求最少操作数
解题思路
注意到奇数加偶数等于奇数，即除了一开始全为偶数，其余情况最后都会变为全是奇数。考虑变为全是奇数。首先求出数组的最大值m。若m为奇数，则可以每次选取m与任意偶数，并将偶数变为奇数，需要操作的次数为偶数的个数。若m为偶数，考虑进行以下操作：每次选取数组中最大的奇数和一个小于它的偶数，将偶数变为奇数。若通过该操作可以将偶数全部变成奇数，则操作次数为偶数的个数，若不行，则选取最大的偶数与任意奇数，得到一个最大的奇数，这需要额外进行一次操作
点击查看代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
int m = 0, ji = 0, ou = 0;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
m = max(m, a[i]);
if (a[i] & 1) ji++;
else ou++;
}
sort(a.begin(), a.end());
if (ji == 0 || ou == 0) {
cout << 0 << endl;
return;
}
if (m & 1) {
cout << ou << endl;
} else {
long long mm = 1;
for (auto x : a) {
if (x > mm && x % 2 == 1) {
mm = x;
}
}
int l = 0;
for (l; l < n; l++) {
if (a[l] % 2 == 0) {
if (mm > 1ll * a[l]) {
mm += a[l];
} else {
break;
}
}
}
if (l == n) {
cout << ou << endl;
} else {
cout << ou + 1 << endl;
}
}
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
C. Light Switches
题目大意
有n个灯，一开始都暗，每个灯会在第a[i]秒变亮，亮k秒后变暗，暗k秒后再变亮，问所有灯同时变亮的最小时刻，或者不可能同时变亮
解题思路
注意到每2k秒为一个周期。首先记最晚亮的那个灯亮的时间为m，将所有其他灯的变亮时间全部移到(m - k, m + k]区间，然后将时间排序。每次检查时间的最大值与最小值之差，若小于k，则可以同时变亮，且答案为最大值；否则将最小值加上2k并重复以上操作。操作n次后若还是无法得出可以同时变亮，则可以确定同时变亮为不可能，输出-1
点击查看代码
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
long long k;
cin >> n >> k;
long long kk = 2 * k;
vector<long long> a(n);
long long m = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
m = max(a[i], m);
}
for (int i = 0; i < n; i++) {
a[i] += (m - a[i]) / kk * kk;
if (m - a[i] >= k) {
a[i] += kk;
}
}
sort(a.begin(), a.end());
deque<long long> q;
for (int i = 0; i < n; i++) {
q.push_back(a[i]);
}
int flag = 0;
for (int i = 0; i < n; i++) {
// cerr << q.front() << ' ' << q.back() << endl;
if (q.back() - q.front() + 1 <= k) {
flag = 1;
break;
} else {
long long u = q.front();
q.pop_front();
q.push_back(u + kk);
}
}
if (flag == 0) {
cout << -1 << endl;
} else {
cout << q.back() << endl;
}
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
D. Med-imize
不会
E. Xor-Grid Problem
更是不会呐
F1. Dyn-scripted Robot (Easy Version)
题目大意
给定一个矩形范围(a,b)和一个脚本s，小车从原点出发按照脚本移动。当小车试图向垂直边界移动时，将脚本中所有垂直移动操作取反（水平同理），问执行k次脚本后小车会经过原点几次（初始位置不记）
解题思路
考虑将矩形进行镜像拓展，当小车每次移除边界，就将原有的矩形镜像翻转以让小车保持在矩形中。与此同时原点也会翻转，注意到原点翻转的位置是具有周期性的，横坐标以2a为周期，纵坐标以2b为周期，因此可以计算出执行一次脚本小车能够到达的位置并记录次数，并通过取模操作将这些位置限制在矩形(2a, 2b)中。每次执行脚本，记录起始点和原点的相对位置，并通过之前的记录查询出对答案的贡献。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int mod(int x, int m) {
return (x + m) % m;
}
void solve() {
int n, k, w, h;
cin >> n >> k >> w >> h;
string s;
cin >> s;
int x = 0, y = 0;
map<pair<int, int>, int> mp;
for (int i = 0; i < n; i++) {
if (s[i] == 'U') y++;
if (s[i] == 'D') y--;
if (s[i] == 'L') x--;
if (s[i] == 'R') x++;
x = mod(x, 2 * w);
y = mod(y, 2 * h);
mp[{x, y}]++;
}
long long ans = 0;
for (int i = 0; i < k; i++) {
int xx = (1ll * i * x) % (2 * w);
int yy = (1ll * i * y) % (2 * h);
if (xx > 0) xx = 2 * w - xx;
if (yy > 0) yy = 2 * h - yy;
ans += mp[{xx, yy}];
}
cout << ans << endl;
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}