出题人题解
Alice 和 Bob
https://ac.nowcoder.com/acm/contest/83318/A
题解如下：
链接：https://pan.baidu.com/s/1Gs5baEZe8kkEwFQaeV6rHg
提取码：flbb
代码：
A
#include <bits/stdc++.h>
const int N = 1e5 + 10;
int p[N];
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
int x;
std::cin >> x;
a[x] = i;
}
for (int i = 1; i <= n; i++) {
int x;
std::cin >> x;
b[x] = i;
}
int m;
std::cin >> m;
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
}
for (int i = 1; i <= n; i++) {
p[i] = i;
}
int need = 0;
for (int i = 1; i <= n; i++) {
if (find(a[i]) != find(b[i])) {
p[find(a[i])] = find(b[i]);
need++;
}
}
if (need > m) {
std::cout << "No\n";
} else {
std::cout << "Yes\n";
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
B
#include <bits/stdc++.h>
const int N = 1e5 + 10;
int f[N];
int main() {
std::ios::sync_with_stdio(false);
for (int i = 1; i < N; i++) {
f[i] = f[i - 1] ^ i;
}
int t;
std::cin >> t;
while (t--) {
int n;
std::cin >> n;
if (n & 1) {
std::cout << f[n] << '\n';
} else {
std::cout << "no one\n";
}
}
return 0;
}
C
#include <bits/stdc++.h>
const int N = 1e5 + 10, M = 20;
int nxt[N][M], s[N];
bool zd[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, Q;
std::cin >> m >> n >> Q;
for (int i = 0; i < m; i++) {
int x;
std::cin >> x;
if (x) zd[i] = true;
}
for (int i = 1; i <= n; i++) {
int x;
std::cin >> x;
s[i] = (s[i - 1] + x) % m;
}
for (int i = 0; i < m; i++) {
nxt[n + 1][i] = n + 1;
}
for (int i = n; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (s[i] == j) nxt[i][j] = i;
else nxt[i][j] = nxt[i + 1][j];
}
}
while (Q--) {
int l, r;
std::cin >> l >> r;
int p = n + 1;
for (int i = 0; i < m; i++) {
if (zd[i]) {
p = std::min(p, nxt[l - 1][(s[l - 1] + i) % m]);
}
}
if (p < r) {
std::cout << p + 1 << '\n';
} else {
std::cout << "No one died\n";
}
}
return 0;
}
D
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
int x, y;
std::cin >> x >> y;
std::string s;
std::string a = "cqust", b = "tsuqc";
if (x < y) {
std::swap(x, y);
std::swap(a, b);
}
int v = 0;
while (x && y) {
if (!v) {
if (s.size() && s.back() == a[0]) s.pop_back();
s += a;
x--;
} else {
if (s.size() && s.back() == b[0]) s.pop_back();
s += b;
y--;
}
v ^= 1;
}
while (x) {
if (s.size() && s.back() == a[0]) s.pop_back();
s += a;
x--;
}
while (y) {
if (s.size() && s.back() == b[0]) s.pop_back();
s += b;
y--;
}
std::cout << s << '\n';
}
return 0;
}
E
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
}
int l = 1;
while (l <= n && a[l] == l) l++;
int r = n;
while (r >= 1 && a[r] == r) r--;
int c = 0;
for (int i = l; i <= r; i++) {
if (a[i] == i) c++;
}
if (l > r) {
std::cout << 0 << '\n';
} else if (c == 0) {
std::cout << 1 << '\n';
} else {
std::cout << 2 << '\n';
}
}
return 0;
}
F
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
vector<int> h[N];
int C[N];
int lowbit(int x) {
return -x & x;
}
void add(int x) {
while(x < N) {
C[x]++;
x += lowbit(x);
}
}
int sum(int x) {
int ans = 0;
while(x) {
ans += C[x];
x -= lowbit(x);
}
return ans;
}
int main() {
int n, m, k;
n = m = 1e6;
cin >> k;
for(int i = 1; i <= k; i++) {
int x, y;
cin >> x >> y;
h[x].push_back(y);
}
long long ans = 0;
for(int i = n; i > 0; i--) {
sort(h[i].begin(), h[i].end());
if(h[i].size() == 0) continue;
int len = h[i].size() - 1;
ans += h[i][len] - sum(h[i][len]);
for(auto x: h[i]) {
if(sum(x) - sum(x - 1) == 0) {
add(x);
ans += i - 1;
}
}
}
cout << ans << '\n';
return 0;
}
G
#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e5 + 10, M = 10;
std::pair<int, int> hill[M], point[N];
int ans[N];
LL d[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, q;
std::cin >> n >> m >> q;
for (int i = 0; i < n; i++) {
std::cin >> point[i].first >> point[i].second;
d[i] = 3e18;
}
for (int i = 0; i < m; i++) {
std::cin >> hill[i].first >> hill[i].second;
}
int sz = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
d[j] = std::min(d[j], 1LL * (point[j].first - hill[i].first) * (point[j].first - hill[i].first) + 1LL * (point[j].second - hill[i].second) * (point[j].second - hill[i].second));
}
}
std::sort(d, d + n);
for (int i = 0; i < q; i++) {
int t;
std::cin >> t;
std::cout << std::upper_bound(d, d + n, 1LL * t * t) - d << '\n';
}
return 0;
}
H
#include <bits/stdc++.h>
const int N = 510, mod = 998244353;
int dp[N][N][2], pre[N][N][2]; //dp[][][0]：表示 a[i] <= a[i - 1]，dp[][][1]：表示 a[i] > a[i - 1]
int ans[2 * N][N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
//初始化
for (int i = 1; i <= m; i++) {
dp[i][0][0] = 1;
}
for (int i = 2; i <= (n + 1) / 2; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= (i - 1) / 2; k++) {
for (int v = 0; v < 2; v++) {
pre[j][k][v] = (pre[j - 1][k][v] + dp[j][k][v]) % mod;
}
}
}
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= i / 2; k++) {
dp[j][k][1] = (pre[j - 1][k][0] + pre[j - 1][k][1]) % mod;
dp[j][k][0] = (1LL * pre[m][k][0] - pre[j - 1][k][0] + pre[j][k][1] - pre[j - 1][k][1]) % mod;
if (k) {
dp[j][k][0] = ((1LL * dp[j][k][0] + pre[m][k - 1][1] - pre[j][k - 1][1]) % mod + mod) % mod;
}
}
}
}
for (int i = 1; i <= m; i++) {
for (int a = 0; a <= ((n + 1) / 2 - 1) / 2; a++) {
for (int b = 0; b <= ((n + 1) / 2 - 1) / 2; b++) {
for (int x = 0; x < 2; x++) {
for (int y = 0; y < 2; y++) {
int cnt = a + b + (x && y);
ans[cnt][i] = (ans[cnt][i] + 1LL * dp[i][a][x] * dp[i][b][y] % mod) % mod;
}
}
}
}
}
for (int i = 0; i <= n; i++) {
int res = 0;
for (int j = 1; j <= m; j++) {
res = (res + 1LL * ans[i][j] * ans[i][j]) % mod;
}
std::cout << res << " \n"[i == n];
}
return 0;
}
I
#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<LL, int> PLI;
const int N = 1e5 + 10;
int cnt[N];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, k;
std::cin >> n >> m >> k;
std::priority_queue<PLI, std::vector<PLI>, std::greater<PLI>> pq;
for (int i = 0; i < m; i++) {
std::cin >> cnt[i];
}
for (int i = 0; i < m; i++) {
int x;
std::cin >> x;
pq.push({x, i});
}
LL ans = 0;
auto f = [&](LL x) {
return (x + k) | (x & k);
};
while (n--) {
PLI it = pq.top();
pq.pop();
ans += it.first;
if (--cnt[it.second] > 0) pq.push({f(it.first), it.second});
}
std::cout << ans << '\n';
return 0;
}
J
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
std::string s;
std::cin >> s;
int n = s.size();
if (s.find('1') == -1) {
std::cout << 0 << '\n';
} else {
std::cout << n - 1 << '\n';
}
}
return 0;
}
