算法小计B2

发表于 | 分类于
字数统计: 3,086 | 阅读时长 ≈ 17

每天坚持做算法题，熟悉基本的套路，巩固语言基础，总结经验记下所学所想。

2018-04-16

P294 输出所有排列

HINT

递归调用

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 字典序输出1-n的全排列
void print_permutation(int n, int* A, int cur) {
    if(cur == n) { //递归边界
        for(int i = 0; i < n; i++) printf("%d ", A[i]);
        printf("\n");
    }
    else for(int i = 1; i <= n; i++) { //尝试在A[cur]中填各种整数i
        int ok = 1;
        for(int j = 0; j < cur; j++)
            if(A[j] == i) ok = 0; //如果i已经在A[0]~A[cur-1]出现过，则不能再选
        if(ok) {
            A[cur] = i;
            print_permutation(n, A, cur+1); //递归调用
        }
    }
}

// 输出集合P的全排列
void print_permutation(int n, int* A, int cur, int* P) {
    if(cur == n) { //递归边界
        for(int i = 0; i < n; i++) printf("%d ", A[i]);
        printf("\n");
    }
    else for(int i = 1; i <= n; i++) { //尝试在A[cur]中填P[i]
        int c1=0, c2=0;

        for(int k = 0; k < cur; ++k) if(A[k] == P[i]) ++c1;
        for(int k = 0; k < n; ++k) if(P[k] == P[i]) ++c2;

        if(c1<c2) {
            A[cur] = P[i];
            print_permutation(n, A, cur+1); //递归调用
        }
    }
}

2018-04-18

P298 子集生成

HINT

增量构造法、位向量法、二进制法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * 增量构造法,用到了定序的技巧：规定集合A中所有元素的编号从小到大排列，就不会把集合{1, 2}按照{1, 2}和{2, 1}输出两次了。
 * @param  {[type]} int  n             集合为0~n-1
 * @param  {[type]} int* A             存放子集，待打印
 * @param  {[type]} int  cur           当前元素
 */
void print_subset1(int n, int* A, int cur) {
    for(int i = 0; i < cur; i++) printf("%d ", A[i]); //打印当前集合
    printf("\n");
    int s = cur ? A[cur-1]+1 : 0; //确定当前元素的最小可能值
    for(int i = s; i < n; i++) {
        A[cur] = i;
        print_subset(n, A, cur+1); //递归构造子集
    }
}


/**
 * 位向量法
 * @param  {[type]} int  n             集合为0~n-1
 * @param  {[type]} int* B             存放子集，待打印
 * @param  {[type]} int  cur           当前元素
 */
void print_subset2(int n, int* B, int cur) {
    if(cur == n) {
        for(int i = 0; i < cur; i++)
            if(B[i]) printf("%d ", i); //打印当前集合
        printf("\n");
        return;
    }
    B[cur] = 1; //选第cur个元素
    print_subset(n, B, cur+1);
    B[cur] = 0; //不选第cur个元素
    print_subset(n, B, cur+1);
}

/**
 * 二进制法
 * @param  {[type]} int n             集合为0~n-1
 * @param  {[type]} int s             当前二进制数
 */
void print_subset3(int n, int s) { //打印{0, 1, 2,..., n-1}的子集S
    for(int i = 0; i < n; i++)
    if(s&(1<<i)) printf("%d ", i); //这里利用了C语言"非0值都为真"的规定
    printf("\n");
}

int main(){
    int n;
    cin>>n;
    int a[n];

    print_subset1(n, a, 0);
    cout<<endl;

    print_subset2(n, a, 0);
    cout<<endl;

    for(int i = 0; i < (1<<n); i++) //枚举各子集所对应的编码0, 1, 2,..., 2n-1
        print_subset3(n, i);
}

2018-04-19

八皇后问题

HINT

使用book数组判重

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int maxn = 100;
int book[3][maxn] = {0};
int C[maxn];
int tot = 0;
int n;

void search(int cur) {
    if(cur == n) tot++;
    else{
        for(int i = 0; i<n; ++i){
            if(!book[0][i]&&!book[1][cur+i]&&!book[2][cur-i+n]){
                C[cur] = i;
                book[0][i] = book[1][cur+i] = book[2][cur-i+n] = 1;
                search(cur+1);
                book[0][i] = book[1][cur+i] = book[2][cur-i+n] = 0;
            }
        }
    }
    return;
}

