A.Rearranging ABC#
题目描述#
给定字符串,判断是否可以组成
解题思路#
排个序就行了
参考代码#
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
std::string s;
std::cin >> s;
std::sort(s.begin(), s.end());
std::cout << (s == "ABC" ? "Yes" : "No") << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}B.Avoid Rook Attack#
题目描述#
给出棋盘，其中放有的位置为 #, 在放有棋子的上下左右四个方向不能放棋子，问有多少个位置可以放棋子.
解题思路#
模拟下即可
参考代码#
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
std::vector<std::string> s(8, "");
for(int i = 0; i < 8; i++) {
std::cin >> s[i];
}
std::vector a(8, std::vector<int>(8, 1));
for(int i = 0; i < 8; i++) {
for(int j = 0; j < 8; j++) {
if (s[i][j] == '#') {
for(int l = 0; l < 8; l++) {
a[i][l] = 0;
}
for(int l = 0; l < 8; l++) {
a[l][j] = 0;
}
}
}
}
int res = 0;
for(auto i : a) {
for(auto j : i) {
res += j;
}
}
std::cout << res << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}C.Avoid Knight Attack#
题目描述#
给定 的棋盘和 个棋子位置,其中棋子能走的位置上图所示,问多少个位置可以放棋子,并且不被吃掉
解题思路#
模拟，需要注意边界处理
参考代码#
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
int n, m;
std::cin >> n >> m;
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2},
dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
auto check = [&](int x, int y) {
return 0 < x && x <= n && 0 < y && y <= n;
};
std::set<pii > se;
for(int i = 0; i < m; i++) {
int x, y;
std::cin >> x >> y;
se.insert({x, y});
for(int j = 0; j < 8; j++) {
int u = x + dx[j], v = y + dy[j];
if (check(u, v)) se.insert({u, v});
}
}
std::cout << n * n - se.size() << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}D.Many Segments 2#
题目描述#
给你两个长度分别为 、 和 的正整数序列，以及一个整数 。 求满足以下两个条件的整数对 的个数：
- 对于每一个 ，区间 并不完全包含区间 。
解题思路#
考虑 的同时，维护一个左边界，就是当前位置能最多往前多少是刚好不完全覆盖的，最后这个左边界需要取个
max，因为如果前面的左边界更右，那后面的左边界也要和前面一样。
参考代码#
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> a(n + m, 1);
for(int i = 0, l, r; i < n; i++) {
std::cin >> l >> r;
a[r] = std::max(a[r], l + 1);
}
for(int i = 1; i <= m; i++) {
a[i] = std::max(a[i], a[i - 1]);
}
int res = 0;
for(int i = 1; i <= m; i++) {
res += i - a[i] + 1;
}
std::cout << res << endl;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}E.Permute K times 2#
题目描述#
给定长度为 的数组 ,将 替换为 操作 次,输出 次操作后的数组.
解题思路#
在替换时，某个数多替换几轮就可能回到替换前的位置，那么我们就只需要找出环的大小即可，随后再取模即可
参考代码#
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> P(n);
for(int i = 0; i < n; i++) {
std::cin >> P[i], P[i]--;
}
auto qpow = [&](int a, int b, int p) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
};
std::vector<bool> vis(n, false);
for(int i = 0; i < n; i++) {
if (vis[i]) continue;
int j = i;
std::vector<int> t;
while (!vis[j]) {
vis[j] = true, t.push_back(j);
j = P[j];
}
int w = qpow(2, k, t.size());
for(int x = 0; x < t.size(); x++) {
P[t[x]] = t[(x + w) % t.size()];
}
}
for(int i = 0; i < n; i++) std::cout << P[i] + 1 << " \n"[i == n - 1];
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
solve();
return 0;
}