A-抽奖黑幕

思路

  • 看成删除数组的最大值或最小值使得数组总和最大
  • 添加某个尽可能小的正整数使得删除的数更小

代码部分

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

const int N = 2e5 + 10;
int a[N];

int main()
{
    int t, n;
    cin >> t;
    while(t --)
    {
        cin >> n;
        for(int i = 1; i < n; i ++) cin >> a[i];
        sort(a + 1, a + n);
        if(a[1] == a[n - 1]) cout << 1 << endl;
        else cout << a[n - 1] << endl;
    }

    return 0;
}

B-生成函数

题目描述

  • 三种无限多的砝码可以左右添加，使得天平平衡

思路

  • 三种砝码在数轴上可以表示无限多的数，但不一定是所有正整数
  • 只需要m % （任意一个数轴上表示数的差值） == 0 就可以平衡
  • 而数的差值一定为a, b, c 三个数的最大公因数的倍数
  • 所以只需要求最大公因数即可

代码部分

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

int gcd(int a, int b){return b ? gcd(b, a % b) : a;}

int main()
{
    int t, a, b, c, m;
    cin >> t;
    while(t --)
    {
        cin >> a >> b >> c >> m;
        int temp1 = gcd(a, b);
        int temp2 = gcd(temp1, c);
        if(m % temp2) cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}

C-选择交换

  • 代码部分（解释写在注解里）
  • 代码参考——AH-20
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
typedef struct Change{
  //    值     原位置    排序后的位置
    int value, pos_ori, pos_now;
}Change;

Change a[N];
//  m   用于记录输出的位置
int m, output[N][2];

bool cmp1(Change x, Change y){return x.value < y.value;}
bool cmp2(Change x, Change y){return x.pos_ori < y.pos_ori;}
void OutPut(int x, int y);
bool judge_false(int n);
void judge_true(int n);

int main()
{
    int t, n;
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> t;
    while(t --)
    {
        m = 0;
        cin >> n;
      //输入值并记录原位置
        for(int i = 1; i <= n; i ++)
            cin >> a[i].value, a[i].pos_ori = i;
        //如果最大值加上非最小值，那么最小值将无法配对
        sort(a + 1, a + n + 1, cmp1);
        if(judge_false(n))
        {
            //把序列排序为初始时的顺序
            sort(a + 1, a + n + 1, cmp2);
          //可以通过交换时进行处理
            judge_true(n);
        }
    }

    return 0;
}
//判断是否可以通过交换
bool judge_false(int n)
{
    //需要两两相加得到的值
    int judge = a[1].value + a[n].value;
    for(int i = 1; i <= n; i ++)
    {
        if(a[i].value + a[n - i + 1].value != judge)
        {
            cout << "NO\n";
            return false;
        }
        a[i].pos_now = i;
    }
    return true;
}

void judge_true(int n)
{
  //遍历，如果和有序时的顺序不同则记录并交换
  //也就是每个都判断一次位置
    for (int i = 1; i <= n; i++)
        while(a[i].pos_now != i)
        {
            OutPut(i, a[i].pos_now);
            swap(a[i], a[a[i].pos_now]);
        }
    cout << "YES\n";
    cout << m << '\n';
    for(int i = 0; i < m; i ++)
        cout << output[i][0] << ' ' << output[i][1] << '\n';
}
//储存交换的位置
void OutPut(int x, int y)
{
    output[m][0] = x;
    output[m][1] = y;
    m ++;
}