CF1526C Rings

题目传送门

题目大意

从一个长度为\(n\)的二进制数中截取两个长度大于等于\(\lfloor \frac{n}{2} \rfloor\)的二进制数，使两个数存在倍数（正整数倍）关系

思路

不要想太复杂，这题真的没那么难（虽然我最开始也想复杂了

可以在\(0\)上做文章

举个例子，假如我有一个二进制数\(10010\)，那么如果在他的后面添加几个\(0\)，新的数和他一定存在倍数关系（其实就相当于做左移运算）

而如果在他的前面添加\(0\)，他的值是不会变的，也就是存在\(1\)倍关系

据此，可以找到这个二进制数中的第一个\(0\)的位置(\(pos\)):

• \(pos \leq \lfloor \frac{n}{2} \rfloor\) 那么可以构造出\([pos,n]\)和\([pos+1,n]\)，它们存在一倍（即相等）关系

• \(\lfloor \frac{n}{2} \rfloor <pos\) 则可以构造出\([1,pos-1]\)，\([1,pos]\)，它们存在二倍关系（即一个末尾比另一个多出来一个\(0\)）

• \(pos\)不存在（也就是\(n\)里边全是\(1\)） 任意截取两段端点不同长度相同且大于\(\lfloor \frac{n}{2} \rfloor\)即可，为了方便我就是截取了\([1,\lfloor \frac{n}{2} \rfloor]\),\([2,\lfloor \frac{n}{2} \rfloor+1]\)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
void run()
{
    string s;
    int n,flag=0;
    cin>>n>>s;
    for(int i=1;i<=n;i++)
    {
        if(s[i-1]=='0')
        {
            if(i<=n/2) cout<<i<<" "<<n<<" "<<i+1<<" "<<n<<endl;
            else cout<<1<<" "<<i<<" "<<1<<" "<<i-1<<endl;
            flag=1;
            break;
        }
    }
    if(!flag) cout<<1<<" "<<n/2<<" "<<2<<" "<<n/2+1<<endl;
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin>>t;
    while(t--) run();
    system("echo. & pause");
    return 0;
}