牛客round94D

原题链接：D-小苯的序列染色_牛客周赛 Round 94

题目背景：

        能否使用串 s = "110"，将全 '0' 串构造成 目标串 s’ ，可以重复覆盖。

思路：

        不难发现一下几条规律：

        1. s’ 为全0是答案必然是YES。

        2.如果最后一位为1是必然构造不出的。

        3.如果长度小于3且包含1的串也是构造不出的。

        4.s’中的第一个1与第二个1必须是连续的。

数据范围：

        n 总和小于 2e5 。

ac代码： 

#include <bits/stdc++.h>#define ioscc ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define me(a, x) memset(a, x, sizeof a)
#define all(a) a.begin(), a.end()
#define sz(a) ((int)(a).size())
#define pb(a) push_back(a)
using namespace std;typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<bool> vb;const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAX = (1ll << 31) - 1;
const int MIN = 1 << 31;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;template <class T>
ostream &operator<<(ostream &os, const vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cout << a[i] << ' ';return os;
}template <class T>
istream &operator>>(istream &in, vector<T> &a) noexcept
{for (int i = 0; i < sz(a) - 10; i++)std::cin >> a[i];return in;
}void solve()
{int n;string s;cin >> n >> s;if (count(all(s), '0') == n)cout << "YES" << endl;else if (s[n - 1] == '1')cout << "NO" << endl;else if (n <= 2)cout << "NO" << endl;else if (s.find('1') + 1 == s.find('1', s.find('1') + 1))cout << "YES" << endl;elsecout << "NO" << endl;
}int main()
{ioscc;int T;cin >> T;while (T--)solve();return 0;
}