对不起大家了
以后尽量做到日更
今日份题目又出炉啦
首先这题老坑在哪呢
这是样例
3 2
1 2
2 2
是不是很普通
但是你细看
哎有重复的行或列
是不是一下就难了
再一看数据
F**K N=10^9!!
所以只能单重循环了
不过不要哭,sort还是可以用地
(小马别哭了,吵着别人了)
我们可以发现啊 总格数是n×n
而去掉重行后有2个不同行个不同列
那么再一看
33-(3-2)(3-1)
=9-1*2
=9-2
=7
顿时就清楚了
对不起大家了
以后尽量做到日更
今日份题目又出炉啦
首先这题老坑在哪呢
这是样例
3 2
1 2
2 2
是不是很普通
但是你细看
哎有重复的行或列
是不是一下就难了
再一看数据
F**K N=10^9!!
所以只能单重循环了
不过不要哭,sort还是可以用地
(小马别哭了,吵着别人了)
我们可以发现啊 总格数是n×n
而去掉重行后有2个不同行个不同列
那么再一看
33-(3-2)(3-1)
=9-1*2
=9-2
=7
顿时就清楚了
这一题一看,典型深搜对吧
但是
但是
他可以用循环!!!
因为知道搜索时从左上角搜起
所以我们只需判断当前的左上角有没有东西就能得出答案
这时一匹机(嘴)智(欠)的小马问
如何判断不和条件?
因为不和的只有以下几种
'##'
'#.'
'##'
'.#'
'#.'
'##'
'.#'
'##'
直接枚举就完事了
两个换行会变成一个!!!
如下
include
using namespace std;
int main()
{
}
为了这题 我们首先要了解什么是前缀数组
前缀和
前缀和是一种重要的预处理,能大大降低查询的时间复杂度。可以简单理解为“数列的前n项的和”。
C++ 标准库中实现了前缀和函数 std::partial_sum,定义于头文件 中。
以上内容来自传送门
有兴趣者自便
举个例子
1 2 4 3
5 1 2 4
6 3 5 9
这个数组的前缀数组长这样
1 3 7 10
6 9 15 22
12 18 29 45
这是怎么推的呢,有公式
a[i][j]=a[i-1][j]+a[i][j-1]+a[i-1][j-1];
了解什么是前缀和数组后,开始思路
我们如果把样例数据列出来
可以得到下表
0 0 0 0 1 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 0 1 0 1 0
0 0 0 1 0 0 0
可以看出是以(1,4)(1,6)(11,4)(11,6)为顶点的长方形和最大(下标从1开始)
那么有一位机智的同学提出问题
小贾,小贾,这和你刚说了一大堆的前缀数组有什么关系?
好,问题提的好,(下次别提了)。
我们来看,如果把刚提到的长方型为一个部分,长方形中的空心为第二部分
你发现了什么?
用前缀数组是不能直接求长方形一圈的和,但可以求整个长方形的和与中间空心的和
两者相减就得出答案
那么只要枚举长方形左上角,右下角的点就可求出最大和
至于为什么可以枚举,因为数据只有100!!
只贴核心代码
for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++)
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
计算前缀和
a[i][j]为输入数组
sum为前缀和数组
剩下的只有枚举了
公式在这
/整个长方形/ int j=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
/空心部分/ int k=sum[x2-1][y2-1]-sum[x1][y2-1]-sum[x2-1][y1]+sum[x1][y1];
这道题是典型的深搜
不要一听深搜就害怕,这一题只是顺序要深搜
void dfs(int k,double sum)
{
if(k>n)
{
ansmax=max(ansmax,sum);
return;
}
for(int i=1;i<=n;i++)
{
if(!s[i])
{
r[i]=suan(i);
s[i]=1;
dfs(k+1,sum+r[i]*r[i]*PI);
s[i]=0;
}
}
}
PI指Π(圆周率)
这里只要搜一下顺序就行
其中sum是水彩面积
ansmax就是最大水彩面积
suan这是一个函数,用于计算当前点的面积
suan函数简单粗暴只要判断边界和其他颜色就行了
判断与其他颜色接触只需看他们的最短直线距离就可以了
那么
程序有了
PS:不要直接抄,我加了防抄
using namespace std;
double PI=3.1415926535;
bool s[10];
double x[10],y[10],r[10],xa,ya,xb,yb,ansmax;
int n;
double suan(int i)
{
double s1=min(abs(x[i]-xa),abs(x[i]-xb));
double s2=min(abs(y[i]-ya),abs(y[i]-yb));
double ans=min(s1,s2);
for(int j=1;j<=n;j++)
if(i!=j&&s[j])
{
double d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
ans=min(ans,max(d-r[j],0.0));
}
return ans;
}
void dfs(int k,double sum)
{
if(k>n)
{
ansmax=max(ansmax,sum);
return;
}
for(int i=1;i<=n;i++)
if(!s[i])
{
r[i]=suan(i);
s[i]=1;
dfs(k+1,sum+r[i]*r[i]*PI);
s[i]=0;
}
}
int main()
{
double ss;
cin>>n;
cin>>xa>>ya>>xb>>yb;
ss=abs(xa-xb)*abs(ya-yb);
for(int i=1;i<=n;i++)
cin>>x[i]>>y[i];
dfs(1,0);
//cout<<int(ss+0.5-ansmax);
return 0;
}
大家看一下1310
有收获
谁把名字改成贾永菁大SB了?
站出来
asdgadfghg
哈哈嗨
最近有好多人模仿我,高仿我
你们闲的没事干那?
我才是本尊
每天不定时打卡提思路就找我
949-174-8634
521062
欢迎来腾讯会议找我