如果只允许一个操作，即按 K 位向右旋转，其中 K = [0，字符串长度]，则二进制字符串将产生的最大二进制数
Maximum binary number a binary string will result to if only one operation is allowed i.e. Right-Rotate By K-Bits where K = [0, Length of String]
假设您有一个二进制字符串 S 并且您只能执行一项操作，即 Right-Rotate by K-bits 其中 K = [0, Length of the string]。编写一个算法，该算法将打印您可以通过定义的过程创建的最大二进制数。
例如：
S = [00101] 那么我可以从该过程中获得的最大值是 10100 即 20。 S = [011010] 然后我可以从该过程中获得的最大值是 110100 即 52.S = [1100] 然后我可以从该过程中获得的最大值是 1100 即 12.
字符串的长度 S 有一个上限，即 5*(10^5)。
我的想法有点幼稚，就是：众所周知，当你将任何二进制数右旋 1-bit 时，你会在 m 后得到相同的二进制数m = number of bits required to represent that number.
的旋转
所以，我向右旋转 1 直到我得到我开始的数字，在这个过程中，我跟踪我遇到的最大值，最后我打印最大值。
是否有解决问题的有效方法？
UPD1: 这是问题的根源One-Zero，这一切都归结为我上面描述的陈述。
UPD2: 由于答案可能很大，程序将打印答案模 10^9 + 7.
又是我
今天早上我在淋浴时仔细考虑了您的问题，我想到您可以对输入字符串并据此确定最 "valuable" 旋转的索引。
我在这里展示的内容并不关心按照您要求的方式呈现结果，只关心确定旋转的最佳偏移量是多少。
这不是教科书式的 QuickSelect 实现，而是一种简化的方法，它做同样的事情，同时考虑到我们正在处理的是一串零和一。
主要驱动逻辑：
static void Main(string[] args)
{
Console.WriteLine(FindBestIndex("")); // exp -1
Console.WriteLine(FindBestIndex("1")); // exp 0
Console.WriteLine(FindBestIndex("0")); // exp 0
Console.WriteLine(FindBestIndex("110100")); // exp 0
Console.WriteLine(FindBestIndex("100110")); // exp 3
Console.WriteLine(FindBestIndex("01101110")); // exp 4
Console.WriteLine(FindBestIndex("11001110011")); // exp 9
Console.WriteLine(FindBestIndex("1110100111110000011")); // exp 17
}
设置我们将要排序的索引数组，然后调用 FindHighest 来完成实际工作：
static int FindBestIndex(string input)
{
if (string.IsNullOrEmpty(input))
return -1;
int[] indexes = new int[input.Length];
for (int i = 0; i < indexes.Length; i++)
{
indexes[i] = i;
}
return FindHighest(input, indexes, 0, input.Length);
}
将索引数组分成两半，具体取决于每个索引指向的字符串是在字符串中的此偏移量处以零还是以一开头。
一旦完成，如果我们只有一个以 1 开头的元素，我们就有最好的字符串，否则如果我们有更多，则根据下一个索引对它们进行分区。如果 none 从 1 开始，以相同的方式从 0 开始。
static int FindHighest(string s, int[] p, int index, int len)
{
// allocate two new arrays,
// one for the elements of p that have zero at this index, and
// one for the elements of p that have one at this index
int[] zero = new int[len];
int[] one = new int[len];
int count_zero = 0;
int count_one = 0;
// run through p and distribute its elements to 'zero' and 'one'
for (int i = 0; i < len; i++)
{
int ix = p[i]; // index into string
int pos = (ix + index) % s.Length; // wrap for string length
if (s[pos] == '0')
{
zero[count_zero++] = ix;
}
else
{
one[count_one++] = ix;
}
}
// if we have a one in this position, use that, else proceed with zero (below)
if (count_one > 1)
{
// if we have more than one, sort on the next position (index)
return FindHighest(s, one, index + 1, count_one);
} else if (count_one == 1)
{
// we have exactly one entry left in ones, so that's the best one we have overall
return one[0];
}
if (count_zero > 1)
{
// if we have more than one, sort on the next position (index)
return FindHighest(s, zero, index + 1, count_zero);
}
else if (count_zero == 1)
{
// we have exactly one entry left in zeroes, and we didn't have any in ones,
// so this is the best one we have overall
return zero[0];
}
return -1;
}
请注意，这可以通过扩展逻辑进一步优化：如果输入字符串有任何 one，则在字符串以 zero 开头的位置添加索引是没有意义的FindBestIndex 中的索引数组，因为它们会比较差。此外，如果索引确实以 one 开头，但前一个索引也以 one 开头，则您也可以省略当前索引，因为前一个索引总是更好，因为该字符串流入此字符。
如果愿意，您还可以重构以删除递归以支持循环。
如果我要解决这个问题，我会这样做。
我认为这一切都与计算交替的 运行s of '1' 和 运行s of '0' 有关，处理 运行 of '1' 后跟 运行 的 '0' 作为一对，然后抨击这些对的列表。
让我们从扫描到第一个'1'开始，并设置起始位置s。然后计算每个 运行 of '1's c1 和随后的 运行 of '0's c0，创建对 (c1,c0).
然后扫描继续进行到最后，根据需要循环。如果我们将一个或多个'1'和'0'的运行表示为单个数字，而'|'作为字符串的开始和结束，那么我们有 cases:
|10101010|
^ initial start position s -- the string ends neatly with a run of '0's
|1010101|
^ new start position s -- the string starts and ends in a '1', so the first
run of '1's and run of '0's are rotated (left),
to be appended to the last run of '1's
Note that this changes our start position.
|01010101|
^ initial start position s -- the first run of '0's is rotated (left),
to follow the last run of '1's.
|010101010|
^ initial start position s -- the first run of '0's is rotated (left),
to be appended to the last run of '0's.
注意：如果字符串的开头和结尾都是“1”，则最初有 n 运行 个“0”和 n+1 运行s of '1'，但旋转将其减少为 n 运行s of '1'。同样，但相反，如果字符串以“0”开头和结尾。
让我们使用 A 作为对 (a1,a0) 的 shorthand。假设我们有另一对，X——(x1,x0)——然后可以比较这两对，因此：
- if a1 > x1 或 (a1 = x1 和 (a0 < x0) => A > X -- A 是更好的开始
- if a1 = x1 and a0 = x0 => A = X
- if a1 < x1 或 (a1 = x1 and (a0 > x0) => A < X -- X 是更好的开始
技巧可能是将每一对打包成一个整数——比如说 (x1 * N) - x0，其中 N 是至少是字符串的最大允许长度 -- 以便于比较。
在扫描字符串（如上所述）期间，让我们构造一个对向量。在此过程中，收集最大对值 A，以及 A 每次出现的位置列表 s 。列表中的每个 s 都是一个潜在的最佳开始位置。 （记录的s需要是对向量中的索引和原字符串中的偏移量。）
[如果输入的字符串真的很大，那么构建所有对的整个向量会占用内存。在这种情况下，向量需要作为 "virtual" 向量处理，并且当需要该向量中的项目时，必须通过读取实际字符串的相应部分来创建它。]
现在：
让我们简化两个或多个连续 A 的组。很明显，这样一组中的第二个和随后的 A 不可能是最好的开始，因为左边有一个更好的开始。因此，在扫描中，我们只需要记录此类组的前 A 个 s。
如果字符串以一个或多个A开头，并以一个或多个A结尾, 需要 "rotate" 将它们收集为一个组，并仅记录该组中最左边的 A 的 s（在通常的方式）。
如果列表中只有一个s，我们的工作就完成了。如果字符串是端到端的 A，则会在此处发现。
否则，我们需要为我们的（初始）A 考虑每个 s 之后的对 - 其中当我们说 'follow' 时，我们包括从字符串的末尾到开头的环绕（以及等效的对列表）。
注意：此时我们知道我们列表中的所有（初始）A 后跟零个或多个 A，然后是至少一个 x，其中 x < A。
因此，设置 i = 1，并考虑 s+i 处的所有对作为我们的 列表s。只为找到的最大对的实例保留 s。所以对于 i = 1，在这个例子中我们考虑对 x, y 和 z:
- ...Ax....Az...Az..Ax...Ay...
并且如果 x 最大，则此遍丢弃 Ay 和 Az。如果只剩下一个 s——在这个例子中，y 是最大的——我们的工作就完成了。否则，重复 i = i+1.
还有最后一条（我认为）皱纹。假设在找到 z 是最大的 ith 对之后，我们有：
- ...A===zA===z...
其中两个运行===是一样的。按照告诉我们忽略相同的 运行 中的第二个和后续 A 的相同逻辑，我们现在可以丢弃第二个 A=== z。事实上，我们可以丢弃第三个、第四个等连续的 A===z。令人高兴的是，它处理了（比如）的极端情况：
- =zA===zA===zA==
其中字符串是 A===z !
的序列
我不知道，这一切似乎比我用铅笔和纸着手时想象的要复杂:-(
我想有人比我聪明得多，可以将其简化为一些标准的最大前缀字符串问题。
今天无聊，敲了一些代码（2020年4月10日修改）
typedef unsigned int uint ; // assume that's uint32_t or similar
enum { max_string_len = 5 * 100000 } ; // 5 * 10^5
typedef uint64_t pair_t ;
static uint
one_zero(const char* str, uint N)
{
enum { debug = false } ;
void* mem ;
size_t nmx ;
uint s1, s0 ; // initial run of '1'/'0's to be rotated
uint s ;
pair_t* pv ; // pair vector
uint* psi ; // pair string index
uint* spv ; // starts vector -- pair indexes
uint pn ; // count of pairs
uint sn ; // count of starts
pair_t bp ; // current best start pair value
uint bpi ; // current best start pair index
uint bsc ; // count of further best starts
char ch ;
if (N > max_string_len)
{
printf("*** N = %u > max_string_len (%u)\n", N, max_string_len) ;
return UINT_MAX ;
} ;
if (N < 1)
{
printf("*** N = 0 !!\n") ;
return UINT_MAX ;
} ;
// Decide on initial start position.
s = s1 = s0 = 0 ;
if (str[0] == '0')
{
// Start at first '1' after initial run of '0's
do
{
s += 1 ;
if (s == N)
return 0 ; // String is all '0's !!
}
while (str[s] == '0') ;
s0 = s ; // rotate initial run of '0's
}
else
{
// First digit is '1', but if last digit is also '1', need to rotate.
if (str[N-1] == '1')
{
// Step past the leading run of '1's and set length s1.
// This run will be appended to the last run of '1's in the string
do
{
s += 1 ;
if (s == N)
return 0 ; // String is all '1's !!
}
while (str[s] == '1') ;
s1 = s ; // rotate initial run of '1's
// Step past the (now) leading run of '0's and set length s0.
// This run will be appended to the last run of '1's in the string
//
// NB: we know there is at least one '0' and at least one '1' before
// the end of the string
do { s += 1 ; } while (str[s] == '0') ;
s0 = s - s1 ;
} ;
} ;
// Scan the string to construct the vector of pairs and the list of potential
// starts.
nmx = (((N / 2) + 64) / 64) * 64 ;
mem = malloc(nmx * (sizeof(pair_t) + sizeof(uint) + sizeof(uint))) ;
pv = (pair_t*)mem ;
spv = (uint*)(pv + nmx) ;
psi = (uint*)(spv + nmx) ;
pn = 0 ;
bp = 0 ; // no pair is 0 !
bpi = 0 ;
bsc = 0 ; // no best yet
do
{
uint x1, x0 ;
pair_t xp ;
psi[pn] = s ;
x1 = x0 = 0 ;
do
{
x1 += 1 ;
s += 1 ;
ch = (s < N) ? str[s] : '[=11=]' ;
}
while (ch == '1') ;
if (ch == '[=11=]')
{
x1 += s1 ;
x0 = s0 ;
}
else
{
do
{
x0 += 1 ;
s += 1 ;
ch = (s < N) ? str[s] : '[=11=]' ;
}
while (str[s] == '0') ;
if (ch == '[=11=]')
x0 += s0 ;
} ;
// Register pair (x1,x0)
reg:
pv[pn] = xp = ((uint64_t)x1 << 32) - x0 ;
if (debug && (N == 264))
printf("si=%u, sn=%u, pn=%u, xp=%lx bp=%lx\n", psi[sn], sn, pn, xp, bp) ;
if (xp > bp)
{
// New best start.
bpi = pn ;
bsc = 0 ;
bp = xp ;
}
else
bsc += (xp == bp) ;
pn += 1 ;
}
while (ch != '[=11=]') ;
// If there are 2 or more best starts, need to find them all, but discard
// second and subsequent contiguous ones.
spv[0] = bpi ;
sn = 1 ;
if (bsc != 0)
{
uint pi ;
bool rp ;
pi = bpi ;
rp = true ;
do
{
pi += 1 ;
if (pv[pi] != bp)
rp = false ;
else
{
bsc -= 1 ;
if (!rp)
{
spv[sn++] = pi ;
rp = true ;
} ;
} ;
}
while (bsc != 0) ;
} ;
// We have: pn pairs in pv[]
// sn start positions in sv[]
for (uint i = 1 ; sn > 1 ; ++i)
{
uint sc ;
uint pi ;
pair_t bp ;
if (debug && (N == 264))
{
printf("i=%u, sn=%u, pv:", i, sn) ;
for (uint s = 0 ; s < sn ; ++s)
printf(" %u", psi[spv[s]]) ;
printf("\n") ;
} ;
pi = spv[0] + i ; // index of first s+i pair
if (pi >= pn) { pi -= pn ; } ;
bp = pv[pi] ; // best value, so far.
sc = 1 ; // new count of best starts
for (uint sj = 1 ; sj < sn ; ++sj)
{
// Consider the ith pair ahead of sj -- compare with best so far.
uint pb, pj ;
pair_t xp ;
pb = spv[sj] ;
pj = pb + i ; // index of next s+i pair
if (pj >= pn) { pj -= pn ; } ;
xp = pv[pj] ;
if (xp == bp)
{
// sj is equal to the best so far
//
// So we keep both, unless we have the 'A==zA==z' case,
// where 'z == xp == sp', the current 'ith' position.
uint pa ;
pa = pi + 1 ;
if (pa == pn) { pa = 0 ; } ; // position after first 'z'
// If this is not an A==zA==z case, keep sj
// Otherwise, drop sj (by not putting it back into the list),
// but update pi so can spot A==zA==zA===z etc. cases.
if (pa != pb)
spv[sc++] = spv[sj] ; // keep sj
else
pi = pj ; // for further repeats
}
else if (xp < bp)
{
// sj is less than best -- do not put it back into the list
}
else
{
// sj is better than best -- discard everything so far, and
// set new best.
sc = 1 ; // back to one start
spv[0] = spv[sj] ; // new best
pi = pj ; // new index of ith pair
bp = xp ; // new best pair
} ;
} ;
sn = sc ;
} ;
s = psi[spv[0]] ;
free(mem) ;
return s ;
}
我已经根据其他地方给出的蛮力方法对此进行了测试，据我所知这是（现在，2020 年 4 月 10 日）工作代码。
当我在我的机器上计时时，对于 400,000..500,000 个字符的 100,000 个随机字符串（随机），我得到：
Brute Force: 281.8 secs CPU
My method: 130.3 secs CPU
这不包括构建随机字符串的 8.3 秒和 运行 空测试。 （这听起来可能很多，但对于 450,000 个字符的 100,000 个字符串，平均而言，每个字符少于 1 CPU 个循环。）
所以对于随机字符串，我的复杂方法比暴力法快两倍多一点。但它使用~N*16 字节的内存，而暴力法使用 N*2 字节。考虑到所涉及的努力，结果并不是非常令人满意。
但是，我也尝试了两种病态情况，(1) 重复“10”和 (2) 重复“10100010”，对于 400,000..500,000 个字符（随机）的 1000 个（不是 100000 个）字符串，我得到了:
Brute Force: (1) 1730.9 (2) 319.0 secs CPU
My method: 0.7 0.7 secs CPU
那个O(n^2)每次都会杀了你！
您想找到以带环绕的二进制编码字符串表示的最大数字。
解决方法如下：
- 设
len为字符串的长度
- 分配一个大小为
2 * len 的数组并将字符串复制到其中。
- 使用线性搜索，找到长度为
len的最大子串在该数组中的位置pos（可以使用字典顺序）。
- 计算
res，转换后的数模109+7，读取len位从pos.[=34=开始]
- 释放数组并 return
res.
下面是一个简单的函数实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long max_bin(const char *S) {
size_t i, pos, len;
char *a;
// long has at least 31 value bits, enough for numbers upto 2 * 1000000007
long res;
if ((len = strlen(S)) == 0)
return 0;
if ((a = malloc(len + len)) == NULL)
return -1;
memcpy(a, S, len);
memcpy(a + len, S, len);
// find the smallest right rotation for the greatest substring
for (pos = i = len; --i > 0;) {
if (memcmp(a + i, a + pos, len) > 0)
pos = i;
}
res = 0;
for (i = 0; i < len; i++) {
res = res + res + a[pos + i] - '0';
if (res >= 1000000007)
res -= 1000000007;
}
free(a);
return res;
}
int main(int argc, char *argv[]) {
for (int i = 1; i < argc; i++) {
printf("[%s] -> %ld\n", argv[i], max_bin(argv[i]));
}
return 0;
}
如果需要，避免内存分配是可行的。
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int convt(int N,string S)
{
int sum=0;
for(int i=0; i<N; i++)
{
int num=S[i];
sum += pow(2,N-1-i)*(num-48);
}
return sum;
}
string rot(int N, string S)
{
int temp;
temp = S[0];
for( int i=0; i<N;i++)
S[i]=S[i+1];
S[N-1]=temp;
return S;
}
int main() {
int t;
cin>>t;
while(t--)
{
int N,K;
cin>>N;
cin>>K;
char S[N];
for(int i=0; i<N; i++)
cin>>S[i];
string SS= S;
int mx_val=INT_MIN;
for(int i=0;i<N;i++)
{
string S1=rot(N,SS);
SS= S1;
int k_val=convt(N,SS);
if (k_val>mx_val)
mx_val=k_val;
}
int ki=0;
int j=0;
string S2=S;
while(ki!=K)
{
S2=rot(N,S2);
if (convt(N,S2)==mx_val)
ki++;
j++;
}
cout<<j<<endl;
}
}
假设您有一个二进制字符串 S 并且您只能执行一项操作，即 Right-Rotate by K-bits 其中 K = [0, Length of the string]。编写一个算法，该算法将打印您可以通过定义的过程创建的最大二进制数。
例如：
S = [00101]那么我可以从该过程中获得的最大值是10100即20。S = [011010]然后我可以从该过程中获得的最大值是110100即52.S = [1100]然后我可以从该过程中获得的最大值是1100即12.
字符串的长度 S 有一个上限，即 5*(10^5)。
我的想法有点幼稚，就是：众所周知，当你将任何二进制数右旋 1-bit 时，你会在 m 后得到相同的二进制数m = number of bits required to represent that number.
的旋转
所以，我向右旋转 1 直到我得到我开始的数字，在这个过程中，我跟踪我遇到的最大值，最后我打印最大值。
是否有解决问题的有效方法？
UPD1: 这是问题的根源One-Zero，这一切都归结为我上面描述的陈述。
UPD2: 由于答案可能很大，程序将打印答案模 10^9 + 7.
又是我
今天早上我在淋浴时仔细考虑了您的问题，我想到您可以对输入字符串并据此确定最 "valuable" 旋转的索引。
我在这里展示的内容并不关心按照您要求的方式呈现结果，只关心确定旋转的最佳偏移量是多少。
这不是教科书式的 QuickSelect 实现，而是一种简化的方法，它做同样的事情，同时考虑到我们正在处理的是一串零和一。
主要驱动逻辑：
static void Main(string[] args)
{
Console.WriteLine(FindBestIndex("")); // exp -1
Console.WriteLine(FindBestIndex("1")); // exp 0
Console.WriteLine(FindBestIndex("0")); // exp 0
Console.WriteLine(FindBestIndex("110100")); // exp 0
Console.WriteLine(FindBestIndex("100110")); // exp 3
Console.WriteLine(FindBestIndex("01101110")); // exp 4
Console.WriteLine(FindBestIndex("11001110011")); // exp 9
Console.WriteLine(FindBestIndex("1110100111110000011")); // exp 17
}
设置我们将要排序的索引数组，然后调用 FindHighest 来完成实际工作：
static int FindBestIndex(string input)
{
if (string.IsNullOrEmpty(input))
return -1;
int[] indexes = new int[input.Length];
for (int i = 0; i < indexes.Length; i++)
{
indexes[i] = i;
}
return FindHighest(input, indexes, 0, input.Length);
}
将索引数组分成两半，具体取决于每个索引指向的字符串是在字符串中的此偏移量处以零还是以一开头。
一旦完成，如果我们只有一个以 1 开头的元素，我们就有最好的字符串，否则如果我们有更多，则根据下一个索引对它们进行分区。如果 none 从 1 开始，以相同的方式从 0 开始。
static int FindHighest(string s, int[] p, int index, int len)
{
// allocate two new arrays,
// one for the elements of p that have zero at this index, and
// one for the elements of p that have one at this index
int[] zero = new int[len];
int[] one = new int[len];
int count_zero = 0;
int count_one = 0;
// run through p and distribute its elements to 'zero' and 'one'
for (int i = 0; i < len; i++)
{
int ix = p[i]; // index into string
int pos = (ix + index) % s.Length; // wrap for string length
if (s[pos] == '0')
{
zero[count_zero++] = ix;
}
else
{
one[count_one++] = ix;
}
}
// if we have a one in this position, use that, else proceed with zero (below)
if (count_one > 1)
{
// if we have more than one, sort on the next position (index)
return FindHighest(s, one, index + 1, count_one);
} else if (count_one == 1)
{
// we have exactly one entry left in ones, so that's the best one we have overall
return one[0];
}
if (count_zero > 1)
{
// if we have more than one, sort on the next position (index)
return FindHighest(s, zero, index + 1, count_zero);
}
else if (count_zero == 1)
{
// we have exactly one entry left in zeroes, and we didn't have any in ones,
// so this is the best one we have overall
return zero[0];
}
return -1;
}
请注意，这可以通过扩展逻辑进一步优化：如果输入字符串有任何 one，则在字符串以 zero 开头的位置添加索引是没有意义的FindBestIndex 中的索引数组，因为它们会比较差。此外，如果索引确实以 one 开头，但前一个索引也以 one 开头，则您也可以省略当前索引，因为前一个索引总是更好，因为该字符串流入此字符。
如果愿意，您还可以重构以删除递归以支持循环。
如果我要解决这个问题，我会这样做。
我认为这一切都与计算交替的 运行s of '1' 和 运行s of '0' 有关，处理 运行 of '1' 后跟 运行 的 '0' 作为一对，然后抨击这些对的列表。
让我们从扫描到第一个'1'开始，并设置起始位置s。然后计算每个 运行 of '1's c1 和随后的 运行 of '0's c0，创建对 (c1,c0).
然后扫描继续进行到最后，根据需要循环。如果我们将一个或多个'1'和'0'的运行表示为单个数字，而'|'作为字符串的开始和结束，那么我们有 cases:
|10101010|
^ initial start position s -- the string ends neatly with a run of '0's
|1010101|
^ new start position s -- the string starts and ends in a '1', so the first
run of '1's and run of '0's are rotated (left),
to be appended to the last run of '1's
Note that this changes our start position.
|01010101|
^ initial start position s -- the first run of '0's is rotated (left),
to follow the last run of '1's.
|010101010|
^ initial start position s -- the first run of '0's is rotated (left),
to be appended to the last run of '0's.
注意：如果字符串的开头和结尾都是“1”，则最初有 n 运行 个“0”和 n+1 运行s of '1'，但旋转将其减少为 n 运行s of '1'。同样，但相反，如果字符串以“0”开头和结尾。
让我们使用 A 作为对 (a1,a0) 的 shorthand。假设我们有另一对，X——(x1,x0)——然后可以比较这两对，因此：
- if a1 > x1 或 (a1 = x1 和 (a0 < x0) => A > X -- A 是更好的开始
- if a1 = x1 and a0 = x0 => A = X
- if a1 < x1 或 (a1 = x1 and (a0 > x0) => A < X -- X 是更好的开始
技巧可能是将每一对打包成一个整数——比如说 (x1 * N) - x0，其中 N 是至少是字符串的最大允许长度 -- 以便于比较。
在扫描字符串（如上所述）期间，让我们构造一个对向量。在此过程中，收集最大对值 A，以及 A 每次出现的位置列表 s 。列表中的每个 s 都是一个潜在的最佳开始位置。 （记录的s需要是对向量中的索引和原字符串中的偏移量。）
[如果输入的字符串真的很大，那么构建所有对的整个向量会占用内存。在这种情况下，向量需要作为 "virtual" 向量处理，并且当需要该向量中的项目时，必须通过读取实际字符串的相应部分来创建它。]
现在：
让我们简化两个或多个连续 A 的组。很明显，这样一组中的第二个和随后的 A 不可能是最好的开始，因为左边有一个更好的开始。因此，在扫描中，我们只需要记录此类组的前 A 个 s。
如果字符串以一个或多个A开头，并以一个或多个A结尾, 需要 "rotate" 将它们收集为一个组，并仅记录该组中最左边的 A 的 s（在通常的方式）。
如果列表中只有一个s，我们的工作就完成了。如果字符串是端到端的 A，则会在此处发现。
否则，我们需要为我们的（初始）A 考虑每个 s 之后的对 - 其中当我们说 'follow' 时，我们包括从字符串的末尾到开头的环绕（以及等效的对列表）。
注意：此时我们知道我们列表中的所有（初始）A 后跟零个或多个 A，然后是至少一个 x，其中 x < A。
因此，设置 i = 1，并考虑 s+i 处的所有对作为我们的 列表s。只为找到的最大对的实例保留 s。所以对于 i = 1，在这个例子中我们考虑对 x, y 和 z:
- ...Ax....Az...Az..Ax...Ay...
并且如果 x 最大，则此遍丢弃 Ay 和 Az。如果只剩下一个 s——在这个例子中，y 是最大的——我们的工作就完成了。否则，重复 i = i+1.
还有最后一条（我认为）皱纹。假设在找到 z 是最大的 ith 对之后，我们有：
- ...A===zA===z...
其中两个运行===是一样的。按照告诉我们忽略相同的 运行 中的第二个和后续 A 的相同逻辑，我们现在可以丢弃第二个 A=== z。事实上，我们可以丢弃第三个、第四个等连续的 A===z。令人高兴的是，它处理了（比如）的极端情况：
- =zA===zA===zA==
其中字符串是 A===z !
的序列我不知道，这一切似乎比我用铅笔和纸着手时想象的要复杂:-(
我想有人比我聪明得多，可以将其简化为一些标准的最大前缀字符串问题。
今天无聊，敲了一些代码（2020年4月10日修改）
typedef unsigned int uint ; // assume that's uint32_t or similar
enum { max_string_len = 5 * 100000 } ; // 5 * 10^5
typedef uint64_t pair_t ;
static uint
one_zero(const char* str, uint N)
{
enum { debug = false } ;
void* mem ;
size_t nmx ;
uint s1, s0 ; // initial run of '1'/'0's to be rotated
uint s ;
pair_t* pv ; // pair vector
uint* psi ; // pair string index
uint* spv ; // starts vector -- pair indexes
uint pn ; // count of pairs
uint sn ; // count of starts
pair_t bp ; // current best start pair value
uint bpi ; // current best start pair index
uint bsc ; // count of further best starts
char ch ;
if (N > max_string_len)
{
printf("*** N = %u > max_string_len (%u)\n", N, max_string_len) ;
return UINT_MAX ;
} ;
if (N < 1)
{
printf("*** N = 0 !!\n") ;
return UINT_MAX ;
} ;
// Decide on initial start position.
s = s1 = s0 = 0 ;
if (str[0] == '0')
{
// Start at first '1' after initial run of '0's
do
{
s += 1 ;
if (s == N)
return 0 ; // String is all '0's !!
}
while (str[s] == '0') ;
s0 = s ; // rotate initial run of '0's
}
else
{
// First digit is '1', but if last digit is also '1', need to rotate.
if (str[N-1] == '1')
{
// Step past the leading run of '1's and set length s1.
// This run will be appended to the last run of '1's in the string
do
{
s += 1 ;
if (s == N)
return 0 ; // String is all '1's !!
}
while (str[s] == '1') ;
s1 = s ; // rotate initial run of '1's
// Step past the (now) leading run of '0's and set length s0.
// This run will be appended to the last run of '1's in the string
//
// NB: we know there is at least one '0' and at least one '1' before
// the end of the string
do { s += 1 ; } while (str[s] == '0') ;
s0 = s - s1 ;
} ;
} ;
// Scan the string to construct the vector of pairs and the list of potential
// starts.
nmx = (((N / 2) + 64) / 64) * 64 ;
mem = malloc(nmx * (sizeof(pair_t) + sizeof(uint) + sizeof(uint))) ;
pv = (pair_t*)mem ;
spv = (uint*)(pv + nmx) ;
psi = (uint*)(spv + nmx) ;
pn = 0 ;
bp = 0 ; // no pair is 0 !
bpi = 0 ;
bsc = 0 ; // no best yet
do
{
uint x1, x0 ;
pair_t xp ;
psi[pn] = s ;
x1 = x0 = 0 ;
do
{
x1 += 1 ;
s += 1 ;
ch = (s < N) ? str[s] : '[=11=]' ;
}
while (ch == '1') ;
if (ch == '[=11=]')
{
x1 += s1 ;
x0 = s0 ;
}
else
{
do
{
x0 += 1 ;
s += 1 ;
ch = (s < N) ? str[s] : '[=11=]' ;
}
while (str[s] == '0') ;
if (ch == '[=11=]')
x0 += s0 ;
} ;
// Register pair (x1,x0)
reg:
pv[pn] = xp = ((uint64_t)x1 << 32) - x0 ;
if (debug && (N == 264))
printf("si=%u, sn=%u, pn=%u, xp=%lx bp=%lx\n", psi[sn], sn, pn, xp, bp) ;
if (xp > bp)
{
// New best start.
bpi = pn ;
bsc = 0 ;
bp = xp ;
}
else
bsc += (xp == bp) ;
pn += 1 ;
}
while (ch != '[=11=]') ;
// If there are 2 or more best starts, need to find them all, but discard
// second and subsequent contiguous ones.
spv[0] = bpi ;
sn = 1 ;
if (bsc != 0)
{
uint pi ;
bool rp ;
pi = bpi ;
rp = true ;
do
{
pi += 1 ;
if (pv[pi] != bp)
rp = false ;
else
{
bsc -= 1 ;
if (!rp)
{
spv[sn++] = pi ;
rp = true ;
} ;
} ;
}
while (bsc != 0) ;
} ;
// We have: pn pairs in pv[]
// sn start positions in sv[]
for (uint i = 1 ; sn > 1 ; ++i)
{
uint sc ;
uint pi ;
pair_t bp ;
if (debug && (N == 264))
{
printf("i=%u, sn=%u, pv:", i, sn) ;
for (uint s = 0 ; s < sn ; ++s)
printf(" %u", psi[spv[s]]) ;
printf("\n") ;
} ;
pi = spv[0] + i ; // index of first s+i pair
if (pi >= pn) { pi -= pn ; } ;
bp = pv[pi] ; // best value, so far.
sc = 1 ; // new count of best starts
for (uint sj = 1 ; sj < sn ; ++sj)
{
// Consider the ith pair ahead of sj -- compare with best so far.
uint pb, pj ;
pair_t xp ;
pb = spv[sj] ;
pj = pb + i ; // index of next s+i pair
if (pj >= pn) { pj -= pn ; } ;
xp = pv[pj] ;
if (xp == bp)
{
// sj is equal to the best so far
//
// So we keep both, unless we have the 'A==zA==z' case,
// where 'z == xp == sp', the current 'ith' position.
uint pa ;
pa = pi + 1 ;
if (pa == pn) { pa = 0 ; } ; // position after first 'z'
// If this is not an A==zA==z case, keep sj
// Otherwise, drop sj (by not putting it back into the list),
// but update pi so can spot A==zA==zA===z etc. cases.
if (pa != pb)
spv[sc++] = spv[sj] ; // keep sj
else
pi = pj ; // for further repeats
}
else if (xp < bp)
{
// sj is less than best -- do not put it back into the list
}
else
{
// sj is better than best -- discard everything so far, and
// set new best.
sc = 1 ; // back to one start
spv[0] = spv[sj] ; // new best
pi = pj ; // new index of ith pair
bp = xp ; // new best pair
} ;
} ;
sn = sc ;
} ;
s = psi[spv[0]] ;
free(mem) ;
return s ;
}
我已经根据其他地方给出的蛮力方法对此进行了测试，据我所知这是（现在，2020 年 4 月 10 日）工作代码。
当我在我的机器上计时时，对于 400,000..500,000 个字符的 100,000 个随机字符串（随机），我得到：
Brute Force: 281.8 secs CPU
My method: 130.3 secs CPU
这不包括构建随机字符串的 8.3 秒和 运行 空测试。 （这听起来可能很多，但对于 450,000 个字符的 100,000 个字符串，平均而言，每个字符少于 1 CPU 个循环。）
所以对于随机字符串，我的复杂方法比暴力法快两倍多一点。但它使用~N*16 字节的内存，而暴力法使用 N*2 字节。考虑到所涉及的努力，结果并不是非常令人满意。
但是，我也尝试了两种病态情况，(1) 重复“10”和 (2) 重复“10100010”，对于 400,000..500,000 个字符（随机）的 1000 个（不是 100000 个）字符串，我得到了:
Brute Force: (1) 1730.9 (2) 319.0 secs CPU
My method: 0.7 0.7 secs CPU
那个O(n^2)每次都会杀了你！
您想找到以带环绕的二进制编码字符串表示的最大数字。
解决方法如下：
- 设
len为字符串的长度 - 分配一个大小为
2 * len的数组并将字符串复制到其中。 - 使用线性搜索，找到长度为
len的最大子串在该数组中的位置pos（可以使用字典顺序）。 - 计算
res，转换后的数模109+7，读取len位从pos.[=34=开始] - 释放数组并 return
res.
下面是一个简单的函数实现：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long max_bin(const char *S) {
size_t i, pos, len;
char *a;
// long has at least 31 value bits, enough for numbers upto 2 * 1000000007
long res;
if ((len = strlen(S)) == 0)
return 0;
if ((a = malloc(len + len)) == NULL)
return -1;
memcpy(a, S, len);
memcpy(a + len, S, len);
// find the smallest right rotation for the greatest substring
for (pos = i = len; --i > 0;) {
if (memcmp(a + i, a + pos, len) > 0)
pos = i;
}
res = 0;
for (i = 0; i < len; i++) {
res = res + res + a[pos + i] - '0';
if (res >= 1000000007)
res -= 1000000007;
}
free(a);
return res;
}
int main(int argc, char *argv[]) {
for (int i = 1; i < argc; i++) {
printf("[%s] -> %ld\n", argv[i], max_bin(argv[i]));
}
return 0;
}
如果需要，避免内存分配是可行的。
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int convt(int N,string S)
{
int sum=0;
for(int i=0; i<N; i++)
{
int num=S[i];
sum += pow(2,N-1-i)*(num-48);
}
return sum;
}
string rot(int N, string S)
{
int temp;
temp = S[0];
for( int i=0; i<N;i++)
S[i]=S[i+1];
S[N-1]=temp;
return S;
}
int main() {
int t;
cin>>t;
while(t--)
{
int N,K;
cin>>N;
cin>>K;
char S[N];
for(int i=0; i<N; i++)
cin>>S[i];
string SS= S;
int mx_val=INT_MIN;
for(int i=0;i<N;i++)
{
string S1=rot(N,SS);
SS= S1;
int k_val=convt(N,SS);
if (k_val>mx_val)
mx_val=k_val;
}
int ki=0;
int j=0;
string S2=S;
while(ki!=K)
{
S2=rot(N,S2);
if (convt(N,S2)==mx_val)
ki++;
j++;
}
cout<<j<<endl;
}
}