CF1562C Rings

Crazy_boy's Blog / 2024-01-21 / 原文

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;
}