Tuesday, May 29, 2007

07年5月29日 在复旦大学的topcoder比赛

先是匹萨,棒约翰的,还不错,我和肖各吃了两块,就饱了,其实是不太好意思吃多 ^_^

然后是比赛,感觉脑子的转速要比在家里做快得多,时间也貌似比一般的一个半小时长得多(因为单位时间的思考能力强了,所以感觉时间就多了)。算是三校联赛吧,被复旦踩是必然的,目标是踩东华。最后338.31,是room2的第7,divsion的第13,还是被两个东华的踩了。

很久没写tc报告了,因为很久不关心算法。但今天还是满有意思的,写一下,纪念一下:

总得来说DIV2的题目就是比较简单的呀。

problem 250:
一个Set包括0-9个数字,其中6和9可以互用,隐含的意思就是可以表示 66 或 99 或 69。
然后给个门牌号,问至少买多少Set能够摆出这个门牌号。

算法很简单,统计一下门牌号中出现过的数字个数。因为6和9可以互用,所以把6的个数和9的个数平均一下,有两个写法:


// method one, after counting
count[6]=count[9]=(count[6]+count[9]+1)/2; // forget add one will be chanllenged

// method two, in counting iteration
if(count[6]<count[9]) count[6]++;
else count[9]++;


看到两个人用第一种写法忘记+1,cha之~,HOHO,赚100分。

problem 500:
有金G银S铜B三种钱币,去银行转换的规则如下:
11 S -> 1 G
11 B -> 1 S
1 G -> 9 S
1 S -> 9 B
问从G1 S1 B1换到 G2 S2 B2的最少交换次数,或-1表示不可能

与其说是贪心,不如说是逻辑题,只要依存简单的逻辑,就能既保证代码清晰,又可保证准确率:
step 1. 如果B不够,只能用S换B
step 2. 如果G不够,只能用S换G
step 3. B和G都够了,若S不够,先用G换S,再用B换S。因为G换S一次可以满足的S多,所以先G换S。

5555,前面的代码都是好好的,可惜最后在B换S的地方,忘记减去B,加上S了。。。好粗心啊 >.<
一开始沈发现了,但他给的cha数据没能把我cha掉~,洋洋得意地笑沈时,忽然某人把我cha了~ 瞬间郁闷

problem 1000:
比赛的时候想了n套方案,结果还是没能决定用什么方法解之。
题目意思是给出一个序列,要求用最小的cost排序,将i放到某个值后面/前面,花费的cost是i。

大大的程序千奇百怪,有STL库牛人的,有搜索解的,有DP的,不过最欣赏的是这个解法:
可以把问题转换为, 求顺序的最大cost的序列,然后用总cost减一下就行了。

例如sample 中的 6 4 5 3 8 2 7 2 11 2 2,顺序序列可以是 4 5 8 11,也可以是4 5 7 11,对于一个顺序序列,剩余的部分便是待移动的数,为了保证待移动的数的cost尽可能小,就是保证顺序序列的cost尽可能大,所以取 4 5 8 11 的cost和为28,所以只需要用最少52-28=24来完成排序。按照这个思路,有程序:


public int calcMinimalCost(int[] arr){
int total=0,len=arr.length,maxCost=0;
int[] cost=new int[len];

for(int i=0;i<len;++i){
cost[i]=arr[i];
total+=arr[i];

for(int j=0;j<i;++j){
if(arr[j]<=arr[i] && cost[j]+arr[i]>cost[i]){
cost[i]=cost[j]+arr[i];
}
}
maxCost=Math.max(cost[i],maxCost);
}

return total-maxCost;
}

No comments: