头像

星瑞




离线:1天前


活动打卡代码 AcWing 426. 开心的金明

星瑞
2个月前

0/1背包写法

#include<bits/stdc++.h>
using namespace std;
int V,m;
int dp[30005];
int v[30];
int p[30];
signed main()
{
    cin>>V>>m;
    for(int i=1;i<=m;i++)cin>>v[i]>>p[i];
    for(int i=1;i<=m;i++)
    {
        for(int j=V;j>=v[i];j--)
        {
            dp[j] = max(dp[j],dp[j-v[i]]+v[i]*p[i]);
        }
    }
    cout<<dp[V]<<endl;
    return 0;
}


活动打卡代码 AcWing 417. 不高兴的津津

星瑞
2个月前
#include<bits/stdc++.h>
using namespace std;

signed main()
{
    int x,y;
    int ans=0,temp=0;
    for(int i=0;i<7;i++)
    {
        cin>>x>>y;
        int t = x+y;
        if(t>8&&t>temp)
        {
            ans = i+1;
            temp = t;
        }
    }
    cout<<ans<<endl;
    return 0;
}


活动打卡代码 AcWing 425. 明明的随机数

星瑞
2个月前
#include<bits/stdc++.h>
using namespace std;

signed main()
{
    int n;
    cin>>n;
    set<int>s;
    int x;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        s.insert(x);
    }
    cout<<s.size()<<endl;
    for(auto i:s)
    {
        cout<<i<<' ';
    }
    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

星瑞
2个月前

经典棋盘DP

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
int n,m;
int dp[maxn][maxn];
int a[maxn][maxn];
void solve()
{
    cin>>n>>m;
    memset(a,0,sizeof(a));
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])+a[i][j];
    cout<<dp[n][m]<<endl;
}
signed main()
{
    int t=1;
    cin>>t;
    while(t--)
        solve();
}


活动打卡代码 AcWing 420. 火星人

星瑞
2个月前

用STL里的next_permutation生成下一个排列就好了

#include<bits/stdc++.h>
using namespace std;

signed main()
{
    int n,m;
    vector<int>p;
    cin>>n>>m;

    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        p.push_back(x);
    }
    while(m--)
    {
        next_permutation(p.begin(),p.end());
    }
    for(int i=0;i<n;i++)
    cout<<p[i]<<' ';
    return 0;
}


活动打卡代码 AcWing 482. 合唱队形

星瑞
2个月前

最长上升子序列 复杂度O(nlogN)写法

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 5;
int n;
int dprise[maxn];
int dpdown[maxn];
int a[maxn];
int cnt;
int r1[maxn], r2[maxn];
signed main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > dprise[cnt])
        {
            dprise[++cnt] = a[i];
            r1[i] = cnt;
        }
        else
        {
            r1[i] = lower_bound(dprise + 1, dprise + 1 + cnt, a[i]) - dprise;
            dprise[r1[i]] = a[i];
        }
    }
    cnt = 0;
    for (int i = n; i >=1; i--)
    {
        if (a[i] > dpdown[cnt])
        {
            dpdown[++cnt] = a[i];
            r2[i] = cnt;
        }
        else
        {
            r2[i] = lower_bound(dpdown + 1, dpdown + 1 + cnt, a[i]) - dpdown;
            dpdown[r2[i]] = a[i];
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++)res = max(res, r1[i] + r2[i] - 1);
    cout << n - res << endl;
}


活动打卡代码 AcWing 1603. 整数集合划分

星瑞
2个月前
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
map<int,int>p;
int n;
int s1;
int sum=0;
int res;
int x;
int cnt;
signed main()
{
    IOS;
    cin>>n;
    cnt = n/2;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        p[x]++;
        sum+=x;
      //  cout<<sum<<endl;
    }
    for(auto i:p)
    {
        if(!cnt)break;
        if(cnt>i.second)
        {
            s1+=i.first*i.second;
            cnt-=i.second;
        }
        else
        {
            s1+=i.first*cnt;
            cnt = 0;
        }
      // cout<<s1<<endl;
    }
    if(n&1)cout<<1<<" ";
    else cout<<0<<" ";
    cout<<sum-2*s1<<endl;
}


活动打卡代码 AcWing 1353. 滑雪场设计

星瑞
2个月前
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n;
int res = inf;
int a[1005];
signed main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    for (int i = a[0]; i <= a[n - 1]; i++)
    {
        int l = i;
        int r = i + 17;
        int cnt = 0;
        for (int j = 0; j < n; j++)
        {
            int temp = 0;
            if (a[j] < l)
                temp = l - a[j];
            if (a[j] > r)
                temp = a[j] - r;
            cnt += (temp*temp);
        }
        //printf("l = %d  r = %d  cnt = %d\n", l, r, cnt);
        res = min(res, cnt);
    }
    cout << res << endl;
}


活动打卡代码 AcWing 1381. 阶乘

星瑞
2个月前

纸上推算一下发现不能单取个位,还需要更多位,理论上需要%1000000但是%1000也能过,既然能过,那就这样吧~

#include<iostream>
using namespace std;
int n;
int res = 1;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        res*=i;
        while(res%10 == 0)
            res/=10;
        res%=1000;
    }
    cout<<res%10<<endl;
}


活动打卡代码 AcWing 1371. 货币系统

星瑞
2个月前
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long dp[100005];
int a[30];
int cnt;
signed main()
{
    cin>>n>>m;
    dp[0] = 1;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=a[i];j<=m;j++)
        {
            dp[j]+=dp[j-a[i]];
        }
    }
    cout<<dp[m]<<endl;
}