题解 | #（附代码）牛客练习赛121#

A-小念吹气球

• 比较简单，直接看注释

下面是代码部分

#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;
}

B-You Brought Me A Gentle Breeze on the Field

• 既然出题者已经写了解题思路——点击此处跳转题解，那么这里就稍微解释一下好了。

前情提要（若两者可以选择的数是相等——也就是没有抛硬币这一步骤）

• 只要有一者可以选择到，那么这一者就必赢
• 设两者可以数的数的个数均为
• 则必定可以维护（m + 1）
• 则只需 若结果为0，则后手可以选择到, 后手赢。
• 若结果不为0，则是先手是可以选择到, 先手赢。

做题思路

• 这道题两者的可选择的数的数量是不同的，所以不能按照上述做法，那该咋办——观察先后手

以下均摘自题解——出题人

• 先手必败

• 先手必胜，这是一个经典的纳什博弈。

• 

• 有多拿一次的机会的人是必胜的，因为它可以更换自己在纳什博弈中的先后手方，从而得到必胜姿态。 例如，在,先手不论怎么拿都会让后手进入必胜态，但如果先手得到多拿一次的机会，那么先手就可以让后手进入必胜态

• 因此，谁有机会多拿一次，谁就必胜。

下面是代码部分

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n, m, p;
        cin >> n >> m >> p;
        if(n == 1) cout << "YangQiShaoNian\n";
        else if(n <= m) cout << "XiaoNian\n";
        else
        {
            if(n - m == 1)
              cout << "XiaoNian\n";
            else
                !p ? cout << "XiaoNian\n" : cout << "YangQiShaoNian\n";
        }
    }
    return 0;
}

C-氧气少年的水滴 2

• 模拟题请直接看代码部分——有注释

下面是代码部分,代码参考来源——Heltion

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
//用于储存水滴的位置及其饱和度
int a[N];

int main() {
    int t, n, p;
    cin >> t;
    while(t --) {
        cin >> n >> p;
        for (int i = 1; i <= n; i ++) cin >> a[i];
      //c_clear左边的位置 c_right右边的位置 l飞向左边的水滴数 r飞向右边的水滴数
        int c_left = p - 1, c_right = p + 1, l = a[p] == 9, r = l;
        while (true) {
          //若c_left 合法，有飞向左边的水滴，则进行判断
            if (c_left >= 1 && l) {
              //此位置水滴加一点饱和度，则飞向左边的水滴数-1
                a[c_left] ++, l --;
                if (a[c_left] == 10) {
                  //飞向两边的水滴数均 + 1
                    l ++, r ++;
                  //指针位置左移
                    c_left --;
                }
            }
          //同理
            else if (c_right <= n && r) {
                a[c_right] ++, r --;
                if (a[c_right] == 10) {
                    l ++, r ++;
                    c_right ++;
                }
            }
          //均不满足时跳出判断
            else break;
        }
        cout << l << " " << r << "\n";//输出答案
    }

    return 0;
}

D-氧气少年的 LCM

题目

• 并未要求最短操作步骤，所以输出可以很长。

思路

• 已有，点击跳转——出题人

前情提要

• 
• 
• 解释:易得某个正整数……
  • 所以lcm(x, y) = gcd(x, y) * (2^a + 2^b + 2^c + ……)
• 当一个10进制的数被按照 “……千，百，十，个” 拆解为后，如何加回去？
• 方法： 可以看出每个数的权值为10 * (某个数)
• 下面这串代码是当 权值为2 ×（某个数） 时的方法

    for(ll i = 0;i < 60; i++)
            if((1ll << i) & n){
                if(cur)
                    outLine(2, cur, (1ll << i) * k);
                cur += (1ll << i) * k;
            }

//=======================================================

下面是代码部分——代码参考来源牛客288141082号

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e3 + 10;
int len;
typedef struct Str{
    int op;
    ll a, b;
}Str;
Str out[N];
//求最大公因数
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
//操作储存答案的函数
void outLine(int op, ll a, ll b);

int main()
{
    ll k, t, x, y, lcm, cur;
    cin>>t;
    while(t--) {
        len = 0;
        cin >> x >> y;
      //计算最小公倍数
        lcm = x * y / gcd(x,y);
      //计算最大公因数
        k = gcd(x,y);
      //按照解题思路先储存gcd(x, y)
        outLine(1, x, y);
        outLine(1, x, y);
        for(ll i = 1; i <= 60; i ++) {
          //当不符合题目要求时，跳出循环
            if(k * 2 > ll(1e18))
                break;
            outLine(2, k, k);
            outLine(2, k, k);
            k *= 2;
        }

        cur=0;
        k=gcd(x,y);
      //n代表，要几个gcd(x, y)相加才能为lcm(x, y)
        ll n = lcm / k;
        for(ll i = 0;i < 60; i++)
          //位运算，看成二进制。可以看成一种以二进制方式进位的计算方法
          //相加得出要求的lcm(x, y)
            if((1ll << i) & n){
                if(cur)
                    outLine(2, cur, (1ll << i) * k);
                cur += (1ll << i) * k;
            }
      //输出结果
        cout << len <<'\n';
        for(int i = 1; i <= len; i ++)
            cout << out[i].op << ' ' << out[i].a << ' ' << out[i].b << '\n';
    }

    return 0;
}

void outLine(int op, ll a, ll b)
{
    len ++;
    out[len].op = op;
    out[len].a = a;
    out[len].b = b;
}

E-氧气少年逛超市 3

思路

• 首先对物品价格和立减卷进行降序排序，折扣卷进行升序排序
• 令 表示当前状态的最大减免，各参数含义如下:
  • 当前第张折扣卷
  • 当前第张立减卷
  • 当前前个物品最大减免值

以下是代码部分——JerryBlack

#include<bits/stdc++.h>
using namespace std;

long double dp[5005][5005];
int p[10010], x[5005], y[5005];

int main()
{
    int t, n, a, b;
    long double temp, ans;
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin >> t;
    while(t --)
    {
        ans = 0.0;
        cin >> n;
        for(int i = 1; i <= n; i ++) cin >> p[i], ans += p[i];
        cin >> a;
        for(int i = 1; i <= a; i ++) cin >> x[i];
        cin >> b;
        for(int i = 1; i <= b; i ++) cin >> y[i];
      //排序
        sort(p + 1, p + n + 1, [](int a, int b){return a > b;});
        sort(x + 1, x + a + 1, [](int a, int b){return a < b;});
        sort(y + 1, y + b + 1, [](int a, int b){return a > b;});
      //初始化
        for(int i = 0; i <= a; i ++) for(int j = 0; j <= b; j ++) dp[i][j] = 0;
        temp = 0.0;
      //递推dp
        for(int i = 0; i <= a; i ++)
            for(int j = 0; j <= b; j ++)
            {
              //上一层使用立减券加这一层使用折扣券获得的总的减免
                if(i > 0)
                    dp[i][j] = fmaxl(dp[i][j], dp[i - 1][j] + 1.0 * (100 - x[i]) * p[i + j] / 100);         
              //进行比较得出是用减免券好还是折扣券好
                if(j > 0)
                    dp[i][j] = fmaxl(dp[i][j], dp[i][j - 1] + min(p[i + j], y[j]));
                temp = fmaxl(temp, dp[i][j]);
            }
      //输出即可
        cout << fixed << setprecision(15) << ans - temp << '\n';
    }

    return 0;
}