寒假限时训练（2）V、W、X

HuiPuKui · 2022-01-25 20:29:14 · 个人记录

V - Polycarp and Sums of Subsequences

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>

    using namespace std;

    int T, n, m;
    int a[11];

    int main()
    {
        cin >> T;
        while(T--)
        {
            for (int i = 0; i < 7 ; i++)
                cin >> a[i];
            cout << a[0] << ' ' << a[1] << ' ' << a[6] - a[0] - a[1] << endl;
        }
        return 0;
    }

W - 二分查找（一）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;
const int M = 1e6 + 5;

int T, n, m;
int a[N];
bool b[M];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        b[a[i]] = true;
    }

    while (m--)
    {
        int x;
        cin >> x;
        if (b[x])
            cout << "YES" << endl;
        else 
            cout << "NO" << endl;
    }

    return 0;
}

// 二分做法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

int T, n, m;
int a[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    while (m--)
    {
        int x;
        cin >> x;
        int l = 0, r = n - 1, mid;
        while (l < r)
        {
            mid = (l + r) / 2;
            if (a[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        if (a[r] == x)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

X - 和为给定数

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

int T, n, m;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    cin >> m;

    int l = 0, r = n - 1, f = 0;

    while (l < r)
    {
        if (a[l] + a[r] == m)
        {
            cout << a[l] << ' ' << a[r] << endl;
            f = 1;
            break;
        }
        else if (a[l] + a[r] < m)
            l++;
        else
            r--;
    }

    if (!f)
        cout << "No" << endl;
    return 0;
}

// 二分做法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;

int T, n, m;
int a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    cin >> m;

    int f = 0;
    for (int i = 0; i < n; i++)
    {
        int l = i, r = n - 1, mid;
        while (l < r )
        {
            mid = (l + r) / 2;
            if (a[mid] + a[i]>= m)
                r = mid;
            else
                l = mid + 1;
        }
        if (a[i] + a[r] == m)
        {
            cout << a[i] << ' ' << a[r] << endl;
            f = 1;
            break;
        }
    }

    if (!f)
        cout << "No" << endl;

    return 0;
}