头像

烛之武

AcWing




离线:7小时前



烛之武
16小时前

最长上升子序列

只要满足两个序列中有一个序列中的元素是不重复的,求最长公共子序列的问题可以转化为求最长上升的问题

最长上升子序列有dp和贪心两种解法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000010;

int id[N],q[N];
int n;

int main(){
    scanf("%d", &n);
    memset(id, -1, sizeof id);
    for(int i = 0; i < n; i ++){
        int x;
        scanf("%d", &x);
        id[x] = i;
    }
    int len = 0;
    q[0] = -1;
    for(int i=0;i<n;i++){
        int x;
        scanf("%d", &x);
        int k = id[x];
        if(k == -1) continue;
        int l = 0, r = len;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(q[mid] < k) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = k;
        len = max(r + 1, len);
    }
    printf("%d\n", len);

    return 0;
}



烛之武
17小时前

打表 + 模拟

class Solution {
public:
    string intToRoman(int num) {
        string text[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        int val[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string ans;
        for(int i = 0; i < 13; i ++){
            while(num >= val[i]){
                ans += text[i];
                num -= val[i];
            }
        }
        return ans;
    }
};



二分
class Solution {
public:

    vector<int> w;
    bool check(int aim,int k){
        int n = w.size();
        int sum = 0, cnt = 1;
        for(int i=0;i<n;i++){
            if(sum + w[i] > aim){
                cnt ++;
                sum = 0;
            }
            sum += w[i];
        }
        return cnt <= k;
    }

    int shipWithinDays(vector<int>& weights, int D) {
        w = weights;
        int l = 0;
        for(auto &ele: w) l = max(l, ele);
        int r = 1e8;
        while(l < r){
            int mid = l + r >> 1;
            cout << l << ' ' << r << endl;
            if(check(mid, D)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};



树的遍历

dfs + bfs

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int l[N],r[N],w[N],q[N],a[N];
int n;

void dfs(int u,int &k){
    if(u == -1) return;
    dfs(l[u],k);
    w[u] = a[k ++];
    dfs(r[u],k);
}

void bfs(int u){
    int hh = 0, tt = 0;
    q[0] = u;
    while(hh <= tt){
        int t = q[hh ++];
        printf("%d ", w[t]);
        if(l[t] != -1) q[++ tt] = l[t];
        if(r[t] != -1) q[++ tt] = r[t];
    }
}

int main(){
    cin >> n;
    for(int i=0;i<n;i++) cin >> l[i] >> r[i];
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a, a + n);

    int k = 0;
    dfs(0, k);

    bfs(0);

    return 0;
}


活动打卡代码 AcWing 3502. 不同路径数

dfs

#include <iostream>
#include <unordered_set>

using namespace std;

const int N = 6;

int q[N][N];
int n,m,k;
int cnt;

unordered_set<int> us;

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

void dfs(int x,int y,int u,int num){
    if(u == k){
        if(us.count(num) == 0){
            us.insert(num);
            cnt ++;
        }
        return;
    }
    for(int i = 0; i < 4; i ++){
        int a = x + dx[i], b = y + dy[i];
        if(a<0 || a>=n || b<0 || b>=m) continue;
        dfs(a, b, u + 1, num * 10 + q[a][b]);
    }
}

int main(){
    cin >> n >> m >> k;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> q[i][j];
        }
    }


    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dfs(i,j,0,q[i][j]);
        }
    }
    cout << cnt << endl;

    return 0;
}


活动打卡代码 AcWing 3499. 序列最大收益

线性dp

#include <iostream>

using namespace std;

const int N = 210;

int f[N][N],w[N][N],h[N];
int n, k, m;

