Codeforces Round 957 (Div. 3)

A

题目大意是对输入的a,b,c三个数，每个数可以自增，但是总自增值不得大于5。求$abc$的最大值。

这题直接使用暴力做法

#include <iostream>
#include <algorithm>

using namespace std;

int num[3][1005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[0][i] >> num[1][i] >> num[2][i];
    }

    for (int i = 0; i < n; i++) {
        int maxnum = 0;
        for (int a = 0; a <= 5; a++) {
            for (int b = 0; a + b <= 5; b++) {
                int c = 5 - a - b;
                int tmp = (num[0][i] + a) * (num[1][i] + b) * (num[2][i] + c);
                maxnum = max(tmp, maxnum);
            }
        }
        cout << maxnum << endl;
    }

    return 0;
}

B

题目大意是将所有数加在一起，但是每次只能减一或加一，求最小的加减次数。

这题可以使用栈来做，但是时间应该会超，因此采用模拟。

#include <algorithm>
#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int arr[N];

signed main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    int cnt = 0;
    cin >> n >> k;
    for (int i = 0; i < k; i++)
      cin >> arr[i];
    sort(arr, arr + k);
    for (int i = 0; i < k - 1; i++) {
      if (arr[i] == 1)
        cnt++;
      else {
        int tmp = 0; //移动次数
        while (arr[i] != 1) {
          arr[i]--;
          cnt++;
          tmp++;
        }
        cnt += tmp + 1;
      }
    }
    cout << cnt << endl;
  }
}

C

题目要求是求出f-g的最大值，这题我们可以根据答案写题解。

答案主要分为三段

• 在n——k，我们需要放入大于k的数，同时，由于f函数是累加的，我们需要从大到小排列，

• 在k——m，我们需要放入大于k小于m的数，这里可以随意排列（对函数的值无影响）

• 在1——k，由于我们要让g函数值最小，因此应该让越大的数排在越后面（被累加的次数越小）。

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    int num = n;
    while (num >= k) {

      cout << num << " ";
      num--;
    }
    num = m + 1;
    while (num < k) {
      cout << num << " ";
      num++;
    }
    num = 1;
    while (num <= m) {
      cout << num << " ";
      num++;
    }
    cout << endl;
  }
  return 0;
}

D

题意大抵是，小伙子为了追寻爱，需要越过n米河流，它可以跳过m米，也可以在水里游k米（注意这里指的是可以游的总距离）。

第一次cf止步于此，也是看了下Neal的题解，发现这题是用贪心做的，跳跃应该从后往前枚举（游最短的距离），用swim记录游泳距离。同时，在字符串前后添加字符，解决了边界问题。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
//
// 贪心算法，从最远开始向近处枚举
// 题目要求是水中游泳距离不超过 m 米，而不是每段水域都可以游 m 米
void judge() {
    int n, m, k;
    int pos = 0, swim = 0;
    string s;
    cin >> n >> m >> k;
    // 河流的长度 n，ErnKor 可以跳跃的最大距离 m，以及游泳不结冰的最大距离 k。
    cin >> s;

    // 在字符串 s 的开头和结尾添加 "L"，表示岸边，方便判断
    s = "L" + s + "L";      

    while (pos <= n) {
        if(s[pos] == 'C')    // 如果当前位置是鳄鱼，则直接退出
            break;
        if(s[pos] == 'W'){   // 如果当前位置是水，则前进一步，并记录游泳的距离
            pos++;
            swim++;
            continue;
        }
        bool jumped = false;

        // 尝试从当前位置向后跳跃，优先跳跃到最近的木头
        for(int i = min(pos + m, n + 1); i > pos; i--) {
            if(s[i] == 'L') {
                pos = i;
                jumped = true;
                break;
            }
        }
        if(jumped)  // 如果成功跳跃，则继续循环
            continue;
        
        // 尝试从当前位置向后跳跃，跳跃到水中
        for(int i = min(pos + m, n + 1); i > pos; i--) {
            if(s[i] == 'W') {
                pos = i;
                jumped = true;
                break;
            }
        }
        if(!jumped)  // 如果无法跳跃，则退出
            break;
    }

    // 判断是否到达河对岸，并且游泳的距离是否在允许范围内
    cout << (pos > n && swim <= k ? "YES" : "NO") << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        judge();
    }
    return 0;
}

E

我们需要找到数字满足a个n - b个n = a*n - b。暴力解法即可，注意字符串的处理。

参考：

Codeforces Round 957 (Div. 3 ABCDEFG题) 视频讲解-CSDN博客

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair<int, int> PII; // 定义一个类型别名，表示一对整数

#define int long long // 将 int 定义为 long long 类型
 int n;
// 计算整数的位数
int dec(int x) {
    int res = 0;
    while (x ) {
        res++;
        x/= 10;
    }
    return res;
}

void solve() {
   
    cin >> n;
    int digit = dec(n);
    vector<PII> res; 

    // 遍历可能的 a 值
    for (int a = 1; a <= 10000; a++) {
        // 遍历重复字符串的可能长度
        for (int i = 1; i <= min(6ll, digit * a); i++) {
            string s = to_string(n); 
            // 重复字符串直到达到长度 i
            while (s.size() < i) s = s + s;
            // 如果字符串超过长度 i，则进行截断
            while (s.size() > i) s.pop_back();      //处理两位数及以上的情况
            int m = stoll(s); 
        
            if (m == a * n - (digit * a - i) && i != digit * a) {
                res.emplace_back(a, digit * a - i); // 将满足条件的对加入结果向量
            }
        }
    }

    // 输出结果的数量
    cout << res.size() << endl;
    // 输出每个结果对
    for (auto v : res) {
        cout << v.first << " " << v.second << endl;
    }
}

signed main() {
    int n;
    cin >> n; // 读取测试用例的数量
    while (n--) {
        solve(); // 处理每个测试用例
    }
    return 0;
}