Chengrui's Blog

0%

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出Hanoi塔的圆盘数\(n\)和已经移动的步数\(m\)，输出三个根柱子上圆盘的个数。当\(n\)为偶数时，目标柱子为第三根；\(n\)为奇数时，为第二根。

思路

从\(n\)到1以此判断每个盘子的位置，若操作次数不小于\(2^{n-1}\)，则当前盘子已经搬到目标位置，都则留在原地。

代码

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
//package main;

import java.util.*;
import java.math.*;

public class Main {

    static int[] ans = new int[3];
    static BigInteger[] e = new BigInteger[110];

    public static void dfs(int s, int tmp, int t, int n, BigInteger m) {
        if (n == 0) {
            return;
        }
        if (m.compareTo(e[n - 1]) != -1) {
            ++ans[t];
            dfs(tmp, s, t, n - 1, m.subtract(e[n - 1]));
        }
        else {
            ++ans[s];
            dfs(s, t, tmp, n - 1, m);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        e[0] = BigInteger.ONE;
        for (int i = 1; i < 110; ++i) {
            e[i] = e[i - 1].multiply(BigInteger.valueOf(2));
        }
        while (sc.hasNext()) {
            int n = sc.nextInt();
            BigInteger m = sc.nextBigInteger();
            if (n == 0 && m.compareTo(BigInteger.ZERO) == 0) {
                break;
            }
            ans[0] = ans[1] = ans[2] = 0;
            if (n % 2 == 0) {
                dfs(0, 1, 2, n, m);
            }
            else {
                dfs(0, 2, 1, n, m);
            }
            System.out.println(ans[0] + " " + ans[1] + " " + ans[2]);
        }
    }
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

有\(s_1,s_2,n\)三个整数，每个整数的各个位上的数字都不相同，且满足\(s_1/s_2=n\)。给出\(n\)，输出满足条件的算式。

思路 ：枚举\(s_2\)，计算出\(s_1\)，然后检验是否满足条件。

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const LL maxn = 9876543210;
bool vis[10];

bool check(LL x) {
    memset(vis, 0, sizeof vis);
    while (x) {
        int tmp = x % 10;
        if (vis[tmp]) {
            return false;
        }
        vis[tmp] = true;
        x /= 10;
    }
    return true;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        LL n;
        scanf("%lld", &n);
        for (LL i = 1, x = n; x <= maxn; ++i, x += n) {
            if (check(i) && check(x)) {
                printf("%lld / %lld = %lld\n", x, i, n);
            }
        }
        if (t) {
            puts("");
        }
    }
    return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

有\(1 \times 1、2 \times 2、3 \times 3、4 \times 4、5 \times 5、6 \times 6\)的盒子，输出把它们放到\(6 \times 6\)的盒子中最少需要的盒子的个数。

思路

优先考虑大的盒子，\(3 \times 3、4 \times 4、5 \times 5、6 \times 6\)的盒子不能与更大的放在一起，可以直接计算，\(5 \times 5\)的可以和11个\(1 \times 1\)的放在一起，\(4 \times 4\)的可以和5个\(2 \times 2\)，\(3 \times 3\)的分多钟情况考虑，最后将多出来的\(2 \times 2\)转化为\(1 \times 1\)的即可。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int c[4][2] = {{0, 0}, {5, 7}, {3, 6}, {1, 5}};
int a[7];

int main() {
    while (~scanf("%d%d%d%d%d%d", &a[1], &a[2], &a[3], &a[4], &a[5], &a[6])) {
        if (!a[1] && !a[2] && !a[3] && !a[4] && !a[5] && !a[6]) {
            break;
        }
        int ans = a[6] + a[5] + a[4] + (a[3] + 3) / 4;
        a[1] -= a[5] * 11;
        a[2] -= a[4] * 5;
        a[1] -= c[a[3] % 4][1];
        a[2] -= c[a[3] % 4][0];
        if (a[2] > 0) {
            int t = (a[2] + 8) / 9;
            ans += t;
            a[2] -= t * 9;
        }
        a[1] += a[2] * 4;
        if (a[1] > 0) {
            ans += (a[1] + 35) / 36;
        }
        printf("%d\n", ans);
    }
    return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出一个数组，求逆序数。

思路

树状数组模版题。

代码

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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 1000010;
int bit[maxn], n;
int a[maxn], r[maxn];

bool cmp(int i,int j) {
    return a[i] < a[j];
}

int sum(int i) {
    int s=0;
    while(i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

void add(int i, int x) {
    while(i <= n) {
        bit[i] += x;
        i += i & -i;
    }
    return;
}

int main(){
    while(~scanf("%d", &n) && n) {
        memset(bit, 0, sizeof bit);
        long long ans = 0;
        for(int i = 0;i < n; ++i) {
            scanf("%d", &a[i]);
            r[i] = i;
        }
        sort(r, r + n, cmp);
        for(int i = 0; i < n; ++i) {
            a[r[i]] = i + 1;
        }
        for(int i = 0; i < n; ++i) {
            ans += i - sum(a[i]);
            add(a[i], 1);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

有一个区间\([0,m]\)，给出若干区间\([l_i,r_i]\)，输出最少使用多少个区间可以覆盖\([0,m]\)，同时输出覆盖方法。

思路

区间覆盖类贪心题，按照左端点排序，每次尽可能向右覆盖即可。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100010;
struct seg {
    int l, r;
    bool operator < (const seg& rhs) const {
        return l < rhs.l;
    }
} a[maxn];
int path[maxn];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int m, n = 0;
        scanf("%d", &m);
        for (;;) {
            scanf("%d%d", &a[n].l, &a[n].r);
            if (!a[n].l && !a[n].r) {
                break;
            }
            ++n;
        }
        sort(a, a + n);
        int l = 0, r = 0, ans = 0;
        for (int i = 0; i < n; ) {
            if (a[i].l <= l) {
                if (a[i].r > r) {
                    path[ans] = i;
                    r = a[i].r;
                    if (r >= m) {
                        ++ans;
                        break;
                    }
                }
                ++i;
            }
            else {
                if (r <= l) {
                    ans = 0;
                    break;
                }
                l = r;
                ++ans;
            }
        }
        ans = r < m ? 0 : ans;
        printf("%d\n", ans);
        for (int i = 0; i < ans; ++i) {
            printf("%d %d\n", a[path[i]].l, a[path[i]].r);
        }
        if (t) {
            puts("");
        }
    }
    return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出\(n\)个圆，输出让它们共切线时最小的宽度。

思路

枚举全排列，注意再枚举的过程中注意随时维护右边界。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 10;
const int per[maxn] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
double a[maxn], p[maxn];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%lf", &a[i]);
        }
        int cnt = per[n];
        double ans = 1e9;
        while (cnt--) {
            p[0] = a[0];
            double cur = 2 * a[0];
            for (int i = 1; i < n; ++i) {
                p[i] = a[i];
                for (int j = 0; j < i; ++j) {
                    p[i] = max(p[i], p[j] + 2 * sqrt(a[i] * a[j]));
                }
                cur = max(cur, p[i] + a[i]);
            }
            ans = min(ans, cur);
            next_permutation(a, a + n);
        }
        printf("%.3lf\n", ans);
    }
    return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出\(n\)个5元组，选择\(k\)个，输出在\(k\)个5元组中每一位的最大值的和的最大值。

思路

对于5元组，有31个非空子集。枚举每个5元组所有子集，求出每种子集的最大值。然后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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n, k, ans;
int Max[33];

void dfs(int d, int s, int sum) {
    if (d == k) {
        ans = max(ans, sum);
        return;
    }
    for (int i = s; i; i = (i - 1) & s) {
        dfs(d + 1, s ^ i, sum + Max[i]);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        memset(Max, 0, sizeof Max);
        for (int i = 0; i < n; ++i) {
            int a[5];
            for (int j = 0; j < 5; ++j) {
                scanf("%d", &a[j]);
            }
            for (int j = 31; j > 0; --j) {
                int sum = 0;
                for (int l = 0; l < 5; ++l) {
                    if (j & (1 << l)) {
                        sum += a[l];
                    }
                }
                Max[j] = max(Max[j], sum);
            }
        }
        k = min(k, 5), ans = 0;
        dfs(0, 31, 0);
        printf("%d\n", ans);
    }
    return 0;
}

发表于 分类于 ， ， Disqus：

链接

传送门

题意

给出两个字符串，第一个中的每种字符可以对应1到\(k(1 \leq k \leq 3)\)个字符，如果存在对应规则使两个字符串相同输出1，否则输出0。

思路

枚举当前字符的对应长度，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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 20;
int k, l1, l2;
char Map[27][4], tmp[4];
char s[maxn], lt[maxn * 3];

bool dfs(int p1, int p2) {
    if (p1 == l1 || p2 == l2) {
        return p1 == l1 && p2 == l2;
    }
    for (int i = 1; i <= k && p2 + i <= l2; ++i) {
        for (int j = 0; j < i; ++j) {
            tmp[j] = lt[p2 + j];
        }
        tmp[i] = 0;
        bool flag = Map[s[p1] - 'a'][0] == 0;
        if (flag) {
            strcpy(Map[s[p1] - 'a'], tmp);
        }
        if (!strcmp(Map[s[p1] - 'a'], tmp) && dfs(p1 + 1, p2 + i)) {
            return true;
        }
        if (flag) {
            Map[s[p1] - 'a'][0] = 0;
        }
    }
    return false;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%s%s", &k, s, lt);
        memset(Map, 0, sizeof Map);
        l1 = int(strlen(s)), l2 = int(strlen(lt));
        puts(dfs(0, 0) ? "1" : "0");
    }
    return 0;
}

发表于 Disqus：

待补充……

1-1 General Problem Solving Techniques

1、位运算

1
2
3
i = (i - 1) & s; //枚举子集
i &= (i - 1);    //去掉最低位
i & (-i);        //取最低位

2、scanf类正则表达式

1
2
3
"%[a-z]" //表示匹配a到z中任意字符
"%[abc]" //匹配abc中一员
"%[^a]"  //匹配非a的任意字符

3、next_permutation函数

函数返回值为bool类型，当排序后的序列为升序时，返回false；其他时候，返回true。可以通过如下方式枚举全排列。

1
2
3
4
sort(a.begin(), a.end());
do {
  func();
} while (next_permutation(a.begin(), a.end()));

4、set.rbegin()反向迭代器

set.rbegin()是反向迭代器（reverse_iterator），不能用于set.erase()。需要加*取值删除或只是用set.base()获取对应的正向迭代器。

1
2
s.erase(*s.rbegin());    //取值后删除
s.erase((++rit).base()); //转化为正向迭代器后删除

1-2 Designing Efficient Algorithms

1-3 Dynamic Programming

发表于 分类于 Disqus：

链接

传送门

题意

有\(n\)个敌人排成一排，每次可以选择2到\(n-1\)的位置进行攻击，被攻击的位置的敌人减少\(a\)点生命，他两边的位置的敌人减少\(b\)点生命。敌人生命值小于0时会死去。当前位置的敌人死去之后依然可以进行攻击。输出杀死全部敌人的最少攻击次数。

思路

攻击的顺序对结果没有影响，定义状态\(d(i,h1,h2,h3)\)为当前选择位置\(i\)，第\(i-1\)到\(i+1\)个敌人的生命值依次为\(h1\)、\(h2\)、\(h3\)。读入数据时对所有生命+1，方便状态表示。当\(h1 \leq 0\)时，可以选择继续攻击位置\(i\)或者，开始攻击位置\(i+1\)；其他情况继续攻击位置\(i\)。

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 12;
const int maxh = 19;
int h[maxn];
int d[maxn][maxh][maxh][maxh];
LL p[maxn][maxh][maxh][maxh];
int ans[maxh * maxh];
#define H [h1][h2][h3]
#define C [c1][c2][c3]
#define ENCODE(i, h1, h2, h3) (((i * 19LL + h1) * 19 + h2) * 19 + h3)
#define DECODE(c) h3 = c % 19, c /= 19, h2 = c % 19, c /= 19, h1 = c % 19, x = c / 19

int main() {
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &h[i]);
        ++h[i];
    }
    memset(d, 0x3f, sizeof d);
    d[2][h[1]][h[2]][h[3]] = 0;
    for (int i = 2; i < n; ++i) {
        for (int h1 = h[i - 1]; h1 >= 0; --h1) {
            for (int h2 = h[i]; h2 >= 0; --h2) {
                for (int h3 = h[i + 1]; h3 >= 0; --h3) {
                    int& k = d[i]H;
                    if (k == inf) continue;
                    LL Code = ENCODE(i, h1, h2, h3);
                    int c1 = max(0, h1 - b), c2 = max(0, h2 - a), c3 = max(0, h3 - b);
                    if (k + 1 < d[i]C) {
                        d[i]C = k + 1;
                        p[i]C = Code;
                    }
                    if (h1 == 0 && k < d[i + 1][h2][h3][h[i + 2]]) {
                        d[i + 1][h2][h3][h[i + 2]] = k;
                        p[i + 1][h2][h3][h[i + 2]] = p[i]H;
                    }
                }
            }
        }
    }
    printf("%d\n", d[n][0][0][0]);
    int tmp = d[n][0][0][0], x = n, h1 = 0, h2 = 0, h3 = 0;
    while (tmp != 0) {
        LL Code = p[x]H;
        DECODE(Code);
        ans[tmp--] = x;
    }
    for (int i = 1; i <= d[n][0][0][0]; ++i) {
        printf("%d ", ans[i]);
    }
    return 0;
}