L-China

$\href{https://www.acwing.com/blog/content/30572/}{\huge{\color{gold}{卡塞尔学院}}}$

关注数

粉丝数

阅读量

4.4万

+关注发消息

离线：32分钟前

最近来访(789)

向往.

TT_84

hnsqls

花辞树

尔东

须尽欢干杯

SchwarzS

FJ_EYoungOneC

nobody123

sma11pi9

快乐修狗

LABOUR

AkariSP

神秘的碳基生物

3343806536

link_null

雪中飞狐

风不会停息_6

懒懒散散的five

煌hq

题解 AcWing 1050. 鸣人的影分身

L-China
16小时前

C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

DP

闫氏DP分析法：

                    集合：所有总数是i，且分成j个数的和的方案
        状态表示
        f[i][j]     属性：数量
DP

                    最小值是0： f[i][j - 1] 
        状态计算    
                    最小值不是0：f[i - j][j]

状态转移方程：f[i][j] = f[i][j - 1] + f[i - j][j]

#include <bits/stdc++.h>
using namespace std;

int m, n;

int main() {
    int t; cin >> t;
    while (t --) {
        cin >> m >> n;

        int f[11][11] = {0};
        f[0][0] = 1;
        for (int i = 0; i <= m; i ++)
            for (int j = 1; j <= n; j ++) {
                f[i][j] = f[i][j - 1];
                if (i >= j) f[i][j] += f[i - j][j];
            }
        cout << f[m][n] << endl;    
    }
    return 0;
}

活动打卡代码 AcWing 1050. 鸣人的影分身

L-China
16小时前

                #include <bits/stdc++.h>
using namespace std;

int m, n;

int main() {
    int t; cin >> t;
    while (t --) {
        cin >> m >> n;

        int f[11][11] = {0};
        f[0][0] = 1;
        for (int i = 0; i <= m; i ++)
            for (int j = 1; j <= n; j ++) {
                f[i][j] = f[i][j - 1];
                if (i >= j) f[i][j] += f[i - j][j];
            }
        cout << f[m][n] << endl;    
    }
    return 0;
}

            

活动打卡代码 AcWing 842. 排列数字（算法基础课）

L-China
3天前

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

using namespace std;

int n;
int path[10];
bool st[10];

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i ++) cout << path[i] << ' ';
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i ++) 
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }

}

int main() {
    cin >> n;
    dfs(0);
    return 0;
}

            

活动打卡代码 AcWing 141. 周期（每日一题）

L-China
4天前

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

using namespace std;

const int N = 1e6 + 10;

int n;
char s[N];
int ne[N];

int main() {
    int T = 1;
    while (cin >> n, n) {
        cin >> s + 1;

        for (int i = 2, j = 0; i <= n; i ++) {
            while (j && s[i] != s[j + 1]) j = ne[j];
            if (s[i] == s[j + 1]) j ++;
            ne[i] = j;
        }
        printf("Test case #%d\n", T ++);

        for (int i = 1; i <= n; i ++) {
            int t = i - ne[i];
            if (i % t == 0 && i / t > 1)
                cout << i << ' ' << i / t << endl;
        }
        puts("");
    }

    return 0;
}

            

活动打卡代码 AcWing 831. KMP字符串（算法基础课）

L-China
4天前

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

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
char p[N], s[M];
int ne[N];

int main() {
    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++) {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++;
        ne[i] = j;
    }

    for (int i = 1, j = 0; i <= m; i ++) {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++;
        if (j == n) {
            cout << i - n << ' ';
            j = ne[j];
        }
    }
    return 0;
}

            

活动打卡代码 AcWing 4878. 维护数组

L-China
6天前

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

using namespace std;

const int N = 2e5 + 10;

int n, k, a, b, q;
int d[N];
int tr1[N], tr2[N];

int lowbit(int x) {
    return x & -x;
}

void add(int tr[], int x, int v) {
    for (int i = x; i <= n; i += lowbit(i)) 
        tr[i] += v;
}

int query(int tr[], int x) {
    int sum = 0;
    for (int i = x; i; i -= lowbit(i))
        sum += tr[i];
    return sum;    
}

int main() {
    cin >> n >> k >> a >> b >> q;

    while (q --) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; cin >> x >> y;
            add(tr1, x, min(d[x] + y, b) - min(d[x], b));
            add(tr2, x, min(d[x] + y, a) - min(d[x], a));
            d[x] += y;
        }
        else {
            int p; cin >> p;
            printf("%d\n", query(tr1, p - 1) + query(tr2, n) - query(tr2, p + k - 1));
        }
    }
    return 0;
}

            

活动打卡代码 AcWing 4877. 最大价值

L-China
6天前

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];

int main() {
    int v, w; 
    cin >> n >> m >> v >> w;
    for (int i = v; i <= n; i ++) f[i] = f[i - v] + w; // 完全背包

    for (int i = 1; i <= m; i ++) { // 多重背包
        int l, h; 
        cin >> l >> h >> v >> w;
        for (int j = n; j >= 0; j --)
            for (int k = 1; k <= l / h && k * v <= j; k ++)
                f[j] = max(f[j], f[j - k * v] + k * w);
    }
    cout << f[n];
    return 0;
}

            

活动打卡代码 AcWing 3. 完全背包问题（算法基础课）

L-China
6天前

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

using namespace std;

int n, m;
int f[1010];

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

    for (int i = 1; i <= n; i ++) {
        int v, w; cin >> v >> w;
        for (int j = v; j <= m; j ++)
            f[j] = max(f[j], f[j - v] + w);
    }
    cout << f[m];
    return 0;
}

            

活动打卡代码 AcWing 2. 01背包问题（算法基础课）

L-China
6天前

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

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

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

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

            