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