Educational Codeforces Round 122 (Rated for Div. 2)，C，D

C

C

这道题就是普通的暴力，但是我在做的过程中第10组数据出现了数据溢出的错误

我的错误代码,我在vp的时候没觉得有什么问题

#include <iostream>
using namespace std;
#define int long long 
int t,k,w,a,hc,dc,hm,dm;
void solve()
{
    cin>>hc>>dc>>hm>>dm;
    cin>>k>>w>>a;
    bool yes=false;
    for (int i=0;i<=k;i++)
    {
        int h=hc+i*a;
        int d=dc+(k-i)*w;
        int cnt=(h+dm-1)/dm;
        if (cnt*d>=hm)
        {
            yes=true;
            break;
        }
    }
    if (yes)
    {
        cout<<"YES\n";
    }
    else 
    {
        cout<<"NO\n";
    }
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}

后来看的正确的代码，他换了一种表达方式，可能也有不同之处吧

正确代码

#include <iostream>
using namespace std;
#define int long long 
int t,k,w,a,hc,dc,hm,dm;
void solve()
{
    cin>>hc>>dc>>hm>>dm;
    cin>>k>>w>>a;
    bool yes=false;
    for (int i=0;i<=k;i++)
    {
        int h=hc+i*a;
        int d=dc+(k-i)*w;
        int cnt=(h+dm-1)/dm;
        int cnt2=(hm+d-1)/d;
        if (cnt>=cnt2)
        {
            yes=true;
            break;
        }
    }
    if (yes)
    {
        cout<<"YES\n";
    }
    else 
    {
        cout<<"NO\n";
    }
    return ;
}
signed main ()
{
    cin>>t;
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}

D

D

这一个题目大意就是有一个长度为n的数组，一开始全是1，我们需要把数组每一位变成题目里面给出的b[i],如果成功了，我们就可以获得c[i]的价值，问我们最多可以得到多少价值，变化是把a[i]=(a[i]+a[i]/x),x是任意数，这是一场操作，总共有k次操作（这一部分像不像一个背包问题，问总共有k空间，问背包最多可以获得的价值），不过我们还需要知道让1变成a[i]的“空间”是多大，我们可以看到a[i]的范围是1到1e3，那么这个问题就很好办了，我们可以提前暴力求出每一个1变成a[i]的“空间”大小，我这里用f[i]表示，求出这个，后面就是经典的背包问题了

#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;
const int maxn=1e6+10;
//#define int long long 
int t,n,k,f[maxn],a[maxn],b[maxn],dp[maxn];
void init()
{
    for (int i=1;i<=1000;i++)//记得一定要预处理，后面要求Min
    {
        f[i]=1e9;
    }
    f[1]=0;
    for (int i=1;i<=1000;i++)
    {
        for (int j=1;j<=i;j++)
        {
            f[i+i/j]=min(f[i+i/j],f[i]+1);
        }
    }
    return ;
}
void solve()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for (int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    for (int i=0;i<=k+10;i++)
    {
        dp[i]=0;
    }
    for (int i=1;i<=n;i++)//把这些看成是一个简单的背包问题，f[a[i]]是a[i]的空间，b[i]是a[i]的价值
    {
        for (int j=k;j>=f[a[i]];j--)
        {
            dp[j]=max(dp[j],dp[j-f[a[i]]]+b[i]);
        }
    }
    cout<<dp[k]<<'\n';
    return ;
}
signed main ()
{
    cin>>t;
    init();
    while (t--)
    {
        solve();
    }
    system ("pause");
    return 0;
}