源代码:ACM/OpenjudgeNow/Codeforces at master · abmcar/ACM (github.com)

A. Div. 7

在这里插入图片描述

题目大意:

在这里插入图片描述

思路:

对于任意一个数,在只更改最后一位的情况下,必定一种方式使得%7 == 0

代码:

void work()
{
    cin >> n;
    if (n % 7 == 0)
    {
        cout << n << endl;
        return;
    }
    for (int i = 0; i <= 9; i++)
    {
        if ((n / 10 * 10 + i) % 7 == 0)
        {
            cout << (n / 10 * 10 + i) << endl;
            break;
        }
    }
}

B. Minority

在这里插入图片描述

题目大意:

在这里插入图片描述

思路:

  • 如果0和1的数量相同,则任意取一个大小为n-1的区间,可以删掉nums[0]-1个字符
  • 如果不同,则选整个区间,可以删掉min(nums[0],nums[1])个字符

代码:

void work()
{
    cin >> s;
    vector<int> nums(3);
    for (char it : s)
        nums[it-'0']++;
    if (nums[0] == nums[1])
        cout << nums[0]-1 << endl;
    else 
        cout << min(nums[0],nums[1]) << endl;
}
     

C. Kill the Monster

在这里插入图片描述

题目大意:

在这里插入图片描述

思路:

对于固定的血量和攻击力,我们只需要判断能挨的最大次数和怪物能挨的最大次数即可

如果大于等于或者攻击力大于怪物血量,则可以战胜

因此我们可以枚举升级血量的次数为i,则升级攻击力的次数为(k-i),用升级后的数值判断即可

代码:

void work()
{
    cin >> hc >> dc >> hm >> dm;
    cin >> k >> w >> a;
    for (int i = 0; i <= k; i++)
    {
        int nowHealth = hc + a * i;
        int nowDamage = dc + w * (k - i);
        if (((nowHealth + dm - 1LL) / dm >= (hm + nowDamage - 1LL) / nowDamage) || (nowDamage >= hm))
        {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << Endl;
}

D. Make Them Equal

在这里插入图片描述

题目大意:

在这里插入图片描述

思路:

注意到刚开始所有元素=1,试想一下如果我们知道1到任意数的代价,则这个问题就转变成了一个01背包

因此我们使用dp的方式预处理出代价,pre[i + i / j] = ((pre[i + i / j] < (pre[i] + 1)) ? pre[i + i / j] : pre[i] + 1);之后按照01背包求解即可

代码:

void work()
{
    vector<int> b, c, f;
    cin >> n >> k;
    b.resize(n + 1);
    c.resize(n + 1);
    f.resize(k + 1);
    int temp = 0;
    int tot = 0;
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        cin >> c[i], tot += c[i];
    for (int i = 1; i <= n; i++)
        temp += pre[b[i]];
    if (k >= temp)
    {
        cout << tot << endl;
        return;
    }
    for (int i = 1; i <= n; i++)
        for (int j = k; j >= pre[b[i]]; j--)
            f[j] = (f[j] > (f[j - pre[b[i]]] + c[i])) ? f[j] : (f[j - pre[b[i]]] + c[i]);
    cout << f[k] << endl;
}

signed main()
{
    Buff;
#ifdef Debug
    freopen("temp.in", "r", stdin);
    freopen("temp.out", "w", stdout);
#endif
    pre[1] = 0;
    for (int i = 1; i <= 1e3; i++)
        for (int j = 1; j <= i; j++)
            pre[i + i / j] = ((pre[i + i / j] < (pre[i] + 1)) ? pre[i + i / j] : pre[i] + 1);
    cin >> t;
    while (t--)
        work();
    return 0;
}