AcWing 刷题2
AcWing 1227.分巧克力
思路
首先可以确定是二分，然后就是实现的细节，最开始我左边界设为1，右边界是把所有巧克力的总面积计算出来再除以小朋友的数量（最理想情况下），结果怎么都不对，后来想起来，二分的话，左右边界很大也没太大问题，因为只需要几次就会到正常区间了。所以直接把右边界设为100005了，这才算是对的.....中间真的冥思苦想不知道哪里出错了，气死了。
题解
#include
using namespace std;
const int N=100005;
int h[N],w[N];
int n,k;
int main(void)
{
cin>>n>>k;
int sum=0;
for(int i=0;i>h[i]>>w[i];
int l=1,r=100005,m;
while(l0) r=m-1;
else l=m;
}
cout< AcWing 795.前缀和
思路
就是最基础的前缀和的思路，用一个数组F，Fi表示前i个元素的和，求区间l和r之间的数的和，只需要求Fi-Fi-1就行了
题解
#include
using namespace std;
const int N=100005;
int f[N];
int n,m,x,l,r;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>x;
f[i]=f[i-1]+x;
}
while(m--)
{
cin>>l>>r;
cout< AcWing 796.子矩阵的和
思路
和前缀合一样的原理，只不过变成了二维。（感觉和小时候数学题里的求不规则图形的面积有点相似，容斥原理）
重点在这两句：
f[i][j]+=f[i][j-1]+f[i-1][j]-f[i-1][j-1];
cout<题解
#include
using namespace std;
const int N=1005,M=1005;
int f[N][M],s[N][M];
int n,m,q;
int main()
{
int a,b,c,d;
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>f[i][j];
f[i][j]+=f[i][j-1]+f[i-1][j]-f[i-1][j-1];
}
while(q--)
{
cin>>a>>b>>c>>d;
cout< AcWing 99.激光炸弹
思路
跟子矩阵的和很像，只是有几点需要注意，我写的时候遇到了很多问题。
如果正方形的边长大于地图中最大的横纵坐标，相当于每个点都能覆盖到，那么直接把边长改为最大的横纵坐标的那个就好了
还有，在求二维前缀和矩阵的时候，忘记了加i，j位置本身的值....
题解
#include
using namespace std;
const int N=5005;
int f[N][N];
int n,m,h,l,x,y,w,ans;
int main()
{
cin>>n>>m;
if(m>5001) m=5001;
h=m;
l=m;
while(n--)
{
cin>>x>>y>>w;
f[++x][++y]+=w;
h=max(h,x);
l=max(l,y);
}
for(int i=1;i<=h;i++)
for(int j=1;j<=l;j++)
f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1]+f[i][j];
for(int i=m;i<=h;i++)
for(int j=m;j<=l;j++)
ans=max(ans,f[i][j]-f[i-m][j]-f[i][j-m]+f[i-m][j-m]);
cout<