首页 > 其他分享 >2024.7.31 test

2024.7.31 test

时间:2024-07-31 16:17:10浏览次数:15  
标签:le 2024.7 dep dfrac 31 MID int test sum

A

给定序列 \(S\),一开始只有一个数 \(x\) ,每次操作是把每个 \(S_i\) 替换为 \(S_i\) 的所有约数(从小到大排序)
求 \(k\) 次操作后序列前 \(m\) 的位置的和。\(x,k\le 10^{12},m\le 10^7\)。

因为把每个 \(S_i\) 替换为 \(S_i\) 的所有约数后相对顺序不变,所以直接从前往后搜索,复杂度 \(O(m)\)。

B

\(q\) 次询问,每次给出 \(x\),对于所有长度为 \(n\) 的排列执行以下代码并求和。\(q\le 5e4,n\le 3e5\).

int binsearch(int P[], int L, int R, int x) {
    if(L>R) return 0;
    int MID = (L + R) / 2;
    if(P[MID] == x || L == R) return P[MID];
    if(P[MID] > x) return P[MID] + binsearch(P, L, MID - 1, x);
    if(P[MID] < x) return P[MID] + binsearch(P, MID + 1, R, x);
}

我们把二分经过点的构成的树建出来。考虑枚举终点在哪,可以得出需要找 \(c_1\) 个数 \(<x\),\(c_2\) 个数 \(>x\)。
不难注意到 \((c_1,c_2)\) 只有 \(\log ^2n\) 种,我们可以预处理出来每种有多少条路径。
现在求在 \(1\sim (x-1)\) 中找 \(c_1\) 个数并求和,拆贡献,强制某数选剩下的方案数是 \(A_{x-2}^{c_1-1}\times c_1\),
所以总的贡献是 \(\frac{1}{2}x(x-1)\times A_{x-2}^{c_1-1}\times c_1\)。在 \((x+1)\sim n\) 找 \(c_2\) 个数同理。
注意在合并 \(c_1,c_2\) 总共的贡献时,需要在 \(c_1\) 这边乘上 \(A_{n-x}^{c_2}\),\(c_2\) 乘上 \(A_{x-1}^{c_1}\)。
最后再乘上不属于 \((c_1,c_2)\) 的贡献,是随便填的。

C

有序列 \(A\),如果 \(A_i\&A_j=0\),那么可以交换 \(A_i,A_j\),问最后字典序最小是多少。长度 \(\le 1e6,A_i\le 2^{20}\).

注意到若 \(A_i\) 能与 \(A_j\) 交换,\(A_j\) 能与 \(A_k\) 交换,那么 \(A_i\) 能与 \(A_k\) 交换。
所以一个连通块内的 \(A\) 都可以互相交换。不妨优化建图,\(A_i\) 向 \(A_i\) 取反的子集建双向边。
那么每个点朝其 popcount 少 \(1\) 的子集的点连单向边,最后 Tarjan 缩强连通分量。
在一个联通分量里的都可以互相交换。那么我们从前往后贪心即可。

D

在一棵树上,每个点的颜色在 \([l_u,r_u]\) 里随机,计算所有情况下,所有颜色相同的点两两距离之和的和。
\(n\le 1e5,l\le r\le 1e5\)。

点分治是其中一个做法。
考虑计算每条边的贡献,枚举颜色,这条边被计算了子树内外期望点数之积,这也是一种做法。
下面是通解。拆贡献,设 \(k_i\) 表示 \(r_i-l_i+1\),\(K=\prod k_i\).
$\sum_{c}\sum_{c\in i,j} \dfrac{K}{k_ik_j}(dep_i+dep_j-2dep_{lca(i,j)}) $.
提出 \(K\),\(=\sum_c\sum_{c\in i}\dfrac{dep_i}{k_i}\sum_{c\in j}\dfrac{1}{k_j}+\sum_c\sum_{c\in i}\dfrac{1}{k_i}\sum_{c\in j}\dfrac{dep_j}{k_j}-2\sum_c \sum _{c\in i}\dfrac{1}{k_i}\sum_{c\in j}\dfrac{1}{k_j} dep_{lca(i,j)}\).
前两部分枚举 \(c\),直接扫描线解决。第三部分存在 \(dep_{lca(i,j)}\),转化为 \(i,j\) 公共祖先个数。
所以我们在加入某个点的时候,转化为链加,链求和即可。

