Topcoder Open 2011 Qualification Round 3报告

第一篇竞赛报告……TCO的前两场QR的情况不容乐观，所以把我逼得起早做TCO QR3。最终rank498，rate有微微上涨（不调到DIV2我就很高兴了~）。总体情况问题在于熟练程度，最大的问题就是手速。前两题不难，之所以rank很低原因就在于调试浪费了大量时间。准确的说浪费最多时间的是从写完程序到编译通过这个阶段，看来我的记事本程序设计功力不够啊~

TC这种比赛的程序最猥琐的地方在于，他并不是让你写一个单纯的程序。而是需要将它封装在class中，这给编译和调试带来了很大的不便。从这个侧面我的这个静态差错能力还是不行，更严重的问题可能在于过分依赖IDE和gdb，在没办法进行这样常规意义上的调试的时候显得不知所措。看来近期需要在刷题的时候多多注意了，静态差错和活用输出进行debug才是王道~

这份报告只会写前250pt和500pt，主要是因为1000pt还没有太想好，搞定后我会找时间把那个题补上。

250pt：一道很水的题，需要注意的地方主要在于-1的问题。因为他希望刚好能被n - 1个数整除，除了需要枚举一个点排除掉做LCM之外最后还要检测下能不能被被搞掉的那个数整除。总体上讲没什么好说的。这个题浪费了很多时间，直接导致了这次考试的一堆问题。（P.s.下回他给你的对象名啊函数名啊就直接复制粘贴吧，要不然敲错了会有诡异错误……）

#include <vector>
#include <iostream>
using namespace std;

int gcd(int x, int y)
{
        if (0 == y) return x;
        return gcd(y, x % y);
}

class AllButOneDivisor
{
        public:
                int getMinimum(std::vector <int> divisors)
                {
                        int best = 100000000;
                        for (int i = 0; i < divisors.size(); i++)
                        {
                                int lcms;
                                if (i == 0)
                                {
                                        lcms = divisors[1];
                                        for (int j = 2; j < divisors.size(); j++)
                                                lcms = (divisors[j] * lcms / gcd(lcms, divisors[j]));
                                }
                                else
                                {
                                        lcms = divisors[0];
                                        for (int j = 1; j < divisors.size(); j++)
                                        if (i != j)
                                                lcms = (divisors[j] * lcms / gcd(lcms, divisors[j]));
                                }
                                if (best > lcms && lcms % divisors[i] != 0) best = lcms;
                        }
                        if (best == 100000000) return -1;
                        return best;
                }
};

500pt：这个题看起来挺唬人的，也是一个比较简单的问题。因为我们希望游戏尽量长，所以操作的方法就是按照实际消耗的money的多少排序，然后去贪心。这个方法一定正确因为每次损失的越少的话，才能给之后的损失多的打下基础，并且保证了need的供应。这个题本来想排序搞的，后来觉得悲剧，就直接写了个线性扫描求最小值。虽然效率会有一点损失，但是对于TC这种题目，超时应该是最不容易出现的问题。所以在代码上能精简就精简，怎么好写就怎么写，这样才能在保证最后不被人CHA和通过system test的情况下将分数所得分数最大化。

#include <vector>
#include <iostream>
using namespace std;

class CoinMachinesGame
{
        public:
                int maxGames(int coins, vector <int> need, vector <int> give)
                {
                        int ans = 0;
                        while (coins > 0)
                        {
                                int bestcost = 10000, next = 0;
                                for (int i = 0; i < need.size(); i++)
                                        if (coins >= need[i] && bestcost > need[i] - give[i])
                                        {
                                                bestcost = need[i] - give[i];
                                                next = i;
                                        }
                                if (bestcost == 10000) break;
                                ans += (coins - need[next]) / bestcost + 1;
                                coins = coins - (((coins - need[next]) / bestcost + 1) * bestcost);
                        }
                        return ans;
                }
};