AcWing周赛38

写在前面

排名：40/1701
过题数：3/3 AK！
终于赶上进度了！！现在是2022-02-14 02:08:44 星期一，这场比赛时间是2.12，赶紧总结完上床睡觉哈哈，当然肯定会认真总结的！
第二次AK，而且这回排名来到了40名！历史新高！
我要把表打出来！！一发没wa，全是一发过hhh

A.删点（签到）

题意

题目链接：AcWing 4299. 删点 - AcWing

在一个二维平面上有 $n$ 个点，其中没有任何一个点位于 $y$ 轴上。
请你判断这些点中是否存在一点满足，删除该点后，剩余的所有点都在 $y$ 轴的同一侧。

思路

直接模拟吧，统计两边个数，注意可能一边都没有，这时候任意删另一边一个也是属于正确的

代码

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x>>y;
        if (x>0) cnt1++;
        else cnt2++;
    }
    if (cnt1<=1||cnt2<=1) cout<<"Yes";//注意'≤'
    else cout<<"No";
}

B.两种操作(BFS/贪心)

题意

题目链接：AcWing 4300. 两种操作 - AcWing
给出$n$和$m$，有两种操作：1）n=n*2 ；2）n--。问$n$最少经过多少次操作能够达到$m$
数据范围：$1≤n,m≤10000$

思路

1）BFS

第一反应就是之前atc里面好像是abc一道题吧，直接BFS，BFS能保证每次最小，而且数据范围也不大,如果n>m那么直接统计ans=n-m，一开始的话就直接输出，在BFS里面的话就维护ans，减一和乘二的操作还是在常规BFS里面，并且用vis数组来标记，数字只能出现一次，因为前面一旦出现过，后面的数字操作次数不可能比之前的要小，因为BFS就是这样的，从小到大来的。

2）贪心

反向思考 从$m$的角度思考
如果$n>m$ 必定是最小需要$n-m$步
思路：
$n>m$,最优方法是一直减$1$，返回$n-m$；
$n<m$分组讨论：
1.$m$为奇数，让$m+1$然后除以$2$；
2.当$m$为偶数，直接除以$2$

代码

1）BFS

inline void Case_Test()
{
    cin>>n>>m;
    if (n>=m) {cout<<n-m;return;}
    vis[n]=1;ans=inf;
    q.push({n,0});
    while (!q.empty())
    {
        v=q.front().val;s=q.front().step;q.pop();
        tmp=v*2;
        if (!vis[tmp])
        {
            vis[tmp]=1;
            if (tmp>=m) ans=Min(tmp-m+s+1,ans);
            else q.push({tmp,s+1});
        }
        tmp=v-1;
        if (!vis[tmp]&&tmp>1)
        {
            vis[tmp]=1;
            q.push({tmp,s+1});
        }
    }
    cout<<ans;
}

2）贪心

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20010;
int n, m;
int main()
{
    cin >> n >> m;
    int res = 0;
    while (m != n)
    {
        if (m < n) m ++ ;
        else if (m & 1) m ++ ;
        else m /= 2;
        res ++ ;
    }
    cout << res << endl;
    return 0;
}
/*作者：yxc
链接：https://www.acwing.com/activity/content/code/content/2575480/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/

C.截断数列（枚举）

题意

题目链接：AcWing 4301. 截断数列 - AcWing
给出长度为$n$的数列$a$，要求恰好分为$k$段，让这$k$段每次的和的大小相等，问是否存在这样的$k$

思路

一开始我sb了，都有点小放弃了，但是我们可以注意到！！整个数列的和$sum=\sum a_i$我们可以读入时候知道，然后我们去枚举k，如果sum能够被k整除，那么就是有可能满足条件，对吧？比如和为21，那么k=3是有可能的，而k=4是不可能的，直接continue，这个时候直接枚举k就可以了呀...我还想着去枚举每段的和...实属是我sb了...

代码

inline void Case_Test()
{
    cin>>n>>s;
    for (int i=0;i<s.length();i++)
    {
        a[i+1]=s[i]-'0';
        sum+=a[i+1];
    }
    for (int k=2;k<=n;k++)
    {
        if (sum%k==0)
        {
            x=sum/k;
            int tmp=0;
            check=true;
            for (int i=1;i<=n;i++)
            {
                tmp+=a[i];
                if (tmp==x) tmp=0;//等于就下一段
                if (tmp>x) check=false;//大于了肯定就不行了
            }
        }
        if (check) {cout<<"YES";return;}
    }
    cout<<"NO";
}