"Wei Lai Cup" 2022 Niuke summer multi school training camp 5

[title link]( "Wei Lai Cup" 2022 Niuke summer multi school training camp 5_ACM/NOI/CSP/CCPC/ICPC algorithm programming high difficulty practice competition_ Ox off competition OJ (nowcoder.com))

K Headphones

General idea of the topic

There are N pairs of headphones, and Yasa takes out exactly k pairs. NIO should take out at least how many headphones, which can be more than Yasa takes out. There are a pair of headphones on the left and right. Yasa takes out a pair of headphones, and NIO takes them one by one.

Solution

See code.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, k;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> n >> k)
    {
        if ((n - k) * 2 <= n)
            cout << -1 << endl;
        else
            cout << n + 1 << endl;
    }
}

C Bit Transmission

General idea of the topic

There is a string composed of 01. For some positions, ask whether it is 1, ask 3n times, and ask at least once, and the answer returned is wrong. Ask whether these query results can uniquely determine the string.

Solution

See code.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, x;
string s;
int yes[maxn], no[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= 3 * n; i++)
    {
        cin >> x >> s;
        if (s == "YES")
            yes[x]++;
        else
            no[x]++;
    }
    s = "";
    bool ok = 1;
    for (int i = 0; i < n; i++)
    {
        if (no[i] && yes[i])
        {
            if (ok)
                ok = 0;
            else
            {
                cout << -1 << endl;
                return 0;
            }
            if (yes[i] == 1 && no[i] == 1)
            {
                cout << -1 << endl;
                return 0;
            }
            else if (no[i] == 1)
            {
                s += "1";
            }
            else if (yes[i] == 1)
            {
                s += "0";
            }
            else
            {
                cout << -1 << endl;
                return 0;
            }
        }
        else
        {
            if (no[i])
                s += "0";
            else
                s += "1";
        }
    }
    cout << s << endl;
    return 0;
}

B Watches

General idea of the topic

Given the price of n items, if you choose k items, the cost of purchasing the ith item is ai+k*i. Ask how many items you can buy at most (the ith item is the ith item in the original sequence).

Solution

Two points + greed, determine whether you can choose k items, and the total cost does not exceed M yuan.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int n, m;
int a[maxn], b[maxn];
bool checked(int k)
{
    int ans = 0;
    for (int i = 1; i <= n; i++)
        b[i] = a[i] + k * i;
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= k; i++)
    {
        ans += b[i];
        if (ans > m)
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        int l = 0, r = n, mid, ans;
        while (l <= r)
        {
            mid = (l + r) >> 1;
            if (checked(mid))
            {
                ans = mid;
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        cout << ans << endl;
    }
}

A Don't Starve

General idea of the topic

Given that n points have food (each point can be eaten many times), each point has a coordinate. The rule for walking is that each step must be strictly shorter than the previous step. Ask how many times you can eat food under the optimal scheme.

Solution

First, list all the edges, then sort them from large to small, and then enumerate the edges with the same length each time.

f[i] is defined as the maximum food obtained at the arrival point I in the current state.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 5;
const int Max = 0x3f3f3f3f;
int n;
int x[maxn], y[maxn];
struct Edge
{
    int u, v, dis;
    Edge(int u = 0, int v = 0, int dis = 0) : u(u), v(v), dis(dis) {}
    bool operator<(const Edge &a) const
    {
        return dis > a.dis;
    }
};
vector<Edge> e;
int f[maxn], g[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(f, -Max, sizeof f);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    for (int i = 0; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            if (i != j)
                e.push_back(Edge(i, j, pow(x[j] - x[i], 2) + pow(y[j] - y[i], 2)));
    }
    sort(e.begin(), e.end());
    f[0] = 0;
    for (int i = 0, j = 0; i < e.size(); i = j)
    {
        vector<Edge> v;
        for (; j < e.size() && e[i].dis == e[j].dis; j++)
            v.push_back(e[j]);
        for (auto e : v)
            g[e.v] = -Max;
        for (auto e : v)
            g[e.v] = max(g[e.v], f[e.u] + 1);
        for (auto e : v)
            f[e.v] = max(f[e.v], g[e.v]);
    }
    cout << *max_element(f, f + n + 1) << endl;
    return 0;
}

H Cutting Papers

General idea of the topic

An inequality is given, and the area of the closed region formed by this inequality and the circle centered on the center of the closed region are combined.

Solution

Draw the closed region according to the inequality, and directly calculate the union of the circle and the closed region.

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 5;
const int pi = acos(-1);
double n;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    cout << fixed << setprecision(10) << n * n * (4 - pi) / 8 << endl;
    return 0;
}