写在前面
排名：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.删点（签到）
题意
在一个二维平面上有 $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";
}