14. Juju and Binary String

2024-03-28 22:38

文章标签 string 14 binary juju

本文主要是介绍14. Juju and Binary String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：Juju and Binary String

感觉这题的思路和代码实现都比 E 题简单，不知道怎么评到的 2700 分。

给你一个长为 $n$ 的 01 串，定义其 cuteness 为 1 的个数比上总长度。让你找 $k$ 个子串，使它们的长度之和为 $m$ ，且拼接后的 cuteness 与原串的相等。最小化 $k$ 并输出方案。

设总共有 $x$ 个 1，那么子串中需要 $y=\dfrac{xm}{n}$ 个 1。显然，如果 $y$ 不是整数，那么一定构造不出来。否则肯定能构造出来，因为直接拿 $y$ 个 1 和 $m - y$ 个 0 就是一种方案了。

然后就是最小化 $k$ ，最理想的情况当然是存在一个长为 $m$ 的子串正好有 $y$ 个 1。第二个样例提示我们这种情况并不一定存在，但我们可以把原串连成一个环，如果我们选择的区间正好跨过了连起来的地方， $k$ 就为 $2$ 。可以证明，在环上总是可以找到这样的一个子串。

先证明一个引理：环上两个相邻的长为 $m$ 的子串内 1 的个数相差不会超过 $1$ 。

这是显然的，若第一个子串从 $i$ 处开始，则当且仅当 $s[i]\neq s[i+m]$ 时两个子串内 $1$ 的个数才会发生变化，两者差的绝对值必为 $1$ 。

这就意味着各子串之间 $1$ 的个数的变化是连续的，即如果存在两个子串，其中一个含有的 $1$ 的个数小于 $y$ ，另一个大于 $y$ ，就必然存在一个子串中 $1$ 的个数刚好是 $y$ 。

然后可以用反证法证明不可能所有子串内 $1$ 的个数均小于或均大于 $y$ 。求和一下就行了。

那么将原串复制一遍后求个前缀和就可以找到这个子串了。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
const int maxn = 4e5 + 5;
int n, m;
char str[maxn];
int pre[maxn];
void solve() {cin >> n >> m;cin >> (str + 1);int cnt = 0;for (int i = 1; i <= n; ++i) {if (str[i] == '1')cnt++;str[i + n] = str[i];}for (int i = 1; i <= 2 * n; ++i) {pre[i] = pre[i - 1] + (str[i] == '1');}ll tot = 1LL * cnt * m;if (tot % n != 0) {cout << -1 << endl;return;}tot /= n;for (int i = m; i < n + m; ++i) {if (pre[i] - pre[i - m] == tot) {if (i <= n) {cout << 1 << endl;cout << i - m + 1 << ' ' << i << endl;} else {cout << 2 << endl;cout << 1 << ' ' << i - n << endl;cout << n - (m - (i - n)) + 1 << ' ' << n << endl;}break;}}
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;cin >> T;while (T--) {solve();}
}