hdu2141

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

15 9月 2015

Can you find it?

Problem Description

Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.

Input

There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.

Output

For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO".

Sample Input

3 3 3

1 23

1 2 3

Sample Output

Case 1:

YES

Author

wangye

Source

HDU 2007-11 Programming Contest

题目类型：二分

算法分析：枚举所有的a和b的值，然后对于每个查询，查找x-c是否在(a+b)中

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1e9 + 7;
const int maxn =  1000 + 66;

long long a[maxn], b[maxn], c[maxn], d[maxn*maxn], len;

bool Bin (long long vv)
{
    long long l = 0, r = len - 1, m;
    while (l <= r)
    {
        m = (l + r) >> 1;
        if (d[m] == vv)
            return true;

        if (d[m] < vv)
            l = m + 1;

        else
            r = m - 1;
    }

return false;
}

int main()
{
//    ifstream cin ("aaa.txt");

    int aa, bb, cc, flag = 1;
    while (cin >> aa >> bb >> cc)
    {
        cout << "Case " << flag++ << ":" << endl;

        for (int i = 1; i <= aa; i++)
            cin >> a[i];

        for (int i = 1; i <= bb; i++)
            cin >> b[i];

        for (int i = 1; i <= cc; i++)
            cin >> c[i];

        len = 0;
        for (int i = 1; i <= aa; i++)
        {
            for (int j = 1; j <= bb; j++)
                d[len++] = a[i] + b[j];
        }

        sort (d, d + len);
        len = unique (d, d + len) - d;
        sort (d, d + len);

        int q;
        cin >> q;
        for (int i = 1; i <= q; i++)
        {
            long long vv;
            cin >> vv;
            bool is_valid = false;
            for (int j = 1; j <= cc; j++)
            {
                if (Bin (vv - c[j]))
                {
                    is_valid = true;
                    break;
                }
            }

            if (is_valid)
                cout << "YES" << endl;

            else
                cout << "NO" << endl;
        }
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1e9 + 7;

const int maxn = 1000 + 66;

long long a[maxn], b[maxn], c[maxn], d[maxn*maxn], len;

bool Bin (long long vv)

{

long long l = 0, r = len - 1, m;

while (l <= r)

{

m = (l + r) >> 1;

if (d[m] == vv)

return true;

if (d[m] < vv)

l = m + 1;

else

r = m - 1;

}

return false;

}

int main()

{

// ifstream cin ("aaa.txt");

int aa, bb, cc, flag = 1;

while (cin >> aa >> bb >> cc)

{

cout << "Case " << flag++ << ":" << endl;

for (int i = 1; i <= aa; i++)

cin >> a[i];

for (int i = 1; i <= bb; i++)

cin >> b[i];

for (int i = 1; i <= cc; i++)

cin >> c[i];

len = 0;

for (int i = 1; i <= aa; i++)

{

for (int j = 1; j <= bb; j++)

d[len++] = a[i] + b[j];

}

sort (d, d + len);

len = unique (d, d + len) - d;

sort (d, d + len);

int q;

cin >> q;

for (int i = 1; i <= q; i++)

{

long long vv;

cin >> vv;

bool is_valid = false;

for (int j = 1; j <= cc; j++)

{

if (Bin (vv - c[j]))

{

is_valid = true;

break;

}

if (is_valid)

cout << "YES" << endl;

else

cout << "NO" << endl;

}

return 0;

}

hdu2138

hdu2149

一	二	三	四	五	六	日
« 6月
						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

超客的水墨烟雨

hdu2141

Can you find it?

分类目录

标签云

书签

近期评论