牛客周赛145视频讲解代码
A.小红的好串
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
set<char> st(s.begin(), s.end());
cout << (st.size() == 2 ? "Yes" : "No") << '\n';
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);
String s = fs.next();
boolean[] seen = new boolean[26];
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
int x = s.charAt(i) - 'a';
if (!seen[x]) {
seen[x] = true;
cnt++;
}
}
System.out.println(cnt == 2 ? "Yes" : "No");
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private 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 {
StringBuilder sb = new StringBuilder();
int c;
do { c = read(); } while (c <= 32 && c >= 0);
while (c > 32) {
sb.append((char)c);
c = read();
}
return sb.toString();
}
}
}
import sys
s = sys.stdin.readline().strip()
print("Yes" if len(set(s)) == 2 else "No")
B.小红的好串计数
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
long long same = 0;
for (int l = 0; l < n; ) {
int r = l;
while (r < n && s[r] == s[l]) ++r;
long long len = r - l;
same += len * (len + 1) / 2;
l = r;
}
long long total = 1LL * n * (n + 1) / 2;
cout << total - same << '\n';
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();
long same = 0;
for (int l = 0; l < n; ) {
int r = l;
while (r < n && s.charAt(r) == s.charAt(l)) r++;
long len = r - l;
same += len * (len + 1) / 2;
l = r;
}
long total = 1L * n * (n + 1) / 2;
System.out.println(total - same);
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private 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 {
StringBuilder sb = new StringBuilder();
int c;
do { c = read(); } while (c <= 32 && c >= 0);
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]
same = 0
i = 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
length = j - i
same += length * (length + 1) // 2
i = j
total = n * (n + 1) // 2
print(total - same)
C.小红的染色平均数
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
string s;
cin >> s;
long long sum0 = 0, sum1 = 0;
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '0') sum0 += a[i], cnt0++;
else sum1 += a[i], cnt1++;
}
if (cnt0 == 0 || cnt1 == 0) {
cout << -1 << '\n';
return 0;
}
long long diff = sum0 * cnt1 - sum1 * cnt0;
if (diff % n != 0) cout << -1 << '\n';
else cout << llabs(diff / n) << '\n';
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();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = fs.nextLong();
String s = fs.next();
long sum0 = 0, sum1 = 0;
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '0') {
sum0 += a[i];
cnt0++;
} else {
sum1 += a[i];
cnt1++;
}
}
if (cnt0 == 0 || cnt1 == 0) {
System.out.println(-1);
return;
}
long diff = sum0 * cnt1 - sum1 * cnt0;
if (diff % n != 0) System.out.println(-1);
else System.out.println(Math.abs(diff / n));
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private 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 {
StringBuilder sb = new StringBuilder();
int c;
do { c = read(); } while (c <= 32 && c >= 0);
while (c > 32) {
sb.append((char)c);
c = read();
}
return sb.toString();
}
int nextInt() throws IOException { return Integer.parseInt(next()); }
long nextLong() throws IOException { return Long.parseLong(next()); }
}
}
import sys
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:1 + n]))
s = data[1 + n]
sum0 = sum1 = 0
cnt0 = cnt1 = 0
for x, ch in zip(a, s):
if ch == "0":
sum0 += x
cnt0 += 1
else:
sum1 += x
cnt1 += 1
if cnt0 == 0 or cnt1 == 0:
print(-1)
else:
diff = sum0 * cnt1 - sum1 * cnt0
print(-1 if diff % n else abs(diff // n))
D.小红的排列构造
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
vector<vector<int>> pos(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
pos[a[i]].push_back(i);
}
if (n % 2 == 1) {
cout << -1 << '\n';
return 0;
}
vector<int> b(n, 0), c(n, 0), usedB(n + 1, 0), usedC(n + 1, 0);
for (int v = 1; v <= n; v++) {
if ((int)pos[v].size() > 2) {
cout << -1 << '\n';
return 0;
}
if (pos[v].size() == 1) {
int i = pos[v][0];
b[i] = v;
c[i] = v;
usedB[v] = 1;
usedC[v] = 1;
} else if (pos[v].size() == 2) {
int i = pos[v][0];
b[i] = v;
usedB[v] = 1;
i = pos[v][1];
c[i] = v;
usedC[v] = 1;
}
}
vector<int> missB, missC;
for (int v = 1; v <= n; v++) {
if (!usedB[v]) missB.push_back(v);
if (!usedC[v]) missC.push_back(v);
}
int pb = 0, pc = 0;
for (int i = 0; i < n; i++) {
if (b[i] == 0) b[i] = missB[pb++];
if (c[i] == 0) c[i] = missC[pc++];
}
for (int i = 0; i < n; i++) cout << b[i] << (i + 1 == n ? '\n' : ' ');
for (int i = 0; i < n; i++) cout << c[i] << (i + 1 == n ? '\n' : ' ');
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];
ArrayList<Integer>[] pos = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) pos[i] = new ArrayList<>();
for (int i = 0; i < n; i++) {
a[i] = fs.nextInt();
pos[a[i]].add(i);
}
if ((n & 1) == 1) {
System.out.println(-1);
return;
}
int[] b = new int[n], c = new int[n];
boolean[] usedB = new boolean[n + 1], usedC = new boolean[n + 1];
for (int v = 1; v <= n; v++) {
if (pos[v].size() > 2) {
System.out.println(-1);
return;
}
if (pos[v].size() == 1) {
int i = pos[v].get(0);
b[i] = v;
c[i] = v;
usedB[v] = true;
usedC[v] = true;
} else if (pos[v].size() == 2) {
int i = pos[v].get(0);
b[i] = v;
usedB[v] = true;
i = pos[v].get(1);
c[i] = v;
usedC[v] = true;
}
}
int[] missB = new int[n], missC = new int[n];
int nb = 0, nc = 0;
for (int v = 1; v <= n; v++) {
if (!usedB[v]) missB[nb++] = v;
if (!usedC[v]) missC[nc++] = v;
}
int pb = 0, pc = 0;
for (int i = 0; i < n; i++) {
if (b[i] == 0) b[i] = missB[pb++];
if (c[i] == 0) c[i] = missC[pc++];
}
StringBuilder out = new StringBuilder();
for (int i = 0; i < n; i++) out.append(b[i]).append(i + 1 == n ? '\n' : ' ');
for (int i = 0; i < n; i++) out.append(c[i]).append(i + 1 == n ? '\n' : ' ');
System.out.print(out.toString());
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private 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 {
StringBuilder sb = new StringBuilder();
int c;
do { c = read(); } while (c <= 32 && c >= 0);
while (c > 32) {
sb.append((char)c);
c = read();
}
return sb.toString();
}
int nextInt() throws IOException { return Integer.parseInt(next()); }
}
}
import sys
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
a = data[1:]
if n % 2:
print(-1)
raise SystemExit
pos = [[] for _ in range(n + 1)]
for i, x in enumerate(a):
pos[x].append(i)
b = [0] * n
c = [0] * n
used_b = [False] * (n + 1)
used_c = [False] * (n + 1)
for v in range(1, n + 1):
if len(pos[v]) > 2:
print(-1)
raise SystemExit
if len(pos[v]) == 1:
b[pos[v][0]] = v
c[pos[v][0]] = v
used_b[v] = True
used_c[v] = True
elif len(pos[v]) == 2:
b[pos[v][0]] = v
used_b[v] = True
c[pos[v][1]] = v
used_c[v] = True
miss_b = [v for v in range(1, n + 1) if not used_b[v]]
miss_c = [v for v in range(1, n + 1) if not used_c[v]]
pb = pc = 0
for i in range(n):
if b[i] == 0:
b[i] = miss_b[pb]
pb += 1
if c[i] == 0:
c[i] = miss_c[pc]
pc += 1
print(*b)
print(*c)
E.小红的染色生成树
代码查看
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p, sz;
int comps = 0;
DSU(int n = 0) { init(n); }
void init(int n) {
p.resize(n + 1);
sz.assign(n + 1, 1);
iota(p.begin(), p.end(), 0);
comps = n;
}
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a; sz[a] += sz[b];
comps--;
return true;
}
};
struct Edge { int u, v, w; };
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<Edge> edges(m);
vector<DSU> without(3, DSU(n));
vector<int> first(3, -1);
for (int i = 0; i < m; i++) {
auto &e = edges[i];
cin >> e.u >> e.v >> e.w;
if (first[e.w] == -1) first[e.w] = i;
for (int banned = 0; banned < 3; banned++) {
if (banned != e.w) without[banned].unite(e.u, e.v);
}
}
for (int banned = 0; banned < 3; banned++) {
vector<int> colors;
for (int c = 0; c < 3; c++) if (c != banned) colors.push_back(c);
int a = colors[0], b = colors[1];
if (without[banned].comps != 1 || first[a] == -1 || first[b] == -1) continue;
DSU dsu(n);
vector<Edge> ans;
int ea = first[a], eb = first[b];
dsu.unite(edges[ea].u, edges[ea].v);
ans.push_back(edges[ea]);
if (dsu.unite(edges[eb].u, edges[eb].v)) ans.push_back(edges[eb]);
for (const auto &e : edges) {
if (e.w == banned) continue;
if (dsu.unite(e.u, e.v)) ans.push_back(e);
}
if ((int)ans.size() == n - 1) {
for (auto &e : ans) cout << e.u << ' ' << e.v << '\n';
return 0;
}
}
cout << -1 << '\n';
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static class Edge {
int u, v, w;
Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; }
}
static class DSU {
int[] p, sz;
int comps;
DSU(int n) { init(n); }
void init(int n) {
p = new int[n + 1];
sz = new int[n + 1];
for (int i = 1; i <= n; i++) { p[i] = i; sz[i] = 1; }
comps = n;
}
int find(int x) {
while (p[x] != x) {
p[x] = p[p[x]];
x = p[x];
}
return x;
}
boolean unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
p[b] = a; sz[a] += sz[b];
comps--;
return true;
}
}
static int n, m;
static Edge[] edges;
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
n = fs.nextInt();
m = fs.nextInt();
edges = new Edge[m];
DSU[] without = new DSU[3];
for (int i = 0; i < 3; i++) without[i] = new DSU(n);
int[] first = {-1, -1, -1};
for (int i = 0; i < m; i++) {
int u = fs.nextInt(), v = fs.nextInt(), w = fs.nextInt();
edges[i] = new Edge(u, v, w);
if (first[w] == -1) first[w] = i;
for (int banned = 0; banned < 3; banned++) {
if (banned != w) without[banned].unite(u, v);
}
}
for (int banned = 0; banned < 3; banned++) {
StringBuilder ans = build(banned, without[banned], first);
if (ans != null) {
System.out.print(ans.toString());
return;
}
}
System.out.println(-1);
}
static StringBuilder build(int banned, DSU pairDsu, int[] firstEdge) {
int first = -1, second = -1;
for (int c = 0; c < 3; c++) {
if (c == banned) continue;
if (first == -1) first = c;
else second = c;
}
if (pairDsu.comps != 1) return null;
int eFirst = firstEdge[first], eSecond = firstEdge[second];
if (eFirst == -1 || eSecond == -1) return null;
DSU dsu = new DSU(n);
ArrayList<Edge> ans = new ArrayList<>();
dsu.unite(edges[eFirst].u, edges[eFirst].v);
ans.add(edges[eFirst]);
if (dsu.unite(edges[eSecond].u, edges[eSecond].v)) {
ans.add(edges[eSecond]);
}
for (Edge e : edges) {
if (e.w == banned) continue;
if (dsu.unite(e.u, e.v)) ans.add(e);
}
if (ans.size() == n - 1) {
StringBuilder out = new StringBuilder();
for (Edge e : ans) out.append(e.u).append(' ').append(e.v).append('\n');
return out;
}
return null;
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private 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 val = 0;
while (c > 32) {
val = val * 10 + (c - '0');
c = read();
}
return val * sign;
}
}
}
import sys
data = list(map(int, sys.stdin.buffer.read().split()))
n, m = data[0], data[1]
edges = []
p = 2
for _ in range(m):
edges.append((data[p], data[p + 1], data[p + 2]))
p += 3
class DSU:
def __init__(self, n):
self.p = list(range(n + 1))
self.sz = [1] * (n + 1)
self.comps = n
def find(self, x):
while self.p[x] != x:
self.p[x] = self.p[self.p[x]]
x = self.p[x]
return x
def unite(self, a, b):
a = self.find(a)
b = self.find(b)
if a == b:
return False
if self.sz[a] < self.sz[b]:
a, b = b, a
self.p[b] = a
self.sz[a] += self.sz[b]
self.comps -= 1
return True
without = [DSU(n) for _ in range(3)]
first_edge = [None] * 3
for u, v, w in edges:
if first_edge[w] is None:
first_edge[w] = (u, v, w)
for banned in range(3):
if banned != w:
without[banned].unite(u, v)
def build(banned):
colors = [c for c in range(3) if c != banned]
first, second = colors
if without[banned].comps != 1:
return None
e_first = first_edge[first]
e_second = first_edge[second]
if e_first is None or e_second is None:
return None
dsu = DSU(n)
ans = []
u, v, _ = e_first
dsu.unite(u, v)
ans.append((u, v))
u, v, _ = e_second
if dsu.unite(u, v):
ans.append((u, v))
for u, v, w in edges:
if w == banned:
continue
if dsu.unite(u, v):
ans.append((u, v))
if len(ans) == n - 1:
return ans
return None
for banned in range(3):
ans = build(banned)
if ans is not None:
sys.stdout.write("\n".join(f"{u} {v}" for u, v in ans) + "\n")
raise SystemExit
print(-1)
F.小红的好串构造
代码查看
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
int t = k - (n - 1);
string s;
s.append(t, 'a');
s.push_back('b');
s.push_back('a');
s.append(n - t - 2, 'c');
cout << s << '\n';
}
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 T = fs.nextInt();
StringBuilder out = new StringBuilder();
while (T-- > 0) {
int n = fs.nextInt();
int k = fs.nextInt();
int t = k - (n - 1);
StringBuilder s = new StringBuilder();
for (int i = 0; i < t; i++) s.append('a');
s.append('b');
s.append('a');
for (int i = 0; i < n - t - 2; i++) s.append('c');
out.append(s).append('\n');
}
System.out.print(out.toString());
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { in = is; }
private 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 {
StringBuilder sb = new StringBuilder();
int c;
do { c = read(); } while (c <= 32 && c >= 0);
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.buffer.read().split()
T = int(data[0])
ans = []
p = 1
for _ in range(T):
n = int(data[p])
k = int(data[p + 1])
p += 2
t = k - (n - 1)
ans.append("a" * t + "ba" + "c" * (n - t - 2))
print("\n".join(ans))