2016省队集训试题讨论.pdfVIP

LYK loves jum • 题目大意：有n个点，如果将它们按照高度 排序，每一个点能跳到一段前缀的点，每 次跳都是随机的，如果无法跳到任意点上 则跳到地方，求每个点期望跳几次跳到地 上。 得分情况 • 100分：std等10人 • 90分：zhangYUNsheng • 80分：suxiaobin等4分 • 30~70：sunwenhou等6人 • 0~10 ：若干 试题讨论 算法1 • 若ti不等于0 ，设它能跳到x个位置，这些位 置为起点期望步数和为sum ，则点i为起点的 期望步数为1+sum/x。 • 若ti=0 ，设它能跳到x个h不等于hi的位置， 这些位置为起点的期望步数和为sum ，它能 跳到y个h等于hi的位置，则点i为起点的期 望步数为(x+y)/x+sum/x。 • 注意无穷步即可。 • 时间复杂度nlgn。 LYK loves girls • 题目大意：n个人坐在圆桌上，其中至少有 一个人是男生，求存在多少种方案使得至 多连续k个 ，循环同构算 案，答 案对大质数取模。 得分情况 • 100分： sunwenhou,zhangyizhao,xiexingyu,zhangchen, std • 0~20 ：若干 试题讨论 算法1 • 枚举每个是男还是女，用最小表示法 记录这个信息，hash判断是否循环同构。 • 时间复杂度为2^n*n 。 • 期望得分20分。 bunside引理 • 假设存在G种置换，令c{ai}为第i种置换中的 不动点个数，那么方案数为 (c{a1}+c{a2}+…+c{aG})/G。 • 应用到本题中。 • c{ai}可以表示成不动点的方案数。 算法2 • 观察到k至多等于10。 • 我们枚举前10个人是男是女。 • 问题转换成线性。 • 时间复杂度为2^10*10*n^2。 • 期望得分20分。 算法3 • 听说读入只有两个数。 • 打表！ • 期望得分20分。 算法4 • 考虑环形的情况下怎么做。 • 令dp[i]表示有i个人，且最后一个人是男的方案总数。 • 那么一个递推式是。 • dp[i]=dp[i-1]+dp[i-2]+...+dp[i-k-1]。 • 这个dp是可以通过前缀和加速的。 • 令x表示变成线性后每一堆共有x个人，假设一开始 有连续y个女的，且第y+1个人是男的，那么前y个人 是可以任意旋转的 （共y+1种可能），对答案的贡献 为(y+1)*dp[x-y-1]。 • 时间复杂度为n^2。 • 期望得60分，结合算法3得到80分。 算法5 • 实际上大多数置换中不动点都是相同的。 • 具体地，对于第i种置换，有用的数仅仅是 (i,n)种，也就是说我们只需处理n的所有 约数就可以了。 • 时间复杂度为tot*n 。（其中tot表示n的约数 个数） • 期望得分100分。