# 牛客周赛 Round 20 解题报告 | 珂学家 | 状压DP/矩阵幂优化 + 前缀和的前缀和

https://ac.nowcoder.com/acm/contest/69695/A

# 整体评价

## A. 赝品

import java.io.*;
import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));

int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}

// 获取数组的最大值
int maxValue = Arrays.stream(arr).max().getAsInt();
// 过滤最大值，并计数
System.out.println(Arrays.stream(arr).filter(x -> x != maxValue).count());
}

}


## B. 小红的01连续段

import java.io.*;
import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
String s = sc.next();

int res = 0;
int s0 = 0, s1 = 0;
for (char c: s.toCharArray()) {
if (c == '0') {
s0++;
s1 = 0;
} else if (c == '1') {
s1++;
s0 = 0;
} else {
// 遇到？号
s0++;
s1++;
}
res = Math.max(res, Math.max(s0, s1));
}
System.out.println(res);
}

}


## C. 小红的01串构造

111000100

110001100

import java.io.*;
import java.util.*;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt(), k = sc.nextInt(), t = sc.nextInt();

if (k > n || k - 1 < t) {
System.out.println(-1);
} else {
int k1 = t + 1;
int k2 = k - t - 1;
if (k1 + k2 * 2 <= n) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < k1; i++) sb.append("1");
for (int i = 0; i < k2; i++) sb.append("01");
for (int i = k1 + k2 * 2; i < n; i++) sb.append("0");
System.out.println(sb);
} else {
System.out.println(-1);
}
}
}

}


## D. 小红的数位删除

### 1. 二进制枚举

• 从大到小枚举
• 引入剪枝
import java.io.*;
import java.util.*;
import java.util.function.BiFunction;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(new BufferedInputStream(System.in));
char[] astr = sc.next().toCharArray();
char[] bstr = sc.next().toCharArray();

int inf = Integer.MAX_VALUE;
int n1 = astr.length, n2 = bstr.length;
int ans = inf;

BiFunction<Integer, char[], Integer> calculate = (s, str) -> {
int val = 0;
for (int t = 0; t < str.length; t++) {
if ((s & (1 << t)) != 0) {
val = val * 10 + (str[t] - '0');
}
}
return val;
};

for (int i = (1 << n1)  - 1; i > 0; i--) {
int r1 = n1 - Integer.bitCount(i);
if (r1 >= ans) continue;

int a = calculate.apply(i, astr);
if (a == 0) continue;

for (int j = (1 << n2) - 1; j > 0; j--) {
int r2 = n2 - Integer.bitCount(j);
if (r1 + r2 >= ans) continue;
int b = calculate.apply(j, bstr);
if (b == 0) continue;
if (a % b == 0 || b % a == 0) {
ans = Math.min(ans, r1 + r2);
}
}
}
System.out.println(ans == inf ? -1 : ans);

}

}



## E. 小红的漂亮串

### 1. 正向状压解

• 0, any是1,2,3,4以外的所有状态
• 1, 以r字母结尾
• 2，以d字母结尾
• 3，以re字母结尾
• 4，以de字母结尾

Q: 子串不包含‘der’

Q: 需要包含至少一个‘red’

DP递推的话，以下两种都可以

• 填表法
• 刷表法

import java.io.BufferedInputStream;
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();

// any
// r, d
// re, de,
long mod = 10_0000_0007l;

// red, der
long[][] dp = new long[2][5];
dp[0][0] = 24;
dp[0][1] = dp[0][2] = 1;

for (int i = 1; i < n; i++) {
long[][] dp2 = new long[2][5];

// 不包含red字符串(在本身的圈子内转移)
dp2[0][0] = (dp[0][0] * 24 % mod + dp[0][1] * 23 % mod + dp[0][2] * 23 % mod + dp[0][3] * 24 % mod + dp[0][4] * 24 % mod) % mod;
dp2[0][1] = (dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3]) % mod;
dp2[0][2] = (dp[0][0] + dp[0][1] + dp[0][2] + dp[0][4]) % mod;
dp2[0][3] = dp[0][1];
dp2[0][4] = dp[0][2];

// 包含red字符串(在本身的圈子内转移)
dp2[1][0] = (dp[1][0] * 24 % mod + dp[1][1] * 23 % mod + dp[1][2] * 23 % mod + dp[1][3] * 24 % mod + dp[1][4] * 24 % mod) % mod;
dp2[1][1] = (dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3]) % mod;
dp2[1][2] = (dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4]) % mod;
dp2[1][3] = dp[1][1];
dp2[1][4] = dp[1][2];

// 非常俏皮的阶级跃迁(最特别)，单独拎出来
dp2[1][2] = (dp2[1][2] + dp[0][3]) % mod;

dp = dp2;
}

