在THU的機試題里算是很水的一套吧。。
1. 最小花費
簡單DP，一開始理解錯題意了。。以為a[]是相鄰兩站間的距離，結果WA*6。。以為我DP都不會寫了。。
//2011年清華大學計算機研究生機試題 最小花費
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 100010
#define I long long
#define INF -1
int a, b, n;
I l1, l2, l3, c1, c2, c3, w[N], dp[N];
int main() {
int i, j;
I tp, wt;
while(~scanf("%lld %lld %lld %lld %lld %lld", &l1, &l2, &l3, &c1, &c2, &c3)) {
scanf("%d %d", &a, &b);
if(a > b) swap(a, b);
scanf("%d", &n);
for(i = 2; i <= n; ++i) scanf("%lld", &w[i]);
w[1] = 0;
if(a == b) {
puts("0");
continue;
}
for(i = a; i <= b; ++i) dp[i] = INF;
dp[a] = 0;
for(i = a; i <= b; ++i) {
for(j = i + 1; j <= b; ++j) {
if(dp[i] == -1) continue;
tp = w[j] - w[i];
if(tp > l3) break;
if(l2 < tp && tp <= l3) wt = c3;
else if(l1 < tp && tp <= l2) wt = c2;
else
wt = c1;
if(dp[j] == -1 || dp[i] + wt < dp[j]) dp[j] = dp[i] + wt;
}
}
printf("%lld\n", dp[b]);
}
return 0;
}
2. 約數的個數
暴力就行，不過只需算到sqrt
//2011年清華大學計算機研究生機試題 約數的個數
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n, a[1010];
int main() {
int i, tp, j;
while(~scanf("%d", &n)) {
for(i = 0; i < n; ++i) scanf("%d", &a[i]);
for(i = 0; i < n; ++i) {
if(a[i] == 1) {
puts("1");
continue;
}
else {
tp = (int)sqrt(a[i]);
int cnt = 0;
for(j = 1; j <= tp; ++j) {
if(a[i] % j == 0) cnt++;
}
cnt += cnt;
if(a[i] == tp * tp) cnt--;
printf("%d\n", cnt);
}
}
}
return 0;
}
3. 剩下的樹
暴力水過
//2011年清華大學計算機研究生機試題 剩下的樹
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int L, M, fg[10010];
int main() {
int i, a, b;
while(~scanf("%d %d", &L, &M)) {
memset(fg, 0, sizeof(fg));
while(M--) {
scanf("%d %d", &a, &b);
for(i = a; i <= b; ++i) fg[i] = 1;
}
int ans = 0;
for(i = 0; i <= L; ++i)
if(!fg[i]) ans++;
printf("%d\n", ans);
}
return 0;
}