bzoj1432_[ZJOI2009]Function
发布日期:2021-09-03 20:58:07 浏览次数:3 分类:技术文章

本文共 1445 字,大约阅读时间需要 4 分钟。

题目描述

有n 个连续函数fi (x),其中1 ≤ i ≤ n。对于任何两个函数fi (x) 和fj (x),(i != j),恰好存在一个x 使得fi (x) = fj (x),并且存在无穷多的x 使得fi (x) < fj (x)。对于任何i; j; k,满足1 ≤ i < j < k ≤ n,则不存在x 使得fi (x) = fj (x) = fk (x)。
图
如上左图就是3 个满足条件的函数,最左边从下往上依次为f1; f2; f3。右图中红色部分是这整个函数图像的最低层,我们称它为第一层。同理绿色部分称为第二层,蓝色部分称为第三层。注意到,右图中第一层左边一段属于f1,中间属于f2,最后属于f3。而第二层左边属于f2,接下来一段属于f1,再接下来一段属于f3,最后属于f2。因此,我们称第一层分为了三段,第二层分为了四段。同理第三层只分为了两段。求满足前面条件的n 个函数,第k 层最少能由多少段组成。

输入输出格式

输入格式

一行两个整数n; k。

输出公式

一行一个整数,表示n 个函数第k 层最少能由多少段组成。

样例

INPUT

1 1

OUTPUT

1

HINT

SOLUTION

(#`O′)喂这样例也太水了点吧。
感谢zzr的友情支持。

推规律:自己多画几个图就出来啦(最好画到\(n=5\)以上吧,不然看不出啥规律),注意一下可以对称翻转整个图形即可。

数学证明:

首先,我们要求的是且仅是\(n\)条线,分出的第\(k\)层的最优解,所以,若能使我们的\(1~n/2\)层有最优解,由于对称性,将整个图形翻转过来之后,我们的\(n/2~n\)层一样也可以有最优解。

然后有一个特判:\(n=1\)时,\(ans=1\)

接下来我们要找的就是上半部分(也可以是下半部分,反正是某半边就可以了对吧)的最优解的求得方法。

数学归纳法证明:
[Warning]其实我并不太熟悉数学归纳法,如果有dalao对这篇题解有问题提出,欢迎一起讨论qwq但这好像姑且算个数学归纳法吧

我们首先可知在\(\forall n\in N_+(n\neq1)\)中,\(k=1时\)一定有\(ans=2\)

\(k>1\)时,对于\(k-1\)层,我们假使结论\(ans=2*(k-1)\)成立,

我们第\(k-1\)层现有的\(2*(k-1)\)段的每一段向原延伸方向延伸直至碰到下一个交点为止,于是得到了新的\(2*(k-1)\)段,而我们又知道,一个交点涉及的的有且只有两条直线,而易得我们每一层的两端必定是由无限远延伸来的射线,因为出现过的直线的线段就是由一个端点延伸而来,故这两条射线所在的直线应该是第一次出现,不能包含在原有的\(2*(k-1)\)段里,所以可以得出,对于第\(k\)层,我们有\(ans=2*k\)

命题得证。

#include 
    
     #include 
     
      using namespace std;int main(){
      
int n,k;
scanf("%d%d",&n,&k);
if (n==1) {puts("1");return 0;}
printf("%d\n",min(k*2,2*(n-k+1)));
return 0;}

转载于:https://www.cnblogs.com/hkpls/p/9791976.html

转载地址:https://blog.csdn.net/weixin_34195142/article/details/92855003 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:kafka清理数据日志
下一篇:2019-05-31 Java学习日记之IO(其他流)&Properties

发表评论

最新留言

感谢大佬
[***.172.111.71]2022年05月22日 09时50分27秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章