早上8:00整,我们又又来到了这与我们“亲爱”的Quanzhou No.1 High School有长达20个英文字符的最长公共子序列的Changzhou No.1 High School。
上午
370/400(第三)
考试分析(见下)
下午
讲了算法分析
考试
第一题:错误探测 (mistake)
思路 (注:这是一道送分题)
因为题目要求只能更改一个地方的数字,所以只需将每行和每列中有奇数个1的个数分别计算出来,再判断一下就好了。
代码
第二题:距离 (dis)
思路 (注:这题我们3个做过了的)
正常思路(一般人)
一般人一看到这题都会想到递推算法,这是最简单的,也是分最低的。
递推算法:
从a开始乘2或加1,直到a=b。
可得30分
代码
逆向思路(非一般人)
从b开始,如果b是偶数,则b一定是从b/2乘2得来的,如果b是奇数,则b一定是从b-1加1得来的。按以上规律一直除2和减1。直到b=a。
可得100分
代码
第三题:求和 (sum)
思路
将数组a排序,再预处理每个负数的左边和右边的第一个正数的下标。最后再求最小的| a[i] – a[j] |就好了。
代码
第四题:流感传染 (flu)
时间不够了,就不打了,不过也打过了。