img

牛客练习赛121

A-小念吹气球

哈希暴力即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

string s;
int a[26];//存储字母的种类

int main()
{
    int n, ans = 0;
    cin >> n >> s;
  //计算每种字母的数量
    for(int i = 0; i < n; i ++) a[s[i] - 'A'] ++;
  //如果这种字母只剩，那么ans + 2, 否则 ans + 1
    for(int i = 0; i < 26; i ++)
        while(a[i])
            a[i] == 1 ? ans += 2 : ans ++, a[i] --;
    cout << ans << '\n';

    return 0;
}

师兄代码：

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
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long 
#define For(i, a, n) for(int i = a; i <= n; i++)
#define rof(i, n, a) for(int i = n; i >= a; i--)
#define endl "\n"
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 998244353;
int T;
int n;
string s;
void solve()
{
    cin >> n;
    cin >> s;
    map<char, int> mp;
    for(auto x:s)
    {
        if(!mp[x])
        {
            mp[x]++;
            n++;
        }
    }
    cout << n << endl;
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // cin >> T;
    T = 1;
    For(I, 1, T)
    {
        solve();
    }
    return 0;
}

B-You Brought Me A Gentle Breeze on the Field

观察，一个必输

2-m+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
#include<iostream>
using namespace std;
int main(){
    int t,p;
    long n,m;
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>n>>m>>p;
        if(n==1){
            cout<<"YangQiShaoNian"<<endl;
            continue;
        }
        if(n<=m+1){
            cout<<"XiaoNian"<<endl;
        }else{
            if(p==0){
                cout<<"XiaoNian"<<endl;
            }else{
                cout<<"YangQiShaoNian"<<endl;
            }
        }
    }
    return 0;
}

C-氧气少年的水滴 2

纯模拟

直接模拟罢

注意遇到l--,r--的过程

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
#include<iostream>
using namespace std;
int main(){
    int t,n,p;
    long a[1000000];
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>n>>p;
        int l=0,r=0;
        int left=p-1,right=p+1;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        if(a[p]+1==10){
            l=r=1;
        }
       while(1){
           if(left>=1&&l){
                l--; 
               a[left]+=1;
               if(a[left]==10){
               l++;
                r++;
                left--;
               }
           }
           else if(right<=n&&r){
                 r--;
               a[right]+=1;
               if(a[right]==10){
                   l++;
                   r++;
                   right++;
               }
           }
           else{
               break;
           }
       }
        cout<<l<<" "<<r<<endl;
    }
    return 0;
}

D-氧气少年的 LCM

采取二进制的凑数法

image-20240311112319543 
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
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
struct Node
{
    int x, y, z;
};
 
void solve()
{
    int x, y;
    cin >> x >> y;
    int d = x * y / __gcd(x, y);
    if (x > y) swap(x, y);
    if (y % x == 0) 
    {
        cout << 0 << "\n";
        return;
    }
 
    vector<Node> g;
    int t = gcd(x, y);
    int p = d / t;
    g.push_back({1, x, y});
    g.push_back({1, x, y});
    //放入两个gcd
 
    int k = 0;
    int w = log2(p);
    while (w --)
    {
        g.push_back({2, t, t});
        g.push_back({2, t, t});
        t *= 2;
    }
    //这个也是每次放入两个gcd的二倍
    w = log2(p);
    t = gcd(x, y);
    int ans = 0;
    for (int i = 0; i <= w; i ++)
    {
        if (p & 1) 
            //类似二进制的拆分，直接一直放一直加即可
        {
            if (!ans) 
                ans = (1LL << i) * t;
            else
            {
                g.push_back({2, (1LL << i) * t, ans});
                ans += (1LL << i) * t;
            }
        }
        p >>= 1;
    }
     
 
    cout << g.size() << "\n";
    for (auto t : g)
        //输出
        cout << t.x << ' ' << t.y << ' ' << t.z << '\n';
}
 
signed main()
{
 
    int T;
    for (cin >> T; T -- ; )
       solve();
 
}