注意到 BN-string 长成什么样根本不重要，我们把它表述为 BN-pair \((x, y)\) 即可，两个 BN-strings 相似的充要条件即两者分别映射得到的 BN-pairs 相等。将 BN-pairs 放到平面上来研究，题目中给出的变换就对应 \((x,y)\rightarrow(x\pm1,y),(x,y\pm1),(x\pm1,y\pm1)\)，注意到在斜线方向上的移动只能同时加或减。我们可以用这样移动方式的所派生的 \(\text{dist}(a, b)\) 函数导出在平面上的「圆」（是一般意义下的 hexagon），如下图
二分「半径」\(r\) 我们现在的问题就转化为了，判定原图上所有点以 \(r\) 导出「圆」的是否有交。由于这是个凸图形，我们考虑用六条直线围成的图形来描述，于是两个「圆」有交的充要条件即为「在横轴上有交，且在竖轴上有交，且在 \(y=x\) 轴上有交」。前两个的判断都不怎么迷惑，在斜轴（即 \(y=x\) 轴）上的判断需要小小的考虑一下。不妨用一条 \(y=-x+b\) 的直线来切斜线，如下图
这样把 \(y=-x+b\) 看作数轴，我们就把问题转化成了前两个判断，但是实际上我们不需要这个算这个六边形斜线与轴交点的坐标再转化（这样算出来还会带根号，很麻烦），等价地，直接看六边形斜线与已有数轴（即横轴和竖轴）的交点即可。
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int n, xx[300100], yy[300100];
char s[500100];
int lx, rx, ly, ry, lz, rz;
bool check(int r) {
lx = -inf, rx = inf, ly = -inf, ry = inf, lz = -inf, rz = inf;
for (int i = 1; i <= n; ++i) {
lx = max(lx, xx[i]-r), rx = min(rx, xx[i]+r);
ly = max(ly, yy[i]-r), ry = min(ry, yy[i]+r);
lz = max(lz, xx[i]-yy[i]-r), rz = min(rz, xx[i]-yy[i]+r);
}
lx = max(lx, 0), ly = max(ly, 0);
if (lx > rx || ly > ry || lz > rz) return 0;
return lx-ry <= rz && rx-ly >= lz;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s;
for (int j = 0, r = strlen(s); j < r; ++j) {
if (s[j] == 'B') xx[i]++;
else yy[i]++;
}
}
int l = 0, r = 1e9, mid, ans = l;
while (l <= r) {
if (check(mid = (l+r)/2)) {
r = mid-1;
ans = mid;
}
else {
l = mid+1;
}
}
check(ans);
cout << ans << "\n";
for (int i=0;i<min(rx, ry+rz);++i) {
cout << "B";
}
for (int i=0;i<min(min(rx, ry+rz)-lz,ry);++i) {
cout << "N";
}
}
题外话：抑郁场，开局一小时只出A，死活想不来B，最后因为D题出锅ura才保住可怜的分。但咱本来就写不到DB-LongLegs（数论）本题题解法一学自同样抑郁的知乎作者幽血魅影的题解，有讲解原理。法二来着知乎巨佬cup-pyy（大佬说《不难发现》呜呜）题意三种操作：向上走mmm步向右走mmm步给自己一次走的步数加111，即使得m=m+1m=m+1m=m+1问从(0,0)(0,0)(0,0)走到(a,b)(a,b)(a,b)的最小操作次数，值得注意的是操作三不可逆。解析假设我们最终一步的大小增长到mmm，那么在这个过程中我能以[1,m][1,m][1,m]（当步数增长到该数时）之间的任何数字向上或
我的电脑有IEEE1394(FireWire)输入。如何以编程方式知道1394是否已连接到我的Windows7？ 最佳答案 您可以使用Win32_1394ControllerDeviceWMI类。 关于windows-如何知道IEEE1394(FireWire)是否连接到我的Windows7？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/16372170/
主机:Windows7x64guest:WindowsXPSP3x86我在两端都有2个PCI火线卡(SIIG1394安装为德州仪器OHCI兼容IEEE1394主机Controller)。在WindowsXP上，我在boot.ini中添加了以下内容:/debug/debugport=1394/channel=10我重新启动了WindowsXP，OHCI驱动程序变成了黄色(这是预料之中的)。在Windows7(主机)上，我运行WinDBG(x86)，打开内核调试，1394，指定channel10并运行它说:Using1394fordebuggingChecking1394debugdriv
我正在使用libraw1394库，它可以直接访问Linux中的IEEE1394总线。它非常易于使用，我想知道是否有适用于Windows的类似libraw1394的东西？一般来说，我如何在Windows中访问IEEE1394总线？DDK是唯一的方法吗？UPD。我找到了VHPD1394。一种特殊的设备驱动程序，它为Win32应用程序提供对IEEE1394设备的直接访问。文档指出它可以与任何类型的IEEE1394设备一起使用，使应用程序开发人员无需开发内核模式WDM驱动程序即可控制设备。编程接口(interface)支持C、C++和Delphi。不幸的是它不是免费的!UPD.FreddieW
A.Yura'sNewName题意：给出一个仅由_或^组成的字符串，你可以在任意位置添加_或^字符，使得字符串满足：任意字符要么属于^_^的一部分，要么属于^^的一部分。求最少添加的字符数量。分析：对于_我们只需处理没有组成^_^的_:①如果_在首位置且左边没有^则添加^②如果_在尾位置且右边没有^则添加^③如果_在中间部分且右边没有^则添加^当字符串只有一个^时末尾添加一个^code:#includeusingnamespacestd;intmain(){ std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); intt; cin
文章目录题目描述思路AC代码题目描述GarrisonandAndersonareworkinginacompanynamed“AdjustmentOffice”.Incompetingcompaniesworkerschangethereality,inthiscompanytheytrytopredictthefuture.Theyaregivenabigsquareboardn×n.Initiallyineachcell(x,y)ofthisboardthevalueofx+yiswritten(1≤x,y≤n).Theyknowthatinthefuturetherewillbetwot
文章目录题目描述思路AC代码题目描述GarrisonandAndersonareworkinginacompanynamed“AdjustmentOffice”.Incompetingcompaniesworkerschangethereality,inthiscompanytheytrytopredictthefuture.Theyaregivenabigsquareboardn×n.Initiallyineachcell(x,y)ofthisboardthevalueofx+yiswritten(1≤x,y≤n).Theyknowthatinthefuturetherewillbetwot
目录A.Garland（签到）题面翻译思路：代码B.PointsonPlane（数学）题面翻译思路：代码C.SumonSubarray（构造）题面翻译：思路：代码D.BinaryStringSorting题面翻译思路：代码A.Garland（签到）Youhaveagarlandconsistingof 4 coloredlightbulbs,thecolorofthe i-thlightbulbis si.Initially,allthelightbulbsareturnedoff.Yourtaskistoturnallthelightbulbson.Youcanperformthefollo
目录A.Garland（签到）题面翻译思路：代码B.PointsonPlane（数学）题面翻译思路：代码C.SumonSubarray（构造）题面翻译：思路：代码D.BinaryStringSorting题面翻译思路：代码A.Garland（签到）Youhaveagarlandconsistingof 4 coloredlightbulbs,thecolorofthe i-thlightbulbis si.Initially,allthelightbulbsareturnedoff.Yourtaskistoturnallthelightbulbson.Youcanperformthefollo
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴匈牙利算法一、题目1、原题链接1394.完美牛棚2、题目描述农夫约翰上周刚刚建好了新的牛棚，并引进了最新的挤奶技术。不幸的是，由于工程问题，牛棚中的每个单间都不太一样。第一周，约翰将奶牛们随机分配在了各个单间中。但是很快他就发现，每头奶牛都只愿意在一部分自己喜欢的单间中产奶。在过去的一周中，农夫约翰一直在收集有关哪些奶牛愿意在哪些单间产奶的数据。一个单间只能分配给一头奶牛，当然，一头奶牛也可能只愿意在一个单间中产奶。给定奶牛的住宿喜好，请你计算，通过合理分配奶牛的住所，最多能够让多少奶牛可以住