头像

夏言




离线:4天前


最近来访(12)
用户头像
无语未央
用户头像
optimjie
用户头像
saltyfishD
用户头像
crunch
用户头像
FreeStyle
用户头像
yxc
用户头像
wyzhii
用户头像
Eden_
用户头像
ffffffffffffffffffffffffffffff
用户头像
mtyu007

活动打卡代码 AcWing 3559. 围圈报数

夏言
2个月前

约瑟夫环

#include <iostream>

using namespace std;

const int N = 55;
int ne[N];
int n;


int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n;
        for(int i = 1; i < n; i++) ne[i] = i + 1;
        ne[n] = 1;
        int p = n;
        for(int i = 0; i < n; i++){
            p = ne[ne[p]];
            cout << ne[p] << ' ';
            ne[p] = ne[ne[p]];
        }
        cout << endl;
    }
    return 0;
}


活动打卡代码 AcWing 3540. 二叉搜索树

夏言
2个月前

二叉搜索树,用的是数组进行模拟二叉树

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

const int N = 1010;
int n;
int L[N], R[N], W[N], idx;
int root;

void insert(int& u, int x){
    if(!u){
        u = ++idx;
        W[u] = x;
    }else if(x > W[u]){
        insert(R[u], x);
    }else if(x < W[u]){
        insert(L[u], x);
    }
}

void dfs(int u, int t){
    if(!u) return;
    if(t == 0) cout << W[u] <<' ';
    dfs(L[u], t);
    if(t == 1) cout << W[u] << ' ';
    dfs(R[u], t);
    if(t == 2) cout << W[u] << ' ';
}

int main(){
    cin >> n;
    while(n--){
        int d;
        cin >> d;
        insert(root, d);
    }
    // for(int i = 0; i < idx; i++) cout << L[i] << ' ';
    for(int i = 0; i < 3; i++){
        dfs(root, i);
        cout << endl;
    }
}



夏言
4个月前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;


const int N = 1010;
int n, m;
string a = " ",b = " ";
// string a, b;
int f[N][N];
vector<char> g;


int main(){
    cin >> n >> m;
    // cin >> a >> b;
    string temp1, temp2;
    cin >> temp1 >> temp2;
    a = a + temp1;
    b = b + temp2;
    cout << a.size() << b.size();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j]){
                if(f[i - 1][j - 1] + 1 > f[i][j]){
                    f[i][j] = f[i - 1][j - 1] + 1;
                }
            }
        }
    }
    // for(int i = 1;i <= n; i++){
    //     for(int j = 1; j <= m; j++){
    //         cout << f[i][j];
    //     }
    //     cout << endl;
    // }

    int i = n, j = m;
    while(i > 0 && j > 0){
        if(f[i][j] == max(f[i - 1][j], f[i][j - 1])){
            if(f[i][j] == f[i - 1][j]) i--;
            else j--;
        }else{
            g.push_back(a[i]);
            i--,j--;

        }

    }

    cout << f[n][m] << endl;
    for(int i = g.size() - 1; i >= 0; i--){
        cout << g[i];
    }


    return 0;
}



夏言
4个月前

题目描述

给定两个长度分别为 N 和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
题目本来的就是求个最大值,最近总是看到面经里出现要求你输出其最长公共子序列,所以这个题解里会有怎么输出最长公共子序列。(一开始遇到会有点懵,后面和别人交流一下,之后有了个思路,感觉也就是类似于从最后往回找的过程,在此记录一下)

样例

输入:
4 5
acbd
abedc

输出;
3
abd

算法

(线性dp)

最长公共子序列真的是非常非常经典的dp问题,是面试很喜欢考的题目,其中的状态表示是f[i][j];
其中i是代表a序列到位置i,j是代表b序列到位置j,f[i][j]则是代表a序列到位置i和b序列到位置j公共子序列的长度max值
那么需要考虑如何推:
针对a序列的位置i和b序列的位置j上面的两个字符,有四种可能(0:代表不在公共子序列中,1表示在公共子序列中):
00 –> f[i - 1][j - 1];
这两种情况可以取最大值:(从逻辑上两者其实不等,但是用这个代替包含i或者j的最大值是ok的)
01 –> f[i - 1][j];
10 –> f[i][j - 1];

11 –> f[i - 1][j - 1] + 1(同时取到的前提是a[i] == b[j])

时间复杂度

参考文献

C++ 代码

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


const int N = 1010;
int n, m;
string a = " ",b = " ";
// string a, b;
int f[N][N];
vector<char> g;


