时间不够代码没写注释，抱歉!!!
题目（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);
}