导刊2012模拟试题3

导刊2012模拟试题3

ID:1660966

大小:199.50 KB

页数:10页

时间:2017-11-12

导刊2012模拟试题3_第1页
导刊2012模拟试题3_第2页
导刊2012模拟试题3_第3页
导刊2012模拟试题3_第4页
导刊2012模拟试题3_第5页
资源描述:

《导刊2012模拟试题3》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、一.permutation解析:这道题一看就知道不会的,就想去暴力枚举了。其实改变的位数最多只有13位,13!=6227020800>10(9)我们一位一位的来递推求出第k个排列。关键做法:由于第i位增加“1”(如果+1后与前面相同则再加1,直到没有相同),这个排列的编号就会增加(n-i)!,所以我们由n-13位递推到n-1位、确定某一位增加的数量可以用二分。然后求出实际增加的数量(再加上增加的数量比前面确定的数字大的个数)前11位的index数就全部打表,方便查找1到n-14位的数是否为index数程序:varsz,n,k,last,tmp,l,r,mid,ans,ans2:int

2、64;size,i,j,ii:longint;p:array[1..2000]ofint64;q:array[1..20000]ofint64;proceduredfs(k,s:int64);begininc(size);q[size]:=s;{size记录index数的个数}ifk=11thenexit;dfs(k+1,s*10+4);dfs(k+1,s*10+7);end;procedureinit;{找出1到11位的index数,然后排序}begindfs(1,0);fori:=1tosize-1doforj:=i+1tosizedoifq[i]>q[j]thenbeginq[

3、i]:=q[i]xorq[j];q[j]:=q[j]xorq[i];q[i]:=q[i]xorq[j];end;end;functionfac(s:int64):int64;{计算阶乘}beginifs=1thenexit(1);exit(s*fac(s-1));end;functioncheck(n:int64):boolean;{判断n是不是index数}varf:boolean;beginf:=true;ifn=0thenexit(false);whilen>0dobeginif(nmod10<>4)and(nmod10<>7)thenbeginf:=false;break;e

4、nd;n:=ndiv10;end;exit(f);end;functionmax(x,y:int64):int64;{取最大值}beginifx>ythenexit(x)elseexit(y);end;beginreadln(n,k);dec(k);{找第k个序列}init;fori:=1tosizedoif(q[i]

5、l:=0;r:=n-i;ans:=0;whilel<=rdobegin{二分,寻找第i位最大的增加值后记录在ans上}mid:=(l+r)div2;ifmid*tmp>kthenr:=mid-1elsebeginans:=mid;l:=mid+1;end;end;k:=k-ans*tmp;{剩余的值必然在后面几位上改变}inc(ans);forj:=1toszdoifp[j]<=anstheninc(ans);{计算实际数字还要加上多少}{增加后数字比前面确定的数字大的情况,此时应将这个数字加上比前面数字大的个数}inc(sz);p[sz]:=ans;{插入增加的数值}forii:=

6、1tosz-1do{排序}forj:=ii+1toszdoifp[ii]>p[j]thenbeginp[ii]:=p[ii]xorp[j];p[j]:=p[j]xorp[ii];p[ii]:=p[ii]xorp[j];end;ifcheck(i)andcheck(max(0,n-14)+ans)thenans2:=ans2+1;{i是否index数}{实际增加的数值}end;ans:=1;{肯定加1}forj:=1toszdoifp[j]<=anstheninc(ans);ifcheck(n)andcheck(max(0,n-14)+ans)theninc(ans2);{同上}ifk

7、>0thenwriteln(-1){超过k>n!}elsewriteln(ans2);end.解析:题意是找出一个x符合index数,还要被所有的直线包含。然后找出这样的点的个数。先处理所有的index数,给区间端点设好初始值(1,1)每次循环时把右端点加1,适当将左端点右移,直至满足修改次数小于等于k关键是怎样求修改次数,我们考虑对于当前区间(l,r),如果要将其变成合法的,那么我们需要把所有左端点大于L的线段的左端点移至L,把所有右端点小于R的线段的右

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。