B~E题解

B-lz的数字问题

思路：将 a，b 当成字符串，如果没有精确到小数点后 6 位就给它补上。怎么补？

  • 先看看有没有小数点，缺了就补上；

  • 然后找小数点的位置，没有精确到小数点后 6 位就给它添加 0 ；

  • 最后遍历从下标 0 开始到小数点后 6 位，如果 a[i] != b[i]，那就输出 NO。

#include<bits/stdc++.h>
using namespace std;

int t,n,m;
void solve(){
	string a,b;
	cin>>a>>b;
	if(a.find('.')==-1)a+='.';//find查找，没找到返回-1，找到了返回元素所在下标（string类型下标从0开始）
	if(b.find('.')==-1)b+='.';
	int index=b.find('.');//找小数点位置，找a的也行
	if(a.size()<index+6)//a的长度够不够到小数点后 6 位？不够就补'0'
		//string类型可以 + 或者 - 一个字符串，就是在原来的字符串末尾 加上 或者 减去 某一段字符串
		//string(number, 'ch')，构造一段长度为number，全为'ch'的字符串
		a+=string(index+6-a.size()+1,'0');
	if(b.size()<index+6)
		b+=string(index+6-b.size()+1,'0');
	//处理完了a、b就遍历找不同了
	for(int i=0;i<=index+6;i++)
	{
		if(a[i]!=b[i])
		{
			cout<<"NO";
			return ;
		}
	}
	cout<<"YES";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

C-lz的蛋挞问题

文字解析：

首先，最重要的前提是v [ i ] [ j ] == '.'，然后才有下文：

  1. 如果这个点的左边以及右边都是 '.' 而且下一行具体来说是v [ 1 ] [ j - 1 ]、v [ 1 ] [ j ]、v [ 1 ] [ j + 1 ] 3个位置，只要有一个是 'x' 就够了
  2. 如果这个点的左边以及下边是 '.'，而且v [ 1 ] [ j - 1 ] == 'x'
  3. 如果这个点的右边以及下边是 '.'，而且v [ 1 ] [ j + 1 ] == 'x'
  4. 最后一种情况就是 '.' 被 'x'包围的情况了

满足以上情况的任意一个或者多个，那这个点就满足题意，计数君++。

上面是第一行的情况，第二行的情况反一下就好了

图解：

第 1 种情况：

alt

第 2、3、4种情况

alt

//		https://ac.nowcoder.com/acm/contest/95937/C
//		分两行遍历，每一行对v[i][j] == '.'的位置进行判断
//		首先，最重要的前提是v[i][j] == '.'，然后才有下文：
//		如果这个点的左边以及右边都是 '.' 而且下一行（或者上一行）具体来说是v[1][j-1]、v[1][j]、v[1][j+1] 3个位置，只要有一个是'x'就够了
//		如果这个点的左边以及下边是 '.'，而且v[1][j-1] == 'x'
//		如果这个点的右边以及下边是 '.'，而且v[1][j+1] == 'x'
//		最后一种情况就是 '.'背 'x'包围的情况了


#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int t;
int n;
void solve(){
	cin>>n;
	vector<string> v(2);
	for(int i=0;i<2;i++)
		cin>>v[i];
	int cnt=0;
	for(int j=0;j<n;j++)
	{
		if(v[0][j]=='.' && ((j>0&&j<n-1&&v[0][j-1]=='.'&&v[0][j+1]=='.'&&(v[1][j-1]=='x'||v[1][j]=='x'||v[1][j+1]=='x'))
			||(j>0&&v[0][j-1]=='.'&&v[1][j]=='.'&&v[1][j-1]=='x')
			||(j<n-1&&v[0][j+1]=='.'&&v[1][j]=='.'&&v[1][j+1]=='x')
			||((j==0&&v[1][j]=='x'&&v[0][j+1]=='x')||(j==n-1&&v[1][j]=='x'&&v[0][j-1]=='x')||(j>0&&j<n-1&&v[0][j-1]=='x'&&v[0][j+1]=='x'&&v[1][j]=='x'))))
		{
			cnt++;
		}
	}
	for(int j=0;j<n;j++)
	{
		if(v[1][j]=='.' && ((j>0&&j<n-1&&v[1][j-1]=='.'&&v[1][j+1]=='.'&&(v[0][j-1]=='x'||v[0][j]=='x'||v[0][j+1]=='x'))
			||(j>0&&v[1][j-1]=='.'&&v[0][j]=='.'&&v[0][j-1]=='x')
			||(j<n-1&&v[1][j+1]=='.'&&v[0][j]=='.'&&v[0][j+1]=='x')
			||((j==0&&v[0][j]=='x'&&v[1][j+1]=='x')||(j==n-1&&v[0][j]=='x'&&v[1][j-1]=='x')||(j>0&&j<n-1&&v[1][j-1]=='x'&&v[1][j+1]=='x'&&v[0][j]=='x'))))
		{
			cnt++;
		}
	}
	cout<<cnt<<endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	t = 1;
	while(t--){
		solve();
	}
	return 0;
}

D-lz的染色问题

并查集

将有重复查看的位置放到同一个集合，最后遍历集合，如果该集合的大小 > 0，说明这个集合里的元素被查看过，计算集合里的元素个数（重复的也算）以及出现最多次数的数量，ans += cnt - Max；

#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[200005];
int f[200005];

int find(int a)
{
	if(a!=f[a])
	{
		f[a]=find(f[a]);
	}
	return f[a];
}

void Union(int a, int b)
{
	int fa=find(a);
	int fb=find(b);
	if(fa!=fb)
	{
		f[fa]=fb;
	}
}

void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		f[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		Union(l,r);
	}
	vector<vector<int>> v(n+1);
	for(int i=1;i<=n;i++)
	{
		v[find(i)].push_back(a[i]);
	}  
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		if(!v[i].empty())
		{
			map<int,int>mp;
			int mx=0,cnt=0;
			for(int it:v[i])
			{
				mp[it]++;
			}
			for(auto it:mp)
			{
				mx=max(mx,it.second);
				cnt+=it.second;
			}
			ans+=cnt-mx;
		}
	}
	cout<<ans<<endl;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--)
		solve();
}

