HDU - 5210 - Delete && 5211 - Mutiple （BestCoder Round #39）

题目传送：HDU - 5210

HDU - 5210 - Delete

思路：简单题

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;

int n, k; 
int a[105];

int main() {
    while(scanf("%d", &n) != EOF) {
        set<int> se;
        for(int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            se.insert(a[i]);
        }
        scanf("%d", &k);
        int ma = se.size();
        if(k <= n - ma) {
            printf("%d\n", ma);
        }
        else {
            printf("%d\n", n - k);
        }
    }
    return 0;
}

题目传送：HDU - 5211

HDU - 5211 - Mutiple 

思路：直接暴力可以过，时间复杂度直逼O(n^2)，运行出来1000+ms，不过有更好的方法，先初始化每个数的最左位置为最右边（这里即n+1），再从最右往最左遍历，然后找是当前数的倍数的数中的最左位置，找完后再更新当前位置的数的最左位置，时间复杂度O(n*logn)，运行时间15ms;

AC代码（暴力）：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;

int n;
int a[10005];

int main() {
    while(scanf("%d", &n) != EOF) {
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = i + 1; j <= n; j++) {
                if(a[j] % a[i] == 0) {
                    ans += j;
                    //printf("%d\n", ans);
                    break;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

AC代码（带优化）：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cctype>
#define LL long long
#define INF 0x7fffffff
using namespace std;

int f[10005];
int a[10005]; 
int n;

int main() {
	while(scanf("%d", &n) != EOF) {
		for(int i = 1; i <= n; i ++) {
			scanf("%d", &a[i]);
		}
		
		for(int i = 1; i <= 10000; i ++) {
			f[i] = n + 1;			//初始化每个数出现的位置为最右 
		}
		
		int ans = 0;
		for(int i = n; i >= 1; i --) {	//从后往前找，并更新每个数出现的最左位置 
			int tmp = n + 1;
			for(int j = a[i]; j <= 10000; j += a[i]) {	//找每个含有a[i]因子的数中的最小位置 
				tmp = min(tmp, f[j]);
			}
			f[a[i]] = i;		//更新每个数出现的最左位置 
			if(tmp > n) tmp = 0;
			ans += tmp;
		}
		printf("%d\n", ans);
	}
	return 0;
}

HDU - 5210 - Delete && 5211 - Mutiple （BestCoder Round #39）

原文：http://blog.csdn.net/u014355480/article/details/45294479