题解：P12426 [BalticOI 2025] BOI acronym

· · 题解

全局绝对众数一定是 B。

我们容易算出最左和最右的 B，去掉两边的 O 和 I 后不影响 B 的绝对众数地位。此时我们将数组的两端都变为了 B。

考虑从左往右确定每个位置是否是 B。设当前点，设为 i，左边 B 的数量是 c，而总的 B 数量是 S。这两个值我们都是知道的，因为前面已经算出来了。

对于 [1,i) 和 [i,n] 这两段，如果某一段中 B 是绝对众数，设为 [1,i)，那么如果 i 上是 B，那么 [1,i] 的众数数量就是 [1,i) 加一，反之不然。所以我们可以确定 i。

如果 B 在两边都不是绝对众数，那么 O 和 I 一定分别是两边的众数（但不一定是绝对众数，因为可能和 B 的数量一致），这是因为 B 是全局绝对众数，所以不会有字母同时是两边的众数。为了制造出一个绝对众数，我们取 (1,i) 和 [i,n)，这两段中由于分别去掉了一个 B，不存在和 B 一样的情况了，也就是 O 和 I 分别是这两段的绝对众数。此时可以用上面的方法判断 i 是否是 O 或 I，如果都不是则是 B。

于是做完了，复杂度 O(n^2)。

Code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,p[2009][2009],L,R;
bool st[2009];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    if(n==1)return cout<<1<<endl,0;
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)cin>>p[i][j];
    for(int i=1;i<=n;i++)if(p[i][n]==p[1][n])L=i;else break;
    for(int i=n;i;i--)if(p[1][i]==p[1][n])R=i;else break;
    cout<<L<<' ';
    for(int i=L+1,cnt=1;i<R;i++){
        if(p[L][i-1]==cnt&&p[L+1][i-1]==cnt-1){
            if(p[L][i]==p[L][i-1]+1)cout<<i<<' ',cnt++;
            continue;
        }
        if(p[i][R]==p[L][R]-cnt&&p[i][R-1]==p[L][R]-cnt-1){
            if(p[i][R]==p[i+1][R]+1)cout<<i<<' ',cnt++;
            continue;
        }
        if(p[i+1][R-1]==p[i][R]&&p[L+1][i]==p[L][i-1])cout<<i<<' ',cnt++;
    }
    cout<<R<<endl;
    return 0;
}