Blog·Tanky WooABOUTRSS

SRM 522 DIV2总结报告

26 Oct 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

250的题目:

就是两层for循环考虑一对点,组成一个retangle,然后再一个for检查这两个点之间(横坐标),有多少个点的纵坐标在这两个点之间。

550的题目:

比如AXXX或者XXXA,则输出"Alice",否则输出"Bob"。

900的题目:

这题其实也很简单,题目没注意,他说了a,b,c都是1~1000 000(注意c也是的)

因为a+b+c<=3000 000,所以可以考虑C的最大值小于3000 000

又因为A*B=C,可以想到线性筛选法,另A=1~1000 000,然后C从A开始,每次加A,然后判断abs的值。

当然,这题也可以暴力,不过要采取适当的剪枝。

代码:

#include 
#include 
#include 
#include 
#include 
using namespace std;

class CorrectMultiplicationTwo
{
public:
    /*
    int getMinimum(int a, int b, int c)
    {
        long long int tmp = a+b+c;

        for(int i=1; i<=1000000; ++i)
            for(int j=1; j<=1000000; ++j)
            {
                if(abs(i-a) + abs(j-b) + abs(i*j-c) < tmp)
                    tmp = abs(i-a) + abs(j-b) + abs(i*j-c);
                if(i*j > c)
                    break;
            }
        return tmp;
    }
    */

    int getMinimum(int a, int b, int c)
    {
        int x = a, y = b, z = c;
        if(x > y)
            swap(x, y);
        int minn = 3000000;
        int tmp;
        for(int i=1; i<=1000000; ++i)
        {
            for(int j=i; j<=3000000; j+=i)
            {
                tmp = abs(i-x) + abs(j/i-y) + abs(j-z);
                minn = min(minn, tmp);
            }
        }
        return minn;
    }
};