头像

Bug-Free

$ {\color {orange} {\Large{\mathit {AcWing\ University} }} }$




离线:3小时前


活动打卡代码 AcWing 901. 滑雪

Bug-Free
21天前

1.jpg

2.jpg

代码

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 3e2 + 10;

int n, m;
int g[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int& v = f[x][y];
    if (v != -1) {
        return v;
    }

    v = 1;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b]) {
            v = max(v, dp(a, b) + 1);
        }
    }
    return v;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            res = max(res, dp(i, j));
        }
    }
    cout << res << endl;
    return 0;
}



Bug-Free
21天前

1.jpg

2.jpg

代码

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 3e2 + 10;

int n, m;
int g[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y)
{
    int& v = f[x][y];
    if (v != -1) {
        return v;
    }

    v = 1;
    for (int i = 0; i < 4; i++) {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b]) {
            v = max(v, dp(a, b) + 1);
        }
    }
    return v;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
        }
    }
    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            res = max(res, dp(i, j));
        }
    }
    cout << res << endl;
    return 0;
}



Bug-Free
22天前

4.jpg

5.jpg

代码

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 6e3 + 10;

int n;
int head[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = head[a];
    head[a] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = head[u]; ~i; i = ne[i]) {
        int j = e[i];

        dfs(j);

        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

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

    memset(head, -1, sizeof head);

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(b, a);  // b是父节点
        has_fa[a] = true;
    }

    int root = 1;
    while (has_fa[root]) {  // 找到根节点
        root++;
    }

    dfs(root);  //从根节点出发

    cout << max(f[root][0], f[root][1]);

    return 0;
}



Bug-Free
22天前

4.jpg

5.jpg

代码

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 6e3 + 10;

int n;
int head[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = head[a];
    head[a] = idx++;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = head[u]; ~i; i = ne[i]) {
        int j = e[i];

        dfs(j);

        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

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

    memset(head, -1, sizeof head);

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        add(b, a);  // b是父节点
        has_fa[a] = true;
    }

    int root = 1;
    while (has_fa[root]) {  // 找到根节点
        root++;
    }

    dfs(root);  //从根节点出发

    cout << max(f[root][0], f[root][1]);

    return 0;
}


活动打卡代码 AcWing 338. 计数问题

Bug-Free
22天前

1.jpg

代码

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 10;

/*

001~abc-1, 999

abc
    1. num[i] < x, 0
    2. num[i] == x, 0~efg
    3. num[i] > x, 0~999

*/

int get(vector<int> num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; i--)
        res = res * 10 + num[i];
    return res;
}

int power10(int x)
{
    int res = 1;
    while (x--)
        res *= 10;
    return res;
}

int count(int n, int x)
{
    if (!n)
        return 0;

    vector<int> num;
    while (n) {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();

    int res = 0;
    for (int i = n - 1 - !x; i >= 0; i--) {
        if (i < n - 1) {
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x)
                res -= power10(i);
        }

        if (num[i] == x)
            res += get(num, i - 1, 0) + 1;
        else if (num[i] > x)
            res += power10(i);
    }

    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b, a) {
        if (a > b)
            swap(a, b);

        for (int i = 0; i <= 9; i++)
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }

    return 0;
}



Bug-Free
22天前

1.jpg

代码

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 10;

/*

001~abc-1, 999

abc
    1. num[i] < x, 0
    2. num[i] == x, 0~efg
    3. num[i] > x, 0~999

*/

int get(vector<int> num, int l, int r)
{
    int res = 0;
    for (int i = l; i >= r; i--)
        res = res * 10 + num[i];
    return res;
}

int power10(int x)
{
    int res = 1;
    while (x--)
        res *= 10;
    return res;
}

int count(int n, int x)
{
    if (!n)
        return 0;

    vector<int> num;
    while (n) {
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();

    int res = 0;
    for (int i = n - 1 - !x; i >= 0; i--) {
        if (i < n - 1) {
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x)
                res -= power10(i);
        }

        if (num[i] == x)
            res += get(num, i - 1, 0) + 1;
        else if (num[i] > x)
            res += power10(i);
    }

    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> b, a) {
        if (a > b)
            swap(a, b);

        for (int i = 0; i <= 9; i++)
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 91. 最短Hamilton路径

Bug-Free
23天前

1.png

2.png

3.png

4.png

5.png

代码

#include<iostream>
#include<cstring>

using namespace std;

const int N = 20;
const int M = 1 << 20; // 一共最多有20个1 种状态

int n;
int w[N][N];
int f[M][N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> w[i][j];
        }
    }
    memset(f, 0x3f, sizeof f); //由于要存最小值, 因此初始为正无穷会好一些
    f[1][0] = 0;
    for (int state = 1; state < 1 << n; state++) { // 从0到111...11 枚举所有state
        if (state & 1) { // state必须要包含起点1
            for (int j = 0; j < n; j++) {
                if (state >> j & 1) { // 如果当态前点集包含点j, 那么进行状态转移
                    for (int k = 0; k < n; k++) {
                        if (state ^ (1 << j) >> k & 1) { //如果从当前状态经过点集state中, 去掉点j后, state 仍然包含点k, 那么才能从点k转移到点j
                            // 当然这个 if 也可以不加,因为如果 state 去掉第 j 个点后,state 不包含点 k 了,
                            // 那么 f[state ^ 1 << j][k] 必然为正无穷,也就必然不会更新 f[state][j],所以去掉也可以 AC。
                            f[state][j] = min(f[state ^ 1 << j][k] + w[k][j], f[state][j]);
                        }
                    }
                }
            }
        }
    }
    cout << f[(1 << n) - 1][n - 1]; //最后输出 f[111...11][n-1]
    return 0;
}



