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

树与图的遍历

1. 可达性统计
给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。
数据 1≤N,M≤30000 这里folyd 跑 不仅数组开不下 还有n^3的复杂度chun
关于 这个点每个状态的用矩阵肯定存不下这些关系 所以可以考虑用int 二进制来进行压缩
还有bitset STL 进行非常长长度二进制存储和运算
可达性就可以考虑 topsort了 找到循序序列 之后 倒着来吧每个点 或 一下 就 吧可达点 付到上一个 完成统计

#include 
#include 
#include 
using namespace std;
const int maxn = 3e4 + 5;

int n, m;
int head[maxn], cnt;
int to[maxn << 1], nxt[maxn << 1];
int deg[maxn], seq[maxn], k;
bitset f[maxn];

void ade(int a, int b){
    to[++ cnt] = b;
    nxt[cnt] = head[a];
    head[a] = cnt;
}

void topsort(){
    queue q;
    for(int i = 1; i <= n; i ++ ) 
        if(deg[i] == 0) q.push(i);
    while(!q.empty()){
        int x = q.front(); q.pop();
        seq[++ k] = x;
        for(int i = head[x]; i; i = nxt[i]) {
            int y = to[i];
            if(-- deg[y] == 0) q.push(y);
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1, a, b; i <= m; i ++ ) {
        cin >> a >> b;
        ade(a, b);
        deg[b] ++;
    }
    topsort();
    for(int i = n; i >= 1; i --) {
        int x = seq[i];
        f[x][x] = 1;
        for(int j = head[x]; j; j = nxt[j]) 
            f[x] |= f[to[j]];
    }
    for(int i = 1; i <= n; i ++) cout << f[i].count() << endl;
    return 0;
}

DFS

1. 小猫爬山
dfs 优化剪枝
首先 我们dfs 每次搜遍历一边考虑能装下 放入猫
这一操作完后 还原 进行不放入这个猫 加 一辆车的搜索

考虑优化 第一 我们排序每次选最大的 可以使开头第一搜索的选择性减低
显然 我们也可以加入 如果当前搜索车数量 大于min （n, ans） 直接return 放弃这个不好的解

#include 
#include 
using namespace std;
const int maxn = 100;
int n, m, ans;
int car[maxn], cat[maxn];

void dfs(int num, int cnt){
    if(cnt >= ans) return ;
    if(num == n  + 1) {
        ans = cnt;
        return ;
    }
    for(int i = 1; i <= cnt; i ++) {
        if(car[i] + cat[num] <= m) {
            car[i] += cat[num];
            dfs(num + 1, cnt);
            car[i] -= cat[num];
        }
    }
    car[cnt + 1] = cat[num];
    dfs(num + 1, cnt + 1);
    car[cnt + 1] = 0;
}

bool cmp(int a, int b) {return a > b;}

int main(){
    cin >> n >> m;
    for(int i = 1; i > cat[i];
    sort(cat + 1, cat + 1 + n, cmp);
    ans = n;
    dfs(1, 0);
    cout << ans << endl;
    return 0;
}

2. Sudoko (acwing数据)
这个题数据好强啊 不预处理位运算超时的
首先考虑 选择可选位置最少的框填入搜索
其次这题必须加入位运算 行列宫 9位2进制表示出来 lowbit 取出最低位 遍历可选值
位元算 记得还原全部状态再进行下次搜索

#include 
using namespace std;

const int N = 9;
int row[N], col[N];
int ones[1 << N], map[1 << N];
int g[5][5];
char str[105];

inline int lowbit(int x) {
    return x & -x;
}

inline int get(int x, int y) {
    return row[x] & col[y] & g[x/3][y/3];
}

bool dfs(int cnt) {
    if(cnt == 0) return 1;

    int minv = 10, x, y;
    for(int i = 0 ; i < N; i ++) for(int j = 0; j < N; j ++) 
        if(str[i * 9 + j] == '.') {
            int t = ones[get(i, j)];
            if(t < minv) minv = t, x = i, y = j;
        }
    for(int i = get(x, y); i; i -= lowbit(i)) {
        int t = map[lowbit(i)];
        row[x] -= 1 << t;
        col[y] -= 1 << t;
        g[x/3][y/3] -= 1 << t;
        str[x * 9 + y] = '1' + t;

        if(dfs(cnt - 1)) return 1;

        row[x] += 1 << t;
        col[y] += 1 << t;
        g[x/3][y/3] += 1 << t;
        str[x * 9 + y] = '.';

    }
    return 0;
}

void init(){
    for(int i = 0; i < 9; i ++) row[i] = col[i] = (1 << 9) - 1;
    for(int i = 0; i < 3; i ++) 
        for(int j = 0; j < 3; j ++) 
            g[i][j] = (1 << 9) - 1; 
}

int main(){
    for(int i = 0; i < N; i ++) map[1 << i] = i;
    for(int i = 0; i < 1 << N; i ++) {
        int s = 0;
        for(int j = i; j; j -= lowbit(j)) s ++;
        ones[i] = s;
    }

    while(cin >> str && str[0] != 'e') {
        init();
        int cnt = 0;
        for(int i =0, k = 0; i < N; i ++) 
            for(int j = 0; j < N; j ++, k ++ ) 
                if(str[k] != '.') {
                    int t = str[k] - '1';
                    row[i] -= 1 << t;
                    col[j] -= 1 << t;
                    g[i/3][j/3] -= 1 << t;
                }else cnt ++;

        dfs(cnt); 
        cout << str << endl;
    }
    return 0;
}

优化搜索

1. 小木棍
预先处理出所有木棍的总长度，且保证枚举答案的值能被总长度整除。
预先处理出最长的和最短的木棍的长度，搜索时从最大长度到最小长度递减枚举。
若拼接当前木棍时已用了一根长为X的木棍，则dfs时从长度X开始搜索。
若某组拼接不成立 且此时 已拼接的长度为0 或 当前已拼接的长度与刚才枚举的长度之和为最终枚举的答案
则可直接跳出循环，因为此时继续枚举其它更小的值时，显然可能情况更少，且同样凑不完。

#include 
#include 
#include 
using namespace std;
const int maxn = 50+5;

int n,m,x,sum,xz,flag,cnt;
bool cmp(int x,int y) {return x>y;}
bool vis[maxn];
int a[maxn];

void dfs(int len,int k,int lenth,int pos){
    if(flag) return ;
    if(k*lenth==sum){
        cout<<lenth<<endl;
        flag=1;
        return ;
    }
    if(sum-len<a[cnt]) return ;
    if(len==lenth){
        dfs(0,k+1,lenth,1);
        return ;
    }
    for(int i=pos;i<=cnt;i++){
        if(!vis[i]&&len+a[i]<=lenth){
            vis[i]=1;
            dfs(len+a[i],k,lenth,i+1);
            vis[i]=0;
            if(len==0||len+a[i]==lenth) break;
            while(a[i]==a[i+1])i++;
        }
    }
}

int main() { 
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m;
        if(m<=50){
            a[++cnt]=m;
            sum+=m;
        } 
    }
    sort(a+1,a+1+cnt,cmp);
    xz=sum>>1;
    for(int i=a[1];i<=xz;i++){
        if(sum%i==0){
            dfs(0,0,i,1);
            if(flag) break;
        }
    }
    if(!flag) cout<<sum<<endl;
    return 0;
}

acwing （重写版）

#include 
#include 
using namespace std;
const int maxn = 100 + 5;
const int mod = 1e9 + 7;

int n, sum, len;
int a[maxn], cnt;
bool vis[maxn];

bool cmp(int a, int b) {
    return a > b;
}

bool dfs(int k, int len, int p, int lenth){
    if(k * lenth == sum) return 1;
    if(len == lenth) return dfs(k + 1, 0, 1, lenth);
    for(int i = p; i <= cnt; i++){
        if(!vis[i] && len + a[i] <= lenth){
            vis[i] = 1;
            if(dfs(k, len + a[i], i + 1, lenth)) return 1;
            vis[i] = 0;
            if(len == 0) return 0;
            if(len + a[i] == lenth) return 0;
            while(a[i] == a[i + 1] && i <= cnt) i++;
        }
    }
    return 0;
}

signed main() {
    while(cin >> n && n) {
        cnt = 0;
        len = 0;
        sum = 0;
        for(int i = 1, l; i <= n; i ++) {
            vis[i] = 0;
            cin >> l;
            if(l > 50) continue;
            sum += l;
            a[++ cnt] = l;
            len = max (len, l);
        }
        sort(a + 1, a + cnt, cmp);
        for(int i = len; i <= sum; i ++)
            if(sum % i == 0 && dfs(0, 0, 1, i)) {
                cout << i << endl;
                break;
            }
    } 
    return 0;
}

2. 奶油蛋糕
体积一定 让多层蛋糕表面积最小
最小体积+面积预处理 搜索超过限制return
从 上一层 最大r - 1，h - 1 开始搜索 情况树少
s + 2 * (n - v) / R[dep + 1] >= ans 放缩出来的公式 。。果然只加一层超了 再加也超

#include 
#include 
using namespace std;
const int maxn = 100 + 5;
const int mod = 1e9 + 7;

int n, m, ans;
int R[maxn], H[maxn]; 
int mins[maxn], minv[maxn];

void dfs(int dep, int v, int s){
    if(minv[dep] + v > n) return ;
    if(mins[dep] + s >= ans) return ;
    if(s + 2 * (n - v) / R[dep + 1] >= ans) return ;

    if(dep == 0) {
        if(v == n) ans = min(ans, s);
        return ;
    }

    for(int r = min((int)sqrt(n - v), R[dep + 1] - 1); r >= dep; r --) {
        for(int h = min((n - v) / r / r, H[dep + 1] - 1); h >= dep; h --) {
            R[dep] = r, H[dep] = h;
            dfs(dep - 1, v + r * r * h, s + 2 * r * h + (dep == m ? r * r : 0));
        }
    }
    return ;
}

signed main() {
    cin >> n >> m;
    for(int i = 1; i <= 25; i ++) {
        minv[i] = minv[i - 1] + i * i * i;
        mins[i] = mins[i - 1] + i * i * 2; 
    }
    R[m + 1] = H[m + 1] = 0x3f3f3f3f;
    ans = 0x3f3f3f3f;
    dfs(m, 0, 0);
    cout << ans << endl;
    return 0;
}

迭代加深

1. 加成序列
预先设置深度， 搜索再树浅位置解

#include 
using namespace std;
const int maxn = 105;

int n;
int path[maxn];

bool dfs(int u, int k){
    if (u == k) return path[u - 1] == n;
    bool vis[maxn] = {0};
    for (int i = u - 1; i >= 0; i -- )
        for (int j = i; j >= 0; j -- ){
            int s = path[i] + path[j];
            if (s > n || s <= path[u - 1] || vis[s]) continue;
            vis[s] = true;
            path[u] = s;
            if (dfs(u + 1, k)) return true;
        }
    return false;
}

int main(){
    path[0] = 1;
    while (cin >> n, n){
        int k = 1;
        while (!dfs(1, k)) k ++ ;
        for (int i = 0; i < k; i ++ ) cout << path[i] << ' ';
        cout << endl;
    }
    return 0;
}

双向搜索

2. 送礼物
先优化搜索顺序
其次 先搜前一半 dfs出所有情况
再dfs后面n个 这样二分查可能最大值 不用在意dp数据量太。。。。orz

#include 
#include 
using namespace std;
typedef long long ll;
const int maxn = 105;

int n, m, ans, k;
int w[maxn];
int wes[1 << 24], cnt;

void dfs1(int u, int s) {
    if(u == k) {
        wes[cnt ++] = s;
        return ;
    }
    if((ll)s + w[u] <= m) dfs1(u + 1, s + w[u]);
    dfs1(u + 1, s);
}

void dfs2(int u, int s) {
    if(u == n) {
        int l = 0, r = cnt - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if((ll)wes[mid] + s <= m) l = mid;
            else r = mid - 1;
        }
        if((ll)wes[l] + s <= m) ans = max(ans, wes[l] + s);
        return ;
    }
    if((ll)s + w[u] <= m) dfs2(u + 1, s + w[u]);
    dfs2(u + 1, s);
}

bool cmp(int a, int b) {return a > b;}

int main(){
    cin >> m >> n;
    for(int i = 0; i > w[i];
    sort(w, w + n, cmp);
    k = n/2 + 2;
    dfs1(0, 0);

    sort(wes, wes + cnt);
    cnt = unique(wes, wes + cnt) - wes;
    dfs2(k, 0);
    cout << ans << endl;
    return 0;
}