计算机技术协会第十七周算法赛(第一场ACM模拟赛)题解

具体翻译是如何我不太清楚，队伍中我负责编写代码，另外一个同学负责翻译题目。不过大概的题意能够理解。由于最后一题没人做，一共九题，只看了八道题。最后一题就不讲了

A Helpful Maths

题目：

给定一个字符串S， S是一串表达式，且只有加号。需要将位置表达式中各项进行换位置，最小的排在最前面，最大的排在最后。

思路：

处理输入的时候将每一项数据存入到数组中，然后进行排序，最后输出即可。

代码：

#include <bits/stdc++.h>
//#define int long long

#define endl '\n'
using namespace std;
const int N = 1e5 + 10;

int a[N], idx;
signed main() {
  int t;
  char op;
  while (true) {
    scanf("%d%c", &t, &op);
    // 使用 int m = scanf("%d%[+]", &t, &op); if (m == 1) break; 也是可以的
    a[idx ++ ] = t;
    if (op != '+') break;
  }
  sort(a, a + idx);
  for (int i = 0; i < idx - 1; i ++ ) {
    cout << a[i] << "+";
  }
  cout << a[idx - 1] << endl;
  return 0;
}

B：Dictionary

题目：

给定一个长度为2的字符串，判断是第几个word;

1 word: ab, 2 word ac… 25 word az, 26 word ba, 27 word bc … 649 word zx, 650 word zy;

思路：

可以找规律，也可以直接暴力解决，（最开始的思路就是暴力解决最好）

代码：

暴力：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
map<string, int> mp;

void init() {
  int idx = 1;
  for (int i = 0; i < 26; i ++ ) {
    for (int j = 0; j < 26; j ++ ) {
      if (i != j) {
        char _1 = 97 + i;
        char _2 = 97 + j;
        string s = "";
        s += _1;
        s += _2;
        mp[s] = idx ++;
      }
    }
  }
  
}

signed main() {
  init();
  int t;
  cin >> t;
  getchar();
  while (t -- ) {
    string s;
    getline(cin, s);
    cout << mp[s] << endl;
  }
  
  return 0;
}

找规律：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
string s;
int t;
signed main() {
  
    scanf("%lld", &t);
    getchar();
    while (t -- ) {
        getline(cin, s);
        int ans = (s[0] - 97) * 25 + s[1] - 97;
        if (s[0] > s[1]) ans ++;
        cout << ans << endl;
    }
  
} 

C: Splitting in Teams

题目：

有n个由两个或一个人组成的组别，现在教练需要重新组队，每个队三个人，但是之前的队伍中，如果是两个人一起的，则必须一起，否则就不会组队，要么一起参加，要么都不参加。

思路：

要么就是2+1，要么就是1+1+1，所以优先处理2+1，剩余的1三人一组就行，如果有甚于的2则一个都不行。

代码：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
signed main() {
    scanf("%lld", &n);
    int _1 = 0, _2 = 0;
    for (int i = 0, x; i < n; i ++ ) {
        scanf("%lld", &x);
        if (x == 1) _1 ++;
        else _2 ++;
    }
  
    int ans = min(_1, _2);
    if (_1 > _2) {
        _1 -= _2;
        ans += _1 / 3;
    }
    
    cout << ans << endl;
    return 0;
}

D： Count the Number of Pairs

题目：

给定一个长度为n的字符串s。

请检查有多少对满足条件的字符对：一个大写的A对应一个小写的a，有5个大写的A和3个小写的a则有3对满足条件的字符对

并且给k次操作机会。每一次操作可以将小写字符变成大写，大写字母变成小写，这样就能够再多一个字符。

思路：

纯模拟

代码：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
int a[N];
int t, n, k;
string s;
map<char, int> mp;
void solve() {
    mp.clear();
    int len = s.length();
    for (int i = 0; i < len; i ++ ) {
        mp[s[i]] ++;
    }
    int ans = 0;
    for (int i = 0; i < 26; i ++ ) {
        char _1 = 97 + i;
        char _2 = 65 + i;
        if (mp[_1] == 0 && mp[_2] == 0) continue;
        int temp = min(mp[_1], mp[_2]);
        ans += temp;
        int maxNumber = max(mp[_1], mp[_2]) - temp;
        if (maxNumber >= 2 && k > 0) {
            int __ = maxNumber / 2;
            if (__ >= k) {
                ans += k;
                k = 0;
            } else {
                k -= __;
                ans += __;
            }
        }
    }
    cout << ans << endl;
}
signed main() {
    scanf("%lld", &t);
    while (t -- ) {
        scanf("%lld%lld", &n, &k);
        getchar();
        getline(cin, s);
        solve();
    }
    return 0;
}

E： Fake NP

题目：

给定一个区间[l, r]， 对于一个数x，他在这个区间内有y个数能被x整除，请找出一个x，使得整除的数最多。x!=1

思路：

一个区间，一定是能被2整除的数最多，（一个for循环，步长> 1，使得循环次数最多，请问步长为多少？）答案一定是2，如果这个区间只有1个数，则答案就是它本身

代码：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int l, r;

signed main() {
    cin >> l >> r;
    if (l == r) cout << l << endl;
    else puts("2");
    return 0;
}

F: Remove Two Letters

题目：

给定一个字符串s，可以进行一个操作，每次可以删除相邻的两个字符，请问剩余的字符可以有多少组（相同的是为一个）。

