本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-06 20:00:52

A题 Div. 7

签到题，$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
int n;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n%7==0)
        {
            cout<<n<<endl;
            continue;
        }
        int zh=n%10;\/\/最后一位
        int m=n%7;
        if(zh-m>=0)
        {
            cout<<n-m<<endl;
            continue;
        }
        if(zh-m<0)
        {
            cout<<n-m+7<<endl;
        }
    }
 \/\/   system("pause");
    return 0;
}

B题 Minority

题目大意：

给定一个数组。可以随便选一个子区间执行这样的操作：
一、如果这个子区间 $0$ 和 $1$ 的数量相同，不执行操作
二、如果这个子区间 $0$ 和 $1$ 的数量不同，若 $0$ 的数量严格小于 $1$ ，那么删除子区间所有的 $0$ ，反之删除子区间所有的 $1$ 。
求最多能删除的元素个数

题目解法：

第一眼看到，只能想到 $O(n^2)$的暴力（我太菜了）
再想想，可以发现可以贪心的选择整个数组执行操作。这样就能保证删除元素最多了。
如果 $0$ 和 $1$ 数量相等呢？只需要从区间头部或尾部随便删去一个元素就行了。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
int n;
const int maxn=2e5+5;
char a[maxn];
int zero;
int one;
int ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        zero=one=0;
        scanf("%s",a+1);
        n=strlen(a+1);
        for(int i=1;i<=n;i++)
        {
            if(a[i]=='0')zero++;
            if(a[i]=='1')one++;
        }
        ans=min(zero,one);
        if(zero==one)ans--;
        printf("%d\n",ans);
    }
 \/\/   system("pause");
    return 0;
}

C题 Kill the Monster

题目意思：

一个角色与怪物决斗。
角色有以下两个属性：
1.$hc$：生命值
2.$dc$：攻击力
怪物有以下两个属性：
1.$hm$：生命值
2.$dm$：攻击力

决斗方式：
1.角色向怪物发动攻击，怪物生命值掉了 $dc$。
2.怪物向角色发动攻击，角色生命值掉了 $dm$。
如此循环，直到其中一方的生命值小于等于 $0$，另一方获胜。

决斗开始之前，角色可以购买装备，角色有 $k$ 枚硬币，一个硬币可以使生命值增加 $a$，也可以使攻击力增加 $w$。
求如果以最优的方式购买装备，角色是否能打败怪物。

有 $t$ 组数据，$1 \le t \le 5 \cdot 10^4$。

题目分析：

看到这道题，可以发现测试数据组数很多，可能需要 $O(1)$ 回答每组询问，但是，既然是要求最优方案，难以做到 $O(1)$ 回答询问。
此时可以发现，题目里面说了，所有测试数据的 $k$ 之和不超过 $2 \cdot 10^5$。所以直接枚举分配给生命值和角色的硬币数量，对于枚举到的每组方案显然可以 $O(1)$ 判断角色是否可以胜利，如果可以胜利输出 YES，如果所有方案都不可行输出 NO。（我到比赛结束前十几分钟才发现这个最后没时间写了） 这道题就做出来了。

注意事项：

如果就这样写，将会在第 $13$ 个测试点 WA 掉，原因是神仙 hacker 造的数据会爆掉 long long，所以在 C++20 下开 __int128 即可。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
signed main()
{
    scanf("%lld",&t);
    int hc,dc,hm,dm,k,w,a;
    while(t--)
    {
        scanf("%lld%lld",&hc,&dc);\/\/角色的生命和攻击力
        scanf("%lld%lld",&hm,&dm);\/\/怪物的生命和攻击力
        scanf("%lld%lld%lld",&k,&w,&a);
        bool flag=0;
        for(int i=0;i<=k;i++)
        {
            int gjl=(k-i)*w+dc;\/\/新的攻击力
            int sd=hm\/gjl-1;\/\/杀死怪物时受到伤害的次数
            if(hm%gjl>0)sd++;
            if((__int128)hc+(__int128)i*(__int128)a>(__int128)sd*(__int128)dm)
            {
                printf("YES\n");
                flag=1;
                break;
            }
        }
        if(!flag)printf("NO\n");
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

D题 Make Them Equal

题目意思：

有 $3$ 个大小为 $n$ 的数组，$a$，$b$ 和 $c$
给定 $a$ 和 $b$。$a$ 数组初始所有值都为 $0$。

有 $k$ 次操作，每次操作可以过程如下：

1. 选择两个整数 $i$ 和 $x$ $(1 \le i \le n,x \ge 1)$
2. $a_i$ 变为 $a_i + \frac{a_i}{x}$

若 $a_i = b_i $， 则获得 $c_i$ 的分数。
求经过 $k$ 此操作最多能获得的分数。

数据范围：

有 $t$ 组数据 $(1 \le t \le 100)$。
$1 \le n \le 10^3$。
$1 \le b_i \le 10^3$。
$1 \le c_i \le 10^6$。

题目分析：

定义一个数组 $dis$，$dis_i$ 代表$1 \rightarrow i$，最小转换次数，由于 $n$ 特别小，可以 $O(n^2)$ 预处理。
定义一个数组 $f$ ，$f_i$ 代表操作次数为 $i$ 时最多能获得多少分。
可以发现 $1$ 到 $10^3$ 次方的范围内，最多转换 $12$ 次。总共操作数就是 $min(12 \cdot n,k)$。超过了 $12 \cdot n$ 就无意义了。
对于每组询问跑 dp 处理 $f$ 数组。
设 $p = min(12 \cdot n,k)$
最终答案就是 $f_p$。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int t;
int n,k;
int b[maxn];
int c[maxn];
int dis[maxn];\/\/从1到i最少多少步
int f[maxn*12];\/\/操作数量为i时最大收益
int main()
{
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[1]=0;
    for(int i=1;i<=maxn;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dis[i+i\/j]=min(dis[i+i\/j],dis[i]+1);
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&c[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=min(k,12*n);j>=dis[b[i]];j--)
            {
                f[j]=max(f[j],f[j-dis[b[i]]]+c[i]);
            }
        }
        printf("%d\n",f[min(k,12*n)]);
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}