2022年中国大学生程序设计竞赛女生专场 ACEGHIL

Nannan Lv5
  2023-10-08 21:30 2023-10-08 21:30 Created   2024-09-30 17:09:26 2024-09-30 17:09:26 Updated      

2022年中国大学生程序设计竞赛女生专场 ACEGHIL

A. 减肥计划

思路：因为很大但是只有，那么分两种情况考虑：

  1. 对于的情况，那么一定所有人都比完了，因为轮一定可以确定最后的获胜者。那么答案就是最重的。
  2. 对于的情况，直接暴力模拟，最多不超过次。
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
// 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 n,k;
    cin>>n>>k;
    deque<array<int,2>>q;
    int maxx = 0,pos = 0;
    for(int i = 1;i <= n; i++)
    {
        int w; cin>>w;
        a[i] = {w,i};
        q.push_back(a[i]);
        if(w>maxx)
            maxx = w,pos = i;
    }
    if(k>=n)
    {
        cout<<pos<<"\n";
        return 0;
    }
    int cnt = 0;
    while(1)
    {
        auto fi = q.front();
        q.pop_front();
        auto se = q.front();
        q.pop_front();
        bool ok = false;
        while(1)
        {
            if(cnt>=k)
            {
                pos = fi[1];
                ok = true;
                break;
            }
            if(fi[0]>=se[0])
            {
                cnt++;
                q.push_back(se);
                se = q.front();
                q.pop_front();
            }
            else{
                q.push_back(fi);
                q.push_front(se);
                cnt = 1;
                break;
            }
        }
        if(ok)
            break;
    }
    cout<<pos<<"\n";

    return 0;
}

C. 测量学

思路：考虑钝角还是锐角，如果是钝角那么我们考虑取它的补角。枚举每一种情况取即可。

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
// 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;
const double pi = 3.1415926535;
long double a[N];
long double pre[N];
int main()
{
    //ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n;
    long double r,sita;
    cin>>n>>r>>sita;

    for(int i = 1;i <= n; i++)
        cin>>a[i];

    if(sita>pi)
        sita = pi*2-sita;
    long double ans = sita*r;
    for(int i = 1;i <= n; i++)
    {
        ans = min(ans,sita*a[i]+(r-a[i])*2);
    }

    printf("%.8Lf\n",ans);
    return 0;
}

E. 睡觉

思路：这题卡了很久啊，没注意到如果一轮下来清醒度不变的情况。本题分三种情况讨论：

  1. 一首歌的时间内能睡着
  2. 一轮下来清醒度递减
  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
// 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;
ll a[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int tc;
    cin>>tc;
    while(tc--)
    {
        ll x,t,k,n,d;
        cin>>x>>t>>k>>n>>d;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        ll tx = x,now = 0;
        bool ok = false;

        int cnt = 0,i = 1;
        while(cnt<=1e7)
        {
            if(a[i]<=d)tx--;
            else tx++;
            if(tx<=k)
                now++;
            else now = 0;
            if(now>=t){
                ok = true;
                break;
            }
            if(i==n)//注意这里！如果没写的话就不能判断一轮以内是否可以。
            {
                if(tx<x)
                {
                    ok = true;
                    break;
                }
            }
            i++;
            if(i>n)i = 1;
            cnt++;
        }
        if(ok||now>n*2)//now>n*2代表时间无限。因为它持续2轮都满足清醒度<=k,那么无限时间内一定可以
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }

    return 0;
}

总结：这题细节很多，写的时候要注意考虑对所以情况的分析。

G. 排队打卡

思路：这题直接模拟就可以了，但是注意细节。

【在每一秒结束前会放一次排队的人进入入口，一次最多进入不超过 k个人】的意思是，每次会放k人进入，不超过k人，但是小于k人的时候放当前的所有人。

按照这样的题意的话，那么每一秒的人数是确定的了，我们只要去check每一个有人排队的时刻即可。

