The 2024 CCPC National Invitational Contest (Changchun) , The 17th Jilin Provincial Collegiate Programming Contest

D

代码逻辑关键点

  1. 斜率整数表示：使用 b = dx * y3 - dy * x3 将斜率转化为整数，这样可以避免浮点精度问题。
  2. 剪枝：在 q.size() > k 的时候提前终止计算，这样可以提高算法效率，避免不必要的计算。
  3. 点的分布：通过判断每条线上的点的数量，确保每条平行线至少包含两个点。
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int mod = 998244353;

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> p(n + 1);

    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].first >> p[i].second;
    }

    int x1 = p[1].first, y1 = p[1].second;
    int x2, y2;
    for (int i = 2; i <= n; i++)
    {
        x2 = p[i].first, y2 = p[i].second;

        int dx = x2 - x1;
        int dy = y2 - y1;
        map<int, vector<int>> q;

        for (int j = 1; j <= n; j++)
        {
            int x3 = p[j].first, y3 = p[j].second;
            int b = dx * y3 - dy * x3;
            q[b].push_back(j);

            if (q.size() > k)
            {
                break;
            }
        }
        if (q.size() == k)
        {
            int f = 1;
            for (auto x : q)
            {
                if (x.second.size() == 1)
                {
                    f = 0;
                    break;
                }
            }

            if (f)
            {
                for (auto x : q)
                {
                    cout << x.second.size() << " ";
                    for (auto xx : x.second)
                    {
                        cout << xx << " ";
                    }
                    cout << '\n';
                }
                return;
            }
        }
    }
}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

E

由于要满足\(a_i-i<=a_j-j\)还有\(i-b_i<=j-b_j\)，因此可以进行排序，接下来只需要满足第二个要求即可。

贪心的想，如果当前的值比较小，那么必须新开一个块。不然就可以放到之前的某个块里面，并且放的时候也是直接把前面的小值都收纳了。

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
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int mod = 998244353;

void solve()
{
    int n;
    cin >> n;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].first >> a[i].second;
        a[i].first -= i;
        a[i].second = i - a[i].second;
    }
    sort(a.begin() + 1, a.end());
    vector<int> ans;
    for (int i = 1; i <= n; i++)
    {
        if (ans.size() == 0 || a[i].second < ans.back())
        {
            ans.push_back(a[i].second);
        }
        else
        {
            int x = ans.back();
            while (ans.size() && a[i].second >= ans.back())
            {
                ans.pop_back();
            }
            ans.push_back(x);
        }
    }
    cout << ans.size() << '\n';
}
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

G

签到题目，按照高度排序，接着不断判断，注意边界不取到等号。

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
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int mod = 998244353;
struct node
{
    int l, r, y;
};
bool cmp(node x, node y)
{
    return x.y > y.y;
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<node> a(n + 1);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].l >> a[i].r >> a[i].y;
        }
        sort(a.begin() + 1, a.end(), cmp);
        int sx, sy;
        cin >> sx >> sy;
        for (auto s : a)
        {
            if (s.y > sy)
            {
                continue;
            }
            if (sx > s.l && sx < s.r)
            {
                sx = s.r;
                sy = s.y;
            }
        }
        cout << sx << '\n';
    }
    return 0;
}

I

直接数数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 998244353;
bool panduan(int x)
{
    return int(sqrt(x)) * int(sqrt(x)) == x;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cout<<21<<'\n';
    return 0;
}

L

讨论一下：

  • 如果是1直接输出全部都用
  • 如果是偶数，2一定不会被节省，因此也是直接除法。
  • 如果是奇数，尽可能用2，直到需要用1去补全最后的空缺，看看1能不能补全，再讨论一下即可。
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
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const int mod = 998244353;

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        int k;
        cin >> k;
        int x, y;
        cin >> x >> y;
        if (k == 1)
        {
            cout << x + y << '\n';
        }
        else if (k % 2 == 0)
        {
            cout << (y * 2 + x) / k << '\n';
        }
        else
        {
            int cnt = k / 2;
            int sum = y / cnt;
            int ans = 0;
            if (x >= sum)
            {
                x -= sum;
                ans += sum;
                y -= cnt * sum;
                ans += (y * 2 + x) / k;
            }
            else
            {
                ans += x;
                y -= x * cnt;
                ans += y / ((k + 1) / 2);
            }
            cout << ans << '\n';
        }
    }
    return 0;
}