A题
题意是找到一个数组中,右侧第一个比\(a[1]\)大的位置,很简单
B题
给定一个数组\(A[i]\)和数字\(ans\),如果把ans看作背包容量,问您几个背包可以把所有的数组放进去?这和背包问题不相同的是,数组里的内容必须挨着放,所以这个题非常简单,贪心就行,能放得下就放,放不下就不放
C题
给定数组\(A[i]\),对于下面的式子
\[\sum_{i=1}^{N}\sum_{j=i+1}^{N} (a[i]+a[j])\%100000000 \]\[n \leq 3*10^5 \]\[a[i] \leq 10^8 \]这个题求的是模数的和,不是和的模,如果是和的模就比较好做,因为
\[(a+b)\%c+(a+d)\%c=(2*a)\%c+(b+d)\%c \]我们只需要将贡献拆开,用前缀和完成就可以了
但是这个题,我们求的是模数的和,不能用上面的式子,观察到\(a[i]\)的范围,两个数加起来共有两种可能,一种是不超过1e8,一种是超过1e8,超过1e8的话,模操作我们可以减去1e8,
同时,我们把这个式子拆开看,会发现他的意义就是\(C_{n}^2\),任选两个数加起来,所以每个数都被加过n-1次,然后我们再把所有加起来的和超过1e8的减去,所以我们先把答案加进去,然后再减掉1e8的对数就行,怎么寻找1e8的对数呢?
把数组排序,从小到大排序,利用双指针,对于a[1]来说,找到最大的右端点,使其和大于1e8,然后双指针不断移动即可,l左指针不断向右移动,r右指针不断向左移动,当l==r的时候退出,对于l后面的答案,就是大于1e8的,用答案减去即可,感觉这个题还是比较难的
D题
给定数组\(A[i]\),对于下面的式子
\[对于两个正整数x,y,如果x=3,y=14,f(x,y)=314,x=1,y=100,f(x,y)=1100 \sum_{i=1}^{N}\sum_{j=i+1}^{N} f(a[i],a[j]) \]\[n \leq 2*10^5 \]\[a[i] \leq 10^9 \]这个题感觉比第三题简单,对于\(a[i]\),我们先计算出他的位数,比如说123是3位,那么对于\(j< i,所有的a[j]都需要乘以j的10^{位数}\),这部分可以使用前缀和,同时\(a[i]\)被算了\(i-1\)次,加上即可,这就完了
ps:这个题一直错,因为我一直爆掉long long了,long long 最大的范围是\(10^{18}\),切记
标签:10,leq,sum,long,ABC353,数组,1e8 From: https://www.cnblogs.com/sdfzls/p/18197768