为了好写一点，我们加入一个时间为，排队人数是的事件，这样方便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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
array<ll,2>evt[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    ll t,n,m,k;
    cin>>t>>n>>m>>k;
    for(int i = 1;i <= m; i++)
        cin>>evt[i][0]>>evt[i][1];
    m++;
    evt[m][0] = t,evt[m][1] = 0;
    sort(evt+1,evt+1+m);
    ll hav = 0;
    int last = 0;
    ll mn = 1e18,pos = 0;
    for(int i = 1;i <= m; i++)
    {
        hav = max(0ll,hav - (evt[i][0]-last-1)*k);
        hav += evt[i][1];
        last = evt[i][0];
        //cout<<"evt = "<<evt[i][0]<<" "<<hav<<"\n";
        if(evt[i][1] == 0 && hav!=n)
        {
            cout<<"Wrong Record\n";
            return 0;
        }
        if(evt[i][1] != 0 &&evt[i][0] >= t)
        {
            if(mn>=(hav+1)/k+((hav+1)%k!=0))
                mn = (hav+1)/k+((hav+1)%k!=0),pos = evt[i][0];
        }
        hav = max(0ll,hav-k);
    }
    
    cout<<pos<<" "<<mn<<"\n";
    return 0;
}

H. 提瓦特之旅

思路：看到【经过路上的第 个点时 需要 的时间完成委托】可以想到 到号点经过条边的最小花费。

这样就是典型的了，再做一个就可以了。

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 = 1010,M = 4e5+10;
ll n, m, k, dist[N], backup[N],cnt = 0;
struct EDGES
{
    ll a, b, w;
}edge[M];
ll f[N][N],pre[N];
void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    memset(f, 0x3f, sizeof f);
    dist[1] = 0;
    for(int i = 1; i < n; i++)//经过i条边
    {
        memcpy(backup, dist, sizeof dist);
        for(int j = 0; j < m*2; j++)
        {
            auto e = edge[j];
            dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
        }
        for(int j = 1; j <= n; j++)
        {
            f[i][j] = dist[j];
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        ll u,v,w; cin>>u>>v>>w;
        edge[cnt++] = {u,v,w};
        edge[cnt++] = {v,u,w};
    }
    bellman_ford();

    int q;
    cin>>q;
    while(q--)
    {
        int t; cin>>t;
        for(int i = 1;i <= n-1; i++)
        {
            ll w; cin>>w;
            pre[i] = pre[i-1]+w;
        }

        ll res = 1e18;
   
        for(int i = 1;i < n; i++)
        {
            if(f[i][t]!=0)
                res = min(res,f[i][t] + pre[i]);
        }
        cout<<res<<"\n";
    }
    cout<<"\n";
    return 0;
}

引用一篇文章：关于Bellman_ford算法解决有边数限制最短路(打印路径)

I. 宠物对战

思路：一眼字符串哈希+。

我先分别预处理出类和类的值，放到里面。然后做。

我们定义：表示，前位，第位放或放的最少需要的字符串个数。

我们枚举左右端点，转移就是：

1
2
3
4
if(dp[l-1][0]<(1e10)&&b.find(ha.get(l,r))!=b.end())
    dp[r][1] = min(dp[r][1],dp[l-1][0]+1);
if(dp[l-1][1]<(1e10)&&a.find(ha.get(l,r))!=a.end())
    dp[r][0] = min(dp[r][0],dp[l-1][1]+1);

dp思路很容易，但是注意用双哈希防止碰撞，还有就是这题卡常，注意一下。

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

typedef pair<long long, long long> pll;
struct DoubleStringHash
{
    vector<long long> h1, h2, w1, w2;
    long long base1 = 131, base2 = 13331;
    long long p1 = 1e9 + 7, p2 = 1e9 + 9;
    void init(string s) {
        int len = s.size();
        s = " " + s;
        h1.resize(len + 1), w1.resize(len + 1);
        h2.resize(len + 1), w2.resize(len + 1);
        h1[0] = 0, w1[0] = 1;
        h2[0] = 0, w2[0] = 1;
        for(int i = 1; i <= len; i++) {
            h1[i] = (h1[i - 1] * base1 + s[i]) % p1, w1[i] = w1[i - 1] * base1 % p1;
            h2[i] = (h2[i - 1] * base2 + s[i]) % p2, w2[i] = w2[i - 1] * base2 % p2;
        }
    }
    pll get(int l, int r) {
        return {(h1[r] - h1[l - 1] * w1[r - l + 1] % p1 + p1) % p1, (h2[r] - h2[l - 1] * w2[r - l + 1] % p2 + p2) % p2};
    }
}ha;

