2017-C08-team8

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== 题解 ==
=== A ===
题意：有n个人在轮流玩一台赌博机。赌博机胜负由一个周期为m的序列决定。给定n个人的初始金钱，问最早输完的人在第几次游戏出现，不存在输出-1。
每个人面对的序列是(i+kn)%m，周期为n/gcd(n,m)。每隔gcd(n,m)个人，会出现旋转等价的子序列。不同的子序列互不相交，可以对每种子序列倍增后求出每个长为n/gcd(n,m)的段的最小前缀和（段中最小值减段首）。一般实现为O(mlogm)即可。之后枚举人，根据最小前缀和以及子序列和计算其耗尽金钱的时间。O(mlogm+n)。
=== B ===
题意：给定一个无向图。称一个染色为beautiful，当且仅当所有染色值都属于[1,k]内整数。称一个染色为smart，当且仅当所有染色值出现至少两次。给定一个beautiful but not smart（A）和一个smart but not beautiful（B）的染色，求一个beautiful and smart的染色。
选择A中颜色唯一的点，选取B中与其同色的点，染为同色。队列维护即可。O(nlogn)，取决于同色判定。
=== D ===
题意：求一个最大的连通生成子图，每个点度数至少为d。
从度数最小的点删起，用队列维护。O(n+m)。
=== E ===
题意：给定两个字符串AB，长度分别为n和m，求A中首尾位置差>=k的等于B的子序列数量。m<=10。
计算出总次数之后，减去非法的部分。总次数很容易计算。非法部分为了去重，需要枚举A中每个B[0]的出现位置l，计算其对应的非法次数，即dp[l..l+k-1](0,m-1)-dp[l+1..l+k-1](0,m-1)。将一个区间的解抽象为一组dp(i,j)，表示该区间内B的子串B[i..j]的出现次数。这样就获得了O(m^3^)在区间左右两侧分别+1的能力。
注意到所要计算的两个序列，其pair分别是单调非减的，对于这种问题，有在前后缀扩展能力下O(n)的计算方法。假设当前有p<=l_i<q，并且对所有p<=j<q，维护了\prod{f(j..q)}。那么显然只要维护q+1..r_i的乘积即可快速计算f(l_i..r_i)。当l_i>=q时，取p=l_i，q=r_i，重新计算以q结尾的后缀和即可。这样每个i对应一个前缀和和一个后缀和，复杂度为O(n)。
O(nm^3^)。
==== Reconquista ====
solve(l,r)处理所有跨过mid的非法解数量。O(m^2^nlogn)。
=== G ===
题意：设f(n)为n各位数字的平方和，求[a,b]中满足k*f(n)=n的n的数量。
枚举f(n)。O(81log^2^n)。
=== H ===
题意：给定n种草的生长速度，初始高度为0。第d_i天会割掉所有草高于b_i的部分，共m次。问每次割下的草的总长度。
注意到可以快速算出前k天被割掉的总量，即计算有多少种草长到限制，计算它们的贡献，通过预处理可以做到O(logn)。然后对相邻项作差即可。O(mlogn)。
=== J ===
题意：给定平面上n个点，求所有面积在[A,B]范围内的直角三角形个数。
枚举直角顶点，对其他点调整坐标（旋转、取gcd）后丢进map，用lower_bound统计成对极角即可。O(n^2^logn)。

题解

A

题意：有n个人在轮流玩一台赌博机。赌博机胜负由一个周期为m的序列决定。给定n个人的初始金钱，问最早输完的人在第几次游戏出现，不存在输出-1。

每个人面对的序列是(i+kn)%m，周期为n/gcd(n,m)。每隔gcd(n,m)个人，会出现旋转等价的子序列。不同的子序列互不相交，可以对每种子序列倍增后求出每个长为n/gcd(n,m)的段的最小前缀和（段中最小值减段首）。一般实现为O(mlogm)即可。之后枚举人，根据最小前缀和以及子序列和计算其耗尽金钱的时间。O(mlogm+n)。

B

题意：给定一个无向图。称一个染色为beautiful，当且仅当所有染色值都属于[1,k]内整数。称一个染色为smart，当且仅当所有染色值出现至少两次。给定一个beautiful but not smart（A）和一个smart but not beautiful（B）的染色，求一个beautiful and smart的染色。

选择A中颜色唯一的点，选取B中与其同色的点，染为同色。队列维护即可。O(nlogn)，取决于同色判定。

D

题意：求一个最大的连通生成子图，每个点度数至少为d。

从度数最小的点删起，用队列维护。O(n+m)。

E

题意：给定两个字符串AB，长度分别为n和m，求A中首尾位置差>=k的等于B的子序列数量。m<=10。

计算出总次数之后，减去非法的部分。总次数很容易计算。非法部分为了去重，需要枚举A中每个B[0]的出现位置l，计算其对应的非法次数，即dp[l..l+k-1](0,m-1)-dp[l+1..l+k-1](0,m-1)。将一个区间的解抽象为一组dp(i,j)，表示该区间内B的子串B[i..j]的出现次数。这样就获得了O(m³)在区间左右两侧分别+1的能力。

注意到所要计算的两个序列，其pair分别是单调非减的，对于这种问题，有在前后缀扩展能力下O(n)的计算方法。假设当前有p<=l_i=q时，取p=l_i，q=r_i，重新计算以q结尾的后缀和即可。这样每个i对应一个前缀和和一个后缀和，复杂度为O(n)。

O(nm³)。

Reconquista

solve(l,r)处理所有跨过mid的非法解数量。O(m²nlogn)。

G

题意：设f(n)为n各位数字的平方和，求[a,b]中满足k*f(n)=n的n的数量。

枚举f(n)。O(81log²n)。

H

题意：给定n种草的生长速度，初始高度为0。第d_i天会割掉所有草高于b_i的部分，共m次。问每次割下的草的总长度。

注意到可以快速算出前k天被割掉的总量，即计算有多少种草长到限制，计算它们的贡献，通过预处理可以做到O(logn)。然后对相邻项作差即可。O(mlogn)。

J

题意：给定平面上n个点，求所有面积在[A,B]范围内的直角三角形个数。

枚举直角顶点，对其他点调整坐标（旋转、取gcd）后丢进map，用lower_bound统计成对极角即可。O(n²logn)。