头像

密集指针




离线:24天前



密集指针
5个月前
#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int N = 1010;
int f[N][N];


int main(){
    int n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(a[i - 1] == b[j - 1]) f[i][j] = f[i - 1][j -1] + 1;
            else f[i][j] = max(f[i -1][j], f[i][j - 1]);

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



密集指针
5个月前
#include <iostream>
#include <vector>

using namespace std;

const int N = 100010;
int a[N], f[N];

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) cin >> a[i];
    int sz = 0;
    for(int i = 0; i < n; ++i){
        int lo = 0, hi = sz, t = a[i];
        while(lo < hi){
            int mi = lo + hi >> 1;
            if(f[mi] >= t) hi = mi;
            else lo = mi + 1;
        }
        if(lo == sz) ++sz;
        f[lo] = t;
    }
    cout << sz << endl;
    return 0;
}



密集指针
5个月前
#include <iostream>
#include <vector>

using namespace std;

const int N = 1000;
int a[N];

int main(){
    int n;
    cin >> n;
    vector<int> f(n, 1);
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < i; ++j){
            if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
        }
        // cout << i << ' ' << f[i] << endl;
    }
    int res = 0;
    for(auto x : f) res = max(x, res);
    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

密集指针
5个月前
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100010;

struct Sec{
    int a, b;
    bool operator<(const Sec &val){
        if(a < val.a) return true;
        if(a == val.a) return b < val.b;
        return false;
    }
    Sec(int x = 0, int y = 0):a(x), b(y) {}
};

int main(){
    int n, a, b;
    cin >> n;
    vector<Sec> secs(n);
    for(int i = 0; i < n; ++i){
        cin >> a >> b;
        secs[i] = {a, b};
        //secs.push_back(Sec(a, b));
    }
    sort(secs.begin(), secs.end());
    // for(auto x : secs) cout << x.a << ' ' << x.b << endl;
    int i = secs[0].a, j = secs[0].b, res = 1;
    for(int k = 1; k < n; ++k){
        if(secs[k].a > j){
            ++res;
            i = secs[k].a;
            j = secs[k].b;
        }
        else{
            if(secs[k].a > i) i = secs[k].a;
            if(secs[k].b < j) j = secs[k].b;
        }
    }
    cout << res << endl;
    return 0;
}


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

密集指针
5个月前
#include <iostream>

using namespace std;

const int N = 110;
int n, m, s;
int f[N], v[N], w[N];

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

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




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

密集指针
5个月前
#include <iotream>
#include <vector>

const int N = 1010, M = 2010;

struct Good{
    int v, w;
    Good(int a, int b):v(a), w(b) {}
};

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





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

密集指针
5个月前
#include <iostream>
const int N = 110;
int n, m, w, v, s;

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

}


活动打卡代码 AcWing 3. 完全背包问题

密集指针
5个月前
#include <iostream>
const int N = 1010;
int f[N];
int n, m, w, v;

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



密集指针
6个月前

字符串匹配

使用的写法是《数据结构》–严蔚敏书上改进的版本
(对于aaaaaaab这类字符串性能上稍有提升)

输入样例

4
aaab
14
aaaaabaabaaaab

输出样例

2 10

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;
int n, m;
char p[N], s[M];
int ne[N];

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

    int i = 1, j = 0;
    while(i <= n){
        if( j == 0 || p[i] == p[j]){
            ++i, ++j;
            ne[i] = p[i] == p[j] ? ne[j] : j;
        }
        else j = ne[j];
    }

    i = 1, j = 1;
    while(i <= m && j <= n){
        if(j == 0 || s[i] == p[j]){
            ++i, ++j;
        }
        else j = ne[j];
        if(j == n + 1){
            printf("%d ", i - j);
            j = ne[n + 1];
        }
    }
    return 0;
}

next[]数组中存储的值

0 0 0 3
上述方法中下标是从1开始的,
串”aaab”中,第2和3个字符失配时,我们直接将模式串指针置为0,那么我们下一次进行匹配时主串和模式串都会往前移动一个单位(如果不加优化,next数组中的值应当为0 1 2 3,而这里面包含了两次多余的操作)



活动打卡代码 AcWing 2. 01背包问题

密集指针
6个月前
#include<iostream>
using namespace std;

int const N = 1001;
int n, m;
int v[N], w[N], dp[N];

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