Codeforces Educational Round 122(Rated for Div.2)比赛总结 （rating+77）

除夕夜的比赛，除了高三高四那个除夕还在学习，这是第三次了吧，上大学之后的第一次。感觉年味越来越没有了，最有年味的一次是回我妈老家新华槎溪，大家坐在一起吃着东西聊着天，孩子一起玩耍放鞭炮，现在在城里面炮也不是很多，但是相比于其他地方还算可以的，出去散了个步，打了一下牛客的除夕比赛，再洗个澡打cf，唉，说多了。

这次比赛有个教训，就是类似于这句话The sum of k over all test cases does not exceed 2·10^5，计算时间复杂度的时候，往往能够枚举这个k，因为一共k有限，而不是每一个测试样例的k都是2e5

做题做的太慢了，想多了有的时候

A.Div 7

题意

给你一个数字n(10\leq n\leq999)，求改变n的位数最小次数的能整除7的数，如果有多就任意输出

思路

既然放在A题且数据不大，那么我们就可以枚举，样例给出了n=377然后输出的是777，我们还是不这样做，想到另外一种方法在n附近枚举找最近的满足条件的数。

那怎么样判断改变位数最小这个条件呢？因为数据太小，我就用的一个函数一位一位去判断...

其他方法：

思路： 能被7整除，方法有很多种，因为要求最小次数，那么我们特判能被7整除就输出0否则，暴力最后一位能被7整除即可，然后返回1，必定有答案。

所以只需要暴力枚举最后一位，x=n/10存前面两位..不需要左找右找

代码

inline int f(int x)
{
    int y=n,cnt=0;
    while (y)//这里要while n，我因为减x而wa了一发。。
    {
        if (x%10!=y%10) cnt++;
        x/=10;y/=10;
    }
    return cnt;
}
inline void Case_Test()
{
    cin>>n;
    x=n;
    if (x%7==0) {cout<<x<<endl;return;}
    while (x>=0&&x%7!=0)
    {
        x--;
    }
    ans1=x;
    x=n;
    while (x<=999&&x%7!=0)
    {
        x++;
    }
    ans2=x;
    if (f(ans1)<=f(ans2)) cout<<ans1<<endl;//判断一下，相等随便输出
    else cout<<ans2<<endl;
}

B.Minority

题意

给出一个字符串s，求s的子串使得移除较小的那个最大的个数，比如00011111，0有3个1有5个，这样就是3

思路

不难，当时猜的结论，试了一试，直接从头判断到尾，贪心的思想直接cnt计数，然后边计边取max_ans

代码

inline void Case_Test()
{
    cin>>s;
    n=s.length();
    ans=-1;
    cnt0=cnt1=0;
    for (int i=0;i<n;i++)
    {
        if (s[i]=='0') cnt0++;
        else cnt1++;
        if (cnt1>cnt0) ans=Max(ans,cnt0);
        if (cnt0>cnt1) ans=Max(ans,cnt1);
    }
    cout<<ans<<endl;
}

C.Kill the Monster

题意

你需要去打败怪兽，每个人都有自己的血量H和攻击力D，是回合制，你先攻击，他扣你的攻击力值，然后他攻击你，你扣他的攻击力值。这时候你有金币k可以升级，花费一个金币可以使你的攻击力上升w或者血量增加a，问能否打败。

思路

我一直在推不等式，想推出一个关于一个未知数的式子，然后用判别式去判断，但是实在是太麻烦了，后面一看发现就是我之前说的那个，k是可以枚举的（我还想过二分。。）所以就枚举花x金币在血量上，花y金币在攻击力上，[x,y]={[0,k],[1,k-1]...[k-1,1],[k,0]}。

代码

inline int check(int x,int y)
{
    int H=hc+x*a,D=dc+y*w;//升级
    return ceil((double)hm/D)<=ceil((double)H/dm);
}
string s;
inline void Case_Test()
{
    cin>>hc>>dc>>hm>>dm>>k>>w>>a;
    for (int i=0;i<=k;i++)
        if (check(i,k-i)) {cout<<"YES"<<endl;return;}//枚举
    cout<<"NO"<<endl;
}

D. Make Them Equal

题意

给出长度为n的b,c两数组，和最多k次操作，每次消耗1次操作是你可以选择i(1\leq i\leq n)和x(x>0)让a_i增加a_i=a_i+\lfloor \frac{a_i}{x} \rfloor。如果a_i=b_i的话，就能得到c_i的奖励，求最大奖励是多少。

思路

一开始列了一个表，准备去找关系，但是发现数字并不大，b_i的最大值是10^3，所以直接循环递推过去，当时感觉应该是有规律的，直到最后选择暴力求的时候又花了好多时间，烦死了。

也可以打表..这里不重要，所以每次给出的数值我们都能得到花费，花费其实最大才12...所以给出的k最大是10^6用不完，我还在想时间复杂度呢，01背包时间复杂度是O(nk)，没优化前的。

所以这里就用01背包就可以了（我还想了优化，又花费了好久）

代码

inline void init()
{
    int MAXN=1007;
    mem(a,0x3f);
    a[1]=0;
    for (int x=1;x<=MAXN;x++)
        for (int i=1;i<=x;i++)
            if (a[x+x/i]>a[x]+1) 
                a[x+x/i]=a[x]+1;
}
int f[N];
inline void Case_Test()
{
    cin>>n>>k;
    mem(f,0);
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        w[i]=a[x];
    }
    for (int i=1;i<=n;i++)
        cin>>v[i];
    m=Min(k,15*n);//1e6的数据肯定又剩下的，这里需要优化，不然两层循环上天
    for(int i = 1; i <= n; i++) 
        for(int j = m; j >= w[i]; j--) 
            f[j] = max(f[j], f[j-w[i]]+v[i]);//01背包
    cout<<f[m]<<endl;
}

祝大家虎年吉祥！万事如意！

2022/2/2/2:03