PAT学习

发表于

:scream:是😱
:kissing_heart:是😘
:yum:是😋

sscanf()和sprintf()

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;

int main() {
    int n;
    char str[100] = "123";
    sscanf(str, "%d", &n);
    printf("%d\n", n);
    return 0;
} 

123
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;

int main() {
    int n = 456;
    char str[100];
    sprintf(str, "%d", n);
    printf("%s\n", str);
    return 0;
} 

456
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;

int main() {
    int n;
    double db;
    char str1[100] = "2048:3.14,hello", str2[100];
    sscanf(str, "%d:%lf,%s", &n, &db, &str2);
    printf("n = %d, db = %.2f, str2 = %s\n", n, db, str2);
    
    return 0;
} 

n = 2048, db = 3.14, str2 = hello
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
using namespace std;

int main() {
    int n = 12;
    double db = 3.1415;
    char str1[100], str2[100] = "good";
    sprintf(str1, "%d:%.3f,%s", n, db, str2);
    printf("str1 = %s\n", str1);
    
    return 0;
} 

str1 = 12:3.142,good

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
#include <iostream>
using namespace std;

const int maxn = 30;
int n, V, maxValue = 0;
int w[maxn], c[maxn];

void DFS(int index, int sumW, int sumC) {
    if (index == n) {
        if (sumW <= V && sumC > maxValue) {
            maxValue = sumC;
        }
        return;
    }
    DFS(index + 1, sumW, sumC);
    DFS(index + 1, sumW + w[index], sumC + c[index]);
}

int main() {
    scanf("%d%d", &n, &V);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);
    }
    DFS(0, 0, 0);
    printf("%d\n", maxValue);
    
    return 0;
} 

5 8
3 5 1 2 2
4 5 2 1 3

10
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
#include <iostream>
using namespace std;

const int maxn = 30;
int n, V, maxValue = 0;
int w[maxn], c[maxn];

void DFS(int index, int sumW, int sumC) {
    if (index == n) {
        return;
    }
    DFS(index + 1, sumW, sumC);
    if (sumW + w[index] <= V) {
        if (sumC + c[index] > maxValue) {
            maxValue = sumC + c[index];
        }
        DFS(index + 1, sumW + w[index], sumC + c[index]);
    }
}

int main() {
    scanf("%d%d", &n, &V);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);
    }
    DFS(0, 0, 0);
    printf("%d\n", maxValue);
    
    return 0;
}
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
#include <iostream>
using namespace std;
 
const int maxn = 30;
int n, V, maxValue = 0;
int w[maxn], c[maxn];

void DFS(int index, int sumW, int sumC) {
    if (index == n) {
        return;
    }
    if (sumW < V) { // 试着再优化，当容量还有空间，才考虑选与不选
        DFS(index + 1, sumW, sumC);
    }
    if (sumW + w[index] <= V) {
        if (sumC + c[index] > maxValue) {
            maxValue = sumC + c[index];
        }
        DFS(index + 1, sumW + w[index], sumC + c[index]);
    }
}

int main() {
    scanf("%d%d", &n, &V);
    for (int i = 0; i < n; i++) {
        scanf("%d", &w[i]);
    }
    for (int i = 0; i < n; i++) {
        scanf("%d", &c[i]);
    }
    DFS(0, 0, 0);
    printf("%d\n", maxValue);
    
    return 0;
}

全排列

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
#include <iostream>
using namespace std;

const int maxn = 11;
int n, P[maxn], hashTable[maxn] = {0};

void generateP(int index) {
    if (index == n + 1) {
        for (int i = 1; i <= n; i++) {
            printf("%d", P[i]);
        }
        printf("\n");
        return;
    }
    for (int x = 1; x <= n; x++) {
        if (hashTable[x] == 0) {
            P[index] = x;
            hashTable[x] = 1;
            generateP(index + 1);
            hashTable[x] = 0;
        }
    }
}

int main() {
    n = 3;
    generateP(1);

    return 0;
}
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
#include <iostream>
using namespace std;

const int maxn = 11;
int n, P[maxn], hashTable[maxn] = {0};

int cnt = 0;

void generateP(int index) {
    if (index == n + 1) {
        bool flag = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (abs(i - j) == abs(P[i] - P[j])) {
                    flag = false;
                }
            }
        }
        if (flag) cnt++;
        return;
    }
    for (int x = 1; x <= n; x++) {
        if (hashTable[x] == 0) {
            P[index] = x;
            hashTable[x] = 1;
            generateP(index + 1);
            hashTable[x] = 0;
        }
    }
}

int main() {


    return 0;
}

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;

int gcd(int m, int n) {
    return !n ? m : gcd(n, m % n);
}

int main() {
    int m, n;
    while (scanf("%d%d", &m, &n) != EOF) {
        printf("%d\n", gcd(m, n));
    }

    return 0;
}

