2022 CCPC桂林 CEM

Nannan Lv5
  2023-09-12 11:33 2023-09-12 11:33 Created   2024-09-30 17:01:14 2024-09-30 17:01:14 Updated      

The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG)

A Hero Named Magnus 签到

签到，输出2x-1即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
	ll x;	cin>>x;
	cout<<x * 2 - 1<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int tc;	
	cin>>tc;
	while(tc--)
		solve();

}

D. Assumption is All You Need 贪心+构造

题意：给你两个排列和，每次只能交换中的一个逆序对，问你能不能经过若干次操作把变成?

思路：较大的数尽可能的放在前面，这样能交换的更多不会更劣。我们考虑从到枚举，如果当前的数的位置比目标的位置要小那么永远不可能(因为我是当前最大的且没在我要在的位置上的数，我只能和我后面比我小的数交换，因为我前面比我大的数以及在位置上了，相当于是我只能一路往右移)。那么最终就是：从大到小枚举，如果已经在该在的位置上了，我们就不动它，否则的话，在当前位置和目标位置之间找最大的数不停交换直到不能交换为止。最后for一遍看看是不是都是对的。

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
// 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;
int a[N],b[N],n,idx_a[N],idx_b[N];
vector<array<int,2>>ans;
int cnt;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        ans.clear();
        cnt = 0;
        cin>>n;
        for(int i = 1;i <= n; i++)
            cin>>a[i],idx_a[a[i]] = i;
        for(int i = 1;i <= n; i++)
        {
            cin>>b[i],idx_b[b[i]] = i;
        }
        bool ok = true;
        for(int i = n;i >= 1 ; i--)
        {
            if(idx_a[i]==idx_b[i])continue;
            if(idx_a[i]<idx_b[i])//当前我在目标的前面，所以我想要往后移动
            {
                int now = idx_a[i],aim = idx_b[i];
               // cout<<"i = "<<i<<" now = "<<now<<"\n";
                for(int j = i - 1;j >= 1; j--)
                {
                    //可以和后面比我小的交换
                    if(idx_a[j] > now && idx_a[j] <= aim)//位置在我后面，且在目标前面，往目标靠近
                    {
                        cnt++;
                        ans.push_back({now, idx_a[j]});
                        idx_a[i] = idx_a[j];
                        swap(a[now], a[idx_a[j]]);
                        swap(now, idx_a[j]);
                       // cout<<"idx_a[j] = "<<idx_a[j]<<" now = "<<now<<"\n";
                    }
                }
            }
            else if(idx_a[i]>idx_b[i])
            {
                ok = false;
                break;
            }
            
        }

        for(int i = 1;i <= n; i++)
            if(a[i] != b[i]) ok = false;

        if(ok)
        {
            cout<<cnt<<"\n";
            for(int i = 0;i < cnt; i++)
            {   if(ans[i][0]>ans[i][1])swap(ans[i][0],ans[i][1]);
                cout<<ans[i][0]<<" "<<ans[i][1]<<"\n";
            }
        }else cout<<"-1\n";
    }
    return 0;
}

E. Buy and Delete 图论+思维

题意：给你一个图，一开始一条边都没有。可以从商店去买若干条边加到图里面。之后呢要去删边，每次如果只保留删的边不会存在环。人话就是：每次不能删一个完整的环。问想要删的次数最多，想要最少。预测删的轮数。