int main{
    cin>>n;
    search(0);
    cout<<"一共有"<<tot<<"种放置方法"<<endl;
    return 0;
}

P370 和为0的4个值

HINT

hash降低复杂度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int main(){

    int n;
    cin>>n;
    vector<vector<int>> vec(4,vector<int>(n, 0));

    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < n; ++j) {
            cin>>vec[i][j];
        }
    }

    unordered_map<int, int> mp;

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            int aplusb = vec[0][k] + vec[1][i];
            if (!mp.count(aplusb)) mp[aplusb] = 1;
            else mp[aplusb]++;
        }
    }
    int count = 0;

    for (int l = 0; l < n; ++l) {
        for (int i = 0; i < n; ++i) {
            int cplusd = -(vec[2][l] + vec[3][i]);
            if (mp.count(cplusd))
               count+=mp[cplusd];
        }
    }

    cout<<count<<endl;

}

P372 Gergovia的酒交易

HINT

扫描法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int main( ) {
    int n;
    while(cin >> n && n) {
        long long ans = 0, a, last = 0;
        for(int i = 0; i < n; i++) {
            cin >> a;
            ans += abs(last);
            last += a;
        }
        cout << ans << "\n";
    }
    return 0;
}

2018-04-21

两个有序数组求中位数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
// 双指针
int main(){

    int m,n;
    cin>>m>>n;
    int a[m], b[n];
    for (int i = 0; i < m; ++i) {
        cin>>a[i];
    }
    for (int j = 0; j < n; ++j) {
        cin>>b[j];
    }

    int i = 0,j = 0;
    int length = m+n;
    int count = 0;
    if((length&1) == 1) {
        int final = 0;
        while (i != m && j != n && count!= length/2+1) {

            if (a[i] > b[j]) {
                final = b[j];
                ++j;
            } else {
                final = a[i];
                ++i;
            }
            ++count;
        }

        if (count-1 == length/2){
            cout<<final;
        }else {
            if (i == m) {
                if (j == n) {
                    cout << "kong";
                } else {
                    cout << b[length / 2 - m];
                }
            } else if (j == n) {
                cout << a[length / 2 - n];
            }
        }
    }else {
        int second = 0;
        int first = 0;
        int count = 0;

        while (i != m && j != n && count- 1 != length / 2) {
            ++count;
            if (a[i] > b[j]) {
                if(count == length/2){
                    first = b[j];
                }
                second = b[j];
                ++j;
            } else {

                if(count == length/2) {
                    first = a[i];
                }
                second = a[i];
                ++i;
            }


        }

        if(count-1 == length/2) {
            cout << (first + second) / 2.0;
        }else {
            if (i == m) {
                if (j == n) {
                    cout << "kong";
                } else {
                    if (first){
                        cout<<(first+b[length/2 -m])/2.0;
                    } else {
                        cout << (b[length / 2 - m - 1] + b[length / 2 - m]) / 2.0;
                    }
                }
            } else if (j == n) {
                if (first) {
                    cout << (a[length / 2 - n] + first) / 2.0;
                } else {
                    cout << (a[length / 2 - n - 1] + a[length / 2 - n]) / 2.0;
                }
            }
        }
    }

    return 0;

}

2018-04-23

P381 全部相加

HINT

huffman编码的建立过程

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<queue>
using namespace std;

int main() {
    int n, x;
    while(scanf("%d", &n) == 1 && n) {
        priority_queue<int, vector<int>, greater<int> > q;
        for(int i = 0; i < n; i++) { scanf("%d", &x); q.push(x); }
        int ans = 0;
        for(int i = 0; i < n-1; i++) {
            int a = q.top( ); q.pop( );
            int b = q.top( ); q.pop( );
            ans += a+b;
            q.push(a+b);
        }
        printf("%d\n", ans);
    }
    return 0;
}

