牛客周赛 144 视频讲解代码
A. 我是谁？
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
vector<int> cnt(4);
for (char c : s) {
cnt[c - 'A']++;
}
int mx = *max_element(cnt.begin(), cnt.end());
int mn = *min_element(cnt.begin(), cnt.end());
cout << (mx == mn ? "Yes" : "No");
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
String s = fs.next();
int[] cnt = new int[4];
for (int i = 0; i < n; i++) {
cnt[s.charAt(i) - 'A']++;
}
int mn = n;
int mx = 0;
for (int x : cnt) {
mn = Math.min(mn, x);
mx = Math.max(mx, x);
}
System.out.println(mx == mn ? "Yes" : "No");
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int len = 0;
FastScanner(InputStream is) {
in = is;
}
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
String next() throws IOException {
int c;
do {
c = read();
} while (c <= 32 && c >= 0);
StringBuilder sb = new StringBuilder();
while (c > 32) {
sb.append((char) c);
c = read();
}
return sb.toString();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
}
import sys
data = sys.stdin.read().split()
n = int(data[0])
s = data[1]
cnt = [0] * 4
for ch in s[:n]:
cnt[ord(ch) - ord("A")] += 1
print("Yes" if max(cnt) == min(cnt) else "No")
B. 我是清楚姐姐
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n > 3) {
cout << -1;
} else if (n == 1) {
cout << 1;
} else if (n == 2) {
cout << "1 2\n3 4";
} else {
cout << "1 2 3\n5 4 6\n7 8 9";
}
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
if (n > 3) {
System.out.println(-1);
} else if (n == 1) {
System.out.println(1);
} else if (n == 2) {
System.out.println("1 2\n3 4");
} else {
System.out.println("1 2 3\n5 4 6\n7 8 9");
}
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int len = 0;
FastScanner(InputStream is) {
in = is;
}
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= 32 && c >= 0);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int value = 0;
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value * sign;
}
}
}
n = int(input())
if n > 3:
print(-1)
elif n == 1:
print(1)
elif n == 2:
print("1 2\n3 4")
else:
print("1 2 3\n5 4 6\n7 8 9")
C. 其实我是小苯
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
if (n < m) {
swap(n, m);
}
int d = n - m;
if (d == 0) {
cout << "0 ";
} else {
cout << string(d - 1, '9');
if (d > 1) {
cout << string(m - 1, '0');
}
cout << "1 ";
}
cout << string(d, '9') << '8' << string(m - 1, '9');
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int m = fs.nextInt();
if (n < m) {
int tmp = n;
n = m;
m = tmp;
}
int d = n - m;
StringBuilder ans = new StringBuilder();
if (d == 0) {
ans.append("0 ");
} else {
append(ans, '9', d - 1);
if (d > 1) {
append(ans, '0', m - 1);
}
ans.append("1 ");
}
append(ans, '9', d);
ans.append('8');
append(ans, '9', m - 1);
System.out.print(ans);
}
static void append(StringBuilder sb, char ch, int times) {
for (int i = 0; i < times; i++) {
sb.append(ch);
}
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int len = 0;
FastScanner(InputStream is) {
in = is;
}
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= 32 && c >= 0);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int value = 0;
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value * sign;
}
}
}
import sys
n, m = map(int, sys.stdin.buffer.read().split())
if n < m:
n, m = m, n
d = n - m
ans = []
if d == 0:
ans.append("0 ")
else:
ans.append("9" * (d - 1))
if d > 1:
ans.append("0" * (m - 1))
ans.append("1 ")
ans.append("9" * d)
ans.append("8")
ans.append("9" * (m - 1))
print("".join(ans), end="")
D. 骗你的，其实我是小红
代码查看
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
i64 l, r, k;
cin >> l >> r >> k;
i64 n = r - l + 1;
i64 a = n / k;
i64 b = n % k;
auto g = [&](i64 t) {
return t * (t - 1) / 2;
};
i64 ans = b * g(a + 1) + (k - b) * g(a);
cout << ans;
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
long l = fs.nextLong();
long r = fs.nextLong();
long k = fs.nextLong();
long n = r - l + 1;
long a = n / k;
long b = n % k;
long ans = b * g(a + 1) + (k - b) * g(a);
System.out.println(ans);
}
static long g(long t) {
return t * (t - 1) / 2;
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int len = 0;
FastScanner(InputStream is) {
in = is;
}
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
long nextLong() throws IOException {
int c;
do {
c = read();
} while (c <= 32 && c >= 0);
long sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
long value = 0;
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value * sign;
}
}
}
import sys
l, r, k = map(int, sys.stdin.buffer.read().split())
n = r - l + 1
a, b = divmod(n, k)
def g(t):
return t * (t - 1) // 2
print(b * g(a + 1) + (k - b) * g(a))
E. 好吧，我是Bingbong
代码查看
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
int n;
cin >> n;
vector<i64> h(n + 1), sum(n + 1), f(n + 1), ans(n + 1);
vector<vector<pair<int, int>>> e(n + 1);
for (int i = 1; i <= n; i++) {
cin >> h[i];
}
for (int i = 2; i <= n; i++) {
cin >> f[i];
}
for (int i = 2; i <= n; i++) {
int w;
cin >> w;
e[f[i]].push_back({i, w});
}
for (int i = n; i >= 1; i--) {
sum[i] += h[i];
sum[f[i]] += sum[i];
}
auto dfs = [&](auto &&self, int u, i64 base) -> void {
sort(e[u].begin(), e[u].end(), [](auto a, auto b) {
return a.second < b.second;
});
ans[u] = base + sum[u];
i64 prefix = 0;
for (auto [v, w] : e[u]) {
self(self, v, base + prefix + w);
prefix += sum[v];
}
};
dfs(dfs, 1, 0);
for (int i = 1; i <= n; i++) {
cout << ans[i] << " \n"[i == n];
}
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static class State {
int node;
long base;
State(int node, long base) {
this.node = node;
this.base = base;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
long[] h = new long[n + 1];
long[] sum = new long[n + 1];
long[] ans = new long[n + 1];
int[] parent = new int[n + 1];
ArrayList<Edge>[] tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 1; i <= n; i++) {
h[i] = fs.nextLong();
}
for (int i = 2; i <= n; i++) {
parent[i] = fs.nextInt();
}
for (int i = 2; i <= n; i++) {
int w = fs.nextInt();
tree[parent[i]].add(new Edge(i, w));
}
for (int i = n; i >= 1; i--) {
sum[i] += h[i];
sum[parent[i]] += sum[i];
}
ArrayDeque<State> stack = new ArrayDeque<>();
stack.push(new State(1, 0));
while (!stack.isEmpty()) {
State cur = stack.pop();
int u = cur.node;
long base = cur.base;
tree[u].sort(Comparator.comparingInt(edge -> edge.weight));
ans[u] = base + sum[u];
long prefix = 0;
for (Edge edge : tree[u]) {
stack.push(new State(edge.to, base + prefix + edge.weight));
prefix += sum[edge.to];
}
}
StringBuilder out = new StringBuilder();
for (int i = 1; i <= n; i++) {
if (i > 1) {
out.append(' ');
}
out.append(ans[i]);
}
System.out.println(out);
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int len = 0;
FastScanner(InputStream is) {
in = is;
}
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
long nextLong() throws IOException {
int c;
do {
c = read();
} while (c <= 32 && c >= 0);
long sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
long value = 0;
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value * sign;
}
int nextInt() throws IOException {
return (int) nextLong();
}
}
}
import sys
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
idx = 1
h = [0] + data[idx:idx + n]
idx += n
parent = [0] * (n + 1)
for i in range(2, n + 1):
parent[i] = data[idx]
idx += 1
tree = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
w = data[idx]
idx += 1
tree[parent[i]].append((w, i))
subtree_sum = [0] * (n + 1)
for i in range(n, 0, -1):
subtree_sum[i] += h[i]
subtree_sum[parent[i]] += subtree_sum[i]
ans = [0] * (n + 1)
stack = [(1, 0)]
while stack:
u, base = stack.pop()
tree[u].sort(key=lambda item: item[0])
ans[u] = base + subtree_sum[u]
prefix = 0
for w, v in tree[u]:
stack.append((v, base + prefix + w))
prefix += subtree_sum[v]
print(*ans[1:])
F. 牛魔！
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
vector<vector<int>> e(n + 1);
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
vector<int> f(n + 1), dep(n + 1);
auto dfs = [&](auto &&self, int u, int fa) -> void {
f[u] = fa;
dep[u] = dep[fa] + 1;
for (int v : e[u]) {
if (v == fa) {
continue;
}
self(self, v, u);
}
if (a[u] == 0 && dep[u] >= 3) {
a[u] ^= 1;
a[fa] ^= 1;
a[f[fa]] ^= 1;
}
};
dfs(dfs, 1, 0);
if (a[1] == 0) {
for (int v1 : e[1]) {
if (a[v1] == 0 && v1 != f[1]) {
for (int v2 : e[v1]) {
if (v2 != f[v1]) {
a[1] ^= 1;
a[v1] ^= 1;
a[v2] ^= 1;
goto done;
}
}
}
}
}
done:
int ans = accumulate(a.begin(), a.end(), 0);
cout << ans;
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int[] a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = fs.nextInt();
}
ArrayList<Integer>[] tree = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
int u = fs.nextInt();
int v = fs.nextInt();
tree[u].add(v);
tree[v].add(u);
}
int[] parent = new int[n + 1];
int[] depth = new int[n + 1];
int[] order = new int[n];
int[] stack = new int[n];
int top = 0;
int count = 0;
stack[top++] = 1;
depth[1] = 1;
while (top > 0) {
int u = stack[--top];
order[count++] = u;
for (int v : tree[u]) {
if (v == parent[u]) {
continue;
}
parent[v] = u;
depth[v] = depth[u] + 1;
stack[top++] = v;
}
}
for (int i = count - 1; i >= 0; i--) {
int u = order[i];
if (a[u] == 0 && depth[u] >= 3) {
int fa = parent[u];
a[u] ^= 1;
a[fa] ^= 1;
a[parent[fa]] ^= 1;
}
}
if (a[1] == 0) {
boolean done = false;
for (int v1 : tree[1]) {
if (a[v1] != 0 || v1 == parent[1]) {
continue;
}
for (int v2 : tree[v1]) {
if (v2 == parent[v1]) {
continue;
}
a[1] ^= 1;
a[v1] ^= 1;
a[v2] ^= 1;
done = true;
break;
}
if (done) {
break;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans += a[i];
}
System.out.println(ans);
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int len = 0;
FastScanner(InputStream is) {
in = is;
}
int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= 32 && c >= 0);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int value = 0;
while (c > 32) {
value = value * 10 + c - '0';
c = read();
}
return value * sign;
}
}
}
import sys
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
idx = 1
a = [0] + data[idx:idx + n]
idx += n
tree = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = data[idx], data[idx + 1]
idx += 2
tree[u].append(v)
tree[v].append(u)
parent = [0] * (n + 1)
depth = [0] * (n + 1)
order = []
stack = [1]
depth[1] = 1
while stack:
u = stack.pop()
order.append(u)
for v in tree[u]:
if v == parent[u]:
continue
parent[v] = u
depth[v] = depth[u] + 1
stack.append(v)
for u in reversed(order):
if a[u] == 0 and depth[u] >= 3:
fa = parent[u]
a[u] ^= 1
a[fa] ^= 1
a[parent[fa]] ^= 1
if a[1] == 0:
done = False
for v1 in tree[1]:
if a[v1] != 0 or v1 == parent[1]:
continue
for v2 in tree[v1]:
if v2 == parent[v1]:
continue
a[1] ^= 1
a[v1] ^= 1
a[v2] ^= 1
done = True
break
if done:
break
print(sum(a))
全部评论
(0) 回帖