考试的时候cy走进来说:今天提高组模拟,题目很水,请认真对待。
然后......
tm还真信了

T1

题目:有一排硬币堆,两个人轮流取硬币。每个选手随机取最左边或者最右边的一堆硬币。求先手期
望取得的硬币数。
硬币堆数<=1000,数据组数<=1000
60分算法:用f[i][j]表示从i到j的先手期望取硬币数,那么对于一段区间,先手要么取最左边的,要么取最右边的嘛,用s[i][j]表示i到j区间的硬币数和,所以很容易得到状态转移方程f[i][j]=(a[i]+s[i+1][j]-f[i+1][j])×0.5+(a[j]+s[i][j-1]-f[i][j-1])×0.5,其中s[i][j]的功能可以通过前缀和实现,复杂度O(Tn^2),但是T有1000组,超时。
100分算法:容易发现其实对于同样硬币堆数的情况,处于相同位置的硬币堆无论硬币数多少,被取到的期望值是一样的,比如说2堆硬币,左右都是0.5。我们可以预处理出来。用f[i][j]表示i堆硬币的情况下第j堆硬币被取到的期望值,因为先手要么拿最左边要么拿最右边,所以f[i][j]=1-(f[i-1][j]+f[i-1][j-1])×0.5。分别表示后手拿最右边和后手拿最左边的情况。预处理O(n^2),查询O(n)可以过。
代码

T2

题目:给定一个无自环重边的无向图,求这个图的三元环 1 的个数以及补图 2 的三元环个数。
m<=1000000,n<=1000000
30分算法:枚举三个点然后判断是否相连。
100分算法:看一看部分分的得法,补图和原图的和有些玄机。假如两点之间有边或者没有边可以看作是两种不同的颜色,那么对两边答案都没有贡献的是不同色三角形。一个点上任何一个“有”的边和一个“无”的边组合,无论第三边是什么,都会组成不同色三角形,而这样的三角形三条边中一定有一条边和其他两边的颜色都不同,这条边会被顶点重复计算。du[i]表示i点的度数,因此我们得到了一下算法:
pos=∑du[i]×(n-1-du[i])/2。
原图和补图的三角形和就是C(n,3)-pos。
而算原图三角形个数很简单,枚举每一条边,然后取边连接的度数少的那个点,枚举这个点相连的每一条边,链表哈希判断能否构成三角形,最后答案除以3
代码

T3

题目:秋锅对数论很感兴趣,他特别喜欢一种数字。秋锅把这种数字命名为 农数 ,英文名为 AQ
number 。这种数字定义如下:
定义 1 一个数 n 是农数,当且仅当对于每个质数 p ,要么 p ∤ n ,要么 p ≤ maxP rime 且存在一个
正奇数 k 使得 p k | n 且 p k+1 ∤ n 。
秋锅想知道,给定 upto和maxPrime ,问 1 到 Upto 里面的农数有多少个呢?
Upto<=10000000000,maxPrime<=1000000
题目可以转化为求upto以内可以表示为小于等于maxprime的质数的奇数次方的积的数的个数。
30分算法:暴力
60分算法:打出素数表,每次在当前搜到的num的基础上继续搜num×pri[x],num×pri[x]×(pri[x])^2,num×pri[x]×(pri[x])^2×(pri[x])^2…
100分算法:剪个枝,如果当前num×pri[x]只能乘一次了,num×pri[x]×pri[x]就超出upto了,我们知道num×pri[x+1]×pri[x+1]也会超出upto…
我们可以二分出还满足num×pri[w]<n的最后一个w,然后ans直接加上w-x+2,+2是因为此时num也算一个。
代码