首页 > 其他分享 >ABC353

ABC353

时间:2024-05-17 14:56:30浏览次数:20  
标签:10 leq sum long ABC353 数组 1e8

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

相关文章

  • 「ABC353」Yet Another Sigma Problem
    题目字典树做法(用时187ms)#include<cstdio>#include<ctype.h>constintN=3e5+10;intn;longlongans;inttrans[N][26],cnt[N];inttot;chars[N];template<classT>voidread(T&x){ charc=getchar(); while(!isdigit(c))c=getchar()......
  • abc353f 题解
    大分讨,由于没注意到细节挂大分。下面称大小为\(n\timesn\)的为大格子,\(1\times1\)的为小格子。把\(n\timesn\)个小格子组成的正方形称为一个部分。分析我们先来讨论一般情况。思考一对于\(n\ge3\)的一般情况,如果要求任意两个大格子到对方的距离最小,怎么做?根据贪......
  • ABC353 | 如同流星划过天空
    ABC353|如同流星划过天空A.&B.依题意模拟即可。C.注意只有\(f(x,y)\)需要对\(10^8\)取模,\(f\)的求和不需要。关注到\(a_i\in[1,10^8)\),故\(a_i+a_j\in[2,2\times10^8)\)。从而\(f(x,y)=[x+y<10^8](x+y)+[x+y\ge10^8](x+y-10^8)=x+y-10^8[x+y\ge10^......
  • ABC353C Sigma Problem 题解
    ABC353CSigmaProblem题解题目链接:AT题目中的两个求和符号\(\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\)实际上是在枚举所有的有序数对\((i,j)\)。而有序数对的个数\(N(N-1)/2=O(N^{2})\),真的去枚举所有数对肯定会T。这时应该考虑去拆贡献,求出每个\(A_i\)对答案的贡献。......
  • ABC353E字典树处理最长公共前缀
    https://atcoder.jp/contests/abc353/tasks/abc353_e其实就是字典树板子题。似乎遇到最长公共前缀,就该想到字典树。依次加入每个字符串:维护一个数组siz来统计在当前串之前的串在对应点的出现次数。手模一下字典树的建树过程,显然如果当前串\(S_i\)能跑到一个曾经串\(S_......
  • ABC353
    不知道为啥有断更了一周...Ewoc,怎么跟我出的题目这么像先把字符串扔到一个Trie里面,然后对于每一个点我们考虑这一个点到根节点组成的字符串能是多少对字符串的最长公共前缀。我们定义\(cnt_u\)表示共有多少个字符串的结尾在以\(u\)为根的子树内。对于\(u\)节点,其贡献......