2025暑期牛客多校 A.新太阳睡觉中心
Link:Nowcoder
Problem A. 新太阳睡觉中心
题目描述
‘Cause morning rolls around, and it’s another day of sun!
但是作为一个睡瘾患者，肖恩经常睡觉睡个半天，因此，当他醒来时，他甚至记不清今天是星期几。
所以从某一天开始，他开始进行记录：每次他醒来的时候，他就会写下一个数字，表示此时外面是否有阳光。如果有，他会写一个 1；否则，他会写一个 0。在完成记录后，还没等太阳下山，或是太阳升起，他又再次入睡。假设每次肖恩醒来时，他看到的要么是阳光，要么是月光，但不会同时看到两者。
这些记录下来的数字实际上形成了一个长度为 $n$ 的数组：$[a_1, a_2, \dots, a_n]\quad \forall\,1 \le i \le n,\;0 \le a_i \le 1$，其中 $a_i$ 表示肖恩写下的第 $i$ 个数字。
然而，随着时间的推移，一些写下的数字变得模糊不清，你无法判断它是 1 还是 0。如果有 $k$ 个数字无法识别，则可能有 $2^k$ 种不同的数组。
对于每种可能的数组，你都可以依据这个数组计算肖恩看到阳光的最小天数。如果将所有可能数组的最小天数结果相加，得到的总和是多少呢？由于答案可能很大，请将结果对 $998244353$ 取模后输出。
输入格式
- 第一行包含整数 $T$ $(1 \le T \le 10^4)$，表示测试用例的数量。
每个测试用例包含两行：
- 一行整数 $n$ $(2 \le n \le 5\times10^5)$，表示记录的长度。
- 一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $( -1 \le a_i \le 1)$，表示每次记录的数字。只有当 $a_i = -1$ 时，该记录未知。
你可以保证所有测试用例中，$\sum n \le 5\times10^5$。
输出格式
对每个测试用例，输出一个整数——所有可能数组的“最小天数”之和，对 $998244353$ 取模后的结果。
示例
1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
3
3
1 0 1
3
0 0 0
3
1 -1 1
输出：
2
0
3
解释
- 示例 1：数组
[1,0,1]在任意划分中，两个1必定来自不同的天，最小天数 = 2。 - 示例 2：全
0，无阳光天数 = 0。 - 示例 3：未知位可为 0/1，共两种数组：
[1,1,1]→ 最小天数 = 1[1,0,1]→ 最小天数 = 2 总和 = $1 + 2 = 3$。
解析
初看这道题，可能会往DP上面靠，毕竟要转移状态，但是我们分析是很难得到一个明确的转移方程，需要考虑的太多。 其实这道题目的类型是组合计数，如果在数组最前面添上一个0，那么实际计数的就是 $[0,1]$ 作为子数组出现的次数。 我们可以这样来看：
当我们单独看一个 $[i,i+1]$ 子数组的时候，其他位置到底是怎么样，是并不会影响这是一个太阳日的。 因此，此时其他位置的变化实际上只会是 $[i, j]$ 满足 $[0, 1]$ 的一种情况。
当我们只考虑 $i$ 和 $i+1$位置的贡献的时候，一共会有四种情况可能会满足 $[0,1]$：$[0, 1]$, $[-1, 1]$, $[0, -1]$, $[-1, -1]$，其余情况皆不可能。
分别对答案的贡献是 $2^x$, $2^{x - 1}$, $2^{x - 1}$, $2^{x - 2}$。
至此，此题得解。
核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int p2[N];
void pre2()
{
p2[0] = 1;
for (int i = 1; i < N; i++) p2[i] = (p2[i - 1] * 2) % M;
}
void solve()
{
int n; cin >> n;
vector<int> a(n);
int no = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] == -1) no++;
}
int ans = 0;
int u = 0, v = a[0];
if (v == 1) ans = (ans + p2[no]) % M;
else if (v == -1) ans = (ans + p2[no - 1]) % M;
for (int i = 0; i < n - 1; i++)
{
u = a[i];
v = a[i + 1];
if (u == 0 && v == 1) ans = (ans + p2[no]) % M;
else if ((u == 0 && v == -1) || (u == -1 && v == 1)) ans = (ans + p2[no - 1]) % M;
else if (u == -1 && v == -1) ans = (ans + p2[no - 2]) % M;
}
cout << ans << endl;
}