A - aaaadaa
题意：给你一个字符串和两个字符\(c_1\),\(c_2\)，把字符串里的所有不等于\(c_1\)的字符都换成\(c_2\)。
模拟即可。
点击查看代码
void solve() {
int n;
char a, b;
std::cin >> n >> a >> b;
std::string s;
std::cin >> s;
for (auto & c : s) {
if (c != a) {
c = b;
}
}
std::cout << s << "\n";
}
B - ARC Division
题意：你有一个初始分，按顺序参加比赛，比赛由两种，有不同的计分范围，如果你的分数在这个比赛的计分范围内，就会加上\(a_i\)，求最后分数。
也是模拟。
点击查看代码
void solve() {
int n, ans;
std::cin >> n >> ans;
for (int i = 0; i < n; ++ i) {
int d, a;
std::cin >> d >> a;
if (d == 1 && ans >= 1600 && ans <= 2799) {
ans += a;
} else if (d == 2 && ans >= 1200 && ans <= 2399) {
ans += a;
}
}
std::cout << ans << "\n";
}
C - Perfect 排名表
题意：有五个题目，每个题目有一个分数，你要求出做出这五题其中一些题的所有排列的分数，然后按分数从大到小输出，如果分数相同那就字典序小的输出。
dfs搜出所有排列，然后排序。
点击查看代码
void solve() {
std::vector<int> a(5);
for (int i = 0; i < 5; ++ i) {
std::cin >> a[i];
}
std::vector<std::pair<std::string, int> > ans;
auto dfs = [&](auto self, int u, std::string s, int val) -> void {
if (u == 5) {
if (s.size()) {
ans.push_back({s, val});
}
return;
}
self(self, u + 1, s, val);
s += 'A' + u;
val += a[u];
self(self, u + 1, s, val);
};
dfs(dfs, 0, "", 0);
std::sort(ans.begin(), ans.end(), [&](std::pair<std::string, int> & a, std::pair<std::string, int> & b) {
if (a.second == b.second) {
return a.first < b.first;
}
return a.second > b.second;
});
for (auto & [s, v] : ans) {
std::cout << s << "\n";
}
}
D - Repeated Sequence
题意：有一个无限长的序列，以n为周期，现在给你一个周期里的数，求这个序列有没有一段连续区间的和等于s。
记sum等于一个周期的和，如果s <= sum, 我们延长一倍数组双指针模拟就行。如果s > sum，我们选的区间应该是一些完整周期加上结尾一些数和开头一些数，那么我们把所有前缀和记录起来，从后枚举后缀和，已知当前后缀和为x, 那么我们要求一个前缀y, 使得 (s - x - y) % sum = 0，因为y一定小于sum，那么也就是 y = (s - x) % sum。
点击查看代码
void solve() {
int n;
i64 s;
std::cin >> n >> s;
std::vector<i64> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::set<i64> set;
i64 sum = 0;
for (int i = 0; i < n; ++ i) {
sum += a[i];
set.insert(sum);
}
if (sum >= s) {
i64 sum = 0;
for (int i = 0, j = 0; i < n; ++ i) {
j = std::max(j, i);
while (j < 2 * n && sum < s) {
sum += a[j % n];
++ j;
}
if (sum == s) {
std::cout << "Yes\n";
return;
}
sum -= a[i];
}
std::cout << "No\n";
return;
}
set.insert(0);
i64 x = 0;;
for (int i = n - 1; i >= 0 && x <= s; -- i) {
x += a[i];
if (set.count((s - x) % sum)) {
std::cout << "Yes\n";
return;
}
}
std::cout << "No\n";
}
E - Takahashi is Slime 2
题意：一个矩阵，你有一个初始点，你可以往你相邻的点扩展，如果这个点 <= 你的值 / x，那么你可以吃它，并且占领它的格子。问你最大的值是多少。
我们把所有可以吃的格子用小根堆维护起来，每次吃最小的格子然后把它的邻格入队。如果连最小的都吃不了，就只能退出。
点击查看代码
void solve() {
i64 n, m, X, sx, sy;
std::cin >> n >> m >> X >> sx >> sy;
-- sx, -- sy;
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];
}
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
using A = std::array<i64, 3>;
std::priority_queue<A, std::vector<A>, std::greater<A> > heap;
std::vector st(n, std::vector<int>(m));
st[sx][sy] = 1;
i64 ans = a[sx][sy];
for (int i = 0; i < 4; ++ i) {
int nx = sx + dx[i], ny = sy + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
st[nx][ny] = 1;
heap.push({a[nx][ny], nx, ny});
}
while (heap.size()) {
auto [val, x, y] = heap.top(); heap.pop();
if ((__int128)val * X >= ans) {
break;
}
ans += val;
for (int i = 0; i < 4; ++ i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny]) {
continue;
}
st[nx][ny] = 1;
heap.push({a[nx][ny], nx, ny});
}
}
std::cout << ans << "\n";
}
F - Double Sum 2
这题没往位运算那方面想。。。
待补