题目：Rings

题意：给出一个长为n的二进制串s，问是否可以找出其两个\(length \geq \lfloor \frac{n}{2} \rfloor\)的子串s1, s2（这两个串起点位置和终点位置不能同时相等），且\(f(s1) = f(s2) \times k（k \geq 0且为整数）\)，分别输出两个串的起点和终点位置。

\(f(x)：代表将一个二进制数x转换为十进制得到的值\) 。

解析：需要分三种情况情况进行构造。

• 若s中不存在0（即全1情况）：想办法构造两个串相等，并且让其长度正好为\(\lfloor \frac{n}{2} \rfloor\)即可。
• 若s中存在0，这找到第一次出现0的位置记为pos。
  • 若\(pos \leq \lfloor \frac{n}{2} \rfloor\)，可以构造\(s_1 == s_2\)，例如：\(s = 10110, s_1 = 0110, s_2 = 110\)，即区间为：[pos, n]和[pos + 1, n]。
  • 否则，可以构造\(s_1 == 2s_2\)，例如：\(s = 1111001, s_1 = 11110, s_2 = 1111\)，即区间为：[1, pos]和[1, pos - 1]。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int t;
char s[20005];

int main()
{
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        scanf("%s", s + 1);
        int cntone = 0, pos = 0;
        for(int i = 1; i <= n; i++)
        {
            if(s[i] == '0' && !pos) pos = i;
            if(s[i] == '1') cntone ++;
        }
        if(cntone == n) //全为1特判
        {
            cout << 1 << " " << n / 2 << " " << 2 << " " << n / 2 + 1 << endl;
            continue;
        }
        if(pos <= n / 2)
            cout << pos << " " << n << " " << pos + 1 << " " << n << endl;
        else
            cout << 1 << " " << pos << " " << 1 << " " << pos - 1 << endl;
    }
    return 0;
}