该解题报告由fatest提供：

PROBLEM A:

描述：给一串数组An，求存在Ak=Ai+Aj(i!=j)的k有多少个。

一开始我以为是求满足Ak=Ai+Aj(i!=j)的（i，j，k）有多少组，各种WA，

算法：首先对数组进行一次排序，然后处理一下，如果存在相同的数字，那么就把它们合并，并记录这个数字出现多少次。然后枚举每个数字，如果一个数字的出现次数大于1，那么就可以直接加到累加和sum上（取Ak=Ai=Aj，由于存在相同的，i!=j可以满足，故每个k均满足）；否则，用俩个指针，一个向左，一个向右枚举是否存在ij一遍就好了（这边由于排过序了，只要N次枚举即可）。

时间复杂度：O（N^2）。

 

PROBLEM B：

描述：21点，一张值为10加一个A（blackjack）最大，其他按值比较大小，超过21算0，A可以算1或11；一样大为庄家胜。

算法：模拟。注意blackjack和超过21点时的处理即可。

 

PROBLEM C：

描述：定义一个数组，Ai为A（i-1）的每个位的平方和，发现数组按一定长度循环。现给你一个数字（n<10^7）,求这个数字开头的数组长度。

算法：一个visit[1000]来记录i出现在什么时候（1表示第一个出现）。1000就够了，取n的下一个数字开头，最大是7*（9^2）=567；每次根据i的值求下一个值并存到i当中，如果i出现过了，那么就可以输出答案了，否则，步数+1，存到visit[i]中。

 

PROBLEM D：

描述：多米诺骨牌，每个骨牌有高度和位置，推倒一个可能把旁边的碰到从而把旁边的也推倒，现问你从中任意一个骨牌任意方向推，最多能推倒几个。

算法：首先，根据位置排序，然后从左往右扫一遍，再从右往左扫一遍，将最大值输出即可。

     扫的时候，如果第i个骨牌不能被前面的碰倒，那么就把前面的累加值和最大值比较，否则累加值加1，再继续往后面扫即可。

 

PROBLEM E：

描述：从文章中提取Email地址。

算法：模拟,写了伪代码，不想敲了。

      读取字符串;

      While(查找@存在)

       {

            If（@前面合法？&&@后面合法？）{输出，删除该字符串；}

               Else {从头删除字符到@为止}

}

判合法时注意‘。’的判断。

 

PROBLEM F：

描述：我没看懂题目，也不知道可以往右下走，以为是往右或往下走(看了别人的报告才知道的)，不过因为做过不少次了，猜出来了，一个数字矩阵，问你从左上角走到右下角，途中经过的格子的最大值是多少？

算法：一个可以入门级的DP吧，枚举i，j，a[i][j]=a[i][j]+max(a[i-1][j],a[i][j-1]);输出a[n][m]即可。

 

PROBLEM G：

描述：给你n和m，求从n到m的平方和。

算法：暴力模拟。

 

PROBLEM H：

描述：题目是中文就不说了。

算法：计算几何。

1：求圆心（三角形的三边中垂线交点，不用说了吧），根据圆心和三角形的任意一个点可以得到半径。

      2：判断点在圆内，求下距离就好了。不在就可以输出了 dream了。

      3：如果在，那么判断点在三角形内，点在多边形内有模板的。不在就可以输出cry了

      4：如果还在，求面积做比较，圆心连接三个点把圆分成三块，根据角度和面积公式可以求出来。

 

PROBLEM I：

描述：有n个点，告诉你哪些点之间存在边，求每个连通分支。

算法：并查集吧，由于数据小，n只有250，我直接暴力了，如果A连B，那么把所有B相连的点连到A上，输出也是，枚举到一个没输出的，那么再枚举一个，把所有连通的输出。时间是N^2（好孩子不要学我）。

 

PROBLEM J：

描述：判断一个数组是不是严格递增或严格递减数组。

算法：扫俩次，一次判增，一次判减即可。

 

PROBLEM K：

描述：机器人走路，问你从‘G’到‘S’最少要几步，其中‘G’和‘。’可以任意方向走，‘L’只能向左，‘R’只能向右。

算法：宽搜。

附：我从G到S宽了一次，从S到G又宽了一次，结果都错了，但是自己的各种样例各种没问题，于是。。。。。。。。求数据。

 

PROBLEM L

描述：给你一个矩阵，求它的任意一个子矩阵中的所有元素的和。

算法：有点DP的思想，求出每个数据左上方元素的和，输出答案时处理一下就好了。转换成一维的话就是每次求左边的，输出就是a[j]-a[i]的样子了。已经有一个比较详细的报告了，就不多写了。

|返回 |   | 转到页头|