前言
生于生时，亡于亡刻。遵从自心，尽人之事。
整体评价
终于等来了侧重面试的比赛，而且题量刚刚好，不超纲，不涉及算法竞赛。
第一场的比赛，感觉题目出的比较典，A是简单模拟，B则是计数题，C则是贪心思路，D是经典的同余DP。
唯一吐槽的是，牛客好像当前只JDK 8, 用不了var.
欢迎关注
珂朵莉 牛客周赛专栏
珂朵莉 牛客小白月赛专栏
A. 游游画U
找规律题吧，就是找到底托，中间对等分开，然后往两边靠齐。
而N，则限定了最终图的长宽高，还有就是‘*’的长度
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
// 定义结果的画布
char[][] res = new char[4 * n][4 * n];
// 前面的3*n行
for (int i = 0; i < 3 * n; i++) {
Arrays.fill(res[i], '.');
for (int j = 0; j < n; j++) {
res[i][j] = res[i][4*n - 1 - j] = '*';
}
}
// 最下面的n行
for (int i = 3 * n; i < 4 * n; i++) {
int offset = i + 1 - 3 * n;
Arrays.fill(res[i], '.');
for (int j = 0; j < n; j++) {
res[i][offset + j] = res[i][4 * n - 1 - offset - j] = '*';
}
}
// 输出内容
for (int i = 0; i < 4 * n; i++) {
System.out.println(new String(res[i]));
}
}
}
B. 游游的数组染色
先按同值进行分类，然后内部按颜色进行计数
m
a
p
[
v
a
l
u
e
]
[
c
o
l
o
r
]
{map[value][color]}
map[value][color]
那最终的结果为
∑
v
i
∑
c
j
∈
C
m
a
p
[
v
i
]
[
c
j
]
∗
(
∑
k
∈
C
m
a
p
[
v
i
]
[
c
k
]
−
m
a
p
[
v
i
]
[
c
j
]
)
\sum_{v_i} \sum_{c_j \in C} map[v_i][c_j] * (\sum_{k\in C} map[v_i][c_k] - map[v_i][c_j])
∑vi∑cj∈Cmap[vi][cj]∗(∑k∈Cmap[vi][ck]−map[vi][cj])
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) {
AReader sc = new AReader();
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
char[] str = sc.next().toCharArray();
Map
for (int i = 0; i < n; i++) {
if (!range.containsKey(arr[i])) {
range.put(arr[i], new TreeMap<>());
}
range.get(arr[i]).merge(str[i], 1, Integer::sum);
}
long ans = 0;
for (Map.Entry
TreeMap
long acc = 0;
for (Map.Entry
acc += kv2.getValue();
}
for (Map.Entry
ans += (long)(acc - kv2.getValue()) * kv2.getValue();
}
}
System.out.println(ans / 2);
}
static
class AReader {
private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
private StringTokenizer tokenizer = new StringTokenizer("");
private String innerNextLine() {
try {
return reader.readLine();
} catch (IOException ex) {
return null;
}
}
public boolean hasNext() {
while (!tokenizer.hasMoreTokens()) {
String nextLine = innerNextLine();
if (nextLine == null) {
return false;
}
tokenizer = new StringTokenizer(nextLine);
}
return true;
}
public String nextLine() {
tokenizer = new StringTokenizer("");
return innerNextLine();
}
public String next() {
hasNext();
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}
#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
string s;
cin >> s;
map
for (int i = 0; i< n; i++) {
char c = s[i];
if (c == 'B') {
h2[arr[i]]++;
} else {
h1[arr[i]]++;
}
}
long long res = 0LL;
for (auto iter = h1.begin(); iter != h1.end(); iter++) {
if (h2.find(iter->first) != h2.end()) {
res += (long long)h2[iter->first] * (iter->second);
}
}
cout << res << endl;
return 0;
}
C. 游游的交换字符
分类讨论，即构造1开头的串，和0开头的串，两者那个代价小。
一旦确定分头，实际上代价就定下来，重要的是如何计算。
比如当前串，以及构建好了’01…1’, 你要寻找下一个‘0’， 则需要多少代价呢？
这个时候，就是从原串中，下一个‘0’之前有几个’1’呢
同理，‘1’也是统计前置几个‘0’
那这个动态有变动的统计0-1该怎么处理呢？
我们可以尝试引入 0-1 树状数组
就是有一个单独统计‘1’的位置的树状数组，一个统计‘0’的树状数组
前置的01构建完后，就删掉对应的01位置即可。
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static class BIT {
int n;
int[] arr;
public BIT(int n) {
this.n = n;
this.arr = new int[n + 1];
}
void update(int p, int d) {
while (p <= n) {
arr[p] += d;
p += p & -p;
}
}
int query(int p) {
int res = 0;
while (p > 0) {
res += arr[p];
p -= p & -p;
}
return res;
}
}
// *)
public static long solve(char[] buf, char s) {
// 找到最近的0
int n = buf.length;
BIT bit0 = new BIT(n);
BIT bit1 = new BIT(n);
List
List
for (int i = 0; i < n; i++) {
if (buf[i] == '0') {
list0.add(i + 1);
bit0.update(i + 1, 1);
} else {
list1.add(i + 1);
bit1.update(i + 1, 1);
}
}
long ans = 0l;
if (s == '0') {
if (list0.size() < list1.size()) return Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
int idx = list0.get(i/2);
int delta = bit1.query(idx);
bit0.update(idx, -1);
ans += delta;
} else {
int idx = list1.get(i/2);
int delta = bit0.query(idx);
bit1.update(idx, -1);
ans += delta;
}
}
} else {
if (list1.size() < list0.size()) return Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
int idx = list1.get(i/2);
int delta = bit0.query(idx);
bit1.update(idx, -1);
ans += delta;
} else {
int idx = list0.get(i/2);
int delta = bit1.query(idx);
bit0.update(idx, -1);
ans += delta;
}
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
char[] buf = sc.next().toCharArray();
long res = Math.min(solve(buf.clone(), '0'), solve(buf.clone(), '1'));
System.out.println(res);
}
}
不过这个解法，应该是写复杂了。
直接贪心即可
就是
∑
i
=
0
i
=
(
n
+
1
)
/
2
(
c
u
r
r
e
n
t
i
−
e
x
p
e
c
t
i
)
{\sum_{i=0}^{i=(n+1)/2} (current_i - expect_i)}
∑i=0i=(n+1)/2(currenti−expecti)
c
u
r
r
e
n
t
i
是第
i
个
1
所在的位子，
e
x
p
e
c
t
i
是被期望的位子
current_i是第i个1所在的位子，expect_i是被期望的位子
currenti是第i个1所在的位子，expecti是被期望的位子
import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
// *)
public static long solve(char[] buf, char s) {
// 找到最近的0
int n = buf.length;
List
List
for (int i = 0; i < n; i++) {
if (buf[i] == '0') {
list0.add(i);
} else {
list1.add(i);
}
}
long ans = 0l;
if (s == '0') {
if (list0.size() < list1.size()) return Long.MAX_VALUE;
for (int i = 0; i < list0.size(); i++) {
ans += Math.abs(2 * i - list0.get(i));
}
} else {
if (list1.size() < list0.size()) return Long.MAX_VALUE;
for (int i = 0; i < list1.size(); i++) {
ans += Math.abs(2 * i - list1.get(i));
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
char[] buf = sc.next().toCharArray();
long res = Math.min(solve(buf.clone(), '0'), solve(buf.clone(), '1'));
System.out.println(res);
}
}
#include
using namespace std;
struct FastIO {
FastIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
}_fastIo;
int main() {
string s;
cin >> s;
int n = s.length();
vector
for (int i = 0; i < n; i++) {
if (s[i] == '0') list0.push_back(i);
}
long long cost = 0x3f3f3f3f;
if (n % 2 == 0) {
if (list0.size() == n / 2) {
long long tmp1 = 0, tmp2 = 0;
for (int i = 0; i < n / 2; i++) {
tmp1 += abs(list0[i] - (i * 2));
tmp2 += abs(list0[i] - (i * 2 + 1));
}
cost = min(tmp1, tmp2);
}
} else {
if (list0.size() == n / 2 + 1) {
long long tmp1 = 0;
for (int i = 0; i < n / 2 + 1; i++) {
tmp1 += abs(list0[i] - (i * 2));
}
cost = tmp1;
} else if (list0.size() == n / 2) {
long long tmp2 = 0;
for (int i = 0; i < n / 2; i++) {
tmp2 += abs(list0[i] - (i * 2 + 1));
}
cost = tmp2;
}
}
cout << cost << endl;
return 0;
}
D. 游游的9的倍数
经典的同余DP
因为求的是9的倍数，而数字串前缀
S
i
=
a
0
a
1
.
.
.
a
i
=
b
0
∗
9
x
+
b
1
∗
9
x
−
1
.
.
.
+
b
i
∗
9
0
S_i = a_0a_1...a_i = b_0 * 9^x + b_1 * 9^{x-1}... + b_i * 9^0
Si=a0a1...ai=b0∗9x+b1∗9x−1...+bi∗90
那
S
i
a
i
+
1
=
10
∗
b
0
∗
9
x
+
10
∗
b
1
∗
9
x
−
1
.
.
.
+
10
∗
b
i
∗
9
0
+
a
i
+
1
=
10
∗
b
i
+
a
i
+
1
S_ia_{i+1} = 10 * b_0 * 9^x + 10 * b_1 * 9^{x-1}... + 10 * b_i * 9^0 + a_{i+1} = 10 * b_i + a_{i+1}
Siai+1=10∗b0∗9x+10∗b1∗9x−1...+10∗bi∗90+ai+1=10∗bi+ai+1
所以我们令
o
p
t
[
i
]
[
j
]
,
前
i
元素中，构建对
9
余数为
j
的总个数
opt[i][j], 前i元素中，构建对9余数为j的总个数
opt[i][j],前i元素中，构建对9余数为j的总个数
状态转移为
o
p
t
[
i
+
1
]
[
(
j
∗
10
+
a
i
+
1
)
%
9
]
=
o
p
t
[
i
]
[
(
j
∗
10
+
a
i
+
1
)
%
9
]
+
o
p
t
[
i
]
[
j
]
{opt[i+1][(j*10+a_{i+1}) \% 9] = opt[i][(j*10+a_{i+1})\%9] + opt[i][j]}
opt[i+1][(j∗10+ai+1)%9]=opt[i][(j∗10+ai+1)%9]+opt[i][j]
当然这边对空集合的处理，有个小技巧，就是单独加1
o
p
t
[
i
+
1
]
[
a
i
+
1
%
9
]
+
=
1
opt[i+1][a_{i+1}\%9] += 1
opt[i+1][ai+1%9]+=1
可以借助滚动数组来优化DP的空间
复杂度分析，时间
O
(
9
∗
n
)
O(9*n)
O(9∗n), 空间复杂度为
O
(
20
)
O(20)
O(20)
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
char[] buf = sc.next().toCharArray();
long mod = 10_0000_0007l;
long[][] opt = new long[2][9];
opt[0][0] = 0l;
int prev = 0, next = 1;
for (int i = 0; i < buf.length; i++) {
int p = buf[i] - '0';
// 添加/不添加
Arrays.fill(opt[next], 0);
for (int j = 0; j < 9; j++) {
opt[next][j] = opt[prev][j];
}
for (int j = 0; j < 9; j++) {
opt[next][(j * 10 + p) % 9] += opt[prev][j];
opt[next][(j * 10 + p) % 9] %= mod;
}
opt[next][p % 9] = (opt[next][p % 9] + 1) % mod;
prev = 1 - prev;
next = 1 - next;
}
System.out.println(((opt[prev][0]) % mod + mod) % mod);
}
}
#include
using namespace std;
using int64 = long long;
int main() {
string s;
cin >> s;
int64 mod = 1'000'000'000 + 7;
int64 dp[2][9];
memset(dp[0], 0, sizeof(dp[0]));
int prev = 0, next = 1;
for (int i = 0; i < s.length(); i++) {
memset(dp[next], 0, sizeof(dp[next]));
char c = s[i];
int d = c - '0';
for (int j = 0; j < 9; j++) {
dp[next][j] = (dp[next][j] + dp[prev][j]) % mod;
dp[next][(j + d) % 9] = (dp[next][(j + d) % 9] + dp[prev][j]) % mod;
}
dp[next][d % 9] = (dp[next][d % 9] + 1) % mod;
prev = 1 - prev;
next = 1 - next;
}
cout << dp[prev][0] << endl;
return 0;
}
如果9是个变量k，那其实也是同一种套路。
如果此题不用DP，能否解呢? 感觉有，因为9做为除数比较特殊，它打破了字符串的顺序限制。
写在最后
没有绝对的善意，关切的目光中也会掺杂恶意的期待。
参考链接
您阅读本篇文章共花了：
发表评论