做调查的有哪些网站,wordpress输出友情链接,旅游网站的设计与制作html,自己的卡盟网站怎么做分站题目描述
给定一个数列 A(a1,a2,⋯,an)#xff0c;问有多少个区间 [L,R] 满足区间内元素的乘积等于他们的和。
输入描述
输入第一行包含一个整数 n#xff0c;表示数列的长度。
第二行包含 n 个整数#xff0c;依次表示数列中的数 a1,a2,⋯,an。
输出描述 …题目描述
给定一个数列 A(a1,a2,⋯,an)问有多少个区间 [L,R] 满足区间内元素的乘积等于他们的和。
输入描述
输入第一行包含一个整数 n表示数列的长度。
第二行包含 n 个整数依次表示数列中的数 a1,a2,⋯,an。
输出描述
输出仅一行包含一个整数表示满足如上条件的区间的个数。
输入输出样例
示例 输入 4
1 3 2 2输出 6样例解释
符合条件的区间为 [1,1], [1,3], [2,2], [3,3], [3,4], [4,4]。
评测用例规模与约定
对于 20% 的评测用例n ≤ 3000
对于 50% 的评测用例n ≤ 20000
对于所有评测用例1 ≤ n ≤ 200000,1 ≤ ai ≤ 200000。 作者题解
通过题意可以知道我们其实就是想要找到满足区间和等于区间积的区间个数根据评测用例规模我们不难发现如果暴力计算从任意一个数开始的任意长度的区间一定会超时。
暴力计算除了超时还有一个问题就是乘积的变化是非常巨大的。虽然我们可以考虑到使用大数类但不妨我们考虑一下如果满足要求的结果是区间积等于区间和那么如果从某个时刻起区间积已经比理论区间和的最大值还要大了是不是就可以停下来了那么不难发现理论区间和最大值就是2e5 * 2e5。
进一步思考既然区间积的变化速度那么快即便只有2连续起来的增长速度也远超区间和的增长速度而区间积的增长速度要想比区间和慢使最终达到平衡那就只有1这个值是满足要求的。
于是我们便可以从1这个数值开始考虑我们不难发现在新加入区间的数值里如果加入1会使得区间和变大而区间积不变如果加入其他数值则不可控。这就给了我们启示总结一下就是
如果某个区间的区间和比区间积要小那么只要在这个区间的左右两边填充足够数量的1就可以使得区间和等于区间积。
由此我们便可以想到什么样的区间可以在左右两边加1呢我们只要收集所有不是1的数的下标由此进行遍历查找是不是就可以找到每个左右两边可以填充1的区间了。
区间和我们可以使用前缀和直接拿到而只考虑非1的数还有一个好处就是计算区间积的时候我们同样可以忽略1的存在只对非1的数做乘法运算因为乘1不会影响区间积。 编码思路
具体的我们可以在读取数据的时候使用pre数组记录前缀和便于我们计算区间和。
我们可以创建一个动态数组ArrayList记录所有不为1的数据下标并且在其前面加上数值0末尾加上数值n1其目的是为了方便计算整段数据首尾的1的个数。
ans的计算也尤为关键假设我们查询的某个区间刚好区间和等于区间积那么两侧加1都会导致区间和变大而区间积不变此时两侧的1就是多余的仅对ans做运算即可。
假设此时我们区间和小于区间积那么意味着可以通过两侧补1的方式实现相等那么就要具体分析并分类讨论
现在令左边有left个1右边有right个1而我们需要need个1。
如果左右两侧的1数量足够多那么任意一侧都可以填充(0,1,2,...need)个1来满足要求总共就是need1个区间。
如果只有一侧的1数量足够多那么1的数量较少的区间便成为了我们的限制于是满足要求的区间数量就变成了min(left, right)1个区间原理跟上面的差不多。
那么如果两侧的1数量都不是足够多但加起来又足以满足need那么多出来的1的个数便成为了我们的限制假设leftright刚好等于need那么我们就只有一种区间选取方式而不论任意一侧多余出来了一个1我们可以选取的区间就有了左/右移动一个位置的可能性。
于是我们可以想到在上述这种情况下满足要求的区间数量为leftright-need1
具体代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;public class Main {public static void main(String[] args) throws Exception{BufferedReader in new BufferedReader(new InputStreamReader(System.in));String[] temp in.readLine().split( );int n Integer.parseInt(temp[0]);// data表示原始数据int[] data new int[n 1];// pre记录前缀和long[] pre new long[n 1];// list用于记录非1数据的下标ArrayListInteger list new ArrayList();// 首部加0尾部加n1是为了方便计算首尾1的个数list.add(0);temp in.readLine().split( );for (int i 1; i n; i) {data[i] Integer.parseInt(temp[i - 1]);pre[i] pre[i - 1] data[i];if (data[i] ! 1) {list.add(i);}}list.add(n 1);// 以下是具体算法部分long ans 0;// 遍历list除了首尾部分的剩余内容其指的是非1的数据下标for (int i 1; i list.size() - 1; i) {// s表示的区间积// 每次遍历时s都默认是i所在的位置值并且先不考虑单个数构成的区间long s data[list.get(i)];for (int j i 1; j list.size() - 1; j) {// 随着j每往后移动到一个新的不为1的位置s需要进行更新s * data[list.get(j)];// 如果s大于区间和理论最大值就不必再计算了// 由于区间积的增长速度很快所以这个优化很关键// 具体的说可以使内层循环j的运行次数绝对低于log2(2e5 * 2e5)差不多是35左右if (s 2e5 * 2e5) {break;}// sum记录当前考虑的不为1的数之间的区间和注意细节不要写错long sum pre[list.get(j)] - pre[list.get(i) - 1];if (sum s) {if (sum s) { //如果sum刚好和区间积相等满足要求的区间只会增加1个ans;} else { // 如果有多的分类讨论// left记录左边1的个数right记录右边1的个数need表示需要1的个数int left list.get(i) - list.get(i - 1) - 1;int right list.get(j 1) - list.get(j) - 1;long need s - sum;if (left need right need){ // 如果两侧的1都足够多就有need1种选取方式ans need 1;} else if (left need || right need) { // 如果只有一侧1足够多ans Math.min(left, right) 1;} else if (left right need) { // 如果两侧都不足够多但加起来还是够用了ans left right - need 1;}// 如果两侧加起来都不够need那就直接忽略}}}}// 我们计算的时候忽略了所有单数据区间而但数据区间一定满足要求于是加上n进行输出System.out.println(ans n);}
}
