cses 進階題題解

Meet in the Middle

折半枚舉

// Author : ysh
// 02/24/2023 Fri 13:28:19.73
// https://cses.fi/problemset/task/1628
#include<bits/stdc++.h>
using namespace std;
#define int long long
void check(int l,int r,vector<int>&s,vector<int>&f,int sig) {
    if(l == r + 1) {
        s.push_back(sig);
        return;
    }
    check(l + 1,r,s,f,sig + f.at(l));
    check(l + 1,r,s,f,sig);
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a,b;cin>>a>>b;
    vector<int>f(a);
    for(int &i : f) cin>>i;
    int mid = a >> 1;
    vector<int>left,right;
    check(0,mid,left,f,0);
    check(mid + 1,a - 1,right,f,0);
    sort(left.begin(),left.end());
    sort(right.begin(),right.end());
    int ans = 0;
    for(int i : left) {
        ans = ans + ((int) (upper_bound(right.begin(),right.end(),b - i) - lower_bound(right.begin(),right.end(),b - i)));
    }
    cout<<ans;
    return 0;
}

tags: half-brute

Hamming Distance

位元運算

// Author : ysh
// 02/24/2023 Fri 19:44:35.71
// https://cses.fi/problemset/task/2136
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a,b;cin>>a>>b;
    bitset<31>s[a];
    for(int i = 0;i < a;i++) {
        string tmp;cin>>tmp;
        s[i] = bitset<31>(tmp);
    }
    int mmin = 32;
    for(int i = 0;i<a;i++) {
        for(int j = i + 1;j < a;j++) {
            bitset<31>tmp;
            tmp = s[i] ^ s[j];
            mmin = min((int) tmp.count(),mmin);
        }
    }
    cout<<mmin;
    return 0;
}

tags: bit

Beautiful Subgrids

還是位元運算
請用

#pragma GCC target("popcnt");

否則會$\color{cyan}TLE$

// Author : ysh
// 02/25/2023 Sat  6:37:38.90
// https://cses.fi/problemset/task/2137
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int check(int a) {
    return (a * (a - 1)) >> 1;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    bitset<3000>s[n];
    for(int i = 0;i<n;i++) {
        cin>>s[i];
    }
    int ans = 0;
    
    for(int i = 0;i<n;i++) {
        for(int j = i + 1;j < n;j++) {
            ans = ans + check((s[i] & s[j]).count());
        }
    }
    cout<<ans;
    return 0;
}

tags: bit

Reachable Nodes

// Author : ysh
// 02/25/2023 Sat  7:08:07.73
// https://cses.fi/problemset/task/2138
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define N 50000
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a,b;cin>>a>>b;
    vector<vector<int>>f(a);
    vector<int>to(a);
    bitset<N>s[a];
    for(int i = 0;i<b;i++) {
        int a,b;cin>>a>>b;
        a--;b--;
        swap(a,b);
        f.at(a).push_back(b);
        to.at(b)++;
    }
    
    for(int i = 0;i < a;i++) s[i].set(i);
    queue<int>q;
    for(int i = 0;i<a;i++) {
        if(to.at(i) == 0) q.push(i);
    }
    
    while(!q.empty()) {
        int now = q.front();q.pop();
        for(int i : f.at(now)) {
            s[i] = s[i] | s[now];
            if(--to.at(i) == 0) {
                q.push(i);
            }
        }
    }
    
    for(int i = 0;i<a;i++) {
        cout<<s[i].count()<<" ";
    }
    return 0;
}

tags: bit graph tapoo