時間限制 1000 ms 內存限制 65536 KB
題目描述
Given an array with N integers where all elements appear three times except for one. Find out the one which appears only once.輸入格式
Several test cases are given, terminated by EOF.Each test case consists of two lines. The first line gives the length of array N(1≤N≤105), and the other line describes the N elements. All elements are ranged in [0,2^63?1].
輸出格式
Output the answer for each test case, one per line.輸入樣例
4 1 1 1 3 10 1 2 3 1 2 3 1 2 3 4輸出樣例
3 4
這道題，超時超的我不要不要的，明明O(n)的時間復雜度還是超時。就找了一些別人的答案看了看，覺得應該是卡常數（學了新詞）。因此換用另一種算法，雖然還是O(n)但是不再超時。 之前的思路：把每個數轉化成二進制，逐位相加，放在數組（數組大小定為64）里，最后逐位模3，得到的二進制數轉化為十進制即為結果。 AC的思路：定義一個二維數組，2^63 大約 10^19，所以數組為20*10。num[i][j]表示第i位出現過數字j的次數，然后從第一列遍歷數組，若模3得1則直接輸出j。 可見，同為O(n)也是存在差別的。（代碼參照了別的博主，就不貼了） 遇到這種題上來就想換成二進制算，也不知道什么毛病。換來換去還挺耗時間的。
時間限制 1000 ms 內存限制 65536 KB
題目描述
給出一棵有向樹，一共有N(1 小于N≤1000)個節點，如果一個節點的度（入度+出度）不小于它所有兒子以及它父親的度(如果存在父親或兒子)，那么我們稱這個節點為p節點，現在你的任務是統計p節點的個數。如樣例，第一組的p節點為1,2,3；第二組的p節點為0。
輸入格式
第一行為數據組數T(1≤T≤100)。 每組數據第一行為N表示樹的節點數。后面為N?1行，每行兩個數x,y(0≤x,y小于N)，代表y是x的兒子節點。輸出格式
每組數據輸出一行，為一個整數，代表這棵樹上p節點的個數。輸入樣例
2 5 0 1 1 2 2 3 3 4 3 0 2 0 1輸出樣例
3 1
這道題，WA也不知道為啥，找不到錯在哪里，用的結構體。后來發現用鄰接矩陣的方法比較優秀，而且以前沒有這么用過，就換用這種方法，學習學習。 思路：定義一個二組數組作為鄰接矩陣，每次輸入一組節點i，j，就分別在matrix[i][j]和val[i],val[j]加一。 學習使用鄰接矩陣處理兩點相關的問題。代碼不貼。
新聞熱點
疑難解答
