头像




离线:6天前




30天前
void insert(int x){
    int p = 0;
    for(int i  = 30; i >= 0; --i){
        int u = x >> i & 1;
        if(!t[p][u]) t[p][u] = ++idx;
        p = t[p][u];
    }
}




30天前
class Solution {
public:
    int add(int num1, int num2){
        while(num2){
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1;
            num1 = sum, num2 = carry;
        }
        return num1;
    }
};




1个月前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10000 * 201;
int f[N];
int n, m = N;
int k;

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

    int it = 0;
    while(f[it] <= k) ++it;
    cout << it - 1 << endl;
    return 0;
}


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


1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 102;
int f[N][N];
int w[N], v[N], s[N];
int n, m;

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){


        if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    cout << f[n][m] << endl;

    return 0;
}


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


1个月前
#include<iostream>
#include<algorithm>
using namespace std;

const int N =110;

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

int main(){
     cin >> n >> m;
     for(int i = 1; i <= n; ++i){
         cin >> s[i];
         for(int j = 0; j < s[i]; ++j){
             cin >> v[i][j] >> w[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(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

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


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


1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25000, M = 2010;
int f[N];
int n, m;
int v[N], w[N];

int main(){
    cin >> n >> m;
    int cnt = 0;
    for(int i = 1; i <= n; ++i){
        int k = 1;
        int a, b, s;
        cin >> a >> b >> s;
        while(k < s){
            cnt++;
            v[cnt] += a * k;
            w[cnt] += b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0){
            cnt++;
            v[cnt] += a * s;
            w[cnt] += b * s;
        }
    }
    n = cnt;

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


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


1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
int w[N], v[N];
int dp[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 = v[i]; j <= m; ++j)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

    cout << dp[m] << endl;
    return 0;
}


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


1个月前
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010, M = N;
int n, m;
int dp[N];
int v[N], w[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 = m; j >= v[i]; --j){
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    cout << dp[m];
    cout << endl;
    return 0;
}




1个月前

C++代码

#include<iostream>
#include<cstring>
using namespace std;
const int N = 10010, M = N * 2;
int h[N], ne[M], e[M], idx;
int q[N];
int d[N];
int n, m;
int bounus[N];
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort(){
    int tt = -1, hh = 0;
    for(int i = 1; i <= n; ++i)
        if(!d[i])
            q[++tt] = i;
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            //初始入度为0的节点t没有bounus,他的上级有一个,如此迭代
            bounus[j] = max(bounus[j], bounus[t] + 1);
            d[j]--; 
            if(d[j] == 0) q[++tt] = j;
        }
    }
    return tt == n - 1;
}

// int temp[N];
// void copy(int des[], int source[]){
//     for(int i = 1; i <= n; ++i)
//         des[i] = source[i];
// }

int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        add(b, a);
        d[a]++;
    }
    if(topsort()){
        int res = 0;
        for(int i = 1; i <= n; ++i) res += bounus[i] + 100;
        cout << res << endl;
    }
    else printf("Poor Xed\n");

    return 0;
}




1个月前

C++代码

一道朴实无华的拓扑排序题

#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int e[N * 2], ne[N * 2], h[N], idx;
int d[N];
int q[N];
int n;

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

void topsort(){
    int tt = -1, hh = 0;
    for(int i = 1; i <= n; ++i)
        if(!d[i])
            q[++tt] = i;
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            d[j]--;
            if(d[j] == 0) q[++tt] = j;
        }   
    }
    for(int i = 0; i < n; ++i) printf("%d ", q[i]);
}

int main(){
    cin >> n;
    memset(h, -1, sizeof h);
    int x;
    for(int i = 0; i < n; ++i)
        while(cin >> x, x) add(i + 1, x), d[x]++;
    topsort();
    return 0;
}