题解：CF1658F Juju and Binary String / ARIS0_0 - 39

Kei__ · 2026-05-09 09:58:34 · 题解

诈骗题啊。

结论：k\le 2，要么无解，要么是一段区间，要么由一段前缀和一段后缀组成。

我们设 s 内 1 的个数为 x，所选子段内 1 的个数为 y，那么 \frac{x}{n}=\frac{y}{m}，则 y=\frac{mx}{n}，如果 n\nmid mx 则显然无解。

我们将原串接链成环，让一个长度为 m 的区间在环上滑动，设 f(i) 表示以 i 为起点，在环上长度为 m 的区间内 1 的个数，则 f(i)-f(i-1)\in\{-1,0,1\}，且不难发现：

由离散介值定理，一定存在一个 i，满足 f(i)=y。

而在环上滑动的区间在原串上要么是一段区间，要么是一段前缀拼上一段后缀，于是我们前缀和加后缀和枚举一下就搞完了。

最后证一下离散介值定理：

假设 f(1)\le y\le f(n)，令 k=\min\{i\mid f(i)\ge y\}，因为 \bar{f}=y，所以一定存在 f(i)\ge y。

若 k=1，则 f(k)\ge y 且 f(k)\le y，因此 f(k)=y。

若 1<k\le n，因为 f(k)-f(k-1)\in\{-1,0,1\}，所以一定存在 f(k)=y。

对于 f(1)\ge y\ge f(n) 同理，取反即可。证毕。

参考代码如下：

#include<bits/stdc++.h>
#define cin_fast ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define fi first
#define se second
//#define int long long 
#define in(a) a = read()
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5 , mod = 998244353;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f; 
inline int read() {
    int x = 0;
    char ch = getchar();
    bool f = 0;
    while('9' < ch || ch < '0') f |= ch == '-' , ch = getchar();
    while('0' <= ch && ch <= '9') x = (x << 3) + (x << 1) + ch - '0' , ch = getchar();
    return f ? -x : x;
}
ll prv[N];
vector<pair<int , int>>ans;
signed main() {
    //cin_fast;
    int t;
    cin >> t;
    while(t --) {
        ans.clear();
        ll n , m , c;
        string s;
        cin >> n >> m >> s;
        prv[n] = 0;
        for(int i = n - 1 ; ~i ; i --) {
            prv[i] = prv[i + 1] + s[i] - '0';
        }
        if((prv[0] * m) % n != 0) {
            cout << "-1\n";
            continue;
        }
        c = (prv[0] * m) / n;
        for(int i = n - m ; ~i ; i --) {
            if(prv[i] - prv[i + m] == c) {
                ans.push_back({i + 1 , i + m});
                break;
            }
        }
        if(!ans.empty()) {
            cout << 1 << '\n';
            cout << ans[0].first << ' ' << ans[0].second << '\n';
            continue;
        }
        for(int i = 0 , pre = 0 ; i < m ; i ++) {
            pre += s[i] - '0';
            if(pre + prv[n - m + i + 1] == c) {
                ans.push_back({1 , i + 1}) , ans.push_back({n - m + i + 2 , n});
                break;
            }
        }
        cout << 2 << '\n';
        cout << ans[0].first << ' ' << ans[0].second << '\n' << ans[1].first << ' ' << ans[1].second << '\n';
    }
    return 0;
}
/*
破旧的你
即使有再多的遗憾
相同地点的相片
却找不回另一半
你听呐
雪花掩盖着哽咽
叹息着离别
this ARIS 39
*/