目录
1. B 水平考试
2. C 数组段数
3. D 剪纸游戏
4. E 可口蛋糕
1. B 水平考试
（1）思路
· 最终得分只会出现0分和10分
· 分两类讨论
· 两个字符串相等 10分
· 两个字符串不相等，遍历字符串s，只要出现字符串f中没有的字符就为0分，否则10分
· 字符查找函数 s.find( ' ch ' )，若该字符没有找到，其返回值等于函数 s.nops()，因此将两者相比较即可知道是否找到该字符。
（2）代码
#include<iostream>
using namespace std;
int t,ans;
string s,f;
int main()
{
cin>>t;
while (t--)
{
cin>>s>>f;
if (s==f) ans=10;
else
{
int len=s.size(),p=0;
for (int i=0;i<len;i++)
if (f.find(s[i])==f.npos)
p=1;
if (p==1) ans=0;
else ans=10;
}
cout<<ans<<endl;
}
return 0;
}
2. C 数组段数
（1）思路
· 看到区间及其内部个数，首先想到前缀和，接下来维护的数组都是前缀和数组
· 遍历区间，若相邻两数不相等，则在两数之间需加一个隔板，而该区间的值即为隔板数
· 逻辑运算 （a）: · 括号内为真，其值为1
· 括号内为假，其值为0
· 前缀和数组s：从1开始到 i ，有多少个隔板
（2）代码
#include<iostream>
using namespace std;
int n,m,l,r,ans,a[200005],s[200005];
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1;i<=n;i++)
s[i]=s[i-1]+(a[i-1]!=a[i]);
while (m--)
{
cin>>l>>r;
ans=s[r]-s[l]+1;
cout<<ans<<endl;
}
return 0;
}3. D 剪纸游戏
（1）思路
对于每一个剪下的图形，dfs遍历出该图形的最大和最小的 x，y值，并记录下格数，x差值 * y差值得到一个正方形面积，将该面积与剪下图形格数相比较判断是否为长方形
（2）代码
#include<iostream>
using namespace std;
int n,m,ans,s,dx,dy,minx,maxx,miny,maxy,vis[1005][1005];
char a[1005][1005];
void dfs(int x,int y)
{
minx=min(minx,x),maxx=max(maxx,x),miny=min(miny,y),maxy=max(maxy,y);
int tx,ty,next[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
for (int i=0;i<4;i++)
{
tx=x+next[i][0],ty=y+next[i][1];
if (tx>0 && tx<=n && ty>0 && ty<=m && a[tx][ty]=='.' && vis[tx][ty]==0)
{
vis[tx][ty]=1;
s++;
dfs(tx,ty);
}
}
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
cin>>a[i][j];
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (a[i][j]=='.' && vis[i][j]==0)
{
vis[i][j]=1;
s=1,dx=dy=maxx=maxy=0,minx=miny=0x3f3f3f3f;
dfs(i,j);
dx=maxx-minx+1,dy=maxy-miny+1;
if (s==dx*dy)
ans++;
}
cout<<ans;
return 0;
}4. E 可口蛋糕
（1）思路
· 对于饱腹值，用前缀和数组 + lower_bound 代替滑动窗口
· 根据条件列式：sw[ r ] - sw[ l ] >= W，固定左端点找右端点，sw[ r ] >= W + sw[ l ]，因为sw[ l ] 是固定值，因此可用lower_bound找到 r
· 对于可口值，可以理解为在满足饱腹值的前提下的最大字段和，同样可以用前缀和数组代替
· 找到 r 后，可口值为 sd[ r ] - sd[ l ]，因为sd[ l ]是固定值，只需找到从 r 到 n 的最大 sd[ i ]
· 另开一个后缀数组记录可口值前缀和数组从某一点往后的最大值（优化）
（2）代码
#include<iostream>
using namespace std;
long long n,W,ans,w[1000005],d[1000005],sw[1000005],sd[1000005],mx[1000006];
int main()
{
cin>>n>>W;
for (int i=1;i<=n;i++)
{
cin>>w[i];
sw[i]=sw[i-1]+w[i];
}
for (int i=1;i<=n;i++)
{
cin>>d[i];
sd[i]=sd[i-1]+d[i];
}
mx[n+1]=-1e15; // 界外数据赋初值
for (int i=n;i>=1;i--)
mx[i]=max(mx[i+1],sd[i]);
ans=-1e15; // 初始化
for (int i=1;i<=n;i++)
{
int r=lower_bound(sw+1,sw+n+1,W+sw[i-1])-sw;
ans=max(ans,mx[r]-sd[i-1]);
}
cout<<ans;
return 0;
} 
