[数据结构与算法]Acwing 第 36 场周赛

T3读假题了，太菜了，掉大分，没有AK。。。。

1.处理字符串—模拟

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
signed main()
{
    string s;
    cin>>s;
    string cs="aeiouy";
    for(auto c:s)
    {
        c=tolower(c);
        if(cs.find(c)==-1)
            cout<<"."<<c;
    }
}

2.图中的环—并查集+结论

#include <iostream>
using namespace std;
const int N = 110;
int n,m,k;
int p[N];
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)p[i]=i;
    int cnt=0;
    while (m -- )
    {
        int a,b;
        cin>>a>>b;
        int pa=find(a),pb=find(b);
        if(pa==pb)cnt++;
        else p[pa]=pb;
    }
    int cnt2=0;
    for(int i=1;i<=n;i++)if(p[i]==i)cnt2++;
    if(cnt==1&&cnt2==1)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    
}

3.机器人移动----二分

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 200010,mod=1e9+7;
int n;
int st,ed;
char s[N];
int sx[N],sy[N]; 
bool check(int x)
{
	for(int i=1;i+x-1<=n;i++)
	{
		int a=st-(sx[n]-sx[i+x-1]+sx[i-1]);
		int b=ed-(sy[n]-sy[i+x-1]+sy[i-1]);
		if(x>=abs(a)+abs(b))return true;
	}
	return false;
}
signed main()
{
	cin>>n;
	scanf("%s",s+1);
	cin>>st>>ed;
	for(int i=1;i<=n;i++)
	{
		sx[i]=sx[i-1];
		sy[i]=sy[i-1];
		if(s[i]=='L')sx[i]--;
		else if(s[i]=='R')sx[i]++;
		else if(s[i]=='U')sy[i]++;
		else if(s[i]=='D')sy[i]--;
	}
	int d=abs(st)+abs(ed);
    if(n<d||(n&1)!=(d&1))
    {
        cout<<-1<<endl;
        return 0;
    }
    int l=0,r=n;
    while(l<r)
    {
    	int mid=l+r>>1;
    	if(check(mid))r=mid;
    	else l=mid+1;
	}
	cout<<r<<endl;
}