2024牛客暑期多校训练营2

总结

成绩：SOLVE：3，Penalty：5

E

签到题

取 $x − lowbit(x)$ 即可，如果 $x$ 是 2 的整数次幂则无解

C

从左向右DP即可

void solve()
{
    int n;cin>>n;
    string a,b;
    cin>>a>>b;
    int ans=0;
    for(int i=0;i<n;i++){
        dp[0][i]=0;
        dp[1][i]=0;
    }
    a=' '+a;b=' '+b;
    for(int i=1;i<=n;i++){
         
        if(a[i]=='R'){
            dp[0][i]=dp[0][i-1]+1;
        }
        if(b[i]=='R'){
            dp[1][i]=dp[1][i-1]+1;
        }
        int x=dp[0][i],y=dp[1][i];
        if(a[i]=='R'){
            dp[0][i]=max(dp[0][i],y+1);
        }
        if(b[i]=='R'){
            dp[1][i]=max(dp[1][i],x+1);
        }
        ans=max({ans,dp[1][i],dp[0][i]});
    }
    if(ans==0){
        cout<<"0";
        return ;
    }
    cout<<ans-1<<'\n';
}

H

如果选择的左端点为1，那么利用前缀和记录每一个落点即可

对于左端点非1的点，我们可以转化问题，把1到左端点前面的操作加到终点上，等价于从左端点为1开始取

需要注意的是，这里因为经过了转化，我们需要保证选取的转化前的右端点在左端点的右边，才是合法。

因此，我们记录每一个位置，类似单调队列的思想，删去那些不合法的点即可

void SINGLE_TEST()
{
    int n,x,y;
    cin >> n >> x >> y;
    string s;
    cin >> s;
    map<PII, set<int>> mp;
    mp[{0,0}].insert(0);
    if(x==0&&y==0){
        cout<<n*(n+1)/2<<"\n";
        return;
    }
    int tx = 0, ty = 0;
    for (int i = 0; i < n; i++) {
        if(s[i]=='W'){
            ty++;
        }else if(s[i]=='A'){
            tx--;
        }else if(s[i]=='D'){
            tx++;
        }else{
            ty--;
        }
        mp[{tx,ty}].insert(i+1);
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if(i!=0){
            if(s[i-1]=='W'){
                y++;
            }else if(s[i-1]=='A'){
                x--;
            }else if(s[i-1]=='D'){
                x++;
            }else{
                y--;
            }
        }      
        if(!mp.count({x,y})){
            continue;
        }
        while(!mp[{x,y}].empty()&&*mp[{x,y}].begin()<i){
            mp[{x,y}].erase(*mp[{x,y}].begin());
        }
        if (mp[{x, y}].size()) {
            ans += n-*mp[{x,y}].begin()+1;
        }
    }
    cout << ans << "\n";
}

B

使用Kruskal解决，关键在于边怎么取

考虑到$\sum k\leqslant10^5$

对于点集个数$\geqslant \sqrt{10^5}$,那么边的条数在最坏的情况下有可能到达$10^5$，那我们不妨直接遍历所有的边

这里可以得出一个结论，因为$k$的总数固定，那么点集个数$\geqslant \sqrt{10^5}$的情况一定不会出现很多，具体的，是$\sqrt{10^5}$次，时间复杂度为$O(n\sqrt{n})$

对于点集个数$< \sqrt{10^5}$,这样的情况可能会出现很多，而且边的个数显然并不会占总的边的个数的大部分，因此，我们不妨用$O(k^2)$处理出所有的边，时间复杂度为$\sum k^2\times \frac{q}{k}=\sum kq$最坏的情况下时间复杂度为$O(n\sqrt{n})$

因此，加上并行的Kruskal，总时间复杂度为$O(n\sqrt{n}+mlogm)$

unordered_map<int, int> mp[N];
void SINGLE_TEST() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < m; i++) {
        cin >> edges[i][1] >> edges[i][2] >> edges[i][0];
        edges[i][1]--;
        edges[i][2]--;
        if (edges[i][1] > edges[i][2]) swap(edges[i][1], edges[i][2]);
    }
    sort(edges, edges + m);
    for (int i = 0; i < m; i++) {
        if (!mp[edges[i][1]].count(edges[i][2])) {
            mp[edges[i][1]][edges[i][2]] = i;
        }
    }
    DSU dsu(n);
    for (int i = 0; i < n; i++) d[i] = INF;
    while (q--) {
        int k;
        cin >> k;
        vector<int> v(k);
        for (int i = 0; i < k; i++) {
            cin >> v[i];
            v[i]--;
            ex[v[i]] = 1;
        }
        ll ans = 0;
        int cnt = 0;
        if (k <= 300) {
            sort(v.begin(), v.end());
            vector<int> tmp;
            for (auto v1 : v) {
                int t = -1;
                for (auto v2 : v) {
                    if (mp[v1].count(v2)) {
                        tmp.push_back(mp[v1][v2]);
                    }
                }
            }
            sort(tmp.begin(), tmp.end());
            for (auto i : tmp) {
                if (dsu.merge(edges[i][1], edges[i][2])) {
                    ans += edges[i][0];
                    cnt++;
                }
            }
        } else {
            for (int i = 0; i < m; i++) {
                if (ex[edges[i][1]] && ex[edges[i][2]]) {
                    if (dsu.merge(edges[i][1], edges[i][2])) {
                        ans += edges[i][0];
                        cnt++;
                    }
                }
            }
        }
        if (cnt < k - 1) ans = -1;
        cout << ans << "\n";
        for (auto v1 : v) {
            dsu.f[v1] = v1;
            dsu.siz[v1] = 1;
            ex[v1] = 0;
        }
    }
}