2024年美团春招第一场笔试（技术）_小美拿到了一个 n n的矩阵,其中每个元素是 0 或者 1。 小美认

1.

小美的平衡矩阵

小美拿到了一个n∗n的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个i∗i的完美矩形区域。你需要回答1≤i≤n的所有答案。

解法：很明显，i若为奇数，则不可能是完美的。

对于偶数，枚举每个面积为 i*i的矩阵，判断一下这个矩阵的前缀和是不是面积的一半，是的话则符合题意，这题考察一个二维前缀和。

#include<iostream>
 
using namespace std;
const int N = 210;
 
int g[N][N], s[N][N];
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string str;
        cin >> str;
        int k = 0;
        for (int j = 1; j <= n; j++) {
            g[i][j] = str[k++] - '0';
            s[i][j] = g[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
 
    for (int i = 1; i <= n; i++) {
        if (i % 2) {
            cout << "0" << '\n';
            continue;
        }
        int res = 0;
        for (int j = i; j <= n; j++) {
            for (int k = i; k <= n; k++) {
                int sum = s[j][k] - s[j][k - i] - s[j - i][k] + s[j - i][k - i];
                if (sum == (i * i) / 2)res++;
            }
        }
        cout << res << '\n';
    }
}

2.

2.

小美的数组询问

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间[l,r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？
共有q次询问。

解法：先把非0的数累加起来，然后接着想，怎样能让和最小和最大，很明显嘛，区间【L,R】是升序的，那么让那些未知数全部取L，自然加起来就是最小的，全部取R，自然就是最大的，纯纯送分题没啥好说的。

#include<iostream>
#define int long long
using namespace std;
 
int n,q;
signed main()
{
	cin>>n>>q;
	int sum = 0;
	int res = 0;
	
	for(int i = 1;i <= n; i++)
	{
		int x;
		cin>>x;
		if(x==0)res++;
		else sum +=x;
	}
	
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		cout<<sum + res*l<<" "<<sum+res*r<<'\n';
	}
	return 0;
} 

3.

小美的 MT

MT 是美团的缩写，因此小美很喜欢这两个字母。
现在小美拿到了一个仅由大写字母组成字符串，她可以最多操作k次，每次可以修改任意一个字符。小美想知道，操作结束后最多共有多少个'M'和'T'字符？

解法：纯模拟题。遇到非M非T字符，只要还有操作次数，就直接变成M或者T就可以了，最后统计一下有多少个就可以了。

#include<iostream>
 
using namespace std; 
 
int main()
{
	int n,k;
	
	scanf("%d%d",&n,&k);
	
	int res = 0,ans=0;
	
	string str;
	
	cin>>str;
	for(int i = 0;i<str.size();i++)
	{
		if(str[i]=='T')res++;
		else if(str[i]=='M')res++;
		else ans++;
	}
	
	cout<<res + min(ans,k)<<'\n';
	return 0;
}

4.小美的朋友关系

小美认为，在人际交往中，但是随着时间的流逝，朋友的关系也是会慢慢变淡的，最终朋友关系就淡忘了。
现在初始有一些朋友关系，存在一些事件会导致两个人淡忘了他们的朋友关系。小美想知道某一时刻中，某两人是否可以通过朋友介绍互相认识？
事件共有 2 种：
1 u v：代表编号 u 的人和编号 v 的人淡忘了他们的朋友关系。
2 u v：代表小美查询编号 u 的人和编号 v 的人是否能通过朋友介绍互相认识。

注：介绍可以有多层，比如 2 号把 1 号介绍给 3 号，然后 3 号再把 1 号介绍给 4 号，这样 1 号和 4 号就认识了。

解法：判断两个人是不是认识或者间接认识，很明显就是让我们判断在不在一个集合里面，顺着这个想法很快就想到并查集了，但是这个题目要删边（淡忘朋友关系），所以直接正向并查集不好做，并查集只能加边，所以这里要用反向并查集，逆序处理那些事件。

先把事件存起来，然后把是朋友关系的且没有被淡忘的关系并查集加边，然后从最后一个事件逆序往上做，这里要注意的一点：：：：要考虑重边！！！！！，比如添加{a,b}和{b,a}，这应该是同一条边，要特别判断一下，然后反向处理的时候把答案也存起来，再把答案逆序打印出来就好了。

#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<set>
using namespace std;
typedef pair<int,int>PII; 
// 反向并查集 
set<pair<int,int>>hashs,all;
unordered_map<int,int>p;
unordered_set<int>person;
int n,m,q;
const int N=1000100;
//int p[N];
struct OP{
	int op, a,b;
}Op[N];
int find(int x)
{
	if(p[x]!=x)p[x]=find(p[x]);
	return p[x];
}
int main()
{
//	for(int i = 1;i<=n;i++)p[i]=i;
	cin>>n>>m>>q;
	for(int i = 1; i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		hashs.insert({a,b});
		all.insert({a,b});
		person.insert(a);
		person.insert(b);
	}	
//	for(auto t : hashs)
//	{
//		cout<<t.first<<" "<<t.second<<endl;
//	}
	for(int i = 0; i < q;i++)
	{
		int op,a,b;
		cin>>op>>a>>b;
		Op[i]={op,a,b};
		person.insert(a);
		person.insert(b);
		if(op==1)
		{
			hashs.erase({a,b});
			hashs.erase({b,a});
		}
	}
	for(auto t : person)
	{
		p[t]=t;
	}
	for(auto pii:hashs)
	{
		int a= pii.first;
		int b= pii.second;
		p[find(a)]=find(b);
	}
	vector<string>ans;
	for(int i = q-1;i>=0;i--)
	{
		int op =Op[i].op;
		int a=Op[i].a;
		int b= Op[i].b;
		if(op==1){
			if(all.count({a,b})||all.count({b,a}))
			p[find(a)]=find(b);
		}
		else
		{
			if(find(a)==find(b))
			{
				ans.push_back("Yes");
				
			}
			else ans.push_back("No");
		}
	}
	
	for(int i = ans.size()-1;i>=0;i--)
		cout<<ans[i]<<'\n';
	return 0;
} 
 

5.

小美的区间删除

小美拿到了一个大小为n的数组，她希望删除一个区间后，使得剩余所有元素的乘积末尾至少有k个 0。小美想知道，一共有多少种不同的删除方案？

解法：乘积末尾至少要有k个0，那么剩余区间里的数2的因子和5的因子均不能少于k个，

可以先把每个数2的因子和5的因子统计出来，并且累加到c2和c5上
接着采用双指针做法，L指针固定左端点，R指针固定右端点，[L,R]这段区间表示要删除的区间

R指针每右移一位，若当前剩余的因子数仍满足k个，那么就会增加R - L +1个可行删除区间（会影响前R-L个数，并且多了当前新增的这个数，所以是R-L+1），若不满足了，说明左指针需要移动了。

#include<iostream>
#include<unordered_map>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1000010;
int n,k;
int s[N];
LL sum;
 
LL c2,c5;
LL cnt2[N],cnt5[N];
 
int getNums(int x,int num)
{
	int res=0;
	
	while(x%num==0)
	{
		x/=num;
		res++;
	}
	
	return res;
}
int main()
{
	cin>>n>>k;
	
	for(int i = 1;i<=n;i++)
	{
		int x;
		cin>>x;
		cnt2[i] = getNums(x,2);
		cnt5[i] = getNums(x,5);
		c2+=cnt2[i];
		c5+=cnt5[i];
	//	cout<<cnt2[i]<<" "<<cnt5[i]<<'\n';
	}
//	cout<<c2<<" "<<c5<<'\n';
	LL res=0;
	for(int l = 1, r= 1; r<=n;r++)
	{
		c2-=cnt2[r];
		c5-=cnt5[r];
		while(min(c2,c5)<k&&l<=n)
		{
			c2+=cnt2[l];
			c5+=cnt5[l];
			l++;
		}
		if(r>=l)
		res +=r-l+1;
	}
	printf("%lld",res);
}