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