std::string

· · 题解

问题 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")