一、 题目大意给你一个长度为 n 的二进制字符串 s只包含 0 和 1。 你要构造一个无限长的字符串 t它是由 s 无限次拼接得到的tsssss…。 定义一个字符串的“平衡值”为字符 0 的数量减去字符 1 的数量。 现在问你在无限长字符串 t 的所有前缀中有多少个前缀的平衡值恰好等于 x 如果数量有无限个输出-1。(注空字符串也算前缀其平衡值为 0)数据范围1≤n≤10^5。二、 思考过程为什么不是单调队列很多同学一看到“前缀”和“平衡值”第一反应是能不能用滑动窗口能不能用单调栈维护最值绝对不行。单调队列/栈解决的是“局部视野内的相对最值”问题比如谁挡住了谁谁是区间最大值。 而这道题是在一个无限延伸的序列上找一个绝对等于 x的值。无限循环的物理模型本质上就是“等差数列求通项公式”。这道题是一道披着字符串外衣的数学周期枚举题。三、 题目分析与解题思路我们将单个字符串 s 的前缀平衡值预处理出来记为 a[i]。 那么完整走完一圈 s 所带来的总平衡值变化量就是 a[n]。对于无限循环字符串 t 的任意一个前缀它一定可以拆解为k 个完整的 s 周期 内部多出来的 i 个字符其中 k≥01≤i≤n。此时这个前缀的总平衡值公式为总平衡值k⋅a[n]a[i]题目要求这个总平衡值等于 x我们列出一元一次方程k⋅a[n]a[i]x移项解得我们需要找的周期数 kka[n]x−a[i]​解题核心既然 a[n] 是定值目标 x 也是定值。我们只需要用一个for循环遍历单圈内部的所有位置 i看看在这个位置上能不能解出一个合法的整数 k。由于方程里 a[n] 在分母的位置所以我们必须极其严谨地分两种情况讨论情况一a[n]0转圈不改变平衡值如果一整圈的平衡值是 0说明不管经历多少个周期平衡值永远在原地踏步。 此时方程变为 0x−a[i]。如果在第一圈里找到了 a[i]x那么以后每一圈走到这个位置都是 x答案是无限个输出-1。如果第一圈没找到那以后永远也找不到答案是0。情况二a[n]!0每次转圈都有稳定的增减我们需要验证解出来的 k 是否合法必须同时满足两个数学条件能整除(x−a[i])(%a[n])0。时间不能倒流圈数非负(x−a[i])/a[n]≥0。满足这两个条件说明在未来的第 k 圈的第 i 个位置总平衡值刚好为 x计数器1。四、 易错点总结除零异常在对 a[n] 取模或除法之前必须强制把a[n]0的情况用if-else隔离开。空字符串陷阱题目明确说明“空字符串也算一个有效前缀”。空串的平衡值为 0。所以在计算情况二时如果 x0必须让答案初始值cnt。推导符号错位很多同学把非负条件错写成x*a[n]0这是极其致命的数学错误。必须老老实实写完整的等式判断(x - a[i]) / a[n] 0。提前漏算补丁在 a[n]0 且没找到目标值时一定要记得输出0否则程序什么都不输出就进入下一轮导致输出行数对不上。五、 时空复杂度分析时间复杂度O(N)。只需预处理一遍前缀和再遍历一遍 0 到 n−1每次判断是 O(1) 的数学取模运算。整体严格线性。空间复杂度O(N)。只需要一个大小为 105 的数组存储单圈的前缀平衡值。六、 完整代码// Infinite Prefixes cf-1295B #include iostream #include cstring using namespace std; int t; int a[100010];//a[i]代表字符串s第i个位置的平衡值 int main(){ ios::sync_with_stdio(false); cin.tie(0); cint; //总共t组测试数据 while(t--){ int cnt0;//满足条件的前缀数量 int n,x;//字符串s的长度和目标平衡值 cinnx; //初始化a数组为0 memset(a,0,sizeof(a)); string s; cins; //计算单个周期字符串s的平衡值 for(int i1;is.size();i){ //0每出现一次平衡值1 if(s[i-1]0) a[i]a[i-1]1; //1每出现一次平衡值-1 else a[i]a[i-1]-1; } //计算会不会有无限个无限个的情况只能是每组字符串s的平衡值为0 //然后字符串s中存在某个位置的平衡值和x相等 if(a[n]0){//每组字符串s的平衡值 bool flag0;//标记s中是否存在某个位置平衡值和x相等 for(int i1;is.size();i){//遍历s if(a[i]x) flag1; } if(flag1){//如果存在就输出-1 代表有无限个 然后下一轮测试数据 cout-1endl; continue; } //不存在就代表根本没有 cout0\n; } else{ //如果要求平衡值是0 则所有字符串初始就存在一个满足条件的前缀-空串 if(x0) cnt; //否则就非无限个的情况 //a[n]就是每组字符串s总的平衡值 for(int i1;is.size();i){ //如果x能被a[i]通过加多组前缀的总和得到 数量就加一 // 1. (x-a[i])%a[n]0 保证能被完整周期整除 // 2. (x-a[i])/a[n]0 保证走过的圈数非负 if((x-a[i])%a[n]0(x-a[i])/a[n]0) cnt; } coutcnt\n; } } return 0; }