hdu2196 Computer的时间复杂度

题目描述：

输入两个正整数n，m，求n^m的最后三位数表示的整数。

输入：

输入数据有多组，每组数据占一行，包括两个正整数n，m(1<=n,m<=10^6)。

输出：

对于每组输入数据，输出一行，即n^m的最后三位数表示的整数。

样例输入：

2 2

2 3

3 3

样例输出：

4

8

7

算法分析：

本题需要使用快速幂算法，否则会超时。

快速幂算法的时间复杂度为O(log n)。

代码实现：

相关问题

hdu3348 活动安排问题

hdu3348 活动安排问题 是一个经典的贪心算法问题，题目描述如下：

有 n 个活动，每个活动有开始时间 s 和结束时间 t，一个人在同一时间只能参加一个活动，问最多能参加多少个活动。

具体做法是按照结束时间从小到大排序，每次选择结束时间最早的活动，计数器加一，并将其结束时间设为当前时间，然后继续选择结束时间最早的活动，直到所有活动都被选择为止。

以下是 hdu3348 活动安排问题 的 C++ 代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 100010;
struct Activity {
    int s, t;
} a[maxn];

bool cmp(Activity a1, Activity a2) {
    return a1.t < a2.t;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        for (int i = 0; i < n; i++) {
            cin >> a[i].s >> a[i].t;
        }
        sort(a, a + n, cmp);
        int ans = 1, t = a[0].t;
        for (int i = 1; i < n; i++) {
            if (a[i].s >= t) {
                ans++;
                t = a[i].t;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

时间复杂度为 O(nlogn)，其中 n 表示活动的数量。因为需要对活动按照结束时间进行排序，排序的时间复杂度为 O(nlogn)，遍历所有活动的时间复杂度为 O(n)，因此总的时间复杂度为 O(nlogn)。

hdu4911 逆序对

hdu4911 逆序对 是一个经典的归并排序问题，题目描述如下：

给定一个长度为 n 的数组，求其中逆序对的数量，逆序对指的是所有满足 i < j 且 a[i] > a[j] 的 (i, j) 对数。

具体做法是使用归并排序，在排序的过程中统计逆序对的数量。将数组不断分成两半，分别对左半部分和右半部分进行归并排序，然后将两个有序的部分合并成一个有序的数组，并在合并的过程中统计逆序对的数量。

以下是 hdu4911 逆序对 的 C++ 代码实现：

#include <iostream>
using namespace std;

typedef long long ll;
const int maxn = 500010;
int a[maxn], b[maxn];

ll merge_sort(int l, int r) {
    if (l == r) return 0;
    int mid = (l + r) / 2;
    ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            b[k++] = a[i++];
        } else {
            b[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while (i <= mid) b[k++] = a[i++];
    while (j <= r) b[k++] = a[j++];
    for (int i = 0; i < k; i++) {
        a[l + i] = b[i];
    }
    return res;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        ll ans = merge_sort(0, n - 1);
        cout << ans << endl;
    }
    return 0;
}

时间复杂度为 O(nlogn)，其中 n 表示数组的长度。因为归并排序的时间复杂度为 O(nlogn)，在合并的过程中统计逆序对的数量的时间复杂度为 O(n)，因此总的时间复杂度为 O(nlogn)。