回忆：huffman编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void Huffman::HuffmanTree(element huffTree[ ], int w[ ], int n )
{     for (i=0; i<2*n-1; i++)
        {     huffTree [i].parent= -1;
               huffTree [i].lchild= -1;
               huffTree [i].rchild= -1;
         }
       for (i=0; i<n; i++)//0-n-1存放叶子节点
               huffTree [i].weight=w[i];
       for (k=n; k<2*n-1; k++)
        {
            int i1,i2;
            SelectMin( i1, i2，0，k-1);
              huffTree[i1].parent=k;
              huffTree[i2].parent=k;
              huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;
              huffTree[k].lchild=i1;
              huffTree[k].rchild=i2;
         }
}

// 从s到e中找到权值未被使用的两个最小值
void Huffman::SelectMin(int &x, int &y, int s, int e )
{
    int i;
    for ( i=s; i<=e;i++)
        if (HTree[i].parent == -1)
        {
        x =y= i; break; //找出第一个有效权值x，并令y=x
        }
    for ( ; i<e;i++)
        if (HTree[i].parent == -1) //该权值未使用过
        {
            if ( HTree[i].weight< HTree [x].weight)
            {
                y = x; x = i; //迭代，依次找出前两个最小值
            }
            else if ((x==y) || (HTree[i].weight< HTree [y].weight) )
                y = i; //找出第2个有效权值 y
        }
}

P406 记忆化搜索与递推

HINT

避免递归搜索时重复执行操作

代码

1
2
3
4
5
6
7
//思路
memset(d,－1,sizeof(d));

int solve(int i, int j){
    if(d[i][j] ＞= 0) return d[i][j];
    return d[i][j] = a[i][j] ＋ (i == n ? 0 : max(solve(i＋1,j),solve(i＋1,j＋1)));
}

2018-04-24

P265 给任务排序

HINT

dfs判断是否不存在环

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int c[maxn];
int topo[maxn], t;

bool dfs(int u){
    c[u] = -1;//正在访问

    // 判断是否存在环，如果有则返回false，如果出循环都没有则返回true
    for(int i = 0; i<n; ++i){
        if(G[u][i]){
            if(c[i] == -1) return false;
            else if(!c[i]&&!dfs(i)) return false;
        }
    }

    c[u] = 1;topo[--t] = u;
    return true;
}

bool toposort( ){
    t = n;
    memset(c, 0, sizeof(c));
    for(int u = 0; u < n; u++)
        if(!c[u])
            if(!dfs(u)) return false;
    return true;
}

2018-04-25

P266 欧拉回路

HINT

设置标记

代码

1
2
3
4
5
6
7
8
9
void elur(int cur){
    for(int i = 0; i<n; ++i){
        if(G[cur][i]&&!book[cur][i]){
            book[cur][i] = book[i][cur] = 1;
            elur(i);
            cout<<cur<<" "<<i;
        }
    }
}

2018-05-03

P416 城市里的间谍

HINT

DAG动态规划问题,时间是单向的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
int main(){

    int n;cin>>n;
    int T;cin>>T;
    int t[n];
    for(int i = 1; i<n; ++i)
        cin>>t[i];
    int M1;cin>>M1;
    int d1[M1+1];
    int max1 = 0;
    for (int i = 1; i<M1+1; ++i){
        cin>>d1[i];
        if(d1[i]>max1) max1 = d1[i];
    }
    int M2;cin>>M2;
    int d2[M1+1];
    int max2 = 0;
    for (int i = 1; i<M2+1; ++i){
        cin>>d2[i];
        if(d2[i]>max2) max2 = d2[i];
    }

    for(int i = max1; i>=0; --i){
        has_train[i][1][0] = 1;
    }
    for(int i = max2; i>=0; --i){
        has_train[i][n][1] = 1;
    }

    for(int i = 1; i<M1+1; ++i){
        int tt = d1[i];
        for(int j = 2; j <= n; ++j){
            tt += t[j-1];
            has_train[tt][j][0] = 1;
        }
    }

    for(int i = 1; i<M2+1; ++i){
        int tt = d2[i];
        for(int j = n-1 ; j >= 1; ++j){
            tt += t[j];
            has_train[tt][j][1] = 1;
        }
    }


    for(int i = 1; i <= n-1; i++) dp[T][i] = INF;

    dp[T][n] = 0;
    // 参考DAG专题，这里的时间流逝是1->T，所以外层是从T-1到0（是相反的）；
    for(int i = T-1; i >= 0; i--)
    for(int j = 1; j >= n; j++) {
        dp[i][j] = dp[i+1][j] + 1; //等待一个单位
        if(j < n && has_train[i][j][0] && i+t[j] ＜= T)
        dp[i][j] = min(dp[i][j], dp[i+t[j]][j+1]); //右
        if(j > 1 && has_train[i][j][1] && i+t[j-1] ＜= T)
        dp[i][j] = min(dp[i][j], dp[i+t[j-1]][j-1]); //左
    }
    //输出
    cout << "Case Number " << ++kase << ": ";
    if(dp[0][1] >= INF) cout << "impossible\n";
    else cout << dp[0][1] << "\n";
}