分数的表示和化简

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
#include <iostream>
using namespace std;

int gcd(int m, int n) {
    return !n ? m : gcd(n, m % n);
}

struct Fraction {
    int up, down;
};

Fraction reduction(Fraction res) {
    if (res.down < 0) {
        res.up = -res.up;
        res.down = -res.down;
    }
    if (res.up == 0) {
        res.down = 1;
    } else {
        int d = gcd(abs(res.up), abs(res.down));
        res.up /= d;
        res.down /= d;
    }
    return res;
}

Fraction add(Fraction f1, Fraction f2) {
    Fraction res;
    res.up = f1.up * f2.down + f2.up * f1.down;
    res.down = f1.down * f2.down;
    return reduction(res);
}

Fraction minus(Fraction f1, Fraction f2) {
    Fraction res;
    res.up = f1.up * f2.down - f2.up * f1.down;
    res.down = f1.down * f2.down;
    return reduction(res);
}

Fraction multiplication(Fraction f1, Fraction f2) {
    Fraction res;
    res.up = f1.up * f2.up;
    res.down = f1.down * f2.down;
    return reduction(res);
}

Fraction divide(Fraction f1, Fraction f2) {
    Fraction res;
    while (f2.up != 0) {
        res.up = f1.up * f2.down;
        res.down = f1.down * f2.up;
        return reduction(res);
    }
}

void showRes(Fraction r) {
    if (r.down == 1) printf("%d", r.up);
    else if (abs(r.up) > abs(r.down)) {
        printf("%d %d/%d", r.up / r.down, abs(r.up) % abs(r.down), r.down);
    } else {
        printf("%d/%d", r.up, r.down);
    }
}

int main() {
    Fraction f1;
    f1.up = -14, f1.down = 6;
    showRes(f1);
    printf("\n");
    f1 = reduction(f1);
    showRes(f1);


    return 0;
}

-2 2/6
-2 1/3

素数

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
#include <iostream>
#include <math.h>
using namespace std;

bool isPrime_1(int n) {
    if (n <= 1) return false;
    int sqr = (int)sqrt(1.0 * n);
    for (int i = 2; i <= sqr; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

bool isPrime_2(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    printf("%d\n", isPrime_1(13));
    printf("%d\n", isPrime_2(53));

    return 0;
}

1
1

Dijkstra

邻接矩阵

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
const int MAXV = 1000;
const int INF = 0x3fffffff;
int n, G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV] = {false};

void Dijkstra(int s) {
    fill(d, d + MAXV, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

邻接表

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
const int MAXV = 1000;
const int INF = 0x3fffffff;

struct Node {
    int v, dis;
};

vector<Node> Adj[MAXV];
int n;
int d[MAXV];
bool vis[MAXV] = {false};

void Dijkstra(int s) {
    fill(d, d + MAXV, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        vis[u] = true;
        for (int j = 0; j < Adj[u].size(); j++) {
            int v = Adj[u][j].v;
            if (vis[v] == false && d[u] + Adj[u][j].dis < d[v]) {
                d[v] = d[u] + Adj[u][j].dis;
            }
        }
    }
}

一个实例

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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXV = 1000;
const int INF = 0x3fffffff;
int n, G[MAXV][MAXV];
int d[MAXV];
bool vis[MAXV] = {false};
int m, s;

void Dijkstra(int s) {
    fill(d, d + MAXV, INF);
    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1, MIN = INF;
        for (int j = 0; j < n; j++) {
            if (vis[j] == false && d[j] < MIN) {
                u = j;
                MIN = d[j];
            }
        }
        if (u == -1) {
            return;
        }
        vis[u] = true;
        for (int v = 0; v < n; v++) {
            if (vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
                d[v] = d[u] + G[u][v];
            }
        }
    }
}

int main() {
    int u, v, w;
    scanf("%d%d%d", &n, &m, &s);
    fill(G[0], G[0] + MAXV * MAXV, INF);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        G[u][v] = w;
    }
    Dijkstra(s);
    for (int i = 0; i < n; i++) {
        printf("%d ", d[i]);
    }

    return 0;
}

6 8 0
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3

0 1 5 3 4 6

动态葵花

动态规划的递推写法

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
const int maxn = 10000;

int F1(int n) {
    if (n == 0 || n == 1) return 1;
    else return F1(n - 1) + F1(n - 2);
}

int dp[maxn];

int F2(int n) {
    if (n == 0 || n == 1) return 1;
    if (dp[n] != -1) return dp[n];
    else {
        dp[n] = F2(n - 1) + F2(n - 2);
        return dp[n];
    }
}

int main() {
    memset(dp, -1, maxn);
    cout << F2(5) << endl;

    return 0;
}

8