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<();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;
({a,b});
({a,b});
(a);
(b);
}
// for(auto t : hashs)
// {
// cout<<<<" "<<<<endl;
// }
for(int i = 0; i < q;i++)
{
int op,a,b;
cin>>op>>a>>b;
Op[i]={op,a,b};
(a);
(b);
if(op==1)
{
({a,b});
({b,a});
}
}
for(auto t : person)
{
p[t]=t;
}
for(auto pii:hashs)
{
int a= ;
int b= ;
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(({a,b})||({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 = ()-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);
}