時間不夠代碼沒寫注釋，抱歉!!!
題目（1）
時間限制: 400 ms 記憶體限制: 64 MB 代碼長度限制: 16 KB
簡單分析
簡單來說就是求 N的k次方mod素數10007 這裡用到兩個公式。
費馬小定理：
和 基本定律 (a + b * n) mod n ≡ a mod n
詳細可以看：https://www.zybuluo.com/Lin--/note/1373807 上面有簡單描述。
代碼
int Power(int a, int b)
{
if(a > 10007 || b > 10006)
return Power(a%10007, b%10006);
if(a == 0)
return 0;
int answer = 1, tmp = 0;
while(tmp < b)
{
answer *= a;
if(answer >= 10007)
answer = answer % 10007;
tmp++;
}
return answer;
}
題目(2)
時間限制: 1200 ms 記憶體限制: 24 MB 代碼長度限制: 16 KB
簡單分析
與兩個等長有序序列的中位數類似（折半查找和merge算法）
merge算法(僞代碼)：
輸入：數組A[1...m]和它的三個索引去p,q,r，1 <= p <= q < r <= m,兩個子數組A[p...q]和A[q+1...r]各自按升序排列
輸出:合并兩個子數組A[p...q]和A[q+1...r]
comment: B[p...r]是個輔助數組
s <- p; t <- q + 1; k <- p
while s <= q and t <= r
if A[s] <= A[t] then
B[k] <- A[s]
s <- s + 1
else
B[k] <- A[t]
t <- t + 1
end if
k <- k + 1
end while
if s = q + 1 then B[k...r] <- A[t...r]
else B[k...r] <- A[s...q]
end if
A[p...r] <- B[p...r]
merge算法因為是得到一個新的排序是以複雜度為Θ（n），但是我們不用那麼多資訊，是以我們不需要一個個的往後比較，使用二分的方法可以将時間複雜度降為Θ（log2n）。
find_midian 的算法
輸入:數組A[1...n]和B[1...n]
輸出:兩個子數組的合并數組的中位數p
s <- 1; q <- 1; k <- m - 1
while m > 1
if A[s + (k + 1)/2] > B[q + (k + 1)/2]) then
s <- s + (k + 1)/2
else
q <- q + (k + 1)/2
end if
k <- k/2
end while
if A[s] < B[s]（這裡輸出低位中位數） then
p <- A[s]
else
p <- B[s]
上面是等長數組的，而非等長數組我們則需要将其删減為等長數組。A[1…n]和B[1…m]兩個數組，假設n > m + 1，則數組A中存在不可能是中位數的位置。
如：若n > m + 1的情況下，即使在最極端的A[n] > B[1]的情況下，A[(m+n)/2…n]是無法被選取為中位數的，即使同理，A[1] < B[m]的情況下，A[1…(m - n)/2]也是無法被取為中位數的。
Array (A[1], A[2], ... , A[m], B[1], ... , B[n])的中位數為 A[(m+n)/2]
Array ( B[1], ... , B[n] , A[1], A[2], ... , A[m])的中位數為 A[(m-n)/2]
但是這裡我們把數組A删除至長度為 M + 1 ，A數組可以被選為中位數的長度段為 A [ (m - n - 1) / 2 … (m + n) / 2 ]，我們仍然需要讨論特例A[(m + n) / 2]，若A[(m + n) / 2] < B[0] 時，中位數就是A[(m + n) / 2]啦，如果還沒找到剩下的兩個數組丢到上面的find_midian裡面運算完就是中位數啦
代碼
int median(int *a,int *b, int n1,int n2,int lowa,int lowb)
{
if(n1 > n2)
{
lowa = (n1 - n2 - 1)/2;
if(a[lowa + n2] < b[0])
return a[lowa + n2];
if(a[lowa] > b[n2 - 1])
return a[lowa];
}
if(n1 < n2)
{
lowb = (n2 - n1 - 1)/2;
if(b[lowb + n1] < a[0])
return b[lowb + n1];
if(b[lowb] > a[n1 - 1])
return b[lowb];
}
int shanchu;
if(n2 > n1)
shanchu = n1;
else
shanchu = n2;
int tmp_shan = 0;
while(shanchu != 0)
{
tmp_shan = (shanchu + 1)/2;
if(a[lowa + tmp_shan - 1] > b[lowb + tmp_shan - 1])
lowb += tmp_shan;
else
lowa += tmp_shan;
shanchu -= tmp_shan;
}
if(a[lowa] < b[lowb])
return a[lowa];
else
return b[lowb];
}
備注
如果這裡沒有懂，請麻煩私聊我，之後我盡量改進自己的描述
題目（3）
時間限制: 10000 ms 記憶體限制: 64 MB 代碼長度限制: 16 KB
分析
簡單的排序，10000的随機正整數，用Θ（nlog2n）的任意算法都行吧。
這裡用的是快排，寫的不是很好。
代碼
#include <iostream>
using namespace std;
void quick_sort(int a[], int length)
{
if(length < 2)
return;
int side = 0, tmp;
for(int num = 1; num < length; num++)
{
if(a[num] > a[0])
{
side++;
tmp = a[side];
a[side] = a[num];
a[num] = tmp;
}
}
tmp = a[side];
a[side] = a[0];
a[0] = tmp;
quick_sort(a,side);
quick_sort(a+side+1,length-side-1);
}
int arr[1000000];
int main()
{
std::ios::sync_with_stdio(false);
int length;
cin >> length;
for(int num = 0; num < length; num++)
cin >> arr[num];
quick_sort(arr,length);
for(int num = length - 1; num > 0; num--)
cout << arr[num] << " ";
cout << arr[0];
}
題目(4)
時間限制: 400 ms 記憶體限制: 64 MB 代碼長度限制: 16 KB
提示把算法描述的很好了，我就瞎叨叨了。
代碼
#include <iostream>
using namespace std;
int arr[1000];
int quick_sort(int arr[], int length, int k)
{
if(length == 1)
return arr[0];
int side = 0, side2 = 0, tmp;
for(int num = 1; num < length; num++)
{
if(arr[num] == arr[0])
side2++;
if(arr[num] < arr[0])
{
side++;
tmp = arr[num];
arr[num] = arr[side];
arr[side] = tmp;
}
}
if(side > k - 1 && side > 0)
return quick_sort(arr + 1, side, k);
else if(side + side2 < k - 1 && side + side2 > 0)
return quick_sort(arr + side + 1, length - side - 1, k - side - 1);
else
return arr[0];
}
int main()
{
std::ios::sync_with_stdio(false);
int length, k;
cin >> length;
cin >> k;
for(int tmp = 0; tmp < length; tmp++)
cin >> arr[tmp];
cout << quick_sort(arr,length,k);
}