题目描述
思路:(构造题)
首先考虑特殊情况
如果全为1 那么对半就行
如果全为0 那么对半也行
(昨晚不知道为啥考虑到这之后没往后考虑,一直在看样例,到最后直接跳过给D1做了)
构造题多种答案 任意一个即可, 不要太在意样例。。
剩下的就是有0有1的
假设10111 那么取[2, 5] [3, 5] 是一样的 前边只多了一个空0
11101 那么取[1, 4] [1, 3] 也行 因为[1,3] = 2 * [1,4]
C++ 代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair <int, int> PII;
char str[maxn];
int main()//全0全1 直接对半
{
int T;
scanf("%d", &T);
while(T --)
{
int n;
scanf("%d", &n);
scanf("%s", str + 1);
int mid = n / 2;//前半部分
bool flog = false;
bool flag = false;
for(int i = 1 ; i <= mid ; i ++)
{
if(str[i] == '0')
{
flog = true;
printf("%d %d %d %d\n", i , n, i + 1, n);
break;
}
}
if(!flog) //前半部分 没有
{
int sta = 1;
for(int i = mid + 1; i <= n ; i ++)
{
if(str[i] == '0')
{
flag = true;
printf("%d %d %d %d\n", sta, i, sta, i - 1);
break;
}
}
}
if(!flog && !flag)
{
if(n % 2 == 0)
printf("1 %d %d %d\n", mid, mid + 1, n);
else
printf("1 %d %d %d\n", mid + 1, mid + 1, n);
}
}
return 0;
}
这道题我昨晚也没构造出来。。。然后就心态炸了。掉大分😫😫
codeforce 加个好友啊?
我id是peter_hxy
巨巨你的是啥?😁
我就一 小绿名 syyyl