int main(){
    cin >> n >> m;
    // cin >> a >> b;
    string temp1, temp2;
    cin >> temp1 >> temp2;
    a = a + temp1;
    b = b + temp2;
    //先将f[i][j] = max(f[i - 1][j], f[i][j - 1]),而后再判断是否i,j位置是否相等
    cout << a.size() << b.size();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j]){
                if(f[i - 1][j - 1] + 1 > f[i][j]){
                    f[i][j] = f[i - 1][j - 1] + 1;
                }
            }
        }
    }
    // for(int i = 1;i <= n; i++){
    //     for(int j = 1; j <= m; j++){
    //         cout << f[i][j];
    //     }
    //     cout << endl;
    // }

    //从n,m的位置往回推的过程
    int i = n, j = m;
    while(i > 0 && j > 0){
        if(f[i][j] == max(f[i - 1][j], f[i][j - 1])){
            if(f[i][j] == f[i - 1][j]) i--;
            else j--;
        }else{
            g.push_back(a[i]);
            i--,j--;

        }

    }

    cout << f[n][m] << endl;
    for(int i = g.size() - 1; i >= 0; i--){
        cout << g[i];
    }


    return 0;
}


活动打卡代码 AcWing 282. 石子合并

夏言
4个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int n;
int stone[N], s[N];
int f[N][N];


int main(){

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> stone[i];

    for(int i = 1; i <= n; i++){
        s[i] = s[i - 1] + stone[i];
    }

    for(int len = 2; len <= n; len++){
        for(int i = 1; i + len - 1 <= n; i++){
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;
            for(int k = l; k < r; k++){
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }

    cout << f[1][n];

    return 0;
}



夏言
4个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 10010;
int n;
double a[N];
int f[N];

int main(){
    cin >> n;
    for(int i = 1;i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) f[i] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(a[j] < a[i]){
                f[i] = max(f[i], f[j] + 1);
            }
        }
    }
    int ret = 0;
    for(int i = 1; i <= n; i++) ret = max(ret, f[i]);
    cout << ret;
    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

夏言
4个月前

从上到下,很复杂,需要很多的边界处理和初始化的处理
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;


const int N = 510;
int n;
int st[N][N];
int f[N][N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i;j++){
            cin >> st[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0;j <= i + 1; j++){
            f[i][j] = -1e9;
        }
    }

    f[1][1] = st[1][1];

    for(int i = 2; i <= n; i++){
        for(int j = 1;j <= i; j++){
            f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + st[i][j];
        }
    }
    int ret = -1e9;
    for(int i = 1; i <= n; i++) ret = max(ret, f[n][i]);

    cout << ret;

    return 0;
}

从下到上就可以省去这些处理
除了需要注意状态转移方程:
f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + st[i][j];

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

using namespace std;


const int N = 510;
int n;
int st[N][N];
int f[N][N];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= i;j++){
            cin >> st[i][j];
        }
    }
    for(int i = n; i >= 1; i--){
        for(int j = i; j > 0; j--){
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + st[i][j];
            // cout << f[i][j] << ' ';
        }
        // cout << endl;
    }

    cout << f[1][1];

    return 0;
}


活动打卡代码 AcWing 9. 分组背包问题

夏言
5个月前
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 110;
int n,m;
int S[N];
int V[N][N], W[N][N];
int f[N];


int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> S[i];
        for(int j = 0; j < S[i]; j++){
            cin >> W[i][j] >> V[i][j];
        }
    }
    for(int i = 1;i <= n; i++){
        for(int j = m; j >= 0;j--){
            for(int k = 0; k < S[i]; k++){
                if(W[i][k] <= j){
                    f[j] = max(f[j], f[j - W[i][k]] + V[i][k]);
                }
            }
        }
    }
    // for(int i = 1; i <= m; i++) cout << f[i] << ' '; 
    cout << f[m];
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

夏言
5个月前
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 2010;
int n, m;
int f[N];

struct good{
    int w,v;
};

int main(){
    cin >> n >> m;
    vector<good> g;
    for(int i = 1; i <= n; i++){
        int a,b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s){
            s -= k;
            g.push_back({a * k, b * k});
            k *= 2;
        }
        if(s > 0){
            g.push_back({a * s , s * b});
        }
    }
    for(auto item : g){
        for(int j = m; j>= item.w; j--){
            f[j] = max(f[j], f[j - item.w] + item.v);
        }
    }
    // for(auto t : g){
    //     for(int j = m; j>= t.v; j--){
    //         f[j] = max(f[j], f[j - t.v] + t.m);
    //     }
    // }
    cout << f[m];
    return 0;
}


活动打卡代码 AcWing 4. 多重背包问题

夏言
5个月前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;

int n,m;
int V[N], W[N], S[N];
int f[N][N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> V[i] >> W[i] >> S[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= m; j++){
            for(int k = 0; k <= S[i] && k * V[i] <= j; k++){
                f[i][j] = max(f[i][j], f[i - 1][j - V[i] * k] + W[i] * k);
            }
        }
    }
    cout << f[n][m];
    return 0;
}