// 只累加包含red字符串的状态
long res = 0;
for (int i = 0; i < 5; i++) {
res += dp[1][i];
res %= mod;
}
System.out.println(res);
}

}


### 2. 容斥状压解

• 求解不存在der的字符串总个数S1
• 求解同时不存在der，red的字符串总个数S2
• S1 - S2, 即为不存在der，但是存在red的字符串总方案数

### 3. 矩阵幂优化

import java.io.BufferedInputStream;
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();

long mod = 10_0000_0007l;

long[][] translate = new long[][] {
{24, 23, 23, 24, 24, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 24, 23, 23, 24, 24},
{0, 0, 0, 0, 0, 1, 1, 1, 1, 0},
{0, 0, 0, 1, 0, 1, 1, 1, 1, 1},
{0, 0, 0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
};

Matrix matrix = new Matrix(translate);
Matrix matrix2 = Matrix.quickPow(matrix, n, mod);

Matrix vec = new Matrix(new long[][] {{1}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}, {0}});
Matrix res = matrix2.mul(vec, mod);

long ans = 0;
for (int i = 5; i < 10; i++) {
ans += res.arr[i][0];
ans %= mod;
}
System.out.println(ans);
}

static
class Matrix {
long[][] arr;
int r, c;
Matrix(long[][] arr) {
this.arr = arr;
this.r = arr.length;
this.c = arr[0].length;
}

Matrix mul(Matrix other, long mod) {
int nr = this.r, nc = other.c;
long[][] res = new long[nr][nc];
for (int i = 0; i < nr; i++) {
for (int j = 0; j < nc; j++) {
long temp = 0;
for (int k = 0; k < c; k++) {
temp = (temp + arr[i][k] * other.arr[k][j] % mod) % mod;
}
res[i][j] = temp;
}
}
return new Matrix(res);
}

static Matrix E(int n) {
long[][] arr = new long[n][n];
for (int i = 0; i < n; i++) {
arr[i][i] = 1;
}
return new Matrix(arr);
}

static Matrix quickPow(Matrix base, long k, long mod) {
Matrix r = Matrix.E(base.r);
while (k > 0) {
if (k % 2 == 1) {
r = r.mul(base, mod);
}
k /= 2;
base = base.mul(base, mod);
}
return r;
}
}

}


## F. 小红的零

S(i) = S(i-1) + (i+1)*f(i)

• 贡献为 g(r) - g(l - 1)
• 贡献为f(r) - f(l - 1)

• 维护2因子多的区间（累加和，个数）
• 维护5因子多的区间 (累加和，个数)

• 大于z(x)，为2因子多的区间

• 小于等于z(x), 则为5因子多的区间

fw2, fwc2代表2因子的前缀和f(x)，对应2因子的区间个数，

fw5, fwc5代表5因子的前缀和g(x)，对应5因子的区间个数

import java.io.*;
import java.util.*;

public class Main {

static class BIT {
int n;
long[] arr;
public BIT(int n) {
this.n = n;
this.arr = new long[n + 1];
}
void update(int p, long v) {
while (p <= n) {
this.arr[p] += v;
p += p&-p;
}
}
long query(int p) {
long res = 0;
while (p > 0) {
res += this.arr[p];
p -= p&-p;
}
return res;
}
}

static int split(int v, int b) {
int cnt = 0;
while (v % b == 0) {
v /= b;
cnt++;
}
return cnt;
}

public static void main(String[] args) {
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();

int mx = 60 * n; // 2^30 > 1e9, 因为绝对值的问题，所以30*2*n
int offset = 30 * n; // 引入offset，是因为这边没有离散化，而是做了一个偏移，平衡负值

BIT fw2 = new BIT(mx);  // 2的因子累加和
BIT fwc2 = new BIT(mx); // 2的因子计数

BIT fw5 = new BIT(mx);  // 5的因子累加和
BIT fwc5 = new BIT(mx); // 5的因子计数

long res = 0;
int acc2 = 0, acc5 = 0;
int diff = 0;
for (int i = 0; i < n; i++) {
// 前缀和为key
fw2.update(diff + offset, acc2);
fwc2.update(diff + offset, 1);
fw5.update(diff + offset, acc5);
fwc5.update(diff + offset, 1);

int v = sc.nextInt();
int n2 = split(v, 2);
int n5 = split(v, 5);
diff += (n2 - n5);
acc2 += n2;
acc5 += n5;

// 进行统计计算
long sum2 = fw2.query(mx) - fw2.query(diff + offset);
long cnt2 = fwc2.query(mx) - fwc2.query(diff + offset);
long sum5 = fw5.query(diff + offset);
long cnt5 = fwc5.query(diff + offset);
res += (acc2 * cnt2 - sum2) + (acc5 * cnt5 - sum5);
}

System.out.println(res);

}

}


1 回复

1 回复

tql
1 回复

2 2 评论