涉及知识点前缀和我发现我这个想法比官方题解的时间复杂度更低且更容易理解一点分享一下题目大意给定一个长度为 n 的 01 二进制串 s定义字符串的循环平衡状态在它的相邻字符对中00,01,10,11 这四类字符对的数量全部相等并且头尾相邻。共 q 次询问每次给出区间 ( lr ) 一个字串每一次我们可以在子串的任何位置插入一个0或1求对应子串达到循环平衡状态的最小代价。先给个链接Educational Codeforces Round 194 (Div. 2) E. Cyclic Balance核心思路首先我们可以知道一个头尾相连的字符串相邻对数就等于该字符串的长度而要达成题目中所要求的循环平衡状态四种字符对的数量必须相等也就是说我们目标字符串肯定得是 4 的倍数。假设子串长为 m一个字符对出现的次数是 T 次那么目标字符串总长为 4T 。我们需要插入的字符数量就为 4T - m 个。对于所有符合要求的最小四单元子串0011011011001001 我们可以发现本质上就是 0011的循环位移。因此任何长度为 4T 的循环平衡串本质上都可以看作是由 T 个 0011 单元拼接而成的。对于每一个 [l, r] 的区间我们用以下字母统计各字符对的数量a子串中00字符对的数量b子串中11字符对的数量c子串中01或10字符对的数量每一个0011子串单元有以下要求1 个00字符对1 个11字符对1 个01字符对1 个10字符对。由于我们只能插入字符问题就转化成了我们最少需要多少个0011积木单元才能满足所有的条件。约束条件在一个包含01字符对的串中因为首尾相连形成了闭环所以 01 字符对和 10 字符对的数量是相等的对于一个子串lr我们可以预处理出相邻对 01 和 10 的字符对有多少个。假设加上 a[ l ] 和 a[ r ] 是否也是由 0 到 1总共有 d 个字符对那么 01 字符对就有 d / 2 个这里我们记为 c 个 那么我们至少需要 c 个字串单元所以T c。记区间内含 0 的字符对数量为 cnt0 因为含 0 开头的字符串有00、01所以字符对 00 的数量 a 为 cnt0 - c。每个单元至少有两个所以T 记区间内含 1 的字符对数量为 cnt1 因为含 1 开头的字符串有10、11所以字符对 11 的数量 b 为 cnt1 - c。每个单元至少有两个所以T 由于一个子串一定要包含三个字符对a, b, cT 对于上述4个条件由于必须全部都要满足我们应取四个限制条件的 max 这样才是满足所有条件的最小的 T max( t1, t2, t3, t4 )具体实现为了快速求出任意区间 [l, r] 的 cnt1 和01变换次数 d我们预处理两个前缀和数组pre[i]前 i 个字符中1的个数。通过pre[r] - pre[l-1]即可 O(1) 得到区间内 1 的个数 cnt1。pre_diff[i]前 i 个字符中满足 s[i] ! s[i-1] 的相邻位置数量。通过pre_diff[r] - pre_diff[l-1]得到区间内相邻字符不同的次数再结合端点 s[l] 与 s[r] 的关系即可得到 01 变换次数 d。AC代码时间复杂度 O(n q) 官题解是O(n qlogn)#include bits/stdc.h using namespace std; #define int long long #define endl \n typedef pairint,int PII; const int INF0x3f3f3f3f3f3f3f3f; int cal(int a, int b, int c){ int t1 c; int t2 (a c 1) /2; int t3 (b c 1) /2; int t4 (a b c 2) / 3; return max({t1,t2,t3,t4}); } void solve() { int n, q; cin n q; vectorint pre(n 1), pre_diff(n 1); string s; cin s; s s; for(int i 1; i n; i){ pre[i] pre[i - 1] (s[i] - 0); if(i 1) pre_diff[i] pre_diff[i - 1] (s[i] ! s[i - 1]); } while(q--){ int l, r; cin l r; int cnt1 pre[r] - pre[l - 1]; int cnt0 r - l 1 - cnt1; int d pre_diff[r] - pre_diff[l - 1]; d (s[r] ! s[l]); int c d/2; int a cnt0 - c; int b cnt1 - c; int cnt cal(a, b, c); cout 4 * cnt - (r - l 1) endl; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t 1; // cin t; while(t--){ solve(); } return 0; }