思路：

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5500;
ll n, m, c, dist[N][N];
vector<pair<ll, ll>> e[N];
bool vis[N];
void dijkstra(int start)
{
    priority_queue<pair<ll,ll>, vector<pair<ll, ll>>, greater<pair<int, int>>> q;
    memset(vis, false, sizeof vis);
    dist[start][start] = 0;

    q.push({0, start});
    while(q.size() >= 1)
    {
        auto t = q.top();       q.pop();
        int u = t.second;
        if(vis[u])   continue;
        vis[u] = true;
        for(auto [v, w] : e[u])
        {   
            if(dist[start][v] > dist[start][u] + w)
            {

                dist[start][v] = dist[start][u] + w;
                q.push({dist[start][v], v});
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>m>>c;
    bool ok = false;
    for(int i = 1;i <= m; i++)
    {
        ll u,v,p; cin>>u>>v>>p;
        if(c>=p)ok = true;
        e[u].push_back({v,p});
    }
    if(!ok)
    {
        cout<<0<<"\n";
        return 0;
    }
    memset(dist, 0x3f, sizeof dist);
    for(int i = 1;i <= n; i++)
        dijkstra(i);
    ll ans = 1;
    for(int i = 1;i <= n; i++)
    {
        for(int j = 1;j <= n; j++)
        {
            if(i != j && dist[i][j]<(1e10) && dist[j][i]<(1e10))
            {
                ll cost = dist[i][j] + dist[j][i];
                if(cost<=c)
                {
                    ans = 2;
                    break;
                }
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

G. Occupy the Cities 动态规划

题意：

思路：

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
// 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;
ll f[N][3],last[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        string s; cin>>s;
        s = "?"+s;
        int pos = 0;
        for(int i = 0;i <= n; i++)
            f[i][0] = f[i][1] = 0,last[i] = 0;
        int fi = 0;
        for(int i = 1;i <= n; i++)
        {
            if(!fi&&s[i]=='1')fi = i;
            if(s[i]=='1'&&pos==0) last[i] = i,pos = i;
            else if(s[i]=='1')last[i] = pos,pos = i;
            else last[i] = pos;
        }

        //f[i][0/1] 前i个第i个1向左/向右
        if(s[1]!='1')
        {
            ll c = fi-1;
            //l
            f[fi][0] = c;
            //r
            if(c)
                f[fi][1] = c+1;
            else f[fi][1] = 0;
        }else f[1][0] = f[1][1] = 0;

        for(int i = 1;i <= n; i++)if(s[i]=='1'){
            if(i==last[i])continue;
            ll c = i-last[i]-1;//和上一个之间有多少个0
            if(!c){
                f[i][0] = min(f[last[i]][0],f[last[i]][1]);
                f[i][1] = min(f[last[i]][0],f[last[i]][1]);
                continue;
            }
            f[i][0] = c,f[i][1] = c+1;
            ll t1,t2;

            //10001
            //100001

            //l l
            //3->2,4->3
            t1 = max(f[last[i]][0],c/2+1);
            //r l
            //3->2,4->2
            t2 = max(f[last[i]][1],(c+1)/2);
            f[i][0] = min(t1,t2);


            //l r
            //3->3,4->3
            t1 = max(f[last[i]][0],(c+1)/2+1);
            //r r
            //3->2,4->3
            t2 = max(f[last[i]][1],c/2+1);
           
            f[i][1] = min(t1,t2);
        }
        ll ans = min(f[n][0],f[n][1]);
        if(s[n]=='1')
            cout<<ans<<"\n";
        else{
            ll c = n-last[n];
            //l
            ll t1 = max(f[last[n]][0],1+c);
            //r
            ll t2 = max(f[last[n]][1],c);
            cout<<min(t1,t2)<<"\n";
        }
    }
    return 0;
}

I. PTSD 贪心

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
// 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;
int 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;
        string s; cin>>s;
        s = "?"+s;
        
        for(int i = 1;i <= n; i++)
            a[i] = s[i]-'0';
    
        ll cnt0 = 0,ans = 0;
        for(int i = n;i >= 1; i--)
        {
            if(cnt0&&a[i]){
                cnt0--;
                ans += i;
            }else cnt0++;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

K. Tax 图论+搜索

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
int n, m, k, s, t;
vector<pair<ll, ll>> e[N * 4];
ll dist[N * 4],cnt[N * 4],ans[N * 4];
bool vis[N * 4];
int w[N];
void dijkstra(int s)
{
    priority_queue<pair<ll,ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> q;
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    q.push({0, s});
    while(q.size() >= 1)
    {
        auto t = q.top();       q.pop();
        int u = t.second;
        if(vis[u])   continue;
        vis[u] = true;
        for(auto [v,c] : e[u])
        {
            if(dist[v] > dist[u] + 1)
            {
                dist[v] = dist[u] + 1;
                q.push({dist[v], v});
            }
        }
    }
}

void dfs(int u,ll sum)
{
    ans[u] = min(ans[u],sum);
    for(auto [v,c] : e[u])
    {
        if(dist[v] == dist[u] + 1)
        {
            cnt[c]++;
            dfs(v,sum+cnt[c]*w[c]);
            cnt[c]--;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i = 1;i <= m; i++)
        cin>>w[i];
    for(int i = 1; i <= m; i++)
    {
        ll u, v, c;    cin>>u>>v>>c;
        e[u].push_back({v,c});
        e[v].push_back({u,c});
    }

    dijkstra(1);
    memset(cnt,0,sizeof(cnt));
    memset(ans,0x3f,sizeof(ans));
    dfs(1,0);
    for(int i = 2; i <= n; i++)
        cout<<ans[i]<<"\n";
    return 0;
}
  • Title: 2022 CCPC桂林 CEM
  • Author: Nannan
  • Created at : 2023-09-12 11:33:00
  • Updated at : 2024-09-30 17:01:14
  • Link: https://redefine.ohevan.com/2023/09/12/The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG)/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
2022 CCPC桂林 CEM
  1. The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG)
  2. A Hero Named Magnus 签到
  3. D. Assumption is All You Need 贪心+构造
  4. E. Buy and Delete 图论+思维
  5. G. Occupy the Cities 动态规划
  6. I. PTSD 贪心
  7. K. Tax 图论+搜索