《算法竞赛进阶指南》0x01 ~ 0x02 代码 + 杂谈

0x01 位运算

位运算符

第 i 位为从右往左从0开始数
如果要设置 n 的第 i 位为1，n=（n|（1<<i）；                              
如果要设置 n 的第 i 位为0，n=（n &（~（1<<i））；

& 按位与
如果两个相应的二进制位都为1，则该位的结果值为1，否则为0
| 按位或
两个相应的二进制位中只要有一个为1，该位的结果值为1
^  按位异或
若参加运算的两个二进制位值相同则为0，否则为1
~ 取反
~是一元运算符，用来对一个二进制数按位取\反，即将0变1，将1变0
<< 左移
用来将一个数的各二进制位全部左移N位，右补0

>> 右移 
将一个数的各二进制位右移N位，移到右端 的低位被舍弃，对于无符号数，高位补0

补码
一个负整数（或原码）与其补数（或补码）相加，和为模。(C < 0);
-C + S = INT_MAX;
~n = -1 - n;

a^b

#include <iostream>
using namespace std;
typedef long long ll;

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

int main(){
    ll a, b, p;
    cin >> a >> b >> p;
    cout << q_mod(a, b, p) << endl;
    return 0;
}

64位整数乘法(快速乘带mod)

#include <iostream>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

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

int main(){
    ll a, b, p;
    cin >> a >> b >> p;
    cout << mul(a, b, p) << endl;
    return 0;
}

以上都是利用 b的二进制有1的才有乘法和加法意义所做的

lowbit
lowbIt(x) = (-x) & x; 获得最低位的 1 ;

最短 hamilton 路径
状压DP 居然第一节就有了 orz

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 20 + 5;
int mp[maxn][maxn];
int dp[(1 << 20) + 5][maxn];

