資訊專欄INFORMATION COLUMN
摘要：現(xiàn)在小明想統(tǒng)計有哪些帖子曾經(jīng)是熱帖。如果一個帖子曾在任意一個長度為的時間段內(nèi)收到不少于個贊，小明就認(rèn)為這個帖子曾是熱帖。以下行列代表一張海域照片。照片保證第行第列第行第列的像素都是海洋。
2018年4月1日愚人節(jié)，我第一次參加了有關(guān)計算機(jī)算法類比賽“藍(lán)橋杯”，這篇算是經(jīng)驗總結(jié)和題目回顧，水平有限，有不妥之處歡迎留言批評指正，也可以加QQ891465170交流~第一題：第幾天
下面進(jìn)入正題：
2000年的1月1日，是那一年的第1天。 那么，2000年的5月4日，是那一年的第幾天？注意：需要提交的是一個整數(shù)，不要填寫任何多余內(nèi)容。
哈哈這激動的啊，太簡單直接腦算，結(jié)果坑爹了，我把閏年二月記成28天普通年29天，直接錯了，送分題都沒拿到。
解法：2000年是閏年二月有29天，一月和三月有31天，四月有30天，所以：第二題：方格記數(shù)
31+29+31+30+4=125
如圖p1.png所示，在二維平面上有無數(shù)個1x1的小方格。我們以某個小方格的一個頂點為圓心畫一個半徑為1000的圓。 你能計算出這個圓里有多少個完整的小方格嗎？
注意：需要提交的是一個整數(shù)，不要填寫任何多余內(nèi)容。
這個題不太會做，計算出這個圓的內(nèi)接正方形編成為1000sqrt(2)=1414,正方形中方格個數(shù)為14141414，關(guān)鍵在于正方形外不會計算。
第三題：復(fù)數(shù)冪設(shè)i為虛數(shù)單位。對于任意正整數(shù)n，(2+3i)^n 的實部和虛部都是整數(shù)。 求 (2+3i)^123456 等于多少？
即(2+3i)的123456次冪，這個數(shù)字很大，要求精確表示。答案寫成 "實部±虛部i"
的形式，實部和虛部都是整數(shù)（不能用科學(xué)計數(shù)法表示），中間任何地方都不加空格，實部為正時前面不加正號。(2+3i)^2 寫成: -5+12i，
(2+3i)^5 的寫成: 122-597i注意：需要提交的是一個很龐大的復(fù)數(shù)，不要填寫任何多余內(nèi)容。
這個好辦，寫段程序，把實部和虛部存儲，連乘123456次，即循環(huán)123456次。
public class T3 {
public static void main(String[] args) {
int a = 2, b = 3;
for(int i = 1; i<123456; i++){
int temp = 2*a-3*b;
b = 3*a+2*b;
a = temp;
}
System.out.println(a+"+"+b+"i");
}
}
答案：13483137+1100011648i
這題更正一下，由于是大數(shù)運算使用int類型當(dāng)然是不行的，哎，第一次遇到這么大數(shù)運算也是無奈，使用BigInteger類型。
import java.math.BigInteger;
public class T3 {
public static void main(String[] args) {
BigInteger a = new BigInteger("2");
BigInteger b = new BigInteger("3");
BigInteger a1 = new BigInteger("2");
BigInteger b1 = new BigInteger("3");
BigInteger temp;
for(int i = 1; i<123456; i++){
temp = a.multiply(a1).subtract(b.multiply(b1));
b = a.multiply(b1).add(b.multiply(a1));
a = temp;
}
if(b.compareTo(BigInteger.valueOf(0))>0){
System.out.println(a+"+"+b+"i");
}else{
System.out.println(a+""+b+"i");
}
}
}
如果在eclipse中輸出會得到一個--i的東西，是一個 超長字符串，使用cmd控制臺輸出結(jié)果為：感受一下吧~
x星球的居民脾氣不太好，但好在他們生氣的時候唯一的異常舉動是：摔手機(jī)。
各大廠商也就紛紛推出各種耐摔型手機(jī)。x星球的質(zhì)監(jiān)局規(guī)定了手機(jī)必須經(jīng)過耐摔測試，并且評定出一個耐摔指數(shù)來，之后才允許上市流通。x星球有很多高聳入云的高塔，剛好可以用來做耐摔測試。塔的每一層高度都是一樣的，與地球上稍有不同的是，他們的第一層不是地面，而是相當(dāng)于我們的2樓。
如果手機(jī)從第7層扔下去沒摔壞，但第8層摔壞了，則手機(jī)耐摔指數(shù)=7。 特別地，如果手機(jī)從第1層扔下去就壞了，則耐摔指數(shù)=0。
如果到了塔的最高層第n層扔沒摔壞，則耐摔指數(shù)=n為了減少測試次數(shù)，從每個廠家抽樣3部手機(jī)參加測試。
某次測試的塔高為1000層，如果我們總是采用最佳策略，在最壞的運氣下最多需要測試多少次才能確定手機(jī)的耐摔指數(shù)呢？
請?zhí)顚戇@個最多測試次數(shù)。
注意：需要填寫的是一個整數(shù)，不要填寫任何多余內(nèi)容。
這個也簡單，使用二分查找，最壞情況是1000層也不壞
二分查找算法代碼如下：
public class T4 {
public static void main(String[] args) {
int x = 0, y=1000;
int m = 0,count=0;
while(y-x>1){
m = x+(y-x)/2;
if(m<1000) x = m;
else y = m;
count++;
}
System.out.println(count);
}
}
答案：10第五題：快速排序
以下代碼可以從數(shù)組a[]中找出第k小的元素。它使用了類似快速排序中的分治算法，期望時間復(fù)雜度是O(N)的。
請仔細(xì)閱讀分析源碼，填寫劃線部分缺失的內(nèi)容。
注意：只提交劃線部分缺少的代碼，不要抄寫任何已經(jīng)存在的代碼或符號。
import java.util.Random;
public class Main{
public static int quickSelect(int a[], int l, int r, int k) {
Random rand = new Random();
int p = rand.nextInt(r - l + 1) + l;
int x = a[p];
int tmp = a[p]; a[p] = a[r]; a[r] = tmp;
int i = l, j = r;
while(i < j) {
while(i < j && a[i] < x) i++;
if(i < j) {
a[j] = a[i];
j--;
}
while(i < j && a[j] > x) j--;
if(i < j) {
a[i] = a[j];
i++;
}
}
a[i] = x;
p = i;
if(i - l + 1 == k) return a[i];
if(i - l + 1 < k) return quickSelect( _________________________________ ); //填空
else return quickSelect(a, l, i - 1, k);
}
public static void main(String args[]) {
int [] a = {1, 4, 2, 8, 5, 7};
System.out.println(quickSelect(a, 0, 5, 4));
}
}
一個分治法進(jìn)行快速排序 分治法三步第六題：遞增三元組
1.將問題分成盡量左右相等的左右兩半
2.遞歸求解左右兩半
3.合并左右兩半問題和當(dāng)前問題比較 熟悉的話一眼看出，這個也簡單答案：a,i,r,k
給定三個整數(shù)數(shù)組 A = [A1, A2, ... AN], B = [B1, B2, ... BN], C = [C1, C2,
... CN]， 請你統(tǒng)計有多少個三元組(i, j, k) 滿足：1 <= i, j, k <= N
Ai < Bj < Ck
【輸入格式】 第一行包含一個整數(shù)N。 第二行包含N個整數(shù)A1, A2, ... AN。 第三行包含N個整數(shù)B1, B2, ... BN。
第四行包含N個整數(shù)C1, C2, ... CN。對于30%的數(shù)據(jù)，1 <= N <= 100
對于60%的數(shù)據(jù)，1 <= N <= 1000
對于100%的數(shù)據(jù)，1 <= N <=
100000 0 <= Ai, Bi, Ci <= 100000【輸出格式】 一個整數(shù)表示答案
【輸入樣例】
3
1 1 1
2 2 2
3 3 3【輸出樣例】
27資源約定： 峰值內(nèi)存消耗（含虛擬機(jī)） < 256M CPU消耗 < 1000ms
請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入...” 的多余內(nèi)容。 所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。
不要使用package語句。不要使用jdk1.7及以上版本的特性。 主類的名字必須是：Main，否則按無效代碼處理。
這個題我就比較坑了，程序設(shè)計
暴力求解做法