ll dp[N][3],lena[N],lenb[N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int n; cin>>n;
    set<pll>a,b;
    for(int i = 1;i <= n; i++)
    {
        string x; cin>>x;
        ha.init(x);
        int sz = x.size();
        a.insert(ha.get(1,sz));
    } 
    int m; cin>>m;
    for(int i = 1;i <= m; i++)
    {
        string x; cin>>x;
        ha.init(x);
        int sz = x.size();
        b.insert(ha.get(1,sz));
    } 

    string s; cin>>s;
    ha.init(s); int sz = s.size();
    memset(dp,0x3f,sizeof(dp));
    dp[0][1] = dp[0][0] = 0;
    for(int l = 1; l <= sz; l++)
    {
        for(int r = l; r <= sz; r++)
        {
            if(dp[l-1][0]<(1e10)&&b.find(ha.get(l,r))!=b.end())
                dp[r][1] = min(dp[r][1],dp[l-1][0]+1);
            if(dp[l-1][1]<(1e10)&&a.find(ha.get(l,r))!=a.end())
                dp[r][0] = min(dp[r][0],dp[l-1][1]+1);
        }
    }
    ll ans = min(dp[sz][0],dp[sz][1]);
    if(ans>=1e10)
        cout<<-1<<"\n";
    else cout<<ans<<"\n";

    return 0;
}

L. 彩色的树

思路：DSU on Tree 的模板题。套板子即可。

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
93
94
95
96
97
98
99
100
101
102
103
104
// 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 n, k, q;
vector<int> e[N];
int l[N], r[N], id[N], sz[N], hs[N], tot;
int res[N],col[N],cnt[N],dep[N],now;
vector<int>del_c[N*2];
inline void add(int u)
{
    if(cnt[col[u]]==0)now++;
    cnt[col[u]]++;
    del_c[dep[u]].push_back(col[u]);
}

inline void del(int depth)
{
    for(auto x : del_c[depth])
    {
        cnt[x]--;
        if(cnt[x]==0)now--;
    }
    del_c[depth].clear();
}

inline void query(int u)
{
    res[u] = now;
}

void dfs_init(int u,int f) {
    dep[u] = dep[f] + 1;
    l[u] = ++tot;
    id[tot] = u;
    sz[u] = 1;
    hs[u] = -1;
    for (auto v : e[u]) {
        if (v == f) continue;
        dfs_init(v, u);
        sz[u] += sz[v];
        if (hs[u] == -1 || sz[v] > sz[hs[u]])
            hs[u] = v;
    }
    r[u] = tot;
}

void dfs_solve(int u, int f, bool keep) {
    for (auto v : e[u]) {
        if (v != f && v != hs[u]) {
            dfs_solve(v, u, false);
        }
    }
    if (hs[u] != -1) {
        dfs_solve(hs[u], u, true);
    }

    for (auto v : e[u]) {
        if (v != f && v != hs[u]) {
            // for (int x = l[v]; x <= r[v]; x++)
            //     query(id[x]);
            for (int x = l[v]; x <= r[v]; x++)
            {
                if(dep[u]+k>=dep[id[x]])
                    add(id[x]);
            }
        }
    }
    //query(u); 
    add(u);
    del(dep[u]+k+1);
    query(u);
    if (!keep) {
        for(int x = l[u]; x <= r[u]; x++)
            del(dep[id[x]]);
    }
}


int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>k;
    for(int i = 1;i <= n; i++)
        cin>>col[i];
    for (int i = 1; i < n; i++) {
        int u, v;   cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs_init(1, 0);
    dfs_solve(1, 0, false);
    cin>>q;
    for(int i = 1;i <= q; i++)
    {
        int u; cin>>u;
        cout<<res[u]<<"\n";
    }
    return 0;
}

总结

总的来说，没有难题，但关键是细心+读题仔细。会写但不一定写的对，我经常这样，《手比脑子快》。这点要改，以后写之前先理清思路，还要考虑清楚怎么写会好写一点，这点很重要！！！有些写法或许可以，但是复杂，写错的可能性大。这种时候要考虑更好写的写法，比如G题，其实就很简单，但是一开始的写法比较丑。

  • Title: 2022年中国大学生程序设计竞赛女生专场 ACEGHIL
  • Author: Nannan
  • Created at : 2023-10-08 21:30:00
  • Updated at : 2024-09-30 17:09:26
  • Link: https://redefine.ohevan.com/2023/10/08/2022年中国大学生程序设计竞赛女生专场/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
2022年中国大学生程序设计竞赛女生专场 ACEGHIL
  1. 2022年中国大学生程序设计竞赛女生专场 ACEGHIL
  2. A. 减肥计划
  3. C. 测量学
  4. E. 睡觉
  5. G. 排队打卡
  6. H. 提瓦特之旅
  7. I. 宠物对战
  8. L. 彩色的树
  9. 总结