注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1432][ZJOI2009]Function  

2014-12-26 11:26:25|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1432: [ZJOI2009]Function

看到学长100+B的代码吓尿了
样例真良心……差点忘记讨论n=1
题解在代码下方

#include<cstdio>
int n,m;
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
int i,j;
n = scan();m = scan();
if(n==1){printf("1\n");return 0;}
m=(n-m)<(m-1)?n-m:m-1;
printf("%d\n",2+m*2);
return 0;
}





|
|
|
|
|
v










题解:
构造法。
首先千万不要被题里的图糊弄了……
按照题目描述,不一定非得是直线,只要保证任意两个函数都相交一次,并且交点都不一样就行了。
我们可以转化成以下形式,这个显然也是满足题目要求的。
[BZOJ1432][ZJOI2009]Function - 时光机 - 时光机TimeMachine
从下往上分别标上号是1~n
对于n>1的情况,我们把整个图分成三个部分。
[n~k+1],[k],[k-1~1]
我们的目标是最小化在k位置的改变数。
假设我们阻止k位置的线段移动,那么可以发现[n~k+1]和[k-1~1]内部是可以两两相交,但是这三个部分之间不可能相交。
所以我们必须要做的事情就是让这三个部分的线相交。
假设n-(k+1)+1 < (k-1)-1+1,也就是上面部分少。
为了让上面的和下面的相交,我们必须把上面的穿过中间的线移到下面,可以发现每移一条线到下面,都会把下面的一条线交换上来,对答案的贡献是2。
因为中间的线还要和其它线相交,所以答案就是2+min(n-k,k-1)*2
至于具体移动方法就是每次把[k]移动到[1] ,[k-1]移动到[n]
最后注意特判n=1的情况
  评论这张
 
阅读(21)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017