首页 > 其他分享 >杂题

杂题

时间:2023-07-30 15:55:20浏览次数:30  
标签:lfloor lceil frac limits rceil sum 杂题

题意

给定\(n\)个元素的序列\(\{a_i\}\),\(m\)个元素的序列\(\{b_i\}\),以及\(L\),求:
\(\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=1}^L\lceil\frac{a_i+b_j}{k}\rceil\)
\(n,m\le 1000\)
\(a_i、b_i\in[1,10^9]\)
\(L\in[1,2\times 10^9]\)

做法

取\(B\ge \sqrt{a_i+b_j}\)

\[\begin{aligned}&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=1}^L\lceil\frac{a_i+b_j}{k}\rceil\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{l=1}^{\infty}\sum\limits_{k=1}^L[\lceil\frac{a_i+b_j}{k}\rceil\ge l]\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\{(\sum\limits_{l=1}^{B}\sum\limits_{k=1}^L[\lceil\frac{a_i+b_j}{k}\rceil\ge l])+\sum\limits_{k=1}^L\max(\lceil\frac{a_i+b_j}{k}\rceil-B,0)\}\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\{\sum\limits_{l=1}^{B}\min(\lfloor\frac{a_i+b_j-1}{l-1}\rfloor,L)+\sum\limits_{k=1}^L\max(\lceil\frac{a_i+b_j}{k}\rceil-B,0)\}\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\{\sum\limits_{l=1}^{B}\min(\lfloor\frac{a_i+b_j-1}{l-1}\rfloor,L)+\sum\limits_{k=1}^B\max(\lceil\frac{a_i+b_j}{k}\rceil-B,0)\}\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^m\{\sum\limits_{l=1}^{B}\min(\lfloor\frac{a_i+b_j-1}{l-1}\rfloor,L)+\sum\limits_{k=1}^B\max(\lceil\frac{a_i+b_j}{k}\rceil,B)-B\}\\ =&\sum\limits_{l=1}^{B}\sum\limits_{i=1}^n\sum\limits_{j=1}^m\min(\lfloor\frac{a_i+b_j-1}{l-1}\rfloor,L)+\sum\limits_{k=1}^B\sum\limits_{i=1}^n\sum\limits_{j=1}^m\max(\lceil\frac{a_i+b_j}{k}\rceil,B)-B\\ \end{aligned}\]

两部分处理类似,
例如第一部分,对\(\{a_i\},\{b_i\}\)排序,枚举\(l\),扫描\(i\),这时\(j\)可以分为前后两部分从而去掉\(\min\),\(\lfloor\frac{x+y}{l}\rfloor=\lfloor\frac{x}{l}\rfloor+\lfloor\frac{y}{l}\rfloor+[x\mod l+y\mod l\ge l]\),布尔表达式用树状数组处理。

复杂度\(O(nB\log B)\)

标签:lfloor,lceil,frac,limits,rceil,sum,杂题
From: https://www.cnblogs.com/Grice/p/17591551.html

相关文章

  • 2023暑假集训杂题
    2023暑假集训杂题解题报告UOJNOIRound#7Day1那些你不要的题目链接题目描述给定长度为\(n\)的序列\(A\),保证\(n\)为奇数,你是先手,每次先手与后手分别取相邻的\(2\)个数,并将剩下的数合并。先手希望最后剩下的数最大,后手希望剩下的数最小,在最优策略下,最后剩下的数是多......
  • 杂题记录
    随机做题过程中遇到感觉还不错的题就会记录下来,随缘更新CF360BLevkoandArray考虑二分答案\(x\)后用dp检验设\(dp_i\)为钦定\(a_i\)不会改变后,在\(i\)之前有多少数字可以不改变位置,有转移方程\[dp_i=\max\limits_{j<i\;\and\;|a_i-a_j|\leq(i-j)\times......
  • 一些杂题
    一些杂题,主要是贪心(模拟费用流)。Bohater有\(n\)只怪物,为了打败第\(i\)只怪物,你会下降\(d_i\)的血量。击败怪物后,会掉落回复\(a_i\)生命值的血药。任何时刻血量都不能小于等于\(0\)。问是否存在一种打怪顺序使得自身不死掉。数据范围:\(n\le10^5\)。简单贪心,我们把......
  • 初三赛季杂题泛做
    模拟赛1006T3可以发现交集点选的边一定是它的最小生成树上的,2^n爆算即可模拟赛1006T4这种题做过好多遍了,一个广为人知的结论就是k选的区间一定是k+1选的区间的前缀,线段树上二分即可模拟赛1007T3考虑每个不同的字符串前缀都会作为一个trie树上的节点,于是表示出每个前缀t至......
  • 初三赛季杂题泛做(9-10月)
    CF1580div1A:傻逼题,一开始没想出来,冷静了一会发现可以枚举两行,中间记录个前缀后缀最小值就行了B:考虑dp,设f[n][m][k]为答案,发现枚举最大数的位置可以做,于是就做了N^5tm能过C:想了一会,然后5ab说可以根号分治,我想了想好像真可以,于是就写了。x+y大于sqrtn的直接开大桶算贡献......
  • 7月杂题
    1.CF1835FGoodGraph判定YesorNo等同于判是否存在最大匹配。如果不存在,考虑找到一个不在匹配的左部点,在残量网络上bfs即可。如果存在,考虑tight集合是怎么构成的。如果\(S_i\)表示包含左部点\(i\)的最小tight集合,发现每个tight集合都是一些\(S_i\)的并。考......
  • 计数杂题
    搞一点计数题放在这,看到有意思的计数就更(虽然在组合数学那已经更了好多了)。[CTSC2017]吉夫特给定一个长度为\(n\)的序列\(a\),保证\(a_i\)互不相同。求出有多少个长度大于等于二的序列满足\[\prod_{i=2}^{k}\binom{a_{b_{i-1}}}{a_{b_i}}\bmod2=\binom{a_{b_1}}{a_{......
  • 2023.7.5 杂题
    CF1174FEhabandtheBigFinale树链剖分。先s1求出\(x\)所在子树\(y\)。若\(y\)为\(1\)轻儿子,递归求解\(y\)。若\(y\)为重儿子,那么找到重链上与\(x\)深度相同的节点\(c\).调用dc,此时\(c\)向上跳\(x\)与\(c\)距离的一半便是\(lca\),递归求解。相当......
  • 【杂题乱写】6 月多校分治专题训练
    AGym-101471DMoneyfornothing就是求\((d_j-c_i)(q_j-p_i)\)的最大值。可以看作点对\((d_j,q_j)\)与\((c_i,p_i)\)在二维平面上构成矩形的最大值,且\(c_i\ged_j,p_i\geq_j\)。把卖家点对放在序列\(a\),买家点对放在序列\(b\),先删去一定不优的点,删完之后\(a,b\)都......
  • 【杂题乱写】6 月多校分治专题训练
    AGym-101471DMoneyfornothing就是求\((d_j-c_i)(q_j-p_i)\)的最大值。可以看作点对\((d_j,q_j)\)与\((c_i,p_i)\)在二维平面上构成矩形的最大值,且\(c_i\ged_j,p_i\geq_j\)。把卖家点对放在序列\(a\),买家点对放在序列\(b\),先删去一定不优的点,删完之后\(a,b\)都......