How to AK Educational Codeforces Round 122 (1633)

__vector__ · 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 次操作，每次操作可以过程如下：

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

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

数据范围：

有 t 组数据 (1 \le t \le 100)。

$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;
}