SRM 522 DIV2总结报告

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的值。

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

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
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;
    }
};

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《SRM 522 DIV2总结报告》有1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注