E-lz的括号问题

  • 首先，括号匹配问题要想到栈；
  • 然后每个编号的答案为 n - len（括号总对数 - 当前栈的长度）。

为什么是这样呢？是我推出来的，根据样例 1 以及自己写的一个样例：( ( ) ( ) ) ( ( ) )，根据题意我们知道这个样例答案为 4 3 3 4 3。对这两个样例进行操作：遍历字符串，模拟括号的入栈出栈，我们就会发现答案

#include <bits/stdc++.h>
using namespace std;

int n;
int len=0;//记录栈长度
int ans[100005];
void solve()
{
    string s;
    cin>>n>>s;
    int id=1;//id为括号编号
    for(int l=0,r=0;r<s.size();r++)
    {
        if(s[r]=='(')//左括号入栈
        {
            len++;//我们不用定义一个栈，只需要知道它的长度就行，栈中默认存左括号（这个栈是不存在的，想像一下就好）
            ans[id]=n-len;//当前id的答案就是括号总对数 减去 栈的当前长度
            id++;//编号+1
        }
        else if(s[r]==')' && len>0)//出栈
        {
            if(len>0)len--;
            else 
            {//如果栈为空了，那就没有可分配的左括号，输出-1
                cout<<-1;
                return ;
            }
        }
    }
    if(len>0)//如果遍历完了发现栈不为空，说明还有括号没有匹配上，输出-1
    {
        cout<<-1;
        return ;
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
}
int main()
{
    solve();
}

如果对题解有疑问，可以评论或者私信我。

如果题解对你有帮助，可以给我点个赞吗，谢谢！