导刊2012模拟试题3.doc

一permutation解析：这道题一看就知道不会的，就想去暴力枚举了。其实改变的位数最多只有13位， 13！=622702080010(9)我们一位一位的来递推求出第k个排列。关键做法：由于第i位增加“1”（如果+1后与前面相同则再加1，直到没有相同），这个排列的编号就会增加（n-i）!，所以我们由n-13位递推到n-1位、确定某一位增加的数量可以用二分。然后求出实际增加的数量（再加上增加的数量比前面确定的数字大的个数）前11位的index数就全部打表，方便查找1到n-14位的数是否为index数程序：var sz,n,k,last,tmp,l,r,mid,ans,ans2:int64; size,i,j,ii:longint; p:array1.2000 of int64; q:array1.20000 of int64;procedure dfs(k,s:int64);begin inc(size); qsize:=s; size记录index数的个数 if k=11 then exit; dfs(k+1,s*10+4); dfs(k+1,s*10+7);end;procedure init; 找出1到11位的index数，然后排序begin dfs(1,0); for i:=1 to size-1 do for j:=i+1 to size do if qiqj then begin qi:=qi xor qj; qj:=qj xor qi; qi:=qi xor qj; end;end;function fac(s:int64):int64; 计算阶乘begin if s=1 then exit(1); exit(s*fac(s-1);end;function check(n:int64):boolean; 判断n是不是index数var f:boolean;begin f:=true; if n=0 then exit(false); while n0 do begin if (n mod 104) and (n mod 107) then begin f:=false; break; end; n:=n div 10; end; exit(f);end;function max(x,y:int64):int64; 取最大值begin if xy then exit(x) else exit(y);end;begin readln(n,k); dec(k); 找第k个序列 init; for i:=1 to size do if (qimax(1,n-13) and check(qi) then inc(ans2); 小于最小的会改变的index数的个数，一定是符合x的数 for i:=max(1,n-13) to n-1 do begin需要改变的位置的数 tmp:=fac(n-i); 求（n-i）的阶乘 l:=0; r:=n-i; ans:=0; while lk then r:=mid-1 else begin ans:=mid; l:=mid+1; end; end; k:=k-ans*tmp; 剩余的值必然在后面几位上改变 inc(ans); for j:=1 to sz do if pjpj then begin pii:=pii xor pj; pj:=pj xor pii; pii:=pii xor pj; end; if check(i) and check(max(0,n-14)+ans) then ans2:=ans2+1; i是否index数 实际增加的数值 end; ans:=1; 肯定加1 for j:=1 to sz do if pj0 then writeln(-1) 超过kn! else writeln(ans2);end.解析：题意是找出一个x符合index数，还要被所有的直线包含。然后找出这样的点的个数。先处理所有的index数，给区间端点设好初始值（1,1）每次循环时把右端点加1，适当将左端点右移，直至满足修改次数小于等于k关键是怎样求修改次数，我们考虑对于当前区间（l,r）,如果要将其变成合法的，那么我们需要把所有左端点大于L的线段的左端点移至L,把所有右端点小于R的线段的右端点移至R。单调扫描确定哪些线段需要移动的。花费的次数，即Li L，处理好前缀和（即）之后即可O(1)算出所有这些线段的移动花费和。因为前缀和可能超过int64，所以要用浮点型进行处理。程序：const mn=200000;var k,minlen,ans,ll,rr,lp,rp:int64; n,i,j,sz:longint; costl,costr:extended; a:array1.2000000 of int64; l,r:array1.mn of int64; sl,sr:array1.mn of extended;procedure swap(var a,b:int64); 交换var temp:int64;begin temp:=a; a:=b; b:=temp;end;procedure sort(w,x,y:longint); 含3个快排var i,j:longint; k:int64;begin if y-xaj then swap(ai,aj); 2: if lilj then swap(li,lj); 3: if rirj then swap(ri,rj); end; exit; end; case w of 1: k:=a(x+y) div 2; 2: k:=l(x+y) div 2; 3: k:=r(x+y) div 2; end; i:=x; j:=y; repeat case w of 1: begin while aik do dec(j); if i=j then begin swap(ai,aj); inc(i); dec(j); end; end; 2: begin while lik do dec(j); if i=j then begin swap(li,lj); inc(i); dec(j); end; end; 3: begin while rik do dec(j); if ij; if xi then sort(w,i,y);end;procedure dfs(k:longint; s:int64); 记录所有的index数begin if s0 then begin inc(sz); asz:=s; end; if k=19 then exit; 至到19位 dfs(k+1,s*10+4); dfs(k+1,s*10+7);end;procedure Init;begin dfs(1,0); sort(1,1,sz); 快排end;function calcl:extended; 计算移动至l的花费var x:extended;begin while (lp=n) and (llp=all) do inc(lp); l数组递增，找出不过L的节点数，小于等于L x:=n-lp+1; 那么就有n-lp+1个过L的结点数，大于L exit(sllp-x*all); 全部向右移动，详述：一个点左结点l，移动x,花费就是l-xend;function calcr:extended; 计算移动至r的花费var x:extended;begin while (rpn) and (rrp+1ri-li then minlen:=ri-li; 记录最短长度 end; Init; sort(2,1,n); sort(3,1,n); for i:=n downto 1 do sli:=sli+1+li; n到i的左端点的和 for i:=1 to n do sri:=sri-1+ri; 前缀和，1到i右端点的和 ll:=1; rr:=1; 初始区间 lp:=0; rp:=0; costl:=calcl; costr:=calcr; ans:=0; while rrminlen do inc(ll); 最大可能答案，符合被全部线段包含的条件 costl:=calcl; while (costl+costr-0.5k) and (llrr) do begin 调整花费，使符合条件 inc(ll); costl:=calcl; end; if costl+costr-0.5=k then 符合条件的花费 if ansrr-ll+1 then ans:=rr-ll+1; 在区间上，rr和ll是index数的编号，他们之间的个数就是解 inc(rr); costr:=calcr; end; writeln(ans);end.解析：明显是数学题，用模拟或动归肯定不行。条件二指出对于每个元素，不能同时出现在K个集合中。即每个元素有2k- 1 种放法（将集合看成有k个元素，这个集合有2k个非空集合，减去重复的集合就有2k- 1 种放法）。显然每个元素的放法是独立的，所以一共有（2k- 1）n种方案。用快速幕就能完成。程序：const P=1000000007;var n,k:int64;function pow(a,b:int64):int64;求abvar t:int64