《算法竞赛进阶指南》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;
}

分形之城
补充这个

ps : 坐标旋转公式
(x, y) 旋转 b 度 (逆时针)
s = x cos(b) – y sin(b)
t = x sin(b) + y cos(b)

坐标轴旋转