专栏文章

P12765 [POI 2018 R3] 三座塔 2 Three towers 2 题解

cchenzhiyv
P12765题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio3i1sc
此快照首次捕获于
2025/12/02 12:46
3 个月前
此快照最后确认于
2025/12/02 12:46
3 个月前
查看原文

前言

双倍经验
这篇题解主要是提供一种更简单的证明结论的方法。感谢 q1uple 大佬的讲解。

解法

首先，我们根据直觉觉得在随机情况下，答案应该会很长，所以，我们可以通过打表或翻讨论区得到一个结论：答案开头或结尾一定在 [1,3][1,3] 和 [n−2,n][n-2,n] 中。
所以做法就是枚举区间，排除不合法的，记录最长的答案。
现在考虑证明这这个结论。证明这个结论等价于证明当有一个答案，它的左右两边都有大于三个字符时，一定可以向两边扩展得到更长的答案。
首先，我们考虑中间是一个不合法的序列，排除区间本就无解的情况，它肯定可以向外扩展。具体来说，可以分类讨论：
  1. 当不合法是三个字符出现次数全部相等时，向外扩展一个一定会形成一个更长的且合法的串。
  2. 当有两个字符出现次数相等时，若待扩展的字符是这两个之一，扩展后一定更长且合法。现在考虑带扩展的字符是第三种的情况，分两种情况讨论：
    1. 第三个字符的出现次数比这两种出现次数少 11。那么扩展后就转化为了三个字符出现次数全部相等的情况，一定可以再次扩展。
    2. 第三个字符出现次数比这两种出现次数少不止 11。那么这个区间可能无解，排除。
现在考虑中间是合法的序列的情况，当扩展完后是不合法的，根据上上面的证明，一定可以扩展，当扩展完后是合法的，那答案显然更优。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...