题解

1.Coin

大意:一个数列,两个人随机从两端取走数。求先手期望取走多少数。
60分:考场上俺就是这么打的。如果用f[i][j]表示数列[i...j]先手期望取走的数。

f[i][j]=

(f[i+2][j]+w[i]

+f[i][j-2]+w[j]

+f[i+1][j-1]+w[i]

+f[i+1][j-1]+w[j])/4

O(n^2*T);
100分:考虑到对于出现的一定长度的数列,每个位置上的数被取到的概率是不变的。所以如果f[i][j]表示出现了长度为i的数列,第j个数被取到的概率。则:

f[i][j]=

(1-f[i-1][j]+

1-f[i-1][j-1])/2

(其中前者表示取走最后一个数,后者表示取走前一个数。)
这样就可以O(n^2+n*T);

2.Triangle

大意:求一个图中三元环的个数及不图中三元环的个数。
30分:枚举每个点暴力判边。
72分:前30分用30分做法,后42分只输出原图三元环个数,用后文的O(M)算法。
100分:令图中有的边为黑边,没有边为白边。则要求的是全为白边和全为黑边的三元环的个数。令B表示全黑三角形,W为全白三角形,A表示彩色三角形。则

B+W+A=N(N-1)(N-2)/6

其中A可以用O(N)求出:设black[i]表示与i点相连的点数,white[i]表示与i点不相邻的点数,则A=(Σ(black[i]*white[i]))/2 (i∈V).
由于白边数量较多,所以考虑求出B再推出W。
如果枚举每个点i,设book[j]=1((i,j)∈E),再枚举每个点j((i,j)∈E),枚举每个点w((j,w)∈E),如果book[w]==1,则B自加1。由于这样求出的每个三角形被枚举了6次(A(3,3)=3!),所以

W=N(N-1)(N-2)/6 - (Σ(black[i]*white[i]))/2 - (Σi,j,k∈V且(i,j),(i,k),(j,k)∈E1)

这样均摊复杂度为O(M).
至此,B,W已经求出。

3.Aqnum
大意:求1到upto中有几个数满足:每个质因数小于等于maxprime且每种质因数个数为奇数。
30分:暴力搜索,用f(x,k)当前的数为x,在处理第k个质数,则:继续搜索f(x,k+1), f(xp[k],k+1), f(xp[k]*p[k]2a,k+1). 复杂度约为∏(upto/p[k])

60分:如果当前的xp[k]<=upto且xp[k]2>upto,则找到最后一个满足上述条件的k2, ans+=k2-k+2;大约可以剪枝2k以上的状态数。