PTA09-P

[【附件】CCF PTA第九次认证-P试卷-C++.zip](/media/attachment/2025/12/CCF_PTA%E7%AC%AC%E4%B9%9D%E6%AC%A1%E8%AE%A4%E8%AF%81-P%E8%AF%95%E5%8D%B7-C.zip)

```
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main() {

set<string> s;
    int n ;
    string k;
    cin >> n;
    for(int i =0;i <n;i ++)
    {
        cin>>k;
        s.insert(k);
    }
    cout<<40-s.size()<<endl;
    return 0;
}

```

```
#include <iostream>
#include <set>
using namespace std;
const int N = 200000;
int a[N];
int main() {
    set<int> s;
    int n ;
    cin >> n;
    for(int i =0;i <n;i ++)
    {
       cin>>a[i];
    }
    for(int i = 0;i <n;i ++)
    {
        int sum =0;
        for(int j = i;j < n;j ++)
        {
            sum += a[j];
            s.insert(sum);
        } 
    }
    auto it = s.rbegin();
    cout<<*it;
    return 0;
}
```

组合
```
#include <iostream>
#include <vector>
using namespace std;

void printCombination(const std::vector<int>& combination) {
    for (int num : combination) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 生成所有组合的函数
void generateCombinations(const std::vector<int>& arr, int start, int n, std::vector<int>& combination, int k) {
    if (combination.size() == k) {
        printCombination(combination);
        return;
    }
    if (start >= arr.size()) {
        return;
    }
    // 不包含当前元素的情况
    generateCombinations(arr, start + 1, n, combination, k);
    // 包含当前元素的情况
    combination.push_back(arr[start]);
    generateCombinations(arr, start + 1, n, combination, k);
    combination.pop_back();
}

int main() {
    std::vector<int> arr;
    int l,n,m ,k;
    cin >> l>>n>>m;
    for(int i =0;i <n;i ++)
    {
       cin>>k;
       arr.push_back(k);
    }

std::vector<int> combination; // 用于存储当前的组合
    generateCombinations(arr, 0, n, combination, n-m); // 从索引0开始，选择n个元素的组合
    return 0;
}

```

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

// 全局变量/容器，存储含起点+残骸+终点的完整坐标数组
vector<int> pos;
int L, N, M;

// 可行性校验函数：判断能否通过清理<=M块残骸，使所有相邻间距 >= mid
bool check(int mid) {
    int removeCnt = 0;  // 需要清理的残骸数量
    int pre = pos[0];   // 上一个保留的位置（初始是起点0）
    for (int i = 1; i < pos.size(); ++i) {
        // 当前间距不足mid，必须清理当前残骸
        if (pos[i] - pre < mid) {
            removeCnt++;
        } else {
            // 间距足够，更新上一个保留位置
            pre = pos[i];
        }
    }
    // 清理数量不超过上限，可行
    return removeCnt <= M;
}

