自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 21:15:12，当前版本为作者最后更新于2023-07-19 12:50:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

问题 $1$：

将字符串相加（拼接）的操作复杂度是 $O(a+b)$，其中两个字符串长度分别为 $a$ 和 $b$。

因为 $n\le10^5$，所以很可能超时。

输出一个比较大的数，如 $10^5$ 即可。

问题 $2$：

第二个问题，注意到 $a_i$ 可以取 $0$。

模拟一下 $a_x$ 取 $0$ 的情况。

for (int i = 2; i <= n; ++i) pre[i] = pre[i - 1] & a[i];

此时，$pre_x=pre_{x+1}=\dots=pre_{n}=0$。

for (int i = n - 1; i; --i) post[i] = post[i + 1] & a[i];

此时，$post_x=post_{x-1}=\dots=post_{1}=0$。

for (int i = 1; i < n; ++i) if (pre[i] + post[i + 1] == pre[n]) {
    ++ans;
}

我们知道 $pre_n=0$，接下来对这里的 $i$ 进行分讨。

1. 当 $i<x$，$post_{i+1}=0$，此时只有 $pre_i=0$ 时 $ans$ 会加 $1$。
2. 当 $i\ge x$，$pre_{i}=0$，此时只有 $post_{i+1}=0$ 时 $ans$ 会加 $1$。

当 $a$ 中有两个 $0$（假设分别是 $a_x,a_y$ 且 $x<y$），且除了这两个数以外剩下的数按位与的结果不为 $0$ 时，正确的答案是什么？正确的答案是 $2$，把 $a$ 数组分成 $[1,x]$ 和 $[x+1,n]$。但是实际上在最终的这个循环中，$x\le i<y$ 时 $ans$ 都会自增 $1$，此时最终程序输出的 $ans$ 为 $1$（初始值）$+y-x$（在 $[x,y)$ 中加的数）。当 $y-x>1$ 时，程序的答案就会出错。

构造一组数据，其中数组刚好有两个 $0$（并且这两个 $0$ 之间至少有一个不为 $0$ 的数），且剩下所有数按位与的结果不为 $0$ 即可让程序出错。

实际上，剩下的数按位与的结果为 $0$（如 5\n1 0 2 0 4），甚至输入的 $a$ 数组不含 $0$（如 6\n1 1 4 5 1 4），也都有几率会使程序出错。但是只要求构造一组使程序出错的数据即可，所以不需要分析更复杂的情况。

Python 程序代码：

a=int(input())
if(a==1):print(100000)
if(a==2):print("5\n1 0 1 0 1")