题解：P12426 [BalticOI 2025] BOI acronym

· · 题解

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 限制）

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

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

  1. 如果 \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;}