贾永菁的博客

博客

标签

题解

今日打卡思路

2022-05-19 19:41:06 By 贾永菁

对不起大家了

以后尽量做到日更

今日份题目又出炉啦

首先这题老坑在哪呢

这是样例

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

顿时就清楚了

759

2022-05-17 20:17:19 By 贾永菁

这一题一看，典型深搜对吧

但是

他可以用循环！！！

因为知道搜索时从左上角搜起

所以我们只需判断当前的左上角有没有东西就能得出答案

这时一匹机（嘴）智（欠）的小马问

如何判断不和条件？

因为不和的只有以下几种

'##'

'#.'

'##'

'.#'

'#.'

'##'

'.#'

'##'

直接枚举就完事了

阅读全文

论快乐的熊果不会markdown

2022-05-15 20:32:33 By 贾永菁

两个换行会变成一个！！！

如下

include

using namespace std;

int main()

{

}

阅读全文

C 套圈题解

2022-05-10 19:34:35 By 贾永菁

为了这题我们首先要了解什么是前缀数组

前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前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];

阅读全文

D:水彩画题解

2022-05-09 19:46:33 By 贾永菁

这道题是典型的深搜

不要一听深搜就害怕，这一题只是顺序要深搜

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：不要直接抄，我加了防抄

include

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;

}