终于 AK 了一次挑战赛，不容易啊...
T1
个人难度：红 中位
如果按照题意直接模拟的话，那么就会每个数都会有 101101101 种情况，需要运算 1015≈1.05×1010101^5\approx1.05\times 10^{10}1015≈1.05×1010 次，肯定会 TLE。
注意到 i,j,k,z,pi,j,k,z,pi,j,k,z,p 都是非负整数，
所以 8×i≤x,6×j≤x,4×k≤10,2×z≤10,p≤108\times i\le x,6\times j\le x,4\times k\le 10,2\times z\le 10,p\le 108×i≤x,6×j≤x,4×k≤10,2×z≤10,p≤10，
即 i≤1,j≤1,k≤2,l≤5,p≤10i\le 1,j\le 1,k\le 2,l\le 5,p\le 10i≤1,j≤1,k≤2,l≤5,p≤10。
按照上面这个范围去循环判断即可，运算次数为 2×2×3×6×11=7922\times 2\times 3\times 6\times 11=7922×2×3×6×11=792，可以通过。
时间复杂度：O(1)O(1)O(1)。
T2
个人难度：橙 下位
模拟，筛出 nnn 以内的所有质数，一个一个累加即可。（如果不会埃式筛等筛法，使用 O(nn)O(n\sqrt n)O(nn ) 的暴力找质数也是能通过的。
时间复杂度： O(nloglogn)O(n\log\log n)O(nloglogn)（感觉埃式筛的复杂度更高，后面计算的就舍去了）
T3
个人难度：橙 中位
显然题目是想让我们找出 A,BA,BA,B 的所有公因数。
显然 A,BA,BA,B 的所有公因数就是 A,BA,BA,B 最大公因数的所有因子。所以我们就可以通过这个方法轻松找出了。
时间复杂度：O(N)O(\sqrt N)O(N )。
T4
个人难度：黄 上位
O(n3)O(n^3)O(n3) 的解法是个人都会，所以我来教大家一个 O(n2logn)O(n^2\log n)O(n2logn) 的解法。
思考一下如果一个三角形是直角三角形，那它得满足什么？
1. 有直角。
2. 符合勾股定理（即存在两边的平方和等于第三边）。
性质 2 想不出来怎么优化，所以我考虑性质 1。
注意到在平面直角坐标系内，如果一个角是直角，它的两边的解析式分别为 y=k1x+b1,y=k2x+b2(k1,k2≠0)y=k_1x+b_1,y=k_2x+b_2(k_1,k_2\not= 0)y=k1 x+b1 ,y=k2 x+b2 (k1 ,k2 =0)，则有 k1×k2=−1k_1\times k_2=-1k1 ×k2 =−1。如果两边解析式分别为 y=b1y=b_1y=b1 和 x=b2x=b_2x=b2 ，也可以构成直角。
我们可以先预处理出每个边的解析式的 kkk 值，然后枚举每个顶点， 计算它们作为直角顶点的个数，这个个数就是这个图内直角三角形的个数。
时间复杂度：O(n2logn)O(n^2\log n)O(n2logn)。
T5
个人难度：黄 中位
比 T4 简单。
简单的并查集板子题，参考 01迷宫_信奥算法普及/提高--ACGO题库。不做详细解释。
时间复杂度：O(N×Mlog(N×M))O(N\times M\log (N\times M))O(N×Mlog(N×M))。
T6
个人难度：黄 上位
首先来一个正常的 DP：
dp[i][j]dp[i][j]dp[i][j] 记录在第 iii 格，当 l=jl=jl=j 时收集宝石的最大值。
显然递推式如下：
dp[i][j]=max(dp[i−j][j−1],dp[i−j][j],dp[i−j][j+1])+bidp[i][j]=max(dp[i-j][j-1],dp[i-j][j],dp[i-j][j+1])+b_i dp[i][j]=max(dp[i−j][j−1],dp[i−j][j],dp[i−j][j+1])+bi
其中 bib_ibi 为第 iii 格的宝石数，并且要保证 i−j≥mi-j\ge mi−j≥m。
时间复杂度：O(ai×(ai−d))O(a_i\times (a_i-d))O(ai ×(ai −d))。
得分：70pts70pts70pts。
这对于 ai≤3×104a_i\le 3\times 10^4ai ≤3×104 的数据还是太吃操作了，怎么优化呢？
注意到在 3×1043\times 10^43×104 格内，跳跃过程中 lll 的取值范围很小，一定在 d±300d\pm 300d±300 的范围内，也就是说上面的 dpdpdp 存在大量无效状态。
根据上面的推理，我们可以把 dpdpdp 的第二维的大小减少到 601601601，dp[i][j]dp[i][j]dp[i][j] 表示第 iii 格，当 l=j+d−301l=j+d-301l=j+d−301 时收集宝石的最大值。将上面的状态转移方程稍加改变即可。
时间复杂度：O((ai−d)×ai)O((a_i-d)\times \sqrt{a_i})O((ai −d)×ai )。
得分：100pts100pts100pts。
