P12765 [POI 2018 R3] 三座塔 2 Three towers 2 题解
前言
双倍经验
这篇题解主要是提供一种更简单的证明结论的方法。感谢 q1uple 大佬的讲解。
解法
首先，我们根据直觉觉得在随机情况下，答案应该会很长，所以，我们可以通过打表或翻讨论区得到一个结论：答案开头或结尾一定在
所以做法就是枚举区间，排除不合法的，记录最长的答案。
现在考虑证明这这个结论。证明这个结论等价于证明当有一个答案，它的左右两边都有大于三个字符时，一定可以向两边扩展得到更长的答案。
首先，我们考虑中间是一个不合法的序列，排除区间本就无解的情况，它肯定可以向外扩展。具体来说，可以分类讨论：
- 当不合法是三个字符出现次数全部相等时，向外扩展一个一定会形成一个更长的且合法的串。
-
当有两个字符出现次数相等时，若待扩展的字符是这两个之一，扩展后一定更长且合法。现在考虑带扩展的字符是第三种的情况，分两种情况讨论：
- 第三个字符的出现次数比这两种出现次数少
1 。那么扩展后就转化为了三个字符出现次数全部相等的情况，一定可以再次扩展。 - 第三个字符出现次数比这两种出现次数少不止
1 。那么这个区间可能无解，排除。
- 第三个字符的出现次数比这两种出现次数少
现在考虑中间是合法的序列的情况，当扩展完后是不合法的，根据上上面的证明，一定可以扩展，当扩展完后是合法的，那答案显然更优。
代码
#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
inline void print(char x) { putchar(x); }
inline void print(char *x) { while (*x) putchar(*x++); }
inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
inline void print(bool b) { putchar(b+48); }
template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
const int N=1e6+10;
int n;
string S;
int cnt[4][N];
int id(char c)
{
if(c=='B')
return 1;
else if(c=='C')
return 2;
else
return 3;
}
bool check(int s,int t)
{
int a=cnt[1][t]-cnt[1][s-1],b=cnt[2][t]-cnt[2][s-1],c=cnt[3][t]-cnt[3][s-1];
if(a!=b&&b!=c&&a!=c)
return 1;
return 0;
}
signed main()
{
cin>>n;
cin>>S;
S=" "+S;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=3;j++)
cnt[j][i]+=cnt[j][i-1];
cnt[id(S[i])][i]++;
}
int ans=0;
for(int s=1;s<=3;s++)
for(int t=s+1;t<=n;t++)
if(check(s,t))
ans=max(ans,t-s+1);
for(int t=n-2;t<=n;t++)
for(int s=1;s<=t;s++)
if(check(s,t))
ans=max(ans,t-s+1);
if(ans==0)
cout<<"NIE"<<endl;
else
cout<<ans<<endl;
return 0;
}