蓝桥杯(一)

1.小蓝和小桥的挑战

#include<iostream>
using namespace std;
int t, n, a, cnt, sum;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        sum=0;//价值之和
        cnt=0;//操作的次数
        while (n--)
        {
            cin >> a;
            if (a == 0)
            {
                a++;//避免价值之积为0
                cnt++;
            }
            sum += a;
        }
            while (sum == 0)
            {
                cnt++;
                sum++;
            }
            cout << cnt << endl;
        
    }

}

? ? ? 如果物品的价值为0，而价值之积不能为0，所以对其加1；当价值之和为0时，直接对和加1即可。每次结束需要将操作次数和价值之和置为0。

2.DNA序列修正

#include<bits/stdc++.h>
using namespace std;
 
map<char, int> pp = {{'A', 0}, {'C', 1}, {'G',2}, {'T',3}};
 
int main()
{
    int n; cin >> n;
    string a,b;
    cin >> a >> b;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        if(pp[a[i]] + pp[b[i]] != 3)//不等于3不互补
        {
            for(int j = i+1; j < n; j++)
            {
                if(pp[a[i]] + pp[b[j]] ==3 && pp[a[j]] + pp[b[i]] == 3)
                {
                    swap(b[j], b[i]);//交换b互补两个位置
                    break;
                }
            }
             cnt++;
        }
    }
    cout << cnt;
    return 0;
}

? ? ? ?如果能交换位置，自然比替换更有效，所以如果不互补，我们先找能够交换碱基的两个位置，找到了就交换，计数器加1，其他情况直接对计数器加1即可。

3.最大数组和

?

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 9;
ll a[N], pre[N];
int t,n,k;
int main()
{
 
   cin >> t;
    while(t--)
    {
        
        cin >> n >> k;
        for(int i = 1; i <= n; i++)cin >> a[i];
        
        sort(a + 1, a + n + 1);
        
        for(int i = 1; i <=n; i++)pre[i] = pre[i-1] + a[i];
     
        
        ll ans = 0, q = 0;//q为最小的删除个数(k,q这样定义简化了思路的关系式)***
        while(k>=0)//k为最大的删除个数 
        {
            ans = max(ans, pre[n-k] - pre[q]);
            //区间和最大值。前缀和的优势：快速计算某一段区间和（O(1)）
            q += 2;
            k--;
        }
        cout << ans << "\n"; 
    }
      return 0;
}

? ? ?巧妙之处在于操作的顺序是无关紧要的，先删除两个最小的宝石、再删除最大的宝石和先删除最大的宝石、再删除两个最小的宝石的结果是一样的。假设删除了两个最小宝石的操作次数为m,当我们删除两个最小宝石的时候，剩下的宝石就是从中删除了2m个最小宝石和(k-m)个中最大宝石的宝石数组。计算剩下区间元素的总和可以用前缀和。

4.最大的卡牌价值

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define all(s) s.begin(),s.end()

int n, k;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    std::vector<int> a(n), b(n), d(n);
    LL ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ans += a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    for (int i = 0; i < n; ++i) d[i] = b[i] - a[i];
    sort(all(d), greater<int>());
    n = min(n, k);
    for (int i = 0; i < n; ++i) {
        if (d[i] > 0) ans += d[i];
    }
    cout << ans << '\n';
    return 0;
}

? ? ? 计算每张牌反面和正面的点数之差d，如果d>0，则反面点数大于正面，可以翻转；否则不翻转。同时k有可能大于n，但多余次数没有意义，所以取n和k的较小值。

5.最小化战斗力

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

int n;
int main()
{
    ios::sync_with_stdio(0),cin.tie(0); cout.tie(0);
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    int ans = 1e9;
    for (int i = 1; i < n; ++i) ans = min(ans, a[i] - a[i - 1]);
    cout << ans << '\n';
    return 0;
}

? ? ? ?战斗力差距最小，就是求排序之后序列相邻两项之差的最小值。