写在前面
排名 ：136/1823
过题数：2/3
同样是1.29的比赛，现在2.13来补，这是一场年前接近过年的比赛，这个时候都还在打比赛呢哈哈，其实除夕当晚的cf我也打了，之前有些总结，好吧其实是没什么年味了这个原因也占一部分...
这次比上次肯定是有进步的，毕竟多过了一倍的题呢，第二题很妙，是一个结论我当时还询问了图论大师——曹佬，第三题确实更妙！值得重开写一篇，我还是写在这里吧hh，总结总结
没能做出第三题来，第三题确实是一个好题，希望下次不能再做不出啦！加油！
A.处理字符串（签到）
题意
题目链接：AcWing 4215. 处理字符串 - AcWing
给出一个字符串，元音(多包括'y')不输出，其他输出前加一个'.'，注意大写要变为小写
思路
模拟
代码
inline void Case_Test()
{
cin>>s;
for (int i=0;i<s.length();i++)
if (isupper(s[i])) s[i]=char(s[i]+32);
for (auto i:s)
if (i=='a'||i=='o'||i=='y'||i=='e'||i=='u'||i=='i')
continue;
else cout<<"."<<i;
}
B.图中的环（基环树/图论）
题意
题目链接：AcWing 4216. 图中的环 - AcWing
给定一个 $n$ 个点 $m$ 条边的无向图。
点的编号从 $1$ 到 $n$。
图中不含重边和自环。
请你对给定图进行判断，如果该图是一个有且仅有一个环的连通图，则输出YES，否则输出NO。
思路
给出n和m，判断是否只有一个环，并且！！是否是连通图（因为判联通wa了一发）
结论：只有一个环的，其他都是树的，叫做基环树，这个在之前也写过：【基环树+思维】AcWing 1738.蹄球——每日一题2.6 - CarryNotKarry。基环树的特点就是n个点n条边，我们这么想一下，假如给你n个点和n-1条边，这个时候就是一颗树，在此基础上多加一条边，这个时候无论如何都会形成一个环，仅仅就一个环，所以按照这个我们直接判断是否n和m相等即可
记住！！判断是否联通！用dfs遍历一遍就好了
代码
inline void dfs(int x)
{
vis[x]=x;
for (int i=head[x];i;i=edge[i].next)
{
if (!vis[edge[i].to])
dfs(edge[i].to);
}
}
inline void Case_Test()
{
cin>>n>>m;
for (int i=1;i<=m;i++)
{
cin>>x>>y;
add(x,y);add(y,x);
}
dfs(1);
bool boo=true;
for (int i=1;i<=n;i++) if (vis[i]==false) boo=false;//这里也可以扫的时候统计cnt，最后判断cnt==n?即可
if (n==m&&boo) cout<<"YES";
else cout<<"NO";
}
C.机器人移动（二分+前缀和+双指针）
题意
题目链接：AcWing 4217. 机器人移动 - AcWing
在一个无限大的二维平面上有一个机器人。
初始时，机器人位于点 $(0,0)$。
机器人可以执行四种行动指令：
U— 从 $(x,y)$ 移动到 $(x,y+1)$；
D— 从 $(x,y)$ 移动到 $(x,y−1)$；
L— 从 $(x,y)$ 移动到 $(x−1,y)$；
R— 从 $(x,y)$ 移动到 $(x+1,y)$。
给定一个长度为 $n$ 的指令序列，指令编号 $1\sim n$，机器人将按顺序依次执行序列中的每个行动指令。
我们希望机器人最终抵达目标地点 $(a,b)$。
为了达成这一目的，我们可能需要对指令序列进行修改。
每次修改可以选择其中一个指令，并将其替换为四种指令之一。
注意，只能对序列中的指令进行替换，不得随意删除指令或添加额外指令。
不妨设经过修改的指令中，编号最小的指令编号为minID，编号最大的指令编号为maxID。
我们定义修改成本为maxID−minID+1。
例如，将RRRRRRR修改为RLRRLRL，则编号为 $2,5,7$ 的指令经过了修改，修改成本为 $7−2+1=6$。
请你计算，为了使得机器人能够最终抵达目标点 $(a,b)$，所需花费的最小修改成本。
如果不需要对序列进行修改，则成本为 $0$。
思路
二分答案，答案要求的就是修改序列的最小长度
check的思路是：
依次枚举长度len的进行修改的区间(也就是题目中的修改成本)，
对于每一个区间，求出除去修改区间以外的序列还需要多少dx,dy来到达目的地(x,y)。
对于dx,dy, 首先需要满足 len >= abs(dx)+abs(dy) ,
其次如果有冗余的长度，即 len>abs(dx)+abs(dy) 的情况下，我们需要用两个相反的指令来抵消，
所以还需要满足 (len-abs(dx)-abs(dy))%2==0，也就是需要同奇偶，
另外答案为0和-1的时候先判断一下。
具体思路详见代码及注释
我们把每一次操作相当于一个向量，我们用前缀和的思想进行向量的叠加，同前缀和一样，我们最后求区间的移动的时候就可以用$O(1)$的时间复杂度来求的，我们二分长度，然后枚举长度的起点，实际上这个区间都枚举出来了，我们可以用$O(1)$的方法求得前后除了中间枚举（可修改）得区间其他的两个区间的位置，我们在判断是否能够与后面的区间“接上”，也就是是否能满足那个范围。
注意：我们如果还有冗余的步骤，我们可以来回走，但是需要判断一下奇偶性，需要同奇偶
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, X, Y;
int sx[N], sy[N];
char str[N];
bool check(int len)
{
for (int i = 1; i + len - 1 <= n; i ++ )//循环去移动，判断改动是否可以达到目的地
{
int j = i + len - 1;
int x = sx[n] - (sx[j] - sx[i - 1]);
int y = sy[n] - (sy[j] - sy[i - 1]);
int d = abs(x - X) + abs(y - Y);
if (d <= len && (d - len) % 2 == 0)
return true;
}
return false;
}
int main()
{
scanf("%d", &n);
scanf("%s", str + 1);
scanf("%d%d", &X, &Y);
for (int i = 1; i <= n; i ++ )
{
sx[i] = sx[i - 1], sy[i] = sy[i - 1];
char c = str[i];
if (c == 'U') sy[i] ++ ;
else if (c == 'D') sy[i] -- ;
else if (c == 'L') sx[i] -- ;
else sx[i] ++ ;
}//前缀和处理
if (abs(X) + abs(Y) > n || (X + Y - n) % 2) puts("-1");
else
{
int l = 0, r = n;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;//二分长度
else l = mid + 1;
}
printf("%d\n", r);
}
return 0;
}
/*作者：yxc
链接：https://www.acwing.com/activity/content/code/content/2464653/
来源：AcWing*/
文章评论