头像

Ritalin




离线:1小时前


最近来访(65)
用户头像
Meteor_7
用户头像
旧尘丶
用户头像
WL_4
用户头像
楼故
用户头像
墨染流年
用户头像
New_lzc
用户头像
空银子和彦
用户头像
SELFIE1
用户头像
gushiyu
用户头像
平顶山学院6380
用户头像
花轮和彦
用户头像
McKinleyLu
用户头像
孟博韬
用户头像
helloworld666
用户头像
华仔
用户头像
Naive_512
用户头像
Mamba_Chu
用户头像
长夜难明
用户头像
egg12140
用户头像
Stereo


Ritalin
8天前
#include<bits/stdc++.h>
using namespace std;
int n,m,s;
int v1[110],v2[110];
int dp[1010][510];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> m >> s;
    for(int i = 1;i <= s;i ++){
        cin >> v1[i] >> v2[i];
    }
    for(int i = 1;i <= s;i ++){
        for(int j = n;j >= v1[i];j --){
            for(int k = m;k >v2[i];k --){
                    dp[j][k] = max(dp[j][k],dp[j - v1[i]][k - v2[i]] + 1);  
            }
        }
    }
    int x = m;
    while(x > 0 && dp[n][x] == dp[n][m])x --;
    cout << dp[n][m] << " " << m - x <<endl;
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

Ritalin
8天前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL mul(LL a,LL b,LL p){
    LL ans = 0;
    while(b){
        if(b & 1)ans = (ans + a) % p;
        a = a * 2 % p;
        b >>= 1;
    }
    return ans;
}
int main(){
    LL a, b, p;
    cin >> a >> b >> p;
    cout<<mul(a, b, p)<<endl;
    return 0;
}


活动打卡代码 AcWing 1024. 装箱问题

Ritalin
8天前
#include<bits/stdc++.h>
using namespace std;
int V,n;
int v[35],dp[35][20010];
int ans;
int main(){
    cin >> V >> n;
    for(int i = 1;i <= n;i ++){
        cin>>v[i];
    }
    ans = V;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= V;j ++){
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i])dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + v[i]);
            ans = min(ans,V - dp[i][j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
int V,n;
int v[35],dp[20010];
int ans;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> V >> n;
    for(int i = 1;i <= n;i ++){
        cin>>v[i];
    }
    ans = V;
    for(int i = 1;i <= n;i ++){
        for(int j = V;j >= v[i];j --){
            dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
            ans = min(ans,V - dp[j]);
        }
    }
    cout<<ans<<endl;
    return 0;
}



Ritalin
16天前
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>nums;
void dfs(int t,int c){
    if(t == n + 1){
        if(c == m){
            for(int i = 0;i < nums.size();i ++)printf("%d ",nums[i]);
            puts("");
        }
    return;
    }
    else{
        nums.push_back(t);
        dfs(t + 1,c + 1);
        nums.pop_back();
        dfs(t + 1, c);
    }
}
int main(){
    cin >> n >> m;
    dfs(1, 0);
    return 0;
}



Ritalin
16天前
#include<bits/stdc++.h>
using namespace std;
vector<int> chosen;
char en[] = {' ','\n'};
int n;
void calc(int x){
    if(x == n + 1){
        for(int i = 0;i < chosen.size();i ++)
            printf("%d ",chosen[i]);
        puts("");
        return;
    }
    calc(x + 1);
    chosen.push_back(x);
    calc(x + 1);
    chosen.pop_back();
}
int main(){
    cin >> n;
    calc(1);
    return 0;
}



Ritalin
17天前
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,m;
pair<string, int>a[N];
int calc(int bit,int now){
    for(int i = 0;i < n;i ++){
        int x = a[i].second >> bit & 1;
        if(a[i].first == "AND")now &= x;
        else if(a[i].first == "OR") now |= x;
        else now ^= x;
    }
    return now;
}
int main(){
    cin >> n >> m;
    for(int i = 0;i < n;i ++){
        char str[5];
        int x;
        scanf("%s%d",str,&x);
        a[i] = make_pair(str,x);
    }
    int val = 0,ans = 0;
    for(int bit = 29; ~bit ; bit --){
        int res0 = calc(bit,0);
        int res1 = calc(bit,1);
        if(val + (1 << bit) <=m && res1 > res0){
            val += 1 << bit;
            ans += res1 << bit;
        }
        else ans += res0 << bit;
    }
    cout << ans << endl;
    return 0;
}


活动打卡代码 AcWing 3769. 移动石子

Ritalin
17天前
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n,d;
int a[N];
int getans(){
    int ans = a[0];
    for(int i = 1;d && i < n;i ++){
        int nd = min(a[i]*i,d);
        d -= nd;
        ans += nd/i;
    }
    return ans;
}
int main(){
    int T;
    cin>>T;
    while(T -- ){
        cin >> n >> d;
        for(int i = 0;i < n;i ++){
            cin >> a[i];
        }
        cout << getans() << endl;
    }
    return 0;
}


活动打卡代码 AcWing 91. 最短Hamilton路径

Ritalin
17天前
#include<bits/stdc++.h>
using namespace std;
int n,f[1 << 20][20];
int w[20][20];
int hamilton(int n,int weight[20][20]){
    memset(f,0x3f,sizeof f);
    f[1][0] = 0;
    for(int i = 1;i < 1 << n;i ++){
        for(int j = 0;j < n;j ++){
            if(i >> j & 1){
                int t = i ^ 1 << j;
                for(int k = 0;k < n;k ++){
                    if(t >> k & 1)f[i][j] = min(f[i][j], f[t][k] + w[k][j]);
                }
            }
        }
    }
    return f[(1 << n) - 1][n - 1];
}
int main(){
    cin>>n;
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < n;j ++)cin>>w[i][j];
    }
    cout<<hamilton(n,w)<<endl;
    return 0;
}


活动打卡代码 AcWing 90. 64位整数乘法

Ritalin
20天前
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL mul(LL a,LL b,LL p){
    LL ans = 0;
    while(b){
        if(b & 1)ans = (ans + a) % p;
        a = a * 2 % p;
        b >>= 1;
    }
    return ans;
}
int main(){
    LL a, b, p;
    cin >> a >> b >> p;
    cout<<mul(a, b, p)<<endl;
    return 0;
}


活动打卡代码 AcWing 423. 采药

Ritalin
27天前
朴素
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1010;
int n,m;
int v[N],w[N],f[N][M];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> m >> n;
    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]<<endl;
    return 0;
}
优化
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1010;
int n,m;
int v,w,f[M];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> m >> n;
    for(int i = 1;i <= n;i ++){
        cin >> v >> w;
        for(int j = m;j >= v;j --){
            f[j] = max(f[j],f[j - v] + w);
        }
    }
    cout<<f[m]<<endl;
    return 0;
}