牛客小白月赛65 A-D题解

2023/1/6 算法竞赛 题解 C++ 牛客 小白月赛

第一次打牛客rating赛

A. 牛牛去购物

题面

反正就一组输入，遍历所有解找极值即可

AC代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int n,a,b;
    cin>>n>>a>>b;
    int m=1e9;
    for(int i=0;i<=n/b;i++)
    {
        m=min(m,(n-b*i)%a);
    }
    cout<<m<<'\n';
    return 0;
}

B. 牛牛写情书

题面

先把牛可乐加的字符筛掉，然后用string自带的find()函数查找即可

AC代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    string s,k;
    cin>>s;
    cin>>k;
    string t;
    for(int i=0;i<s.length();i++)
    {
        if(isalpha(s[i]))
            t=t+s[i];
    }
    if(t.find(k)!=string::npos)
        cout<<"YES"<<'\n';
    else
        cout<<"NO"<<'\n';
    return 0;
}

C. 牛牛排队伍

题面

操作次数较多，每一次都是随机一种操作，需要一个比较合理的算法.

想到用静态双向链表，每一次查找和修改都是O(1)的复杂度.

AC代码： 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
struct node
{
    int pre;
    int next;
}a[N];
bool v[N];
int main() {
    ios::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    memset(v,false,sizeof(v));
    for(int i=0;i<=n;i++)
    {
        a[i].pre=i-1;
        a[i].next=i+1;
    }
    for(int i=1;i<=k;i++)
    {
        int op,x;
        cin>>op>>x;
        if(op==1)
        {
            a[a[x].next].pre=a[x].pre;
            a[a[x].pre].next=a[x].next;
        }
        else if(op==2)
        {
            cout<<a[x].pre<<'\n';
        }
    }
    return 0;
}

D. 牛牛取石子

题面

是我第一次碰到博弈论的问题.

两种操作很相似，找一些不变的东西，比如 的奇偶，但是可能会在中间步骤被对面卡死，比如9 1先手必胜(只需要把1那一堆取走就赢了).

如果只有一堆石子，每一次操作为取1个或2个，那么可以有模仿步. 比如一开始是 a 个石子，如果 a ≢ 0(mod3) ，那么第一次取a%3个石子，后面每一次操作都将a变为3的倍数(取a%3个石子)，那么最后一次操作必然属于先手方，那么先手必胜；如果 a ≡ 0(mod3) ，则情况相反.

两堆石子和一堆石子有点类似，分类讨论一下.

首先不妨 a ≤ b ，然后因为操作以两个人为周期，a = b 时会出现操作一次后 a 和 b 的顺序反掉，也许会影响结果，所以把 a = b 的情况单独拿出来讨论.

讨论的过程十分的冗杂，不想过多赘述，只留下结果

a < b 时，若 3 ∣ a, 3 ∤ b或3 ∣ a, 3 ∣ b 时，后手胜，其余先手胜. a = b 时，若 a ≡ 2(mod3) 时，先手胜，其余后手胜.

AC代码： 

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        ll a,b;
        cin>>a>>b;
        if(a>b)
            swap(a,b);
        if(a<b)
        {
            if(a%3==0)
                cout<<"niumei"<<'\n';
            else
                cout<<"niuniu"<<'\n';
        }
        else
        {
            if(a%3==2)
                cout<<"niuniu"<<'\n';
            else
                cout<<"niumei"<<'\n';
        }
    }
    return 0;
}
img_show