洛灵酱的小窝

洛灵酱的小窝

闻道有先后，术业有专攻。

0%

发表于 更新于 分类于 Valine：

明天就要CSP了，祝大家RP++！

今天打了一遍常用算法的板子。

  1. 数论部分
  • GCD
  • LCM
  • EXGCD
  • 快速幂
  1. 高精度部分
  • 加法高精
  • 乘法高精
  • 除法高精
  1. 图论部分
  • Dijkstra
  • SPFA
  • Floyd
  • Kruskal
  1. 排序部分
  • 归并排序（求解逆序对）
阅读全文 »

发表于 更新于 分类于 Valine： 
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
/* P1104 采药
 * 来源: NOIP 2005
 * 作者: RainbowBird
 * 日期: 2020-11-04
 * 算法: 记忆化搜索
 */

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

int W, n;
int w[105], v[105];

int mem[105][1005];
int dfs(int pos, int rest) {
    if (mem[pos][rest] != -1) return mem[pos][rest];
    if (pos == n + 1) return mem[pos][rest] = 0;
    int a = 0, b = -1;
    a = dfs(pos + 1, rest);
    if (rest >= w[pos])
        b = dfs(pos + 1, rest - w[pos]) + v[pos];
    return mem[pos][rest] = max(a, b);
}

int main() {
    cin >> W >> n;
    for (int i = 1; i <= n; i++)
        cin >> w[i] >> v[i];
    
    memset(mem, -1, sizeof(mem));

    cout << dfs(1, W) << endl;
    return 0;
}

发表于 更新于 分类于 Valine：

题目链接

P1776 宝物筛选

题目代码

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
/* P1776 宝物筛选
 * 来源: Luogu
 * 作者: RainbowBird
 * 日期: 2020-10-30
 * 算法: 多重背包
 */

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

struct Item {
    int v, w;
} item[400005];

int n, W, tot;
ll f[400005];

int main() {
    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        int v, w, m;
        cin >> v >> w >> m;
        // 二进制分组优化
        int c = 1;
        while (m - c > 0) {
            m -= c;
            item[++tot].v = c * v;
            item[tot].w = c * w;
            c *= 2;
        }

        item[++tot].v = m * v;
        item[tot].w = m * w;
    }

    n = tot;

    for (int i = 1; i <= n; i++) {
        for (int j = W; j >= 0; j--) {
            if (j >= item[i].w) {
                f[j] = max(f[j], f[j-item[i].w] + item[i].v);
            }
        }
    }

    cout << f[W] << endl;
    return 0;
}

发表于 更新于 分类于 Valine： 
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
/* NC21228 货币系统
 * 来源: Nowcoder
 * 作者: RainbowBird
 * 日期: 2020-11-03
 * 算法: 筛法
 */

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

int T;
// 核心思想：判断某个数能不能被之前的数给凑出来

int main() {
    cin >> T;
    while (T--) {
        int n, a[105], money[25005]; // 0 1 2
        cin >> n;
        memset(money, 0, sizeof(money));
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            money[a[i]] = 2; // 就是自己
        }

        sort(a + 1, a + 1 + n);

        for (int i = 1; i <= a[n]; i++) {
            if (money[i] > 0) { // 如果money[i]能被凑出来
                // 则 money[i + a[j]] 也能凑出来
                for (int j = 1; j <= n; j++) {
                    if (i + a[j] > a[n]) break; // 防止数组越界
                    money[i + a[j]] = 1;
                }
            }
        }

        int tot = 0; // 不能被别的货币凑到的数额即最小的个数
        for (int i = 1; i <= a[n]; i++) {
            if (money[i] == 2) tot++;
        }

        cout << tot << endl;
    }
    return 0;
}

发表于 更新于 分类于 Valine：

01背包

例题中已知条件有第ii个物品的重量ww，价值viv_i，以及背包的总容量WW。

设 DP 状态f(i,j)f(i,j)为在只能放前ii个物品的情况下，容量为jj的背包所能达到的最大总价值。

阅读全文 »

发表于 更新于 Valine： 
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
/* NC22924 货币系统
 * 来源: Nowcoder
 * 作者: RainbowBird
 * 日期: 2020-11-03
 * 算法: 完全背包
 */

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

int v, n, a[26];
ll f[10005];

int main() {
    cin >> v >> n;
    for (int i = 1; i <= v; i++)
        cin >> a[i];

    f[0] = 1;
    for (int i = 1; i <= v; i++) {
        for (int j = a[i]; j <= n; j++) {
            f[j] += f[j-a[i]];
        }
    }

    cout << f[n] << endl;
    return 0;
}

发表于 更新于 分类于 Valine： 
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
/* NC20861 兔子的逆序对
 * 来源: Nowcoder
 * 作者: RainbowBird
 * 日期: 2020-11-03
 * 算法: 归并排序
 */

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

int n, m;
int a[100005], b[100005];
ll tot;

int qread() {
    int base = 1, k = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') base = -1;
        ch = getchar();
    }

    while (ch >= '0' && ch <= '9') {
        k = k * 10 + (ch - '0');
        ch = getchar();
    }

    return k * base;
}

void merge(int l, int mid, int r) {
    int p1 = l, p2 = mid + 1;
    for (int i = l; i <= r; i++) {
        if ((p1 <= mid && (p2 > r || a[p1] <= a[p2]))) {
            b[i] = a[p1];
            p1++;
        } else {
            b[i] = a[p2];
            p2++;
            tot += mid - p1 + 1;
        }
    }

    for (int i = l; i <= r; i++)
        a[i] = b[i];
}

void merge_sort(int l, int r) {
    int mid = (l + r) >> 1;
    if (l < r) {
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
    }

    merge(l, mid, r);
}

int main() {
    n = qread();
    for (int i = 1; i <= n; i++)
        a[i] = qread();

    merge_sort(1, n);

    m = qread();
    tot %= 2;
    
    while (m--) {
        int l, r;
        l = qread();
        r = qread();
        int p = (r - l + 1) * (r - l) / 2;
        if (p & 1) tot ^= 1;
        tot == 0 ? printf("like\n") : printf("dislike\n");
    }

    return 0;
}

发表于 更新于 分类于 Valine：

  1. scanf(" %c", &n)
    其中%c前面加一个空格可以过滤掉一切的空格，回车以及Tab，如果没有的话则不影响。

  2. 函数有返回值而不返回或者数组下标越界可能会产生各种奇怪的问题，比如C11能AC但是C14会RE等等。

  3. 用memset给int赋值为0x7f即为近似最大值，二进制位为0111 0111 0111 0111。

  4. 有向无环图的单源点最短路使用BFS算法最佳。