Day 43kotori 和抽卡二解题思路这不是“数学期望”而是“二项分布中的概率”n次抽卡中恰好有m次抽到 R 卡的概率。思路可以分成三步。第一步计算C(n, m)。C(n, m)表示在n次抽卡中选择哪m次抽到 R 卡。公式是[ C(n,m)\frac{n!}{m!(n-m)!} ]C(5, 3) (5 * 4 * 3) / (3 * 2 * 1)代码中for (int i n; i n - m 1; i--) { ret * i; }计算的是[ n \times (n-1) \times \cdots \times (n-m1) ]一共有m个数。然后for (int i m; i 2; i--) { ret / i; }除以[ m! ]由于前面没有乘上完整的n!所以实际上已经隐含完成了[ \frac{n!}{(n-m)!m!}C(n,m) ]第二步计算m次抽到 R 卡的概率for (int i 0; i m; i) { ret * 0.8; }也就是[ 0.8^m ]第三步计算剩下n-m次没有抽到 R 卡的概率for (int i 0; i n - m; i) { ret * 0.2; }R 卡概率是0.8所以非 R 卡概率是[ 1-0.80.2 ]因此是[ 0.2^{n-m} ]最终公式就是[ \boxed{C(n,m)\times 0.8^m\times 0.2^{n-m}} ]例如输入3 2表示抽 3 次恰好抽到 2 张 R 卡。可能的情况有R R 非R R 非R R 非R R R一共有[ C(3,2)3 ]每种情况的概率是[ 0.8^2\times0.2 ]所以总概率[ 3\times0.8^2\times0.20.384 ]输出0.3840代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt(),min.nextInt();doubleans1.0;// 计算 C(n, m)for(intin;in-m;i--)ans*i;for(intim;i0;i--)ans/i;// m 次抽到 R 卡for(inti0;im;i)ans*0.8;// n - m 次没有抽到 R 卡for(inti0;in-m;i)ans*0.2;System.out.printf(%.4f,ans);}}ruby 和薯条解法一排序 二分查找这两个二分其实是在找同一个合法区间的左右边界。对于当前的nums[i]我们要找前面的nums[j]满足l nums[i] - nums[j] r移项得到nums[i] - r nums[j] nums[i] - l代码实现importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();longlin.nextLong();longrin.nextLong();long[]numsnewlong[n];for(inti0;in;i){nums[i]in.nextLong();}Arrays.sort(nums);longcnt0;for(inti1;in;i){/* * l nums[i] - nums[j] r * * 等价于 * nums[i] - r nums[j] nums[i] - l */longhighnums[i]-l;// 找第一个大于 high 的位置intleft0;intrighti;while(leftright){intmidleft(right-left)/2;if(nums[mid]high){leftmid1;}else{rightmid;}}intrightBoundleft;longlownums[i]-r;// 找第一个大于等于 low 的位置left0;righti;while(leftright){intmidleft(right-left)/2;if(nums[mid]low){leftmid1;}else{rightmid;}}intleftBoundleft;// 合法下标范围是 [leftBound, rightBound)cntrightBound-leftBound;}System.out.println(cnt);}}解法二前缀和 滑动窗口代码实现importjava.util.*;publicclassMain{publicstaticintn,l,r;publicstaticint[]arr;// 找出差值在 [0, x] 区间内一共有多少对publicstaticlongfind(intx){intleft0;intright0;longret0;while(rightn){while(arr[right]-arr[left]x){left;}retright-left;right;}returnret;}publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);nin.nextInt();lin.nextInt();rin.nextInt();arrnewint[n];for(inti0;in;i){arr[i]in.nextInt();}Arrays.sort(arr);System.out.println(find(r)-find(l-1));}}循环汉诺塔解题思路代码实现importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerinnewScanner(System.in);intnin.nextInt();intx1;inty2;intMOD1000000007;for(inti2;in;i){intxxx;intyyy;x(2*yy1)%MOD;y((2*yy2)%MODxx)%MOD;}System.out.println(x y);}}