台州学院第四届大学生程序设计竞赛解题报告

台州学院第四届大学生程序设计竞赛解题报告-by fatest

PROBLEM A:

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

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

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

时间复杂度:ON^2)。

 

PROBLEM B

描述:21点,一张值为10加一个Ablackjack)最大,其他按值比较大小,超过210A可以算111;一样大为庄家胜。

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

 

PROBLEM C

描述:定义一个数组,AiAi-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吧,枚举ija[i][j]=a[i][j]+max(a[i-1][j],a[i][j-1]);输出a[n][m]即可。

 

PROBLEM G

描述:给你nm,求从nm的平方和。

算法:暴力模拟。

 

PROBLEM H

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

算法:计算几何。

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

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

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

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

 

PROBLEM I

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

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

 

PROBLEM J

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

算法:扫俩次,一次判增,一次判减即可。

 

PROBLEM K

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

算法:宽搜。

附:我从GS宽了一次,从SG又宽了一次,结果都错了,但是自己的各种样例各种没问题,于是。。。。。。。。求数据。

 

PROBLEM L

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

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


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.