自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:15:30，当前版本为作者最后更新于2025-06-11 10:45:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Solution

唯一的难点在于想到可以从左到右逐位确定每个数是否是 $\texttt B$。

显然我们可以找到左边和右边第一个 $\texttt B$。

我们在 $(l,r)$ 中从小到大决策每个 $p$ 是否是 $\texttt B$。

我们已经确定了 $p$ 之前有 $x$ 个 $\texttt B$，同时也能知道 $p$ 及之后有 $y$ 个 $\texttt B$。记 $cnt[l,r]$ 表示 $[l,r]$ 的众数出现次数。

1. 如果 $\texttt B$ 在 $[l,p)$ 中作为众数出现。

即 $cnt[l,p)=x$。那么 $p$ 是 $\texttt B$ 的一个充分条件是：$cnt[l,p]=x+1$ 且 $cnt(l,p]=x$。（$cnt[l,p]=x+1$ 保证了 $c_p$ 在 $[l,p)$ 中作为众数出现。但是 $[l,p)$ 的众数不一定唯一，我们通过 $cnt(l,p]=x$ 限制）

2. 如果 $\texttt B$ 在 $(p,r]$ 中作为众数出现。

发现充分条件就是 $cnt(p,r]=y-1$。

3. 如果 $\texttt B$ 在 $[l,p)$ 中不是众数，在 $(p,r]$ 中也不是众数。

显然 $[1,p)$ 和 $(p,r]$ 中的众数不交，都不是 $\texttt B$，所以分别是 $\texttt O$ 和 $\texttt I$。一个必要条件是 $cnt[1,p)=cnt[l,p]$ 且 $cnt[p,r] = cnt(p,r)$，容易证明也是充分的（在这种限制下）。

把三个充分条件拼一起就是充要条件。

放一个主播写的 $\rm 382 \ B$ 的代码：

#include<iostream>
#define F(i,a,b) for(int i=a;i<=b;i++)
#define y (a[1][n]-x)
using namespace std;int n,x=1,l=1,a[2001][2001];int main(){cin>>n;F(l,1,n)F(r,l,n)cin>>a[l][r];while(a[1][n]==a[l+1][n])++l;while(a[1][n]==a[l][n-1])--n;if(l!=n)cout<<l<<' ';F(i,l+1,n-1)if(a[l][i]-x&a[l+1][i]==x|a[i+1][n]<y|a[i][n]==a[i+1][n-1]&a[l][i]==a[l][i-1]&a[l][i-1]>x)cout<<i<<' ',++x;cout<<n;}