Codeforces Beta Round 1 B Spreadsheets

题目

源地址:

http://codeforces.com/contest/1/problem/B

理解

大水题一道,不过我坑了很久,实在是代码功底太弱。 题意非常简单,给出两种表格的坐标体系,要你进行相互转化,本质上是一道26进制转化类的题目。 我遇到的坑基本上分为两类,一个是在判断当前输入的字符串属于何种类型,第二是在具体实现过程中的BUG。 首先,讲一讲判断的过程。我另外写了一个判断的函数,一开始想的比较简单,只要判断第二个是不是字符,就OK。挂在了Test 2,错误样例是A1。然后就在思考,这两种坐标体系的根本不同到底在哪里。实际上,RXCY体系中一定有字符R和C,R和C之间必定会有一个数字。从这一点出发,重写了一遍judge函数,总算是搞定了问题。 其次,来看一下在具体的实现过程中的BUG。这一次挂在了Test 6,一个总共有1000个的输入= =,错误的样例是R228C494R98C688。观察之后发现,问题出在进退位上,因为在A—Z的体系中,实际上是没有代表’0’这个字符的,所以,当R或者C坐标上出现整除的时候,就会发现本应出现’Z’的地方,出现了字符’@‘。不过在挂了这么多发之后,偷懒直接进行了特判,当’Z’出现字符串末尾,也就是c%26==0时,直接指定它为’Z’;当Z出现在字符串最前方时,直接在输出中过滤。 然后= =,A了。

Read More

CodeVS 1474 十进制转m进制

题目

源地址:

http://codevs.cn/problem/1474/

理解

一开始就看到了下面的提示——可以使用反向取余法,然后就去百度了一下,结果没有发现什么有用的东西- -,然后坑爹的麦当劳的网络又一直连不上GoAgent,直接导致谷歌也上不去,然后就只能靠自己YY反向取余法到底是个什么玩意儿了。 题目自然是十分简单,给的数也不大,n<=100,暴力一点也是OK的。然后就联想到了计算机导论课上老师讲的进制转换的知识点。只要不停地使用n去除以m,余数作为当前位置上的数,商作为下一次运算的n参与循环。直到n<m的时候停止。 不过有一个地方需要注意的是,通过这种方法求出来的char数组和答案正好是逆序的,需要将它转换过来。我记得学长有个奇特的技巧可以将字符串逆序输出= =,不过现在条件受限,自己写一个for循环吧。

Read More

POJ 1050 To the Max

题目

源地址:

http://poj.org/problem?id=1050

理解

题意不难理解,在一个矩阵中寻找一个和最大的子矩阵,可以看作是一个二维的DP问题。不过受到时间的限制,太过暴力的程序显然是不行的,所以现在的问题在于,如何把一个二维的问题转化为一个一维的问题。小脑一动,我们可以想到可以将把矩阵的高度压缩为1之后,在进行一次简单的求最大子序列和就可以实现了。

Read More

POJ 3624 Charm Bracelet

题目

源地址:

http://poj.org/problem?id=3624

理解

这道题拖了很久很久,一直没有搞定,对DP以及背包问题的理解,一直处在一个瓶颈之中,特别烦躁。 知道今天在比赛群里面问了学长,才发现是空间优化的问题,二维的记忆化数组会直接超出容量限制。想通了这一点后,优化就变得简单了。只要另外定义一个新的数组f[MAXN],从M->w[i]进行循环,最后的f[m]就是所要求的结果。

Read More