link：模拟笔试 – 卡码网周赛第三十六期

175. 阴阳师✅

简单模拟 注意向上取整技巧

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

int main() {
    int n; 
    cin >> n; 
    
    int a, b;
    while(n--) {
        cin >> a >> b;
        cout << (a + b - 1) / b << endl; //实现向上取整
    }
    
    return 0;
}

176. 切割正数❌

超时：回溯深搜 把int转换为string好切割一些

一般深搜超时的题目就得用DP了 dp[i]表示以下标 i-1为结尾的字符串对应的最大和，即前i个数

注意要单独讨论恰好为100的情况，就是在这里错了

回溯深搜：

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

int res, sum;
string x;

void backTracking(int index) {
    if(index >= x.size()) {
        // cout << sum << endl;
        res = max(res, sum);
        return ;
    }
    //切一位数或两位数
    int number[3];
    number[1] = x[index] - '0';
    number[2] = x[index + 1] - '0' + 10 * number[1];
    for(int i = 1; i < 3; i++) {
        sum += number[i];
        backTracking(index + i);
        sum -= number[i];
    }
}
int main() {
    cin >> x;
    
    backTracking(0);
    
    cout << res;
    
    return 0;
}

DP：

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

int main() {
    string x;
    cin >> x;
    //dp[i]表示以下标i-1结尾的整数的最大切割和，即前i个数
    vector<int> dp(x.size() + 1, 0);
    dp[1] = stoi(x.substr(0, 1));
    dp[2] = stoi(x.substr(0, 2)); //肯定比两个数分别加起来要大
    
    for(int i = 3; i <= x.size(); i++) {
        if(stoi(x.substr(i-3, 3)) == 100) dp[i] = dp[i-3] + 100;
        else dp[i] = max(dp[i-1] + stoi(x.substr(i-1, 1)), dp[i-2] + stoi(x.substr(i-2, 2)));
    }
    
    cout << dp[x.size()];
    
    return 0;
}

177. 学习语言❌

并查集 超时

178. 寻找平均数