算法竞赛进阶指南-0x01基本算法-位运算

a^b 快速幂

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll a, b, p;

ll qpow(ll a, ll b, ll p){
    ll ans = 1ll % p;
    while(b){
        if(b & 1)   ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

int main(){
    __;
    cin >> a >> b >> p;
    ll ans = qpow(a, b, p);
    cout << ans << endl;
    return 0;
}

64位整数乘法

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll a, b, p;

ll qmul(ll a, ll b, ll p){
    ll ans = 0ll;
    while(b){
        if(b & 1)   ans = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ans;
}

int main(){
    __;
    cin >> a >> b >> p;
    ll ans = qmul(a, b, p);
    cout << ans << endl;
    return 0;
}

最短Hamilton路径

题意:0n−1 不重不漏地经过每个点恰好一次的最短路径。

Solution: 状压DP
F[i][j] 表示:所有从 0 走到 j ,走过的所有点的情况是 i 的所有路径。
F[i][j] = min(F[i][j], F[i - (1 << j)][k] + w[k][j])

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n;
int w[21][21];
int f[1 << 21][21];

int main(){
    __;
    cin >> n;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            cin >> w[i][j];
        }
    }
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    for(int i = 0; i < 1 << n; i ++){//i表示所有的情况
        for(int j = 0; j < n; j ++){//j表示走到哪一个点
            if(i >> j & 1){
                for(int k = 0; k < n; k ++){//k表示走到j这个点之前,以k为终点的最短距离
                    if(i >> k & 1) {
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                    }
                }
            }
        }
    }
    printf("%d\n", f[(1 << n) - 1][n - 1]);
    return 0;
}

起床困难综合症

题意: 从[0,m]中选择一个整数x,经过给定的n次位运算,是的结果ans最大。

Solution: 由于题目中只有与、或、异或三种不进位的位运算,所以直接枚举每一位填0还是1。
那么我们先设两个量,一个初始化每一位都是1,一个初始化每一位都是0,然后模拟运算。运算到最后我们可以得到每一位上如果开始是1和如果开始是0的最后情况。
之后就是贪心,我们要让答案中出现的1越多越好。所以如果开始是0最后变成了1,一定是需要选取的。
如果开始是1最后变成了0,或者开始是0结果还是0这种无意义情况,都不选。
如果开始是1最后变成了1,只要加上该位后又小于等于m就可以填1。

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)


bitset<31> one, zero;
int n, m, x;
string s;

int main(){
    __;
    cin >> n >> m;
    one.set();
    zero.reset();
    while(n --){
        cin >> s >> x;
        if(s == "AND"){
            one &= x;
            zero &= x;
        }
        else if(s == "OR"){
            one |= x;
            zero |= x;
        }
        else{
            one ^= x;
            zero ^= x;
        }
    }
    int ans = 0;
    for(int i = 0; i < 31; i ++){
        if(zero[i] == 1){
            ans += (1 << i);
        }
        else if(one[i] == 1 && (1 << i) + ans <= m){
            ans += (1 << i);
        }
    }
    printf("%d\n", ans);
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注