2018-05-04

P422背包问题

HINT

固定起点的DAG最长路径问题，引入层数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// d(i, j)表示“把第i, i＋ 1 , i＋2,…, n个物品装到容量为j的背包中的最大总重量”。
// 边界是i＞n时d(i,j)=0，j＜0时为负无穷
for(int i = n; i >= 1; i--)
    for(int j = 0; j <= C; j++){
        d[i][j] = (i==n ? 0 : d[i+1][j]);// 不放v[i]，直接进下一层
        if(j >= V[i]) d[i][j] max(d[i][j],d[i+1][j-V[i]]+W[i]);
    }

cout<<d[1][C];

// f[i][j]表示第i层(第i次装载动作，可选择是否装载v[i])总体积为j时背包的最大重量
// i=0时为0，j＜0时为负无穷
for(int i = 1; i <= n; i＋＋)
    for(int j = 0; j <= C; j＋＋){
        f[i][j] = (i==1 ? 0 : f[i-1][j]);// 在第i层不装载v[i]，直接进入前一层
        if(j >= V[i]) f[i][j] = max(f[i][j], f[i-1][j-V[i]]+W[i]);
    }

cout<<f[n][C];

// 与f一样，不需要记录v[i]了
for(int i = 1; i <= n; i++){
    scanf("%d%d", &V, &W);
    for(int j = 0; j <= C; j++){
        f[i][j] = (i==1 ? 0 : f[i-1][j]);
        if(j >= V) f[i][j] = max(f[i][j],f[i-1][j-V]+W);
    }
}

memset(f, 0, sizeof(f));
for(int i = 1; i <= n; i++){
    scanf("%d%d", &V, &W);
    for(int j = C; j >= 0; j——)
    if(j >= V) f[j] = max(f[j], = f[j－V]+W);
}

P420 单向TSP

HINT

多阶段决策的最优化问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main()
{
    const int INF = 1000;
    int ans = INF, first = 0;
    for(int j = n-1; j >= 0; j--) { //逆推
        for(int i = 0; i < m; i++) {
            if(j == n-1) d[i][j] = a[i][j]; //边界
            else {
                int rows[3] = {i, i-1, i+1};
                if(i == 0) rows[1] = m-1; //第0行"上面"是第m－1行
                if(i == m-1) rows[2] = 0; //第m－1行"下面"是第0行
                sort(rows, rows+3); //重新排序，以便找到字典序最小的
                d[i][j] = INF;
                for(int k = 0; k < 3; k++) {
                    int v = d[rows[k]][j+1] + a[i][j];
                    if(v < d[i][j]) { d[i][j] = v; next[i][j] = rows[k]; }
                }
            }
            if(j == 0 && d[i][j] < ans) { ans = d[i][j]; first = i; }
        }
    }
    printf("％d", first+1); //输出第1列
    for(int i = next[first][0], j = 1; j < n; i = next[i][j], j++)
        printf(" %d", i+1); //输出其他列
        printf("\n%d\n", ans);
    }
    return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:算法小计B2

文章作者:ChengXiao

发布时间:2018年04月17日 - 22:04

最后更新:2018年06月17日 - 11:06

原始链接:http://chengxiao19961022.github.io/2018/04/17/算法小计B2/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

你的鼓励是我前进的动力~