------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本人只是一个xxs，而以我的能力无法ak挑战赛，以下是我的部分题目题解
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 第一题：直接循环暴力枚举即可
赛时代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 第二题：我写的是埃筛（也可以是欧筛）+暴力（注意要在过程中modmodmod 109310931093，不然可能会爆空间）
赛时代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 第三题：我写的是通过gcdgcdgcd（最大公因数）获取暴力的范围然后暴力枚举[1,gcd(a,b)][1,gcd(a,b)][1,gcd(a,b)]区间内的iii能不能满足a∣ia|ia∣i andandand b∣ib|ib∣i（不求gcdgcdgcd会爆时间）。
赛时代码
> 第四题：80tps，有两个测试点超时(其实是我懒得优化)
> 我的想法是暴力枚举每三个点，再通过勾股定理判断是不是直角三角形(即a2+b2=c2a^2+b^2=c^2a2+b2=c2就代表是直角三角形，其中a,b,ca,b,ca,b,c表示三角形的三条边长度)。
> 但是值得注意的：
> 1.必须确保你的代码的下标（索引）成此关系：i>j>ki>j>ki>j>k，其中i,j,ki,j,ki,j,k表示三层循环的下标（索引），不然会重复计算三角形，（题目要求三角形的三个顶点坐标要全部不同）。
> 2.计算三角形的边长时要使用欧几里得距离而不是曼哈顿距离，而且不要给距离开算数平方根不然会导致精度丢失，而且计算完也要求距离的平方没必要开算数平方根（如：在计算过程中，(x1−x2)2+(y1−y2)22\sqrt{(x1-x2)^2+(y1-y2)^2}^2(x1−x2)2+(y1−y2)2 2）的算数平方根和平方可以抵消（因为算数平方根就是不小于000的数平方的逆运算）。
赛时代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 第五题：我写的有点乱，但是没有问题。
> 具体思路就是构建一个大小为3N∗3M3N*3M3N∗3M的二维数组（此处记作visvisvis）用于标记坐标为i,ji,ji,j的点上是不是墙，若是为111，否则为000，然后在输入时将输入数字转换为二进制（注意要逆序排列而且要保留二进制的前导零！！！！！！！），存放到字符串类里再依次读取字符串内容并将其标记在visvisvis里（推荐使用dx,dydx,dydx,dy数组预处理i,ji,ji,j的加值），最后dfsdfsdfs找联通块（记得要给联通块大小排序，可以像我一样使用优先队列做）。
> 插一句题外话，我的代码里要将dx,dydx,dydx,dy数组的值乘333并依次做判断，悔不如当初应该用结构体写QAQ，现在自己都难看懂（
赛时代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
> 最后一题拿了15分也不知道我写的dpdpdp哪里有问题，望指正，但是应该核心没问题。
> STEP1：分析题目解题方法：
> 因为题目保证移动的步数是正数，且是求最值，所以可以用dpdpdp解（我这里是用dp[x][l]dp[x][l]dp[x][l]表示在xxx点上，上一步步长为lll时最多可以拿可以拿几个个宝石）。
> STEP2：推导适用的动态转移方程：
> 由于dp[x+k][k]dp[x+k][k]dp[x+k][k]（此处kkk指可以跳的步数，即kkk必定等于lll或者等于l±1l±1l±1）点可以拿到dp[x+k][k]dp[x+k][k]dp[x+k][k]点上的宝石（即自己本身，因为可能有多种方法到达x+kx+kx+k点）和dp[x][l]+sum[x+k]dp[x][l]+sum[x+k]dp[x][l]+sum[x+k]个的宝石（即在xxx点，上一步步长为lll的情况下向前走kkk步后能拿到的没拿过的宝石，此处sumsumsum数组表示sum[x]sum[x]sum[x]点上原有的宝石）。
> STEP3：总结出动态转移方程并开始解题：
> 动态转移方程为dp[x+k][k]=maxdp[x+k][k],dp[x][l]+sum[x+k]dp[x+k][k]=\max\limits_{dp[x+k][k],dp[x][l]+sum[x+k]}dp[x+k][k]=dp[x+k][k],dp[x][l]+sum[x+k]max
> （记得要初始化dp[d][d]dp[d][d]dp[d][d]点为sum[d]sum[d]sum[d]点上的宝石数，因为跳ddd步后会直接拿到sum[d]sum[d]sum[d]上的宝石，并且要让其他点设为−1-1−1不然会有bugbugbug）。
赛时代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
点个赞吧QAQ
