【2016江苏省小学生夏令营选拔】小 X 分砖块(brick)

Question

数据范围太大了，求解 c++
【2016江苏省小学生夏令营选拔】小 X 分砖块(brick)
题目描述
小 X 喜欢跟着爸爸跑到建筑工地上去。
这天，小 X 看到一排砖，每块要么是白色的（0），要么是黑色的（1）。小 X 想把这排砖分成若干非空段，使得每段白砖和黑砖块数的比例相同。
当然，小 X 可以直接把整排砖作为一段，那就太简单了。为了增加难度，小 X 想知道最多能分成多少段，例如：
100011 = 10 + 0011（即样例 1，最多分成 2 段，比例为 1:1）；
0001110000000001 = 0001 + 11000000 + 0001（即样例 2，最多分成 3 段，比例为 3:1）。
小 X 百思不得其解，希望你帮他。

输入
从文件 brick.in 中读入数据。

第一行包含一个整数 N。我们将用 N 行来描述这排砖，初始时这排砖为空。
接下来 N 行，每行包含用一个空格隔开的两个整数 Ki,Ci（Ci 只可能是 0 或 1），表示在上一行描述完后尾部又有了 Ki 块颜色为 Ci 的砖。

输出
输出到文件 brick.out 中。

第一行包含一个整数，表示最多能分成的段数。

样例输入 复制
样例输入1
3
1 1
3 0
2 1
样例输入2
4
3 0
3 1
9 0
1 1

样例输出 复制
样例输出1

2
样例输出2

3

数据范围限制
对于 30%的数据，N=1。
对于 60%的数据，所有 Ki 均相等。
对于 100%的数据，1≤N≤100000，1≤Ki≤1000000000，砖的总块数不超过 1000000000。

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题分析： 给定一串由 0 和 1 组成的序列，要求将其尽可能分割为多个子段，使得每个子段内 0 和 1 的个数比例相同。 假设将序列分为了 k 段，则对于每个子段 j，设其中 0 和 1 的个数分别为 a[j] 和 b[j]，总共 0 和 1 的个数分别为 A 和 B，则有： a[j]/b[j] = A/B 进一步变换得： a[j] / A = b[j] / B 其中等式左侧仅与 j 相关，而右侧则与 k 和 j 相关。由于 a[j] 和 b[j] 都是非负整数，因此必定有 A 整除 a[j]，B 整除 b[j]。也就是要求 A 和 B 满足的条件。 令 C = gcd(A,B)（即 A 和 B 的最大公约数），则 A/C 和 B/C 互质。由于对于每个子段 j，左右两侧的比值必定相同，因此有： a[1]+a[2]+...+a[j] = k * (A/C) b[1]+b[2]+...+b[j] = k * (B/C) 得到了 2 个等式和 2 个未知数（A 和 B），问题转化为求解这 2 个未知数。其中 a[i] 和 b[i] 的值可以不用保存，直接在输入的时候处理掉就好，每输入一个数字就更新一下 A 和 B 即可。 最后分 k 段即可，具体方法为：从前往后遍历，同时记录下每一位是从哪个结尾位置开始的，每当找到一个新的位置 i，就检查 i 到前一段结尾（包括前一段结尾）的部分与后面的部分的比例是否相同，如果相同则将其分为一段。 时间复杂度： 总共只需要遍历一遍输入，因此时间复杂度为 O(N)。 参考代码：