Atcoder ABC 393

compaq · 2025-02-17 09:03:58 · 题解

C - Make it Simple

给出N个点和M条边的无向图，最少需要删除多少边使得这个图成为简单图，即没有重边和自环。

遇到自环直接删除。
用map记录重边

#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, int>mp;
// mp [{u,v}] -> u到v的边有没有出现过
int main(){
    int n, m;
    cin >> n >> m;
    int ans = 0;

    for(int i = 1; i <= m; i++){
        int u, v;
        cin >> u >> v;
        //默认让小的点 连向大的点
        if(u > v) swap(u, v);
        if(u == v) ans++;
        else if(mp.count({u, v})) ans++;
        mp[{u, v}] = 1;
    }   
    cout << ans << endl;
    return 0;
}

D - Swap to Gather

先确定移动的位置，可以大胆猜一下，往哪个1去靠。显然往中间的1去靠，比边上的1会更优。类似中位数求最短距离一样。

把所有是1的位置都找出来，放入pos数组中，可以先求出中位数的位置mid。

对于第i个1，它贡献的答案为abs(pos[mid] - pos[i] - (mid - i))

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){

    int n;
    string s;
    cin >> n >> s;

    vector<int> pos;

    for(int i = 0; i < n; i++)
        if (s[i] == '1')
            pos.push_back(i);

    int cnt = pos.size();

    if (cnt <= 1){
        cout << 0 << endl;
        return 0;
    }

    int mid = cnt / 2, ans = 0;
    for (int i = 0; i < pos.size(); i++)
        ans += abs(pos[mid] - (mid - i) - pos[i]);

    cout << ans << endl;

    return 0;
}

解法2：

考虑对0的移动，对于第i位上的0，统计左侧1的个数为x，右侧1的个数为y。

最终的得到的字符串形状：0...01...10..0，前面0的数量可能是0个，后面0的数量可能是0个。

从左往右考虑`0',它对答案的贡献是min(x, y);

E - GCD of Subset

思路：考虑枚举最大公约数d ，再看 d 的倍数个数和 k 的关系，来决定 d 能不能作为答案。

做法：

枚举当前最大公约数d, 再枚举d的倍数，得到原数组中有约数的数量为cnt个。
若cnt >= k, 则说明一定能从原数组中选出k个数，使得他们的最大公约数至少为d，所以可以把所有d的倍数的答案更新为d
考虑完所有的d后，此时ans[i]就是数字i的最优答案。

例如样例1：

3 4 6 7 12

d$ == $1$时，则当前算出$ans[3] = ans[4] = ans[6] = ans[7] = ans[12] = 1

d$ == $2$时，更新$ans[4] = ans[6] = ans[12] = 2

d$ == $3$时，更新$ans[3] = ans[6] = ans[12] = 3

...

#include<bits/stdc++.h>
using namespace std;
const int N = 12e5 + 10;

int a[N], mp[N], ans[N];

signed main(){
    int n, k;
    cin >> n >> k;
    int lim = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        mp[a[i]]++;
        lim = max(lim, a[i]);
    }

    for(int d = 1; d <= lim; d++){
        int cnt = 0;
        for(int i = d; i <= lim; i += d)
            cnt += mp[i];

        if(cnt >= k){
            for(int i = d; i <= lim; i += d)
                ans[i] = d;
        }
    }   
    for(int i = 1; i <= n; i++)
        cout << ans[a[i]] << endl;                             
    return 0;
}

F - Prefix LIS Query

根据DP求LIS的思想，设 f[i] 为当前项时长度为 i 的LIS序列末项最小值，

由于 f[i] 具有递增性，每次二分查找在数组 f 中第一个大于等于 a[i] 的位置更新。

离线查询，每次在对应的r的位置，二分求在当前状态下数组f中最后一个不大于x的位置需要即为答案。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10, inf = 1e18;
int n, q, a[N], f[N];

struct node{
    int id, r, x, ans;
}qry[N];

bool cmp(node A, node B){
    return A.r < B.r;
}

bool cmp2(node A, node B){
    return A.id < B.id;
}

signed main(){
    scanf("%lld%lld", &n, &q);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for(int i = 1; i <= q; i++){
        int r, x;
        scanf("%lld%lld", &r, &x);
        qry[i] = {i, r, x, 0};
    }

    sort(qry + 1, qry + q + 1, cmp);

    for(int i = 1; i <= n; i++) f[i] = inf;

    f[0] = 0;
    for(int i = 1, j = 1; i <= n; i++){
        int k = lower_bound(f, f + n + 1, a[i]) - f;
        f[k] = min(f[k], a[i]);

        while(j <= q && qry[j].r == i){
            qry[j].ans = upper_bound(f, f + n + 1, qry[j].x) - f - 1;
            j++;
        }
    }

    sort(qry + 1, qry + q + 1, cmp2);

    for(int i = 1; i <= q; i++)
        printf("%lld\n", qry[i].ans);

    return 0;
}