int main(){
    scanf("%d%d%d", &n, &k, &m);

    for(int i=0;i<m;i++) scanf("%d",&h[i]);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&w[i][j]);
        }
    }


    for(int i=0;i<m;i++){
        for(int j=0;j<=k;j++){
            for(int u=0;u<i;u++){
                if(i - u - 1 <= j) f[i][j] = max(f[i][j], f[u][j - (i - u - 1)] + w[h[u]][h[i]]);
            }
        }
    }
    printf("%d\n", f[m - 1][k]);

    return 0;
}


活动打卡代码 AcWing 677. 找零

贪心

#include <iostream>

using namespace std;

int m[] = {1, 4, 16, 64};
int tot;

int main(){
    cin >> tot;
    int remain = 1024 - tot;
    int cnt = 0;
    for(int i=3;i>=0;i--){
        cnt += remain / m[i];
        remain %= m[i];
    }
    cout << cnt << endl;

    return 0;
}


活动打卡代码 AcWing 1221. 四平方和

哈希表

将四个数平方和拆分成两个数的平方和,用哈希表将两个数的平方和存储下来

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

using namespace std;

const int N = 5000010;

int C[N], D[N];
int n;

int main(){
    cin >> n;

    memset(C, -1, sizeof C);
    for(int i=0;i*i<=n;i++){
        for(int j=i;i*i+j*j<=n;j++){
            int s = i * i + j * j;
            if(C[s] == -1){
                C[s] = i, D[s] = j;
            }
        }
    }

    for(int i=0;i*i<=n;i++){
        for(int j=i;j*j+i*i<=n;j++){
            int s = n - i * i - j * j;
            if(C[s] != -1){
                cout << i << ' ' << j << ' ' << C[s] << ' ' << D[s] << endl;
                return 0;
            }
        }
    }

    return 0;
}


活动打卡代码 AcWing 3493. 最大的和

前缀和 + 双指针

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;

LL s1[N], s2[N];
int w[N], st[N];
int n,k;

int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }

    for(int i=1;i<=n;i++){
        scanf("%d",&st[i]);
    }

    for(int i=1;i<=n;i++){
        s1[i] = s1[i-1] + w[i];
        if(st[i]){
            s2[i] = s2[i-1] + w[i]; 
        }else{
            s2[i] = s2[i-1];
        }
    }


    LL ans = 0;
    for(int i=k;i<=n;i++){
        LL sum = s1[i] - s1[i-k] + s2[i-k] + s2[n] - s2[i];
        ans = max(ans, sum);
    }

    printf("%lld\n", ans);

    return 0;
}

简洁的写法

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;

int a[N], b[N];
int n,k;

int main(){
    scanf("%d%d", &n, &k);

    for(int i=0;i<n;i++) scanf("%d", &a[i]);
    for(int i=0;i<n;i++) scanf("%d", &b[i]);

    LL s = 0;
    for(int i=0;i<n;i++){
        if(b[i]) s += a[i];
    }

    LL v = 0, ans = 0;
    for(int i=0;i<n;i++){
        if(!b[i]) v += a[i];
        if(i>=k && !b[i-k]) v -= a[i - k];
        ans = max(ans, v);
    }
    printf("%lld", ans + s);

    return 0;
}


活动打卡代码 LeetCode 403. 青蛙过河

记忆化搜索dp

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

class Solution {
public:
    vector<int> stones;
    unordered_map<int,int> um;

    bool dfs(int i,int j){
        if(f[i][j] != -1) return f[i][j];
        f[i][j] = 0;
        for(int k=max(1,j-1);k<=j+1;k++){
            int x = stones[i] - k;
            if(um.count(x)){
                int u = um[x];
                if(dfs(u,k)){
                    f[i][j] = 1;
                    break;
                }
            }
        }
        return f[i][j];
    }

    bool canCross(vector<int>& _stones) {
        stones = _stones;
        int n = stones.size();
        for(int i = 0; i < n; i ++){
            um[stones[i]] = i;
        }
        memset(f, -1, sizeof(f));
        f[0][1] = 1;
        for(int i = 0; i <= n; i ++){
            if(dfs(n-1, i)) return true;
        }
        return false;
    }
};