牛客周赛149①B-构造②C-构造③D-数学+前缀和+二分④E-状态机 DP#

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

B-构造#

问题#

构造一个长度为n的仅包含0,1的字符串s，其中0和1的数量相等，且有尽可能多的i满足si = s(i+1)

题解#

显然的如果n为奇数则无法构造

对于偶数n，只需0*n//2 + 1*n//2即可

1
n = int(input())
2
if n % 2 == 1:
3
    print(-1)
4
else:
5
    k = n // 2
6
    print('0' * k + '1' * k)

C-构造#

问题#

构造一个 n×m 的矩阵，满足：

所有元素为正整数。
任意相邻（四连通）的元素不相等。
所有元素之和恰好为 k。

题解#

为了使总和尽可能小，我们让一种格子放 1，另一种放 2（最小的两个不同正整数）。

总格子数：tot = n * m
根据 (i+j) 的奇偶性，(i+j)%2==0 的格子数为 cnt2，(i+j)%2==1 的格子数为 cnt1。
令较多的一类格子放 2（为了使总和尽量小，应该少放大的数，但这里为了后期加值方便，把多的放2，少的放1），则：
- cnt2 = (tot + 1) // 2 （较多的一类）
- cnt1 = tot // 2 （较少的一类）
最小总和：min_sum = cnt2 * 2 + cnt1 * 1

如果给定的 kk 比这个最小总和还小，则无法构造，输出 NO。

否则，我们一定能通过给某个格子加差值来达到 k。

diff = k - min_sum 时，可以把这 diff 全部加到某一个格子上（例如第一个格子），使其数值增大 diff。这样做：

不会破坏“相邻不等”的性质，因为只改了一个格子，且它的值变大了，本来就和邻居不同，现在更不同。
所有格子仍是正整数。
总和正好是 min_sum + diff = k。

1
n, m, k = map(int, input().split())
2
tot = n * m
3
cnt2 = (tot + 1) // 2
4
cnt1 = tot // 2
5
min_sum = cnt2 * 2 + cnt1 * 1
6

7
if k < min_sum:
8
    print("NO")
9
else:
10
    print("YES")
11
    diff = k - min_sum
12
    fir = True
13
    for i in range(n):
14
        row = []
15
        for j in range(m):
16
            val = 2 if (i + j) % 2 == 0 else 1
17
            if fir:
18
                val += diff
19
                fir = False
20
            row.append(str(val))
21
        print(' '.join(row))

D-数学+前缀和+二分#

题目#

从一个正整数数组中选一个连续子数组，使得：

子数组的和为 S
剩余部分的和为 tot−S
乘积 S×(tot−S) 最大

题解#

显然所求问题为二次函数优化问题，最值在S = tot//2处取得

记前缀和数组 pref，其中 pref[i] 是前 i 个元素的和（pref[0]=0）。
任意子数组的和 = pref[r] - pref[l]，其中 l < r。
目标：找一个 pref[r] - pref[l] 最接近 tot/2。

这等价于：固定右端点 pref[r]，在之前的前缀和中找一个 pref[l]，使得差值最接近目标 t = tot/2。

即对于每个 pref[r]，我们要找 pref[l] 最接近 pref[r] - t 的值。

计算总 tot，目标 t = tot / 2.0。
初始化前缀和列表 pref = [0]。
遍历原数组，累加得到当前前缀和 pre。
在已有的前缀和中用 bisect_left 找到最接近 pre - t 的位置，检查该位置和前一个位置对应的子数组和，更新最接近 t 的 best_sum。
将当前前缀和加入 pref 列表（自动保持有序，因为数组元素为正，前缀和递增）。
最后答案 = best_sum * (tot - best_sum) % MOD。

1
import bisect
2
MOD = 998244353
3
n = int(input())
4
a = list(map(int, input().split()))
5
tot = sum(a)
6
t = tot / 2.0
7
pre = 0
8
pref = [0]
9
best_sum = 0
10
for x in a:
11
    pre += x
12
    idx = bisect.bisect_left(pref, pre - t)
13
    pref.append(pre)
14
    for i in (idx - 1, idx):
15
        if 0 <= i < len(pref):
16
            sub_sum = pre - pref[i]
17
            if abs(sub_sum - t) < abs(best_sum - t):
18
                best_sum = sub_sum
19
print(best_sum * (tot - best_sum) % MOD)

E-状态机 DP#

问题#

给定一个 2×n2×n 的矩阵，元素为 0、1 或 ?。要将所有 ? 替换为 0 或 1，使得矩阵成为“好矩阵”：

好矩阵定义：任意一个 2×2 的子区域内的四个元素不全相同。

求所有可能的填充方案数，对 998244353 取模。

题解#

转移规则：

new_dp[0] = dp[1] + dp[2] + dp[3] （不能从 0 来）
new_dp[1] = dp[0] + dp[1] + dp[2] + dp[3] （都能来）
new_dp[2] = dp[0] + dp[1] + dp[2] + dp[3] （都能来）
new_dp[3] = dp[0] + dp[1] + dp[2] （不能从 3 来）

状态定义

dp[s] 表示处理到当前列，且当前列状态为 s 时的方案数。
初始化

第 0 列：遍历 4 种状态，若与给定字符不冲突，则 dp[s] = 1。
状态转移

从第 1 列到第 n-1 列，根据当前列的可能状态和上一列的合法转移计算新的 dp 数组。
预处理合法状态

用 can[i][s] 表示第 i 列能否取状态 s（即与输入给定的字符一致）。
答案

最终答案是 sum(dp[0..3]) % MOD。

1
MOD = 998244353
2
n = int(input())
3
row1 = input().strip()
4
row2 = input().strip()
5
can = [[0] * 4 for _ in range(n)]
6
for i in range(n):
7
    for s in range(4):
8
        val1 = (s >> 1) & 1
9
        val2 = s & 1
10
        ok = True
11
        if row1[i] != '?' and int(row1[i]) != val1:
12
            ok = False
13
        if row2[i] != '?' and int(row2[i]) != val2:
14
            ok = False
15
        if ok:
16
            can[i][s] = 1
17
dp = [0, 0, 0, 0]
18
for s in range(4):
19
    if can[0][s]:
20
        dp[s] = 1
21
for i in range(1, n):
22
    new_dp = [0, 0, 0, 0]
23
    if can[i][0]:
24
        new_dp[0] = (dp[1] + dp[2] + dp[3]) % MOD
25
    if can[i][1]:
26
        new_dp[1] = (dp[0] + dp[1] + dp[2] + dp[3]) % MOD
27
    if can[i][2]:
28
        new_dp[2] = (dp[0] + dp[1] + dp[2] + dp[3]) % MOD
29
    if can[i][3]:
30
        new_dp[3] = (dp[0] + dp[1] + dp[2]) % MOD
31
    dp = new_dp
32
ans = sum(dp) % MOD
33
print(ans)

音乐

音乐

牛客周赛149①B-构造②C-构造③D-数学+前缀和+二分④E-状态机 DP#

B-构造#

问题#

题解#

C-构造#

问题#

题解#

D-数学+前缀和+二分#

题目#

题解#

E-状态机 DP#

问题#

题解#

音乐

目录

音乐

音乐

牛客周赛149①B-构造②C-构造③D-数学+前缀和+二分④E-状态机DP

牛客周赛149①B-构造②C-构造③D-数学+前缀和+二分④E-状态机 DP#

B-构造#

问题#

题解#

C-构造#

问题#

题解#

D-数学+前缀和+二分#

题目#

题解#

E-状态机 DP#

问题#

题解#

音乐

目录