PDD 8.25 笔试

难度：⭐️⭐️⭐️

考察：模拟，贪心

#pdd##笔试##题解#

第一题

关键词：贪心

关键点：树是无环图，每减少一条边，联通分量必然增加1，因此贪心策略是每次舍弃权值最小的边

int main() {
    int T, n;
    cin >> T;
    for(int uu = 0; uu < T; uu++) {
        cin >> n;
        vector<int> arr1(n);
        vector<int> arr2(n-1);
        // 读入联通分量得分
        for(int i = 0; i < n; i++) {
            cin >> arr1[i];
        }
        // 读入边权
        for(int i = 0; i < n - 1; i++) {
            int _1, _2;
            cin >> _1 >> _2;
            cin >> arr2[i];
        }
        // 按照边权从小到大排序，即从最小的边开始删除
        sort(arr2.begin(), arr2.end());
        arr2.emplace_back(0);
        // 预处理累加和信息，方便计算。
        for(int i = n - 2; i >= 0; i--) {
            arr2[i] += arr2[i+1];
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans = max(ans, arr1[i] + arr2[i]);
        }
        cout << ans << endl;
    }
}

如果溢出就用long long

第二题

关键词：贪心

关键点：如果存在奇数，那么一定是用奇数+偶数的操作，如果不存在，则先将最容易变成奇数的偶数变为奇数，再重复前面。

// 最少计算需要多少次操作1得到奇数
int f(int i) {
    int ans = 0;
    while((i & 1) == 0) {
        i >>= 1;
        ans++;
    }
    return ans;
}


int main() {
    int T, n;
    cin >> T;
    for(int uu = 0; uu < T; uu++) {
        cin >> n;
        int ans = 0;
        int min_operation = 0x3f3f;
        bool flag = false; // 是否存在奇数
        for(int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            min_operation = min(f(tmp), min_operation);
            if(tmp & 1) {
                flag = true;
            } else {
                ans++;
            }
        }
        if(flag) {
            cout << ans;
        } else {
            cout << ans - 1 + min_operation;
        }
        cout << endl;
    }
}

第三题

关键词：模拟

关键点：因为题目提供的操作只能让元素变大，而要求的最终数组非单调递减，所以一定是从后往前遍历，然后判断是否需要进行操作，如果需要操作（arr[i] < arr[i-1]），则判断能否操作（arr[i-1] <= x），如果可以则将操作次数累积到最终答案中，如果不能则返回-1。

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int cost = 0, ans = 0;
    bool flag = true;
    for(int i = n - 1; i > 0; i--) {
        if(arr[i] != arr[i-1] && arr[i] < x) {
            cost++;
        }
        if(arr[i] >= arr[i-1]) continue;
        if(arr[i-1] <= x) {
            ans += cost;
            cost = 0;
            x = arr[i];
        } else {
            flag = false;
            break;
        }
    }
    cout << (flag ? ans : -1) << endl;
}

第四题

关键词：贪心

关键点：可以证明，题目提供的操作可以实现循环移位的作用：ABC -> A|BC->A'|C'B'->A'C'|B'->CAB，所以猜测，当头尾符号一致的时候就是循环移位终止的时候（再操作也没收益了），尝试贪心一发，然后就A了。

int main() {
    int n;
    string s;
    cin >> n;
    cin >> s;
    s += s;
    int ans = 1;
    for(int i = 1, cur = 1; i < 2 * n; i++) {
        if(s[i] != s[i-1]) {
            cur++;
            ans = max(ans, cur);
        } else {
            cur = 1;
        }
    }
    cout << min(ans, n) << endl;
}