Bug-Free
23天前

1.jpg

2.jpg

1.jpg

2.jpg

代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e1 + 2, M = 1 << N;

typedef long long ll;

int n, m;
ll dp[N][M];  // dp[i][j] 表示已经将前 i-1 列摆好, 且从第 i-1列伸出到第 i 列的状态是 j 的所有方案
bool st[M];

int main()
{
    while (cin >> n >> m, n || m) {
        for (int i = 0; i < 1 << n; i++) {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) {
                    if (cnt & 1) {
                        st[i] = false;
                    }
                    cnt = 0;
                }
                else {
                    cnt++;
                }
            }
            if (cnt & 1) {
                st[i] = false;
            }
        }
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 1 << n; j++) {
                for (int k = 0; k < 1 << n; k++) {
                    if ((j & k) == 0 && st[j | k]) {
                        // j & k == 0 表示 i 列和 i - 1列同一行不同时捅出来
                        // st[j | k] == 1 表示 在 i 列状态 j, i - 1 列状态 k 的情况下是合法的.
                        dp[i][j] += dp[i - 1][k];
                    }
                }
            }
        }
        cout << dp[m][0] << endl;
    }
    return 0;
}




Bug-Free
23天前

1.jpg

2.jpg

1.jpg

2.jpg

代码

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e1 + 2, M = 1 << N;

typedef long long ll;

int n, m;
ll dp[N][M];  // dp[i][j] 表示已经将前 i-1 列摆好, 且从第 i-1列伸出到第 i 列的状态是 j 的所有方案
bool st[M];

int main()
{
    while (cin >> n >> m, n || m) {
        for (int i = 0; i < 1 << n; i++) {
            int cnt = 0;
            st[i] = true;
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) {
                    if (cnt & 1) {
                        st[i] = false;
                    }
                    cnt = 0;
                }
                else {
                    cnt++;
                }
            }
            if (cnt & 1) {
                st[i] = false;
            }
        }
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 1 << n; j++) {
                for (int k = 0; k < 1 << n; k++) {
                    if ((j & k) == 0 && st[j | k]) {
                        // j & k == 0 表示 i 列和 i - 1列同一行不同时捅出来
                        // st[j | k] == 1 表示 在 i 列状态 j, i - 1 列状态 k 的情况下是合法的.
                        dp[i][j] += dp[i - 1][k];
                    }
                }
            }
        }
        cout << dp[m][0] << endl;
    }
    return 0;
}



活动打卡代码 AcWing 900. 整数划分

Bug-Free
23天前

1.jpg

2.jpg

3.jpg

代码

// #include <iostream>

// using namespace std;

// const int N = 1e3 + 10, mod = 1e9 + 7;

// int n;
// int dp[N][N];

// int main()
// {
//     cin >> n;

//     dp[0][0] = 1;  // 一个数字都不选, 总和为0是一种方案
//     for (int i = 1; i <= n; i++) {
//         for (int j = 0; j <= n; j++) {
//             for (int k = 0; k * i <= j; k++) {
//                 dp[i][j] = (dp[i][j] + dp[i - 1][j - k * i]) % mod;
//             }
//         }
//     }
//     cout << dp[n][n];

//     return 0;
// }
// #include <iostream>

// using namespace std;

// const int N = 1e3 + 10, mod = 1e9 + 7;

// int n;
// int dp[N][N];

// int main()
// {
//     cin >> n;

//     dp[0][0] = 1;  // 一个数字都不选, 总和为0是一种方案
//     for (int i = 1; i <= n; i++) {
//         for (int j = 0; j <= n; j++) {
//             for (int k = 0; k * i <= j; k++) {
//                 dp[i][j] = (dp[i][j] + dp[i - 1][j - k * i]) % mod;
//             }
//         }
//     }
//     cout << dp[n][n];

//     return 0;
// }
// #include <iostream>

// using namespace std;

// const int N = 1e3 + 10, mod = 1e9 + 7;

// int n;
// int dp[N][N];

// int main()
// {
//     cin >> n;

//     dp[0][0] = 1;

//     for (int i = 1; i <= n; i++) {
//         for (int j = 0; j <= n; j++) {
//             dp[i][j] = dp[i - 1][j];
//             if (j >= i) {
//                 dp[i][j] = (dp[i][j] + dp[i][j - i]) % mod;
//             }
//         }
//     }

//     cout << dp[n][n] << endl;

//     return 0;
// }

// #include <iostream>

// using namespace std;

// const int N = 1e3 + 10, mod = 1e9 + 7;

// int n;
// int dp[N];

// int main()
// {
//     cin >> n;

//     dp[0] = 1;
//     for (int i = 1; i <= n; i++) {
//         for (int j = i; j <= n; j++) {
//             dp[j] = (dp[j] + dp[j - i]) % mod;
//         }
//     }
//     cout << dp[n] << endl;
//     return 0;
// }

#include <iostream>

using namespace std;

const int N = 1e3 + 10, mod = 1e9 + 7;

int n;
int dp[N][N];

int main()
{
    cin >> n;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % mod;
        }
    }
    int res = 0;
    for (int i = 0; i <= n; i++) {
        res = (res + dp[n][i]) % mod;
    }
    cout << res << endl;
    return 0;
}