摘要:現在小明想統計有哪些帖子曾經是熱帖。如果一個帖子曾在任意一個長度為的時間段內收到不少于個贊,小明就認為這個帖子曾是熱帖。以下行列代表一張海域照片。照片保證第行第列第行第列的像素都是海洋。
2018年4月1日愚人節,我第一次參加了有關計算機算法類比賽“藍橋杯”,這篇算是經驗總結和題目回顧,水平有限,有不妥之處歡迎留言批評指正,也可以加QQ891465170交流~第一題:第幾天
下面進入正題:
2000年的1月1日,是那一年的第1天。 那么,2000年的5月4日,是那一年的第幾天?注意:需要提交的是一個整數,不要填寫任何多余內容。
哈哈這激動的啊,太簡單直接腦算,結果坑爹了,我把閏年二月記成28天普通年29天,直接錯了,送分題都沒拿到。
解法:2000年是閏年二月有29天,一月和三月有31天,四月有30天,所以:第二題:方格記數
31+29+31+30+4=125
如圖p1.png所示,在二維平面上有無數個1x1的小方格。我們以某個小方格的一個頂點為圓心畫一個半徑為1000的圓。 你能計算出這個圓里有多少個完整的小方格嗎?
注意:需要提交的是一個整數,不要填寫任何多余內容。
這個題不太會做,計算出這個圓的內接正方形編成為1000sqrt(2)=1414,正方形中方格個數為14141414,關鍵在于正方形外不會計算。
第三題:復數冪設i為虛數單位。對于任意正整數n,(2+3i)^n 的實部和虛部都是整數。 求 (2+3i)^123456 等于多少?
即(2+3i)的123456次冪,這個數字很大,要求精確表示。答案寫成 "實部±虛部i"
的形式,實部和虛部都是整數(不能用科學計數法表示),中間任何地方都不加空格,實部為正時前面不加正號。(2+3i)^2 寫成: -5+12i,
(2+3i)^5 的寫成: 122-597i注意:需要提交的是一個很龐大的復數,不要填寫任何多余內容。
這個好辦,寫段程序,把實部和虛部存儲,連乘123456次,即循環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
這題更正一下,由于是大數運算使用int類型當然是不行的,哎,第一次遇到這么大數運算也是無奈,使用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控制臺輸出結果為:感受一下吧~
x星球的居民脾氣不太好,但好在他們生氣的時候唯一的異常舉動是:摔手機。
各大廠商也就紛紛推出各種耐摔型手機。x星球的質監局規定了手機必須經過耐摔測試,并且評定出一個耐摔指數來,之后才允許上市流通。x星球有很多高聳入云的高塔,剛好可以用來做耐摔測試。塔的每一層高度都是一樣的,與地球上稍有不同的是,他們的第一層不是地面,而是相當于我們的2樓。
如果手機從第7層扔下去沒摔壞,但第8層摔壞了,則手機耐摔指數=7。 特別地,如果手機從第1層扔下去就壞了,則耐摔指數=0。
如果到了塔的最高層第n層扔沒摔壞,則耐摔指數=n為了減少測試次數,從每個廠家抽樣3部手機參加測試。
某次測試的塔高為1000層,如果我們總是采用最佳策略,在最壞的運氣下最多需要測試多少次才能確定手機的耐摔指數呢?
請填寫這個最多測試次數。
注意:需要填寫的是一個整數,不要填寫任何多余內容。
這個也簡單,使用二分查找,最壞情況是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第五題:快速排序
以下代碼可以從數組a[]中找出第k小的元素。它使用了類似快速排序中的分治算法,期望時間復雜度是O(N)的。
請仔細閱讀分析源碼,填寫劃線部分缺失的內容。
注意:只提交劃線部分缺少的代碼,不要抄寫任何已經存在的代碼或符號。
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)); } }
一個分治法進行快速排序 分治法三步第六題:遞增三元組
1.將問題分成盡量左右相等的左右兩半
2.遞歸求解左右兩半
3.合并左右兩半問題和當前問題比較 熟悉的話一眼看出,這個也簡單答案:a,i,r,k
給定三個整數數組 A = [A1, A2, ... AN], B = [B1, B2, ... BN], C = [C1, C2,
... CN], 請你統計有多少個三元組(i, j, k) 滿足:1 <= i, j, k <= N
Ai < Bj < Ck
【輸入格式】 第一行包含一個整數N。 第二行包含N個整數A1, A2, ... AN。 第三行包含N個整數B1, B2, ... BN。
第四行包含N個整數C1, C2, ... CN。對于30%的數據,1 <= N <= 100
對于60%的數據,1 <= N <= 1000
對于100%的數據,1 <= N <=
100000 0 <= Ai, Bi, Ci <= 100000【輸出格式】 一個整數表示答案
【輸入樣例】
3
1 1 1
2 2 2
3 3 3【輸出樣例】
27資源約定: 峰值內存消耗(含虛擬機) < 256M CPU消耗 < 1000ms
請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入...” 的多余內容。 所有代碼放在同一個源文件中,調試通過后,拷貝提交該源碼。
不要使用package語句。不要使用jdk1.7及以上版本的特性。 主類的名字必須是:Main,否則按無效代碼處理。
這個題我就比較坑了,程序設計
暴力求解做法
int count = 0; for(int i = 0; i時間復雜度為O(n^3),必定超時!
我的思路使用子列生成算法,使用增量法生成長度為3的子列。
假設數組A,B,C已經構造完成public class Main{ public void static main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int tlength = 0; int[] tuple = new int[n*3]; int[] temp = new int[n*3]; int[] count = {0}; //記錄有多設個滿足條件的三元組 //根據輸入構造ABC ... //構造一個下標數組{0,0,0,1,1,1,2,2,2,...,n-1,n-1,n-1} for(int i = 0; i3) return; if(cur==3){ if(a[tuple[[temp[0]]] 時間復雜度:O(nlogn)
第七題:螺旋折線
悲劇的是debug好久答案不正確,經驗不足,時間比較緊張,導致后面幾道題時間不夠。如圖所示的螺旋折線經過平面上所有整點恰好一次。 對于整點(X, Y),我們定義它到原點的距離dis(X,
Y)是從原點到(X, Y)的螺旋折線段的長度。例如dis(0, 1)=3, dis(-2, -1)=9
給出整點坐標(X, Y),你能計算出dis(X, Y)嗎?
【輸入格式】 X和Y
對于40%的數據,-1000 <= X, Y <= 1000
對于70%的數據,-100000 <= X, Y <= 100000
對于100%的數據, -1000000000 <= X, Y <= 1000000000【輸出格式】 輸出dis(X, Y)
【輸入樣例】 0 1
【輸出樣例】 3
資源約定: 峰值內存消耗(含虛擬機) < 256M CPU消耗 < 1000ms
請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入...” 的多余內容。
所有代碼放在同一個源文件中,調試通過后,拷貝提交該源碼。 不要使用> package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是:Main,否則按無效代碼處理。觀察后不難發現,可以看成每一步走一個折線,奇數步左上(x-n,y)(x-n,y+n),偶數步右下(x+n,y)(x+n,y-n),n為步數,在走的過程中判斷最后加一個統計變量即可
import java.util.Scanner; public class T7 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); int y = sc.nextInt(); boolean ok = false; int x1 = 0, y1 = 0,m=0,count=0; while(!ok){ if(x1==x&&y1==y){ ok = true; break; } m++; if(m%2==1){//奇數步 for(int i = 0; i第八題:日志統計 小明維護著一個程序員論壇。現在他收集了一份"點贊"日志,日志共有N行。其中每一行的格式是:ts id
表示在ts時刻編號id的帖子收到一個"贊"。
現在小明想統計有哪些帖子曾經是"熱帖"。如果一個帖子曾在任意一個長度為D的時間段內收到不少于K個贊,小明就認為這個帖子曾是"熱帖"。
具體來說,如果存在某個時刻T滿足該帖在[T, T+D)這段時間內(注意是左閉右開區間)收到不少于K個贊,該帖就曾是"熱帖"。
給定日志,請你幫助小明統計出所有曾是"熱帖"的帖子編號。
【輸入格式】 第一行包含三個整數N、D和K。 以下N行每行一條日志,包含兩個整數ts和id。
對于50%的數據,1 <= K <= N <= 1000
對于100%的數據,1 <= K <= N <= 100000
0 <= ts<= 100000 0 <= id <= 100000【輸出格式】 按從小到大的順序輸出熱帖id。每個id一行。
【輸入樣例】 7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3【輸出樣例】 1 3
資源約定: 峰值內存消耗(含虛擬機) < 256M CPU消耗 < 1000ms
請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入...” 的多余內容。
所有代碼放在同一個源文件中,調試通過后,拷貝提交該源碼。 不要使用package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是:Main,否則按無效代碼處理。也不難,獲取日志數組,構造HashMap統計最后判斷滿足k輸出即可.
第九題:全球變暖
這里代碼不在貼出。你有一張某海域NxN像素的照片,"."表示海洋、"#"表示陸地,如下所示:....... .##.... .##.... ....##. ..####. ...###. .......
其中"上下左右"四個方向上連在一起的一片陸地組成一座島嶼。例如上圖就有2座島嶼。
由于全球變暖導致了海面上升,科學家預測未來幾十年,島嶼邊緣一個像素的范圍會被海水淹沒。具體來說如果一塊陸地像素與海洋相鄰(上下左右四個相鄰像素中有海洋),它就會被淹沒。
例如上圖中的海域未來會變成如下樣子:
....... ....... ....... ....... ....#.. ....... .......
請你計算:依照科學家的預測,照片中有多少島嶼會被完全淹沒。
【輸入格式】 第一行包含一個整數N。 (1 <= N <= 1000) 以下N行N列代表一張海域照片。
照片保證第1行、第1列、第N行、第N列的像素都是海洋。
【輸出格式】 一個整數表示答案。
【輸入樣例】 7
.......
.##....
.##....
....##.
..####.
...###.
.......【輸出樣例】 1
資源約定: 峰值內存消耗(含虛擬機) < 256M CPU消耗 < 1000ms
請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入...” 的多余內容。
所有代碼放在同一個源文件中,調試通過后,拷貝提交該源碼。 不要使用package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是:Main,否則按無效代碼處理。不太會,主要基礎不好,是一個圖問題,對圖不太熟悉,dfs算法不會寫,算是基本功不行
第十題:堆的記數我們知道包含N個元素的堆可以看成是一棵包含N個節點的完全二叉樹。
每個節點有一個權值。對于小根堆來說,父節點的權值一定小于其子節點的權值。假設N個節點的權值分別是1~N,你能求出一共有多少種不同的小根堆嗎?
例如對于N=4有如下3種:
1
/
2 3
/
41
/
3 2
/
41
/
2 4
/
3
由于數量可能超過整型范圍,你只需要輸出結果除以1000000009的余數。【輸入格式】 一個整數N。
對于40%的數據,1 <= N <= 1000
對于70%的數據,1 <= N <= 10000
對于100%的數據,1 <= N <= 100000【輸出格式】 一個整數表示答案。
【輸入樣例】 4
【輸出樣例】 3
資源約定: 峰值內存消耗(含虛擬機) < 256M CPU消耗 < 1000ms
請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入...” 的多余內容。
所有代碼放在同一個源文件中,調試通過后,拷貝提交該源碼。 不要使用package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是:Main,否則按無效代碼處理。估計涉及到動態規劃,沒什么思路。
后續繼續跟新!
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/68911.html
摘要:針對計算機類的同學,數學建模,電子科技大賽,大創,,藍橋杯這些都是值得參加的高含金量的比賽,無論是學校加分還是應屆招聘,都被廣泛認可。但近幾屆的藍橋杯題目難度已經明顯增大,準備參加的同學也決不可掉以輕心。 ...
摘要:比如,其循環節為共有位。答案牌型種數小明被劫持到賭城,被迫與其他人玩牌。還有另外一種寫法主要的思路是假設牌是從到按順序取的,表示取到牌數為的牌,表示目前一共取了多少張牌。 1、三角形面積 如圖1所示。圖中的所有小方格面積都是1。那么,圖中的三角形面積應該是多少呢?請填寫三角形的面積。不要填寫任何多余內容或說明性文字。 showImg(https://segmentfault.com/i...
摘要:文章目錄一你應該知道的藍橋杯含金量獲獎率高不高支持哪些編程語言二川川帶你體驗藍橋杯省賽藍橋杯藍橋杯三個人感受一你應該知道的藍橋杯如果你是計算機相關專業,你不知藍橋杯就過不去了,我們來看看藍橋杯如何,不知道更應該來了解下了。 ...
摘要:問題描述審美的歷程課上有位學生,帥老師展示了幅畫,其中有些是梵高的作品,另外的都出自五歲小朋友之手。輸入格式第一行兩個數和,表示學生數和圖畫數接下來是一個的矩陣如果,表示學生覺得第幅畫是小朋友畫的如果,表示學生覺得第幅畫是梵高畫的。 問題描述 《審美的歷程》課上有n位學生,帥老師展示了m幅畫,其中有些是梵高的作品,另外的都出自五歲小朋友之手。老師請同學們分辨哪些畫的作者是梵高,但是老...
閱讀 2254·2021-10-13 09:39
閱讀 3417·2021-09-30 09:52
閱讀 806·2021-09-26 09:55
閱讀 2779·2019-08-30 13:19
閱讀 1895·2019-08-26 10:42
閱讀 3192·2019-08-26 10:17
閱讀 548·2019-08-23 14:52
閱讀 3640·2019-08-23 14:39