int main(){
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ ) 
        cin >> mp[i][j];
        // for(int k=1;k<=n;k++){
        // for(int i=1;i<=n;i++){
        // for(int j=1;j<=n;j++){
        // if(mp[i][j]>mp[i][k]+mp[k][j]) mp[i][j]=mp[i][k]+mp[k][j];
        // }
        // }
        // } 数据保证最短路 不然跑floyd先 
    memset(dp, 0x3f, sizeof dp);
    //for(int i = 0; i <=n ; i ++ ) dp[1 << i][i] = 0; // 任意开始最短路径
    dp[1][0] = 0;
    for(int s = 1; s < (1 << n); s ++ ) {
        for(int i = 0; i < n; i ++ ) {
            if( !(s & (1 << i)) ) continue; // 借助这个城市
            for(int j = 0; j < n; j ++ ) {
                if(s & (1 << j)) continue; // 要去这个城市
                dp[s | (1 << j)][j] = min(dp[s | (1 << j)][j], dp[s][i] + mp[i + 1][j + 1]);
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1] << endl;
    return 0;
}

0x02递推与递归

枚举: 排列组合 (多项式级和指数级别, 递归、循环剪支);

递归实现指数型枚举

#include <iostream>
using namespace std;

const int maxn = 20;
int ans[maxn], hh, tt;
int n;

void dfs(int num){
    if(num == n + 1) {
        for(int i = hh; i < tt; i ++ ) {
            cout << ans[i] << " ";
        }cout << endl;
        return;
    }
    dfs(num + 1);
    ans[tt] = num;
    tt ++;
    dfs(num + 1);
    tt --;
}

int main(){
    cin >> n;
    hh = 1, tt = 1;
    dfs(1);
    return 0;
}

递归实现组合型枚举
注意剪枝

#include <iostream>
using namespace std;

const int maxn = 30;
int ans[maxn], hh, tt;
int n, m;

void dfs(int num){
    if(tt > m + 1|| tt + (n - num) < m)
        return;
    if(tt == m + 1) {
        for(int i = 1; i < tt; i ++ ){
            cout << ans[i] << " ";
        }cout << endl;
        return ;
    }
    ans[tt] = num;
    tt ++;
    dfs(num + 1);
    tt --;
    dfs(num + 1);
}

int main(){
    cin >> n >> m;
    hh = 1, tt = 1;
    dfs(1);
    return 0;
}

递归实现排列枚举型

#include <iostream>
using namespace std;

const int maxn = 15;
bool vis[maxn];
int ans[maxn], hh, tt;
int n, m;

void dfs(int num){
    if(num == n + 1) {
        for(int i = 1; i < tt; i ++ ) {
            cout << ans[i] << " ";
        }cout << endl;
        return ;
    }
    for(int i = 1; i <= n; i ++ ) {
        if(vis[i]) continue;
        ans[tt] = i;
        tt ++;
        vis[i] = 1;
        dfs(num + 1);
        tt -- ;
        vis[i] = 0;
    }
}

int main(){
    cin >> n;
    hh = 1, tt = 1;
    dfs(1);
    return 0;
}

例题:
费解的开关
每一点只影响上下左右
不妨枚举第一次方案这样之后每一层都必须根据上一层来处理翻不翻
最后判断最后一层是否可行就行

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 10;
int a[maxn][maxn], b[maxn][maxn];
int n, ans;

int solve(int k){
    int res = 0;
    for(int i = 2; i <= n; i ++ ) {
        for(int j = 1; j <= n; j ++ ) {
            if((a[i - 1][j] + b[i - 1][j] + b[i - 1][j - 1] + b[i - 1][j + 1] + b[i - 2][j]) & 1) {
                res ++;
                b[i][j] = 1;
            }else {
                b[i][j] = 0;
            }
        }
        if(res + k > 6) return 0x3f3f3f3f;
    }
    
    for(int j = 1; j <= n; j ++ ) {
        if((a[n][j] + b[n][j] + b[n][j - 1] + b[n][j + 1] + b[n - 1][j]) & 1) {
            return 0x3f3f3f3f;
        }
    }
    return res;
}

void dfs(int num, int k) {
    if(num == n + 1) {
        ans = min(solve(k) + k, ans);
        return ;
    }
    b[1][num] = 0;
    dfs(num + 1, k);
    b[1][num] = 1;
    dfs(num + 1, k + 1);
}

int main(){
    int cas ;
    cin >> cas;
    n = 5;
    while(cas --) {
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        string line;
        for(int i = 1; i <= 5; i++ ) {
            cin >> line;
            for(int j = 1; j <= 5; j++ ) {
                if(line[j - 1] == '0') a[i][j] = 1;
            }
        }
        ans = 0x3f3f3f3f;
        dfs(1, 0);
        if(ans > 6) cout << -1 << endl;
        else cout << ans << endl;
    }
    return 0;
}

多汉诺塔问题

首先考虑n个盘子3塔的经典Hanoi问题，设dn表示求解n个盘子3塔问题的最少步数，显然有 dn=2∗dn−1+1

含义为把前n−1个盘子从A借助C转移到B，再将第n个盘子转移到C，最后把n−1个盘子从B借助A转移到C。

类似地，对于本题，设f[n]表示求解n个盘子4塔问题的最小步数，则有 fn=min(2∗fi+dn−i)(1≤i<n)

含义为把前i个盘子在4柱的情况下从A转移到B，再将n−i个盘子在3柱的情况下从A转移到D，最后再将i个盘子在4柱的情况下从B转移到D 　　
那么对于n盘m塔的问题(m>4)，就有 fn,m=min(2∗fi,m+fn−i,m−1)(1≤i<n)
使得我们可以在O(n^2∗m)的复杂度内求解该问题

#include <iostream>
using namespace std;

const int maxn = 25 + 5 ;
int n, m;

int dp[20], d[20];

signed main() {
    d[1] = 1;
    for(int i = 2; i <= 15; i++) {
        d[i] = d[i - 1] * 2 + 1;
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[1] = 1;
    for(int i = 2; i <= 15; i++) {
        for(int j = 1; j < i; j++) {
            dp[i] = min(dp[i], d[i - j] + dp[j] * 2);
        } // 2 * 4塔模式 + 1 * 3塔模式
    }
    for(int i = 1; i <= 12; i++) {
        cout << dp[i] << endl;
    }
    return 0;
}

约数之和 这题不仅分治可以做… 矩阵快速幂还有后面的数论一个解法好像也提到过
这里先先补上书上的解法

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int mod = 9901;
const int maxn = 105;
int n, m;
int p[maxn], c[maxn], cnt;

void divide(int n) {
    cnt = 0;
    for(int i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) {
            p[++cnt] = i, c[cnt] = 0;
            while(n % i == 0)
                n /= i, c[cnt]++;
        }
    }
    if(n > 1)
        p[++cnt] = n, c[cnt] = 1;
}

int q_mod(int a, int b) {
    int res = 1;
    while(b){
        if(b & 1) res = 1ll*  res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}

int dfs(int pt, int ct) {
    if(ct == 0) return 1;
    if(ct % 2 == 1)
        return ((1ll + q_mod(pt, (ct + 1) / 2)) * dfs(pt, (ct - 1) / 2)) % mod;
    else
        return ((1ll + q_mod(pt, ct / 2)) * dfs(pt, (ct / 2) - 1) % mod + q_mod(pt, ct)) % mod;
}

int main(){
    cin >> n >> m;
    divide(n);
    int ans = 1 ;
    if(n == 0) ans = 0;
    for(int i = 1; i <= cnt ; i ++ ) {
        ans *= dfs(p[i], c[i] * m);
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}