填空題
-
求階乘位數
這道題暴力…解決不了，可以使用通過對n！取10的對數來取n！的位數，判斷對數的位數是否大于等于10000，如果是輸出答案。
-
公式
l o g 10 ( n ! ) = l o g 10 ( 1 ∗ 2 ∗ 3 ∗ 4... ∗ n ) = l o g 10 ( 1 ) + l o g 10 ( 2 ) + . . . + l o g 10 ( n − 1 ) + l o g 10 ( n ) log10(n!)=log10(1*2*3*4...*n)=log10(1)+log10(2)+...+log10(n-1)+log10(n) log10(n!)=log10(1∗2∗3∗4...∗n)=log10(1)+log10(2)+...+log10(n−1)+log10(n)
- 代碼
public class b1 {
public static void main(String[] args) {
// TODO Auto-generated method stub
double x=0;
for(int i=1;;i++) {
x+=Math.log10(i);
if(x>=10000) {
System.out.println(i);
break;
}
}
}
}
-
炮台實驗
這一題讓我想到了高中的組合數學問題，有n個位置，不同的位置擺放不同的數，共有n！的排列。對于留存的炮台數的期望，可以對沒一個數留存下來的機率進行累加進而得到期望值。比如最大的數，無論放在哪，留存下的機率都為1。第二大的數，如果最大的數放在其前面會被摧毀，而放在後面不會被摧毀，是以留存的機率為 1 2 \frac{1}{2} 21，最小的數除了放在第一個位置，其餘位置都會被摧毀，是以留存的機率為 1 n \frac{1}{n} n1。是以要求的期望值為 1 + 1 2 + . . . + 1 n 1+\frac{1}{2}+...+\frac{1}{n} 1+21+...+n1,代入n=2019即可算出答案
- 代碼
public class b2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
double c=0;
double n=1;
while(n<=2019) {
c+=1/n;
n++;
}
System.out.println(c);
}
}
- 蒜頭國有 n 座城市，編号分别為 0,1,2,3,…,n−1。編号為 x 和 y 的兩座城市之間如果要修高速公路，必須花費 x∣y 個金币，其中|表示二進制按位或。 吝啬的國王想要花最少的價格修建高速公路，使得所有城市可以通過若幹條高速公路互相達到。現在請你求出 n=2019 時，一共有多少不同的方案，能讓所有城市連通并且造價最低。方案數可能很大，你隻需輸出對 10 9 +7 取模的結果。
思路
n座城市要實作互通，并且使得造價最低，屬于最小生成樹問題。
最小生成樹是需要在樹中構造n-1條邊使得n個結點都相連，不能有環。
這個問題中，可以将每個結點用二進制表示如，編号為13則二進制表示為1101。
而當把x和y這兩個城市連接配接時要使得花費金币數最少，即使得x|y等于x自身。
如編号為1101時，與0000，0001，0100，1000，1100，1001，0101，1101相連時會使得花費的金币數為1101。
即除了x上位數為1的位置可以為1或0時才能使得x|y=x。 是以可以計算1101這個編号中1的個數為3，是以可以選擇連接配接的城市有 2 3 − 1 2^3-1 23−1。
而對于n個城市，每個編号可以連接配接的城市為其二進制編碼中所含1的個數的序列排列數，是以可以編寫如下代碼：
package monisai1;
public class b4 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n=2019;
long ans=1;//0隻能和自己本身相連才不會使得金币數增加
long mod=(long)1e9+7;
for(int i=1;i<n;i++) {
int t=0;
for(int j=0;i>>j>0;j++) {
if((i>>j&1)==1) {
t++;
//二進制枚舉，
//将i右移j位（且保證右移後的數大于0），将其與1按位與，結果為1則表示i對應二進制第j位上的數字為1
}
}
ans=ans*((1<<t)-1)%mod; //1<<t 表示2^t 即将1左移t位
//注意（1<<t）要哒括号 ,因為<<優先級小于-
}
System.out.println(ans);
}
}
代碼填空題
1. 歐拉函數
-
公式推導
首先先看下對12求質因子的過程，可知 12 = 1 ∗ 2 ∗ 2 ∗ 3 = 2 2 ∗ 3 1 12=1*2*2*3=2^2*3^1 12=1∗2∗2∗3=22∗31
通過歸納法我們可以證明出 n = p 1 k 1 ∗ p 2 k 2 ∗ . . . p j k j n=p_1^{k1}*p_2^{k2}*...p_j^{kj} n=p1k1∗p2k2∗...pjkj( p i p_i pi為n的質因子)
而 φ ( n ) = ∏ i = 1 j p i k i \varphi(n)=\prod_{i=1}^jp_i^{ki} φ(n)=∏i=1jpiki
= p 1 k 1 ∗ ( ( p 1 − 1 ) / p 1 ) ∗ p 2 k 2 ∗ ( ( p 2 − 1 ) / p 2 ) ∗ . . . p j k j ∗ ( ( p j − 1 ) / p j ) =p_1^{k1}*((p_1-1)/p_1)*p_2^{k2}*((p2-1)/p2)*...p_j^{kj}*((p_j-1)/p_j) =p1k1∗((p1−1)/p1)∗p2k2∗((p2−1)/p2)∗...pjkj∗((pj−1)/pj)
= p 1 k 1 ∗ p 2 k 2 ∗ . . . p j k j ∗ ( 1 − 1 p 1 ) ∗ ( 1 − 1 p 2 ) ∗ . . . ∗ ( 1 − 1 p j ) =p_1^{k1}*p_2^{k2}*...p_j^{kj}*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*...*(1-\frac{1}{p_j}) =p1k1∗p2k2∗...pjkj∗(1−p11)∗(1−p21)∗...∗(1−pj1)
= n ∗ ( 1 − 1 p 1 ) ∗ ( 1 − 1 p 2 ) ∗ . . . ∗ ( 1 − 1 p j ) =n*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})*...*(1-\frac{1}{p_j}) =n∗(1−p11)∗(1−p21)∗...∗(1−pj1)
- 代碼
import java.util.*;
public class Main {
public static int euler(int n) {
int res = n;
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
res = res-res/i ;
while (n % i == 0) {
n /= i;
}
}
}
return res;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(euler(n));
}
}
程式設計
- 掎角之勢
package monisai1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class c1_answer {
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
int N;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
N=Integer.parseInt(br.readLine());
while(N--!=0){
StringTokenizer token=new StringTokenizer(br.readLine());
int x1=Integer.parseInt(token.nextToken());
int y1=Integer.parseInt(token.nextToken());
int x2=Integer.parseInt(token.nextToken());
int y2=Integer.parseInt(token.nextToken());
int x3=Integer.parseInt(token.nextToken());
int y3=Integer.parseInt(token.nextToken());
//假設三點為A、B、C
x1 -= x3;
y1 -= y3;
x2 -= x3;
y2 -= y3;
//計算兩條邊向量AC（x1,y1）BC (x2,y2)
if(x1*y2==x2*y1) { //叉乘公式 S=1/2*BA*BC=1/2*(x1*y2-x2*y1) 如果三角形面積為0則表明解不存在
System.out.println("NO SOLUSTION");
continue;
}
double s=Math.abs(x1*y2-x2*y1); //三角形ABC面積的一半
double a=Math.sqrt(x1*x1+y1*y1);
double b=Math.sqrt(x2*x2+y2*y2);
x1-=x2;
y1-=y2;
double c = Math.sqrt(x1 *x1 + y1 *y1);
//計算AB的距離 注意未避免c計算錯誤 在之前計算AC BC向量時要A，B的坐标要減去同一個點的坐标
double r1=s/(a+b+c); //内接圓半徑公式
double r2=a*b*c/s/2;// 外接圓半徑公式
System.out.println(String.format("%.10f", Math.acos(-1)*r1*r1)+" "+String.format("%.10f", Math.acos(-1)*r2*r2));
}
System.out.println(Integer.MAX_VALUE);
System.out.println(Long.MAX_VALUE);
}
}
- 輕重搭配
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int []a=new int[500010];
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine());
StringTokenizer token=new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
a[i]=Integer.parseInt(token.nextToken());
}
Arrays.sort(a, 0,N);
int ans=N;
int j=N/2;
for(int i=0;i<N/2;i++) {
while(j<N&&a[j]<2*a[i]) j++;
if(j==N) break;
ans--;
j++;
}
System.out.println(ans);
}
}
貪心算法，初始票設定為n，兩兩配對，從數組中的0号位置開始和n/2位置後的資料開始比較，如果符合超出a[i]兩倍的條件就開始配對，配對成功就将購票數減一。接着繼續往下配對，直至pos到達終點。
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)