紫书习题 第八章

发表于 | 分类于 |
字数统计: 618 字

我自己做的紫书第八章部分习题的整合。

例8-1 UVa120 Stacks of Flapjacks

题目链接

显然，直接把对应的数放到它应该在的地方的排序方式是最快的。
所以可以先对整个序列排一个序，然后从底向上判断某个位置上的数是否是排序后对应的数，不是的话就先把该数翻到最顶上，然后再翻到对应位置。
这么做就是最快的排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
char s[10005];
int st[10005], n, p[10005], cur;
int read(){
    int x = 0;
    char c = s[cur];
    while(c < '0' || c > '9'){
        if(c == '\n' || c == EOF)
            return 0;
        c = s[++cur];
    } 
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = s[++cur];
    return x; 
}
void init(){
    cur = n = 0;
    while(st[n] = read())
        p[n] = st[n], n++;
    sort(p, p + n);
}
void solve(){
    for(int i = 0; i < n - 1; ++i)
        printf("%d ", st[i]);
    printf("%d\n", st[n - 1]);
    for(int i = n - 1; i > 0; --i){
        if(p[i] == st[i])
            continue;
        int j;
        for(j = i - 1; st[j] != p[i]; --j)
            ;
        if(j) reverse(st, st + j + 1), printf("%d ", n - j);
        reverse(st, st + i + 1), printf("%d ", n - i);
    }
    printf("0\n");
}
int main(){
    while(fgets(s, 10000, stdin) != NULL){
        init();
        solve();
    }
    return 0;
}

例8-3 UVa1152 4 Values whose Sum is 0

题目链接

这题神烦，哈希表几乎不可能过得了。
所以还是直接排序后二分比较快。即所谓中途相遇法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[4005], b[4005], c[4005], d[4005];
int q[16000005];
ll ans;
void init(){
    n = read();
    for(int i = 0; i < n; ++i)
        a[i] = read(), b[i] = read(), c[i] = -read(), d[i] = -read();
    int cnt = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            q[cnt++] = c[i] + d[j];
    sort(q, q + cnt);
}
void solve(){
    ans = 0;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            ans += upper_bound(q, q + n * n, a[i] + b[j]) - lower_bound(q, q + n * n, a[i] + b[j]);
    printf("%lld\n", ans);
}
int main(){
    int T = read();
    while(T--){
        init();
        solve();
        if(T > 0) printf("\n");
    }
    return 0;
}