2023 GDCPC 广东省赛 ACDIK

Nannan Lv5
  2023-10-24 16:57 2023-10-24 16:57 Created   2024-09-30 17:13:01 2024-09-30 17:13:01 Updated      

The 2023 Guangdong Provincial Collegiate Programming Contest ACDIK

去年打了这场，当时没有补题，现在来直面恐惧。

A. Programming Contest

思路：签到

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin>>t;
    while(t--)
    {
        int y1; cin>>y1;
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        int y2; cin>>y2;
        ll ans = y2-y1+1;
        for(int i = 1;i <= n; i++)
        {
            if(a[i]>=y1&&a[i]<=y2)ans--;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

C. Trading

思路：排序+双指针

按照价格从大到小排序，从便宜的买入从贵的卖出，做一个双指针即可。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
array<int,2>a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i][0]>>a[i][1];
        sort(a+1,a+1+n);
        int l = 1,r = n;
        ll ans = 0;
        while(l<r)
        {
            int mn = min(a[l][1],a[r][1]);
            ans += 1ll*(a[r][0]-a[l][0])*mn;
            a[l][1] -= mn;
            a[r][1] -= mn;
            if(a[l][1]==0)l++;
            if(a[r][1]==0)r--;  
        }
        cout<<ans<<"\n";
    }


    return 0;
}

D. New Houses

思路：就是这个题！明明思路就是对滴，当时赛时没写出啊。

考虑个人有邻居的最大值，注意可能所有人都没有邻居(2*n-1<=m)。每次让没有邻居的变成有邻居的，增加的是差值。

注意特判。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
array<ll,2>a[N];
ll d[N];

bool cmp(ll a,ll b)
{
    return a>b;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin >> t;
    while(t--)
    {
        int n,m; cin>>n>>m;
        ll ans = 0;
        ll hav = 0,no = 0;
        for(int i = 1;i <= n; i++)
        {
             cin>>a[i][0]>>a[i][1];
             hav += a[i][0],no += a[i][1];
             d[i] = a[i][0]-a[i][1];
        }
        if(n==1)
        {
            cout<<a[1][1]<<"\n";
            continue;
        }
        if(n==m)
        {
            cout<<hav<<"\n";
            continue;
        }

        sort(d+1,d+1+n,cmp);
        //k个人有邻居，剩下的没有邻居：需要k+2(n-k) = 2n-k个房子

        if(m>=2*n-1)//所有人都没有邻居
            ans = no;
        ll now = no;
        now += d[1];
        for(int i = 2;i <= n; i++)//i个人有邻居
        {
            now += d[i];
            if(2*n-i<=m)ans = max(ans,now);
        }   
        cout<<ans<<"\n";
    }


    return 0;
}

I. Path Planning

思路：考虑，当前的mex值由什么决定？是由当前没出现过的最小的决定。如果当前的最小值是x，那么<x的值一定都被取到了。我们可以考虑二分答案。但是问题又来了，怎么去check答案？由于我们只能往下和往右走，我们走出来的路径一定是呈现阶梯状的。

![image-20231024165435446](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20231024165435446.png)

比如上图这样一个行驶路线，我们观察每一行，上一行的有边界一定<=这一行的左边界。那么依据这个做check即可。

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
// #define ll int
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
int a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n,m; 
        cin>>n>>m;
       // vector<vector<ll>> a(m+10, vector<ll>(n+10));
        for(int i = 1; i <= n; i++)
            for(int j = 1;j <= m; j++)
                cin>>a[i*m+j];

        auto judge = [&](ll x)
        {
            //<x都要取到
            ll l = 0,r = 0;
            for(int i = 1;i <= n; i++)
            {
                bool st = false;
                ll tl = -1,tr = -1;
                for(int j = 1;j <= m; j++)
                {
                    if(a[i*m+j]<x&&!st)
                        tl = j,st = true;
                    if(a[i*m+j]<x&&st)
                        tr = j;
                }
                if(tl==-1)continue;
                if(tl>=r)
                    l = tl,r = tr;
                else return false;
            }
            return true;
        };

        ll l = 0,r = n*m;
        while(l<=r)
        {
            ll mid = (l+r)>>1;
            if(judge(mid))l = mid+1;
            else r = mid-1;
        }
        cout<<l-1<<"\n";
    }


    return 0;
}

K. Peg Solitaire

思路：数据范围很小，直接暴搜。注意初始化！

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 10;
int a[N][N];
                // 上    下     左     右
int dir[4][2] = {{-2,0},{2,0},{0,-2},{0,2}};
int n,m,k; 
bool vaild(int op ,int x,int y)
{
    if(op==0){//上
        if(x-2>=1&&a[x][y]&&a[x-1][y]&&!a[x-2][y])
            return true;
        else return false;
    }else if(op==1){
        if(x+2<=n&&a[x][y]&&a[x+1][y]&&!a[x+2][y])
            return true;
        else return false;
    }else if(op==2){
        if(y-2>=1&&a[x][y]&&a[x][y-1]&&!a[x][y-2])
            return true;
        else return false;
    }else{
        if(y+2<=m&&a[x][y]&&a[x][y+1]&&!a[x][y+2])
            return true;
        else return false;
    }
}


int ans;
void dfs(int now)
{
    ans = min(ans,now);
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)if(a[i][j]==1){
            for(int d = 0;d < 4; d++)if(vaild(d,i,j)){
                    int x = i,y = j,op = d;
                    if(op==0){//上
                    a[x][y] = 0,a[x-1][y] = 0,a[x-2][y] = 1;
                    dfs(now-1);
                    a[x][y] = 1,a[x-1][y] = 1,a[x-2][y] = 0;

                }else if(op==1){
                    a[x][y] = 0,a[x+1][y] = 0,a[x+2][y] = 1;
                    dfs(now-1);
                    a[x][y] = 1,a[x+1][y] = 1,a[x+2][y] = 0;

                }else if(op==2){
                    a[x][y] = 0,a[x][y-1] = 0,a[x][y-2] = 1;
                    dfs(now-1);
                    a[x][y] = 1,a[x][y-1] = 1,a[x][y-2] = 0;

                }else{
                    a[x][y] = 0,a[x][y+1] = 0,a[x][y+2] = 1;
                    dfs(now-1);
                    a[x][y] = 1,a[x][y+1] = 1,a[x][y+2] = 0;
                }
            }
        }
}

void solve()
{
    cin>>n>>m>>k;
    memset(a,0,sizeof(a));
    for(int i = 1;i <= k; i++)
    {
        int x,y; cin>>x>>y;
        a[x][y] = 1;
    }

    ans = k; dfs(k);
    cout<<ans<<"\n";
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        solve();
    }


    return 0;
}

  • Title: 2023 GDCPC 广东省赛 ACDIK
  • Author: Nannan
  • Created at : 2023-10-24 16:57:00
  • Updated at : 2024-09-30 17:13:01
  • Link: https://redefine.ohevan.com/2023/10/24/The 2023 Guangdong Provincial Collegiate Programming Contest/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
2023 GDCPC 广东省赛 ACDIK
  1. The 2023 Guangdong Provincial Collegiate Programming Contest ACDIK
    1. A. Programming Contest
    2. C. Trading
    3. D. New Houses
    4. I. Path Planning
    5. K. Peg Solitaire