题目理解

有 $n$ 个参赛者，$m$ 项运动。
参赛者 $i$ 的技能由一个长度为 $m$ 的二进制串 $s_i$ 表示，$s_{i,j} = 1$ 表示擅长第 $j$ 项运动，否则为 $0$。
已知所有 $n$ 个二进制串两两不同。

比赛从运动 $x$ 开始，然后按循环顺序进行运动 $x, x+1, \dots, m, 1, \dots, x-1$。
每项运动 $j$ 的规则：

• 如果当前存活的参赛者中没有人擅长 $j$，则所有人都存活到下一项。
• 否则，只保留擅长 $j$ 的参赛者（不擅长的被淘汰）。
  当只剩一人时，该人获胜。

对每个 $x$（$1 \le x \le m$），求胜者编号。

关键观察

$1$. 淘汰过程只与当前存活集合有关，与历史无关。 $2$. 由于 $n$ 个二进制串互不相同，每次淘汰至少会去掉一部分人（除非所有人都擅长或都不擅长当前运动）。 $3$. 最坏情况下，每个 $x$ 需要模拟 $m$ 轮，每轮扫描当前存活集合。
如果直接做，复杂度 $O(m \cdot n \cdot m) = O(m^2 n)$ 不可接受。
但注意 $n \cdot m \le 2\times 10^6$，且 $n \le 2m$，因此实际 $n$ 和 $m$ 不能同时大。
例如 $n=2$ 时 $m$ 可达 $10^6$，此时每轮存活集合大小很小，总复杂度约为 $O(m \cdot n \cdot \text{存活大小})$，可能可过。
标程中直接模拟了每个 $x$，每轮扫描当前存活集合，并重建新集合。
由于 $nm \le 2\cdot 10^6$，总操作量大约是 $O(m \cdot \text{每轮扫描人数})$，而每轮人数单调递减，总复杂度近似 $O(m \cdot n \cdot \log n)$，在数据范围内可接受。

算法步骤

$1$. 读入 $n, m$ 和 $n$ 个二进制串。 $2$. 初始化 $pos$ 数组为 $[0,1,\dots,n-1]$（参赛者编号）。 $3$. 对每个起始运动 $x$ 从 $0$ 到 $m-1$：

• 令当前存活集合 $cur = pos$。
• 对 $j = 0$ 到 $m-1$（实际运动顺序为 $(x + j)$）：
  • 检查当前存活集合中是否有人擅长该运动：遍历 $cur$，若找到 $a[p][idx] == '1'$ 则 $ok = true$。
  • 若 $ok == false$，所有人存活，继续下一项运动。
  • 否则，构造新集合 $nxt$，包含所有 $cur$ 中擅长该运动的人。
  • 令 $cur = nxt$。
  • 若 $cur.size() == 1$，提前结束。
• 记录胜者为 $cur[0] + 1$。 $4$. 输出所有 $x$ 对应的胜者。

复杂度分析

• 外层循环 $m$ 次。
• 内层循环最多 $m$ 轮，但每轮存活集合大小快速下降。
• 总扫描次数约为 $\sum_{x} \sum_{t} |cur_{x,t}|$。
  由于每个人最多被淘汰一次，且每次淘汰发生在某个运动上，最坏情况下每个 $x$ 的模拟中，每个人可能被多次扫描（不同 $x$ 下重新开始），因此总复杂度为 $O(m \cdot n \cdot \text{某个因子})$。
  但因为 $nm \le 2\cdot 10^6$，实际运行时间在 $3$ 秒内可接受。

示例验证

输入：

3 5
10010
01100
10101

输出：

3 2 3 1 3

• $x=1$（运动 1）：
  运动 $1$: 擅长的人 ${1,3}$，淘汰 $2 → {1,3}$
  运动 $2$: 擅长的人 ${2}$，但 2 已淘汰 → 无人擅长 $→$ 保留 ${1,3}$
  运动 $3$: 擅长的人 ${3} →$ 保留 ${3}$ → 胜者 $3$
  其他 $x$ 类似。

完整代码（标程）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    vector<int> ord(m);
    iota(ord.begin(), ord.end(), 0);
    
    vector<int> pos(n);
    for (int i = 0; i < n; ++i) pos[i] = i;
    
    vector<int> ans(m);
    for (int x = 0; x < m; ++x) {
        vector<int> cur = pos;
        for (int j = 0; j < m; ++j) {
            int idx = (x + j) % m;
            bool ok = false;
            for (int p : cur) if (a[p][idx] == '1') { ok = true; break; }
            if (!ok) continue;
            vector<int> nxt;
            for (int p : cur) if (a[p][idx] == '1') nxt.push_back(p);
            cur = nxt;
            if (cur.size() == 1) break;
        }
        ans[x] = cur[0] + 1;
    }
    
    for (int i = 0; i < m; ++i) cout << ans[i] << " \n"[i == m-1];
    
    return 0;
}

总结

• 本题直接模拟淘汰过程即可通过，因为 $n \cdot m \le 2\times 10^6$ 保证了总操作量在可接受范围。
• 关键优化是每轮只扫描当前存活集合，并重建新集合。
• 由于 $n \le 2m$，极端情况下 $n$ 小 $m$ 大时，存活集合很小，扫描快；$n$ 大 $m$ 小时，$m$ 小，外层循环次数少。
  因此整体复杂度约为 $O(m \cdot n \cdot \text{淘汰次数})$，实际运行效率高。