Codeforces#811 Div3 题解
D. Color with Occurrences
You are given some text t and a set of n strings $s_1, s_2, \dots, s_n$ .
In one step, you can choose any occurrence of any string $s_i$ in the text $t$ and color the corresponding characters of the text in red. For example, if $t=\texttt{bababa}$ and $s_1=\texttt{ba}$ , $s_2=\texttt{aba}$ , you can get $t=\color{red}{\texttt{ba}}$ $\texttt{baba}$ , $t=\texttt{b}\color{red}{\texttt{aba}}$ $\texttt{ba}$ or $t=\texttt{bab}$ $\color{red}{\texttt{aba}}$ in one step.
You want to color all the letters of the text t in red. When you color a letter in red again, it stays red.
In the example above, three steps are enough:
- Let’s color $t[2 \dots 4]=s_2=\texttt{aba}$ in red, we get $t=\texttt{b}\color{red}{\texttt{aba}}$ $\texttt{ba}$ ;
- Let’s color $t[1 \dots 2]=s_1=\texttt{ba}$ in red, we get $t=\color{red}{\texttt{baba}}$ $\texttt{ba}$ ;
- Let’s color $t[4 \dots 6]=s_2=\texttt{aba}$ in red, we get $t=\color{red}{\texttt{bababa}}$ . Each string $s_i$ can be applied any number of times (or not at all). Occurrences for coloring can intersect arbitrarily.
Determine the minimum number of steps needed to color all letters t in red and how to do it. If it is impossible to color all letters of the text t in red, output -1.
Input
The first line of the input contains an integer $q (1 \le q \le 100)$ —the number of test cases in the test.
The descriptions of the test cases follow.
The first line of each test case contains the text $t (1 \le |t| \le 100)$ , consisting only of lowercase Latin letters, where $|t|$ is the length of the text t.
The second line of each test case contains a single integer $n (1 \le n \le 10)$ — the number of strings in the set.
This is followed by n lines, each containing a string $s_i (1 \le |s_i| \le 10)$ consisting only of lowercase Latin letters, where $|s_i|$ — the length of string $s_i$ .
Output
For each test case, print the answer on a separate line.
If it is impossible to color all the letters of the text in red, print a single line containing the number -1.
Otherwise, on the first line, print the number m — the minimum number of steps it will take to turn all the letters t red.
Then in the next m lines print pairs of indices: $w_j$ and $p_j (1 \le j \le m)$ , which denote that the string with index $w_j$ was used as a substring to cover the occurrences starting in the text t from position $p_j$ . The pairs can be output in any order.
If there are several answers, output any of them.
解法一
题目核心其实是一个区间覆盖的问题，每个 $s_i$ 在 $t$ 中能匹配上的部分就是一个区间，题目求的就是用最少的区间去覆盖整个 $t$。所以我们按照贪心的思路，从$t_0$开始找到能overlap右边界的最大区间，然后更新右边界，最后覆盖完所有的区间，得到的就是最少的覆盖次数。在过程中记录下区间信息，输出步骤即可。
代码实现如下：
import java.util.*;
import java.io.*;
// AtCoder/AcWing 提交上面部分即可，CF需要将JavaMain移到上面然后提交
public class D {
public static void main(String[] args) throws Exception {
// 输入重定向，通过jvm参数判断环境
if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
System.setIn(new FileInputStream("./input.txt"));
}
new Main().main(args);
}
}
class Main {
public static void main(String[] args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int Q = read(br)[0];
while (Q-- > 0) {
String t = br.readLine();
int n = read(br)[0];
// match[i]: t第i个位置最远能匹配到哪里
var match = new int[t.length()][2];
String[] s = new String[n];
for (int i = 0; i < n; i++) {
s[i] = br.readLine();
// 预处理每个s[i]在t中能匹配的位置
for (int j = 0; j < t.length(); j++) {
var flag = true;
for (int k = 0; k < s[i].length(); k++) {
if (j + k >= t.length() || t.charAt(j+k) != s[i].charAt(k)) {
flag = false;
break;
}
}
if (!flag) continue;
if (match[j][1] <= s[i].length() + j) {
match[j] = new int[]{i, s[i].length() + j};
}
}
}
// 下一次开始匹配的位置
var last = 0;
var flag = true;
var cnt = 0;
var lis = new ArrayList<String>();
while (last < t.length()) {
var temp = last;
int w = 0, p = 0;
for (int i = 0; i <= temp; i++) {
if (match[i][1] >= last) {
last = match[i][1];
w = match[i][0]+1;
p = i+1;
}
}
// 没有能cover last的区间
if (last == temp) {
flag = false;
break;
}
cnt++;
lis.add(w + " " + p);
}
if (flag) {
out.println(cnt);
lis.stream().forEach(out::println);
} else {
out.println(-1);
}
}
out.flush();
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
E. Add Modulo 10
You are given an array of n integers $a_1, a_2, \dots, a_n$
You can apply the following operation an arbitrary number of times:
- select an index $i (1 \le i \le n)$ and replace the value of the element $a_i$ with the value $a_i + (a_i \bmod 10)$, where $a_i \bmod 10$ is the remainder of the integer dividing $a_i$ by $10$.
For a single index (value $i$), this operation can be applied multiple times. If the operation is applied repeatedly to the same index, then the current value of $a_i$ is taken into account each time. For example, if $a_i=47$ then after the first operation we get $a_i=47+7=54$, and after the second operation we get $a_i=54+4=58$.
Check if it is possible to make all array elements equal by applying multiple (possibly zero) operations.
For example, you have an array $[6, 11]$.
- Let’s apply this operation to the first element of the array. Let’s replace $a_1 = 6$ with $a_1 + (a_1 \bmod 10) = 6 + (6 \bmod 10) = 6 + 6 = 12$. We get the array $[12, 11]$.
- Then apply this operation to the second element of the array. Let’s replace $a_2 = 11$ with $a_2 + (a_2 \bmod 10) = 11 + (11 \bmod 10) = 11 + 1 = 12$. We get the array $[12, 12]$.
Thus, by applying 2 operations, you can make all elements of an array equal.
Input
The first line contains one integer $t (1 \le t \le 10^4)$ — the number of test cases. What follows is a description of each test case.
The first line of each test case contains one integer $n (1 \le n \le 2 \cdot 10^5)$ — the size of the array.
The second line of each test case contains n integers $a_i (0 \le a_i \le 10^9)$ — array elements.
It is guaranteed that the sum of n over all test cases does not exceed $2 \cdot 10^5$.
Output
For each test case print:
- YES if it is possible to make all array elements equal;
- NO otherwise.
You can print YES and NO in any case (for example, the strings yEs, yes, Yes and YES will be recognized as a positive answer) .
解法一
找规律，题目大意是给定一组数组，尝试替换$a_i$为$a_i+(a_i \bmod 10)$，问能否是的数组所有元素相等。
我们可以将元素替换序列都列出来，然后找规律，进行分组，具体见代码：
import java.util.*;
import java.io.*;
// AtCoder/AcWing 提交上面部分即可，CF需要将JavaMain移到上面然后提交
public class E {
public static void main(String[] args) throws Exception{
// 输入重定向，通过jvm参数判断环境
if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
System.setIn(new FileInputStream("./input.txt"));
}
new Main().main(args);
}
}
class Main {
// 1 2 4 8 16 22 24 28 36 42 44 ...
// 3 6 12 14 18 26 32 34 38 46 52 ...
// 5 10 10 10 ....
// 15 20 20 20 ...
// 7 14 18 26 ....
// 9 18
public static void main(String[] args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = read(br)[0];
// 分析发现20为一个循环，我们将20以内的元素进行分组，两组元素序列完全平行，无法相交
// 所以如果元素 mod 20在同一组中，那么就一定可以转化成一样的，否则一定不行
// 除此之外，需要额外注意5和0结尾的元素，它们最多只能转化一次，所以如果有5/0结尾的元素，那么所有元素都必须是5/0结尾，且5结尾经过转换后与0结尾相同
var s1 = new HashSet<>();
s1.add(1); s1.add(2); s1.add(4); s1.add(8); s1.add(13); s1.add(16); s1.add(17); s1.add(19);
var s2 = new HashSet<>();
s2.add(3); s2.add(6); s2.add(7); s2.add(9); s2.add(11); s2.add(12); s2.add(14); s2.add(18);
while (T-- > 0) {
read(br);
var a = read(br);
var set5 = new HashSet<Integer>();
var cnt5 = 0;
var ins1 = false;
var ins2 = false;
for (Integer v : a) {
if (v%10 == 5 || v%10 == 0) {
cnt5++;
set5.add(v + v%10);
}
if (s1.contains(v%20)) {
ins1 = true;
}
if (s2.contains(v%20)) {
ins2 = true;
}
}
// 既有s1中的元素，又有s2中的元素 || 有5/0结尾的但是不全是 || 全是5/0结尾的，但是转换后不想等
if ((ins2 && ins1) || (cnt5 != 0 && cnt5 != a.length) || (cnt5 == a.length && set5.size() != 1)) {
out.println("No");
} else {
out.println("Yes");
}
}
out.flush();
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
G. Path Prefixes
You are given a rooted tree. It contains $n$ vertices, which are numbered from $1$ to $n$. The root is the vertex $1$.
Each edge has two positive integer values. Thus, two positive integers $a_j$ and $b_j$ are given for each edge.
Output $n-1$ numbers $r_2, r_3, \dots, r_n$, where $r_i is defined as follows.
Consider the path from the root (vertex $1$) to $i (2 \le i \le n)$. Let the sum of the costs of $a_j$ along this path be $A_i$. Then $r_i$ is equal to the length of the maximum prefix of this path such that the sum of $b_j$ along this prefix does not exceed $A_i$.
… 题目太长，懒得copy，去看原题吧
解法一
dfs栈上二分，如果这题放在D或者E我肯定能写出来，放在后面并且题目这么长，让人有点畏惧，不过说到底还是太菜了。
import java.util.*;
import java.io.*;
// AtCoder/AcWing 提交上面部分即可，CF需要将JavaMain移到上面然后提交
public class G {
public static void main(String[] args) throws Exception{
// 输入重定向，通过jvm参数判断环境
if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
System.setIn(new FileInputStream("./input.txt"));
}
new Main().main(args);
}
}
class Main {
static int idx;
static int[] e, ne, h, wa, wb;
static int si;
static long[] stack;
static int[] res;
public static void add(int a, int b, int i, int j) {
e[idx] = b; ne[idx] = h[a];
wa[idx] = i; wb[idx] = j;
h[a] = idx++;
}
public static void main(String[] args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = read(br)[0];
while (T-- > 0) {
int N = read(br)[0];
idx = 0;
h = new int[N+1]; Arrays.fill(h, -1);
e = new int[N+1]; ne = new int[N+1];
wa = new int[N+1]; wb = new int[N+1];
stack = new long[N+1];
si = 0;
res = new int[N+1];
for (int i = 2; i <= N; i++) {
int[] t = read(br);
add(t[0], i, t[1], t[2]);
}
dfs(1, 0, 0);
for (int i = 2; i <= N; i++) {
out.print(res[i] + " ");
}
out.println();
}
out.flush();
}
public static void dfs(int x, long suma, long sumb) {
stack[si++] = sumb;
// 二分找suma
int left = 0, right = si-1;
while (left <= right) {
int mid = left + (right-left)/2;
if (stack[mid] <= suma) {
res[x] = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
for (int i = h[x]; i != -1; i = ne[i]) {
dfs(e[i], suma+wa[i], sumb+wb[i]);
}
// 出栈
si--;
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}
解法二
倍增的做法，学习下
import java.util.*;
import java.io.*;
// AtCoder/AcWing 提交上面部分即可，CF需要将JavaMain移到上面然后提交
public class G_2 {
public static void main(String[] args) throws Exception{
// 输入重定向，通过jvm参数判断环境
if (args.length > 0 && "Resolmi_DEBUG".equals(args[0])) {
System.setIn(new FileInputStream("./input.txt"));
}
new Main().main(args);
}
}
class Main {
static int idx;
static int[] e, ne, h, wa, wb;
static int[] res;
// fa[i][j]，节点i向上跳2^j的节点
static int[][] fa;
// fsb[i][j]，节点i向上跳2^j的节点sumb总和
static long[][] fsb;
static int[] dep;
static long[] suma, sumb;
public static void add(int a, int b, int i, int j) {
e[idx] = b; ne[idx] = h[a];
wa[idx] = i; wb[idx] = j;
h[a] = idx++;
}
// 倍增做法
public static void main(String[] args) throws Exception {
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = read(br)[0];
while (T-- > 0) {
int N = read(br)[0];
idx = 0;
h = new int[N+1]; Arrays.fill(h, -1);
e = new int[N+1]; ne = new int[N+1];
wa = new int[N+1]; wb = new int[N+1];
suma = new long[N+1]; sumb = new long[N+1];
dep = new int[N+1];
// fa[i][j]: i向上跳2^j的节点
fa = new int[N+1][31];
fsb = new long[N+1][31];
for (int i = 2; i <= N; i++) {
int[] t = read(br);
add(t[0], i, t[1], t[2]);
}
// 构建倍增数组
dfs(1);
for (int i = 2; i <= N; i++) {
int res = dep[i];
if (suma[i] < sumb[i]) {
// 向上走大于等于t距离的第一个
long t = sumb[i]-suma[i];
int x = i;
for (int k = 30; k >= 0; k--) {
if (fsb[x][k] <= t) {
t -= fsb[x][k];
x = fa[x][k];
res = dep[x];
}
}
// 找不到sumb刚好相差t的节点，再往上走一步
if (t > 0) res--;
}
out.print(res+" ");
}
out.println();
}
out.flush();
}
public static void dfs(int root) {
for (int i = 1; i < 31; i++) {
fa[root][i] = fa[fa[root][i-1]][i-1];
// root跳2^i = root跳到2^(i-1) + 2^(i-1)到2^i
fsb[root][i] = fsb[root][i-1] + fsb[fa[root][i-1]][i-1];
}
for (int i = h[root]; i != -1; i = ne[i]) {
int t = e[i];
suma[t] = suma[root] + wa[i];
sumb[t] = sumb[root] + wb[i];
dep[t] = dep[root] + 1;
fa[t][0] = root;
fsb[t][0] = wb[i];
dfs(t);
}
}
public static int[] read(BufferedReader br) throws Exception {
return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
}
}