思路：

如果第i个字符串与第i+2个字符串相同的话，则操作后会造成相同的字符串。

代码：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

int t, n, ans;
string s;
signed main() {
    scanf("%lld", &t);
    while (t -- ) {
        ans = 0;
        scanf("%lld", &n);
        getchar();
        getline(cin, s);
        int ans = n - 1;
        for (int i = 0; i < n - 2; i ++ ) {
            if (s[i + 2] == s[i]) ans --;
        }
        cout << ans << endl;
    }
    return 0;
}

G:Make Them Odd

题目：

给定一个长度为n的正整数数组，每一次操作可以选择n个value为c并且能被2整除的元素，并且将这些元素拿出来除以2，重新放进数组中。一直操作，直到数组中的元素全为奇数。

思路：

暴力：数据量较小，总共数据不会超过2E5， 单个元素不超过1E9，所以如果纯模拟的话，时间复杂度应该是2E5*log1E9, 不会超时，所以直接暴力做也可以做出来。

贪心：优先处理最大的元素，因为处理大的元素的时候，可能会顺带把小的数据给一起处理了。

代码：

方法1：暴力：

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
int t, n, a[N];

set<int> st;

void solve(int x) {
    if (x & 1) return;
    st.insert(x);
    solve(x / 2);
}

signed main() {
    scanf("%lld", &t);
    getchar();
    while (t -- ) {
        st.clear();
        scanf("%lld", &n);
        for (int i = 0; i < n; i ++ ) {
            scanf("%lld", a + i);
            solve(a[i]);
        }
        cout << st.size() << endl;
    }
} 

方法2： 使用优先队列，将偶数push进队列中，然后使用map进行标记是否已经处理过了

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, t, idx;
int main()
{
    scanf("%d", &t);
    while (t -- ) {
        map<int, bool> mp;
        priority_queue<int> q;
        scanf("%d", &n);
        for (int i = 0, x; i < n; i ++ ) {
            scanf("%d", &x);
            if (x % 2 == 0) mp[x] = true;
        }
        // 偶数去重, 因为一次操作一个和多个的效果是一样的
        for (auto i : mp) q.push(i.first);
        // 记录次数
        int cnt = 0;
        while (!q.empty()) {
            // 找到没有被处理过的且最大的元素，如果当前最大的元素已经在之前处理的时候被处理了，则舍弃就行
            while (!q.empty() && !mp[q.top()]) q.pop();
            // 可能队列已经空了
            if (q.empty()) break;
            // 取出最大的，然后进行处理
            int t = q.top();
            q.pop();
            mp[t] = false;
            while (t % 2 == 0) {
                // 标记小的已经处理过了
                mp[t / 2] = false;
                t >>= 1;
                // 记录操作的次数
                cnt ++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

H

题目：

给定一个长度为n的数组an，如果满足所以的i, j, k(1<= i < j < k <= n)使得a[i] + a[j] + a[k]的结果也在数组中；则称这个数组为3SUM-CLOSED。

思路：

假设取出三个最小的负数， 则三数之和一定会变得更小，所以一定不存在两个以上的负数。同理，正数也一样。

当有0的情况下，数组中也不能有两个正数，因为x+y+0 = x + y，而x+y会比x或y更大。同理负数也一样；当数组中全是0，则一定满足条件。当数组中只有一个正数，其他全为0，也一定满足条件(0+0+x = x)，同理，负数也一样。当数组中只有一对正负数的时候，即：x < 0, y > 0, sum = x + y + 0, sum必须为0才能满足条件。

没有0的情况下，且都小于3个数，则只有一种情况：数组长度为4；

长度为4最后只需要直接三个for循环搞定就行了，也就循环96次。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, t, idx;

// 

bool check() {
    int _l = 0, _mid = 0, _r = 0, sum = 0;
    for (int i = 0; i < n; i ++ ) {
        if (a[i] < 0) _l ++;
        else if (a[i] == 0) _mid ++;
        else _r ++;
        sum += a[i];
    }
    
    if (n == 3) {
        return a[0] == sum || a[1] == sum || a[2] == sum;
    }
    
    // 肯定不能有三个负数 
    // 同理；肯定不能有三个正数 
    if (_l >= 3 || _r >= 3) return false;
    // 有零的情况 
    if (_mid > 0) {
        // 两个正数或两个负数
        // 2 3 0 => 5
        if (_l == 2 || _r == 2) return false;
        // 只有1个正数和1个负数
        if (_l == 1 && _r == 1) return sum == 0;
        // 只有1个正数或负数 
        // 001 002 003 001 0+0+0  0+0+x => x 
        if (_r + _l == 1) return true;
        // 一个正数和负数都没有 => 0+0+0
        return true; 
    }
    // 长度为4且没有0的 i < j < k
    for (int i = 0; i < n; i ++ ) {
        for (int j = i + 1; j < n; j ++ ) {
            for (int k = j + 1; k < n; k ++ ) {
                bool f = false;
                for (int w = 0; w < n; w ++ ) {
                    if (a[i] + a[j] + a[k] == a[w]) {
                        f = true;
                        break;
                    }
                }
                if (!f) return false;
            }
        }
    }
    return true; 
}

int main()
{
    scanf("%d", &t);
    while (t -- ) {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", a + i);
        if (check()) puts("YES");
        else puts("NO");
    }
    return 0;
}