标签:le,2024.7,dep,dfrac,31,MID,int,test,sum
From: https://www.cnblogs.com/Simon-Gao/p/18334906

相关文章

  • GYOI Beginning Contest #1 -zh
    GYOIBeginningContest#1Div.3WelcometoGBCRound1。题目顺序按难度排序。ProblemContents来自XU的评价:T1需要思考一下T2有点水T3直接暴力T4?ProblemHintListT1Hint到底要怎样才需要交换呢?T2Hint我们设$g(i,j)$表示结点$i$到他的第$2^j$个......
  • 20240731题解
    这么简单的题目没有AK(计时器(timer)题目:每次可以加上\(2^n-1\),问多少次变成\(x\)题解:因为较大的数大于较小的数的两倍,直接贪心的选最大的即可。复杂度\(\Theta(T\logn)\)代码:#include<cstdio>#defineintlonglongconstintN=105,A=1000000000000000000;intT,x,f[N......
  • 闲话 731
    核方法(Kernelmethod),一种神秘的解析方法来解生成函数的(通常是多元的)式子。简单的例子:求Dyck路,即横着每次可以走斜上斜下,不能走到\(y\)轴下面,从\((0,0)\)走到\((n,0)\)的方案数。设\(f_i(z)\)为走到\((n,i)\)的方案数的OGF。那么显然有:\[f_i(z)=zf_{i-1}(z)+zf_{i......
  • Flink的DateStream API中的ProcessWindowFunction和AllWindowFunction两种用于窗口处
    目录ProcessWindowFunctionAllWindowFunction具体区别ProcessWindowFunction示例AllWindowFunction示例获取时间不同,一个数据产生的时间一个是数据处理的时间ProcessWindowFunctionAllWindowFunction具体示例ProcessWindowFunction示例AllWindowFunction示例总......
  • 【JAVA】TestNG 开源测试框架
    创建maven项目https://www.cnblogs.com/phoenixy/p/16850747.htmlpom.xml<?xmlversion="1.0"encoding="UTF-8"?><projectxmlns="http://maven.apache.org/POM/4.0.0"xmlns:xsi="http://www.w3.org/2001/XMLSche......
  • 2024/7/31 每日一题
    LeetCode3111覆盖所有点的最少矩形数目方法1:贪心classSolution:defminRectanglesToCoverPoints(self,points:List[List[int]],w:int)->int:lst=sorted(set(xforx,_inpoints))ans,idx,i=1,0,0#位于第一个whilei<le......
  • Tox 中的 Pytest - 找不到测试,`ImportError`
    我有一个具有当前结构的包:my_package|-pyproject.toml|-poetry.lock|-tox.ini|-my_package||-__init__.py||-my_package.py|-tests|-test_my_package.pypyproject.toml为pytest配置如下:[tool.pytest.ini_option......
  • backtesting.pyplot() 不在 x(时间)轴上显示 EST
    目前我有一个数据框,其中索引是配置了东部标准时间(EST)的DateTime对象。当我在backtesting.py中使用plot()绘制此数据框时,x轴显示为UTC时区,而不是EST时区。有没有办法让我更改它以显示EST时区?谢谢!很遗憾,backtesting.py库的plot()函数......
  • UnitTest
    UnitTest框架是Python自带的单元测试框架,也可以用来做自动化测试(管理和执行用例)核心要素(组成):1、TestCase(测试用例)2、TestSuite(测试套件):打包TestCase3、TestRunner(测试执行):执行Testsuite4、TestLoader(测试加载):对TestSuite的补充,也是打包Te......
  • python3 unittest+BeautifulReport单个进程输出多个测试报告
    最近一个项目中需要由于输出的案例内容非常多(上万条),导致BeautifulReport输出的报告内容非常大(几百兆)。浏览器无法正常处理这么大的测试报告,就算打开了,也不方便阅读和处理,因此需要将报告分成多个输出。经修改代码,发现单个进程内输出多个测试报告出现问题:第一个测试报告能正常数据......