int main() {
    cin >> L >> N >> M;
    pos.push_back(0);  // 起点：阿尔法空间站，距离0
    for (int i = 0; i < N; ++i) {
        int d;
        cin >> d;
        pos.push_back(d);
    }
    pos.push_back(L);  // 终点：欧米伽空间站，距离L

int left = 1, right = L;
    int ans = 0;
    // 二分答案核心循环
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防溢出写法，等价于 (left+right)/2
        if (check(mid)) {
            ans = mid;        // 记录可行的最大最小值
            left = mid + 1;   // 尝试更大的候选值
        } else {
            right = mid - 1;  // 候选值太大，需要缩小
        }
    }
    cout << ans << endl;
    return 0;
}
```

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

// 高精度加法核心函数：逆序存储的两个大数相加，返回逆序的和【仅此处修改，加了截断100位】
vector<int> bigAdd(vector<int>& a, vector<int>& b) {
    vector<int> res;
    int carry = 0;
    int i = 0;
    while (i < a.size() || i < b.size() || carry > 0) {
        if (i < a.size()) carry += a[i];
        if (i < b.size()) carry += b[i];
        res.push_back(carry % 10);
        carry /= 10;
        i++;
        // 提前优化：加到100位就停，后面的高位直接不要，效率拉满
        if(res.size() >= 100) break;
    }
    // ========== 核心修改：保留最多100位，超过则截断 ==========
    if(res.size() > 100) {
        res.erase(res.begin() + 100, res.end());
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // 加速输入，应对50000的大输入
    
    int n, m;
    cin >> n >> m;
    
    // 一维滚动数组，每个元素是逆序存储的大数(最多100位)
    vector<vector<int>> dp(m + 1);
    // 初始化：所有dp[j] = 1 （大数1的逆序存储是 {1}）
    for (int j = 0; j <= m; j++) {
        dp[j].push_back(1);
    }

// 一维滚动数组DP核心循环，逻辑完全不变
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[j] = bigAdd(dp[j], dp[j-1]);
        }
    }

int index = 0;
    // 输出最终结果：逆序存储，倒序打印，最多100位
    if(dp[m].size()<100)
    {
        for (int i = 0;i < 100-dp[m].size();i++) 
        {
            index++;
            cout<<"0";
            if(index%10==0)cout<<endl;
        }
    }
    for (int i = dp[m].size() - 1; i >= 0; i--) {
        
        cout << dp[m][i];
        index++;
        if(index%10==0)cout<<endl;
    }
    cout << endl;

return 0;
}
```

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

vector<int> nums;   // 存储竹简片段长度
vector<bool> used;  // 标记片段是否被使用
int n;              // 片段数量
int total_sum;      // 所有片段总长度

// 回溯核心函数：判断能否凑出若干个和为len的分组，用完所有片段
// cur_sum: 当前正在凑的这一组的长度, start: 起始枚举下标(避免重复组合)
bool backtrack(int cur_sum, int start, int len) {
    // 凑够了一组，重新开始凑下一组
    if (cur_sum == len) {
        // 检查是否所有片段都被用完 → 满足条件，返回true
        for (bool u : used) {
            if (!u) {
                // 还有未使用的片段，继续凑下一组，从下标0开始
                return backtrack(0, 0, len);
            }
        }
        return true; // 全部用完，完美匹配
    }

// 剪枝1：当前凑的长度超过目标，直接返回false
    if (cur_sum > len) return false;

// 从start开始枚举，避免重复组合
    for (int i = start; i < n; ++i) {
        // 剪枝2：当前片段已被使用，跳过
        if (used[i]) continue;
        // 剪枝3：同值去重，相同长度的片段，上一个没选则当前也不选，避免重复递归
        if (i > start && nums[i] == nums[i-1] && !used[i-1]) continue;
        // 剪枝4：当前片段加入后超过目标，跳过（降序排序后，后面的更小，可提前退出）
        if (cur_sum + nums[i] > len) continue;

used[i] = true;
        if (backtrack(cur_sum + nums[i], i + 1, len)) {
            return true;
        }
        used[i] = false; // 回溯

// 剪枝5：如果当前是凑某一组的第一个元素，选这个数失败则直接返回
        if (cur_sum == 0) return false;
    }
    return false;
}

// 判断候选长度len是否是合法的标准长度
bool is_valid(int len) {
    if (total_sum % len != 0) return false; // 必须是总长度的约数
    fill(used.begin(), used.end(), false);  // 重置使用标记
    return backtrack(0, 0, len);
}

int main() {
    // 输入数据
    cin >> n;
    nums.resize(n);
    used.resize(n, false);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

// 计算总长度 + 找片段最大值
    total_sum = accumulate(nums.begin(), nums.end(), 0);
    int max_num = *max_element(nums.begin(), nums.end());

// 核心优化：降序排序，让大的数先被枚举，触发更多剪枝，提速关键
    sort(nums.rbegin(), nums.rend());

// 从小到大枚举候选长度，第一个满足条件的就是最小标准长度
    for (int L = max_num; L <= total_sum; ++L) {
        if (is_valid(L)) {
            cout << L << endl;
            return 0;
        }
    }

// 兜底：理论上不会走到这里，因为L=total_sum一定满足（所有片段凑成1篇）
    cout << total_sum << endl;
    return 0;
}
```