CarryNotKarry

  • 首页
  • 语言学习
    • C++程序设计
    • 汇编语言
    • Python
  • 比赛总结
  • ACM-ICPC
    • 动态规划
    • 字符串
    • 搜索
    • 数学
    • 数据结构
    • 图论
    • 计算几何
    • 杂项
  • 分享
  • 上课内容
  • 其他
Carry
CUGBACMer/皇马球迷/C罗人迷
  1. 首页
  2. 比赛总结
  3. 正文

AcWing周赛38

2022年2月14日 385点热度 0人点赞 0条评论

写在前面

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

得分 罚时 A B C
3 0:43:33 0:02:06 0:13:27 0:28:00

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";
}
标签: AcWing BFS 枚举 贪心
最后更新:2022年2月20日

Carry

来自于湖南长沙

点赞
< 上一篇
下一篇 >

文章评论

取消回复
标签
AcWing BFS 枚举 贪心
文章目录
  • 写在前面
  • A.删点(签到)
    • 题意
    • 思路
    • 代码
  • B.两种操作(BFS/贪心)
    • 题意
    • 思路
    • 代码
  • C.截断数列(枚举)
    • 题意
    • 思路
    • 代码
其他文章

Carry爱三进制题解

【区间DP】POJ2955.Brackets

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

汇编语言 实验四 子程序结构

汇编语言 实验三 循环结构和分支结构程序设计

C++程序设计

【基环树+思维】AcWing 1738.蹄球——每日一题2.6

AtCoder Beginner Contest 238比赛总结

【算法学习】线性基

【线性基】[BJWC2011]元素题解

From Carry
  • 在下不才,本博客也是为了记录自己的成长,并非成为非常专业的博客。
  • 如果有能够帮助你的地方是我最大的荣幸,一起加油吧!

ECNU-My love

THEME KRATOS MADE BY VTROIS