导刊2012模拟试题3

《导刊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

2、,mid,ans,ans2:int64;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:

3、=i+1tosizedoifq[i]>q[j]thenbeginq[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>0dobegini

4、f(nmod10<>4)and(nmod10<>7)thenbeginf:=false;break;end;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、的数}fori:=max(1,n-13)ton-1dobegin{需要改变的位置的数}tmp:=fac(n-i);{求（n-i）的阶乘}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);{计算

6、实际数字还要加上多少}{增加后数字比前面确定的数字大的情况，此时应将这个数字加上比前面数字大的个数}inc(sz);p[sz]:=ans;{插入增加的数值}forii:=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:

7、=1;{肯定加1}forj:=1toszdoifp[j]<=anstheninc(ans);ifcheck(n)andcheck(max(0,n-14)+ans)theninc(ans2);{同上}ifk>0thenwriteln(-1){超过k>n!}elsewriteln(ans2);end.解析：题意是找出一个x符合index数，还要被所有的直线包含。然后找出这样的点的个数。先处理所有的index数，给区间端点设好初始值（1,1）每次循环时把右端点加1，适当将左端点右移，直至满足修改次数小于等于k关键是怎样求修改次数，我们考虑对于当前区间（l,

8、r）,如果要将其变成合法的，那么我们需要把所有左端点大于L的线段的左端点移至L,把所有右端点小于R的线段的右