AC. 梦想

frank_c1

2016多校联合训练1

发布于2016年07月19日 | 暂无评论 | 1,070阅读 | 比赛经历

本来只有高一打。今天伟大领袖zzx问我们有没有多校账号。然后规模就从半个年级扩大到四个年级。最后在大家的合力下终于AK了。虽然有点悲伤的是自己一道题也没有贡献,不过看着榜还是很爽的~ 高二高三的大爷们都太神啦,跪跪跪……

好那么我们来填坑吧~~~~

[ 施工中... , 不当之处敬请在评论中指出 ]

1001. Abandoned country

给定n个点m条边的带权无向图,边权互不相同。求最小生成树。求最小生成树上随机选取两点构成的路径长度的期望,保留两位小数。

1 \le T \le 10, 1 \le n \le 10 ^ 5, 1 \le m \le 10 ^ 6, 1 \le w_i \le 10 ^ 6

最小生成树O(m\alpha(n))求一下就好了,由于边权不同,最小生成树是确定的。随机选取两点的路径长度的期望其实就是求树上任意两点构成的路径长度总和。考虑一条边的贡献,即被选到的次数,就是边两端的点数的乘积。DFS一遍即可。

时间复杂度O(T(m \alpha(n) + n))

1002. Chess

n20列的棋盘上有若干棋子。Alice和Bob在玩一个游戏,每次可以将一枚棋子向右移到距离它最近的空格里。不能移到界外。如果谁不能移动判负。已知两人都采取最优策略,问先手是否有必胜策略。

1 \le T \le 100,1 \le n \le 1000

简单博弈。注意到行与行之间是不影响的,故可以按行拆分成若干子游戏。对于每一行,注意到列数不大,我们可以直接预处理所有2 ^ {20}个状态的SG函数值。

时间复杂度O(m 2 ^ m + Tn)

1003. Game

1004. GCD

给定长度为n的数列a,有q个询问。每次询问l,r,求\gcd(a_l,a_{l+1},...,a_r)和有多少对l',r'满足1 \le l' \le r' \le n\gcd(a_{l'},a_{l'+1},...,a_{r'}) = \gcd(a_l,a_{l+1},...,a_r)

1 \le n,q \le 10 ^ 5, 1 \le a_i \le 10 ^ 9

第一问比较容易。我们可以先预处理一下后O(\log n)回答询问。

考虑第二问,当确定的左端点l后,随着右端点r的增加,\gcd是单调不增的。我们发现这样\gcd实际上是质因子集合求交的过程。考虑到一个整数n的质因子个数是O(\log n)的,所以当确定区间的一个端点后,只有O(\log n)种不同的\gcd值。我们可以枚举左端点l,统计所有可能的\gcd值出现次数,存在map里。询问时O(\log n)回答即可。

时间复杂度O(T(n \log ^ 3 n + q \log n)),上界较松。(为分析方便,我们默认\max(a_i)n同阶)

1005. Necklace

n个宝石,每种宝石都有对应的阴属性石和阳属性石,共2n个。给定m个条件,即当阳属性石x和阴属性石y相邻时,x会变暗。现要求确定一个宝石的环排列,满足阴阳相间,且变暗的宝石数目最少。输出最少的变暗宝石数目。

0 \le n \le 9, 0 \le m \le n ^ 2

听说标算是爆搜+剪枝……

同校的爷爷们提出了一个做法。枚举阴属性宝石的全排列,于是产生了n个位置来摆放阳属性宝石。如果对于位置i,阳属性宝石j不会因两边的阴属性宝石变暗,就在X_iY_j间连一条边。于是问题转化成二分图匹配。n减去最大匹配数就是这种排列下的最优解。

由于本题是环排列,所以只需枚举[2,n]的排列即可。

时间复杂度O((n-1)!n ^ 3),上界较松。

1006. PowMod

给定n,m,p,定义k = \sum_{i=1} ^ {m} {\phi(i \cdot n)} \mod {10 ^ 9 + 7}

k ^ {k ^ {k ^ {...}}} \mod {p}k有无穷个。

1 \le T \le 100, 1 \le n,m,p \le 10 ^ 7

为什么要强行将两个问题拼起来……

[ this part is incomplete... ]

时间复杂度O(n + T \log ^ 2 n)

1007. Rigid Frameworks

我们定义一个网格图是稳定的,当且仅当我们无法自由地旋转其中的一些边。

给定n \times m的网格,每个格子中至多可以加入一根斜线,方向任意。求有多少种方案使得网格图稳定。答案对10 ^ 9 + 7取模。

1 \le n,m \le 10

[ this part is incomplete... ]

f(n,m)为不连通的n - m二分图数目,g(n,m)为连通的n - m二分图数目,h(n,m)为所有n - m二分图数目。由于在本题中,两点间有两种边,故h(n,m) = 3 ^ {nm},又g(n,m) = h(n,m) - f(n,m),因此我们只需要考虑f(n,m)

枚举X部点1所在的连通分量,大小为i - j,其他边就可以随便加,故有

f(n,m) = \sum_{i=1} ^ {n} \sum_{j=0} ^ {m} {g(i,j)h(n-i,m-j){{n-1} \choose {i-1}}{m \choose j}}

时间复杂度O(n ^ 2 m ^ 2)

1008. Shell Necklace

定义长度为i的区间权值为a_i。定义一个区间的划分方案的权值为所有区间权值之积。求对于所有可能的划分方案的权值之和,答案对313取模。

1 \le T \le 20, 1 \le n \le 10 ^ 5, 1 \le a_i \le 10 ^ 7

f(i)为区间[1,i]的所有可能的划分方案的权值之和,有

f(i) = \sum_{j=1}^ {i} {f(i-j) a_j}

暴力是O(n ^ 2)的。注意到这是卷积的形式,可以用和CDQ分治和FFT优化。

时间复杂度O(n \log ^ 2 n)

1009. Solid Dominoes Tilings

nm列的棋盘有多少1 \times 2骨牌的完美覆盖,满足所有可能的直线都会穿过某些骨牌。答案对10 ^ 9 + 7取模。

1 \le n,m \le 16

1010. Subway

有两棵同构的n个点的无根树,点以长度不超过10的小写字母字符串作为编号。求一个点的映射,使得两棵树的结构相同。

1 \le n \le 10 ^ 5

1011. tetrahedron

给定四个三维空间中四个整点A,B,C,D。若它们能构成四面体,输出其内切球球心及半径,保留四位小数。否则输出"O O O O"。

1 \le T \le 100, -10 ^ 6 \le x,y,z \le 10 ^ 6

纯数学题感觉也并没有什么意义啊。

\mathbf{p}是内切球球心坐标,S_A, S_B, S_C, S_D分别是四个顶点对面的面积,有

\mathbf{p} = \frac{\mathbf{a} S_A + \mathbf{b} S_B + \mathbf{c} S_C + \mathbf{d} S_D} {S_A + S_B + S_C + S_D}

内切球半径类比内切圆半径的求法,设V是四面体的体积,可得

r = \frac{3V} {S_A + S_B + S_C + S_D}

四面体体积V可以求向量\mathbf{a} - \mathbf{d}, \mathbf{b} - \mathbf{d}, \mathbf{c} - \mathbf{d}的三重积,有

V = \frac{1} {6} (\mathbf{a} - \mathbf{d}) \cdot ((\mathbf{b} - \mathbf{d}) \times (\mathbf{c} - \mathbf{d}))

注意无解情况的判断。

时间复杂度O(T)