題目大意:
n n n個字元串,每個字元串僅包含 B , N B,N B,N兩種字元,可以對 B N − s t r i n g BN-string BN−string進行如下操作:
- 移走一個字元
- 移走 “ B N ” “BN” “BN”, “ N B ” “NB” “NB”的子串
- 添加一個字元 B B B,或 N N N在 s s s的末尾
- 添加 “ B N ” “BN” “BN”或者 “ N B ” “NB” “NB”在 s s s的末尾
定義兩個字元串相似的條件: B B B與 N N N的個數分别都相等
且定義 d i s t ( s , t ) dist(s,t) dist(s,t)代表 s s s與 t t t相似的最小操作次數
找到一個字元串 t t t,使得 m a x i = 1 n d i s t ( s i , t ) max_{i=1}^{n}dist(s_i,t) maxi=1ndist(si,t)最小
解題思路:(思路來源:WYXkk)
首先隊對以上的操作進行分析:
- 假設字元串 t t t的 B B B, N N N都大于 s s s,那麼此時最好先對 t t t進行第二種操作,再執行第一種操作,而第二種操作必須是子串,是以我們可以将 t t t變成類似形式: B . . . B N . . . N B...BN...N B...BN...N
- 假設字元串 t t t的 B B B, N N N都小于 s s s,那麼此時先對 t t t執行第四種操作,再執行第三種操作
- 最後這種情況,就是分别執行第一種,第三種操作即可
通過以上分析,操作可以變成如下:
- 移走一個字元或添加一個字元
- 添加/删除一個 B B B以及一個 N N N
對于最大值最小這類問題,一般都是二分答案,那麼現在就是如何檢驗
假設二分的答案是 l l l
- 可以将每個字元串的 B B B的個數以及 N N N的個數,分别當作橫縱坐标畫在坐标軸上
那麼每個點移動的方向就如下:
最後範圍就是:
是以隻要對所有點這樣的圖形判斷是否有交集即可
- 對于這種非正常則的圖形,很多可以不用半平面交來判斷
先寫出方程:
{ x ≤ x [ i ] + l x ≥ x [ i ] − l y ≤ y [ i ] + l y ≥ y [ i ] − l x − y ≤ x [ i ] − y [ i ] + l x − y ≥ x [ i ] − y [ i ] − l \left\{\begin{matrix} x \le x[i] + l \\ x \ge x[i]-l \\ y \le y[i] + l \\ y \ge y[i] - l \\ x - y \le x[i] - y[i] + l \\ x - y \ge x[i] - y[i] - l \end{matrix}\right. ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x≤x[i]+lx≥x[i]−ly≤y[i]+ly≥y[i]−lx−y≤x[i]−y[i]+lx−y≥x[i]−y[i]−l
- 對于以上方程分别對每個範圍的最小值取 m a x max max,以及最大值取 m i n min min
判斷是否圖形有交集:( x m i n xmin xmin為 x x x的最小範圍,其餘同理,設 z m i n zmin zmin為斜的最小距離)
- x m i n > x m a x xmin > xmax xmin>xmax 或者 y m i n > y m a x ymin > ymax ymin>ymax 或者 z m i n > z m a x zmin > zmax zmin>zmax即交集為空
- 因為 z m i n ≤ x − y ≤ z m a x zmin \le x-y\le zmax zmin≤x−y≤zmax,而 x − y x-y x−y又有範圍: x m i n − y m a x ≤ x − y ≤ x m a x − y m i n xmin - ymax \le x-y\le xmax - ymin xmin−ymax≤x−y≤xmax−ymin,是以還要判斷兩個區間是否有交集
最後得到一個答案 l l l,還要找出有多少個 B B B以及 N N N
- 因為 z m i n ≤ x − y ≤ z m a x zmin \le x - y \le zmax zmin≤x−y≤zmax,是以 z m i n + y m i n ≤ x ≤ z m a x + y m a x zmin + ymin \le x \le zmax + ymax zmin+ymin≤x≤zmax+ymax,而 x x x又有 x m i n ≤ x ≤ x m a x xmin \le x \le xmax xmin≤x≤xmax,取交集中的一個數 x 0 x_0 x0就好
- 已知 x 0 x_0 x0以及 z m i n ≤ x − y ≤ z m a x zmin \le x - y \le zmax zmin≤x−y≤zmax,是以 x 0 − z m a x ≤ y ≤ x 0 − z m i n x_0 - zmax \le y \le x0 - zmin x0−zmax≤y≤x0−zmin,而 y y y又有 y m i n ≤ y ≤ y m a x ymin \le y \le ymax ymin≤y≤ymax,取交集即可
AC代碼:
#include <bits/stdc++.h>
#define ft first
#define sd second
#define pb push_back
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) //不能跟puts混用
#define seteps(N) fixed << setprecision(N)
#define endl "\n"
const int maxn = 5e5 + 10;
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
int n, x[maxn], y[maxn];
bool check(int l) {
int xmin = -inf, xmax = inf, ymin = -inf, ymax = inf, zmin = -inf, zmax = inf;
for (int i = 1; i <= n; i++) {
xmin = max(xmin, x[i] - l);
xmax = min(xmax, x[i] + l);
ymin = max(ymin, y[i] - l);
ymax = min(ymax, y[i] + l);
zmin = max(zmin, x[i] - y[i] - l);
zmax = min(zmax, x[i] - y[i] + l);
}
xmin = max(xmin, 0); ymin = max(ymin, 0);
if (xmin > xmax || ymin > ymax || zmin > zmax) return 0;
int zzmin = xmin - ymax, zzmax = xmax - ymin;
if (zzmax < zmin || zmax < zzmin) return 0;
return 1;
}
int main() {
cin >> n;
string s;
for (int i = 1; i <= n; i++) {
cin >> s;
for (int j = 0; j < s.size(); j++)
(s[j] == 'B') ? x[i]++ : y[i]++;
}
int lc = 0, rc = 1e6, mc, res;
while (lc <= rc) {
mc = (lc + rc) >> 1;
if (check(mc)) rc = mc - 1, res = mc;
else lc = mc + 1;
}
cout << res << endl;
int xmin = -inf, xmax = inf, ymin = -inf, ymax = inf, zmin = -inf, zmax = inf;
for (int i = 1; i <= n; i++) {
xmin = max(xmin, x[i] - res);
xmax = min(xmax, x[i] + res);
ymin = max(ymin, y[i] - res);
ymax = min(ymax, y[i] + res);
zmin = max(zmin, x[i] - y[i] - res);
zmax = min(zmax, x[i] - y[i] + res);
}
int x0 = min(xmax, zmax + ymax), y0 = min(x0 - zmin, ymax);
for (int i = 1; i <= x0 + y0; i++)
if (i <= x0) cout << 'B';
else cout << 'N';
cout << endl;
return 0;
}