解題區/解題區 - 其他題目

2015 Facebook Hacker Cup 資格賽

［2015 Facebook Hacker Cup 資格賽］贖罪篇

windows 參賽，卡了一個 \r\n 問題，剛好有裝 git，使用以下指令做轉換

1
$ awk '{ sub("\r$", ""); print }' out.txt > output.txt
  • Cooking the Books (15 points)

會計師要騙過稽查人員，可以把金融數值任意交換兩個位置上的數字，請問能交換得到的最大、最小值分別為何？並且數字不可起首為 0。

喵蛋，最簡單的這題 recover step 因 continue 指令而被忽略，窮舉兩個位置做交換，大部分可以看到寫法有 string compare, int compare，最方便是在字串下處理，接著看要轉數字或者直接用字典順序比較都行。

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
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    freopen("cooking_the_books.txt", "r", stdin);
    freopen("out.txt", "w+", stdout); 
    int testcase, cases = 0;
    char s[64];
    scanf("%d", &testcase);
    while (testcase--) {
        long long ret1, ret2, tmp;
        scanf("%s", s);
        sscanf(s, "%lld", &ret1);
        sscanf(s, "%lld", &ret2);
        int n = strlen(s);
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                swap(s[i], s[j]);
                sscanf(s, "%lld", &tmp);
                if (s[0] != '0') { 
                    ret1 = min(ret1, tmp);
                    ret2 = max(ret2, tmp);
                } 
                swap(s[i], s[j]);
            }
        }
        printf("Case #%d: %lld %lld", ++cases, ret1, ret2);
        putchar('\n');
    }
    return 0;
}
  • New Year’s Resolution (30 points)

新年新希望，目標均衡飲食，要求蛋白質、澱粉、脂肪攝取剛好的量，挑選 n 個食物，只有不選、或者是只能一樣走。求是否能辦到？

在 n 不大的時候，套用 bitmask 窮舉最為方便。用 Dfs 搜索當然喜聞樂見，如果 n 很大，而要求的量很小，則可以使用三維 dp[P][C][F] 狀態來解決。如果要求倍數關係，而數量無限的話，可以轉換成幾何分析。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    freopen("new_years_resolution.txt", "r", stdin);
    freopen("out.txt", "w+", stdout); 
    int testcase, n, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        int GP, GC, GF;
        int P[32], C[32], F[32];
        scanf("%d %d %d", &GP, &GC, &GF);
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d %d", &P[i], &C[i], &F[i]);
            
        int ret = 0;
        for (int i = (1<<n)-1; i >= 0 && !ret; i--) {
            int a = 0, b = 0, c = 0;
            for (int j = 0; j < n; j++) {
                if ((i>>j)&1) {
                    a += P[j];
                    b += C[j];
                    c += F[j];
                }
            }
            ret |= a == GP && b == GC && c == GF;
        }
        printf("Case #%d: %s\n", ++cases, ret ? "yes" : "no");
    }
    return 0;
}
  • Laser Maze (55 points)

給予 2D 地圖，裡面的雷射裝置將會感應使用者的腳步，每踏一步則順時針換方向，並且發射出雷射，雷射只會因牆壁、雷射塔而被屏蔽，但是雷射跟雷射之間不會相消、折射。現在雷射裝置的起始方向各有不同，避開雷射，找最少步數抵達終點。(只能走上下左右四個方向，停留不能解決問題，雷射裝置因感測而行動。)

基礎的 Bfs，因為只有四個方向，根據時間做紀錄，每四次操作進行一個循環，則 int dist[time4][pos_x][pos_y]，考慮在哪一個 time mod 4 抵達某個位置。接下來麻煩的是檢查操作，檢查操作有兩種，其一，預處理每個時間下雷射發射，其二，從當前位置反搜索雷射光是否對著自己。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <assert.h>
using namespace std;
char g[128][128];
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const char dv[] = "<^>v";
int dist[4][128][128], n, m;
int valid(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m;
}
char next(char c, int t) {
    static char v[] = "^>v<";
    for (int i = 0; i < 4; i++) {
        if (v[i] == c)
            return v[(i + t)%4];
    }
    assert(false);
}
int test(int t, int x, int y) {
    int tx, ty;
    for (int i = 0; i < 4; i++) {
        tx = x, ty = y;
        while (valid(tx, ty) && g[tx][ty] == '.')
            tx += dx[i], ty += dy[i];
        if (valid(tx, ty) && g[tx][ty] != '#') {
            char c = g[tx][ty];
            if (next(c, t) == dv[i])
                return 1;
//			printf("%c %c %d\n", next(g[tx][ty], t), dv[i], i);
        }
    }
    return 0;
}
void bfs() {
    memset(dist, 0, sizeof(dist));
    int sx, sy, ex, ey;
    int x, y, tx, ty, t;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'S')
                sx = i, sy = j, g[i][j] = '.';
            if (g[i][j] == 'G')
                ex = i, ey = j, g[i][j] = '.';
        }
    }
    dist[0][sx][sy] = 1;
    queue<int> X, Y, T;
    X.push(sx), Y.push(sy), T.push(0);
    while (!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        t = T.front(), T.pop();
        int d = dist[t][x][y] + 1;
        if (x == ex && y == ey) {
            printf("%d\n", d - 2);
            return;
        }
        for (int i = 0; i < 4; i++) {
            tx = x + dx[i], ty = y + dy[i];
            if (!valid(tx, ty))
                continue;
            if (g[tx][ty] != '.')
                continue;
            if (test((t+1)%4, tx, ty))
                continue;
            if (dist[(t+1)%4][tx][ty] == 0) {
                dist[(t+1)%4][tx][ty] = d;
                X.push(tx), Y.push(ty), T.push((t+1)%4);
            }
        }
    }
    puts("impossible");
}
int main() {
    freopen("laser_maze.txt", "r", stdin);
    freopen("out.txt", "w+", stdout);
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
            scanf("%s", &g[i]);
        printf("Case #%d: ", ++cases);
        bfs();
    }
    return 0;
}
/*
999
2 5
##^##
S...G
2 6
###<##
S....G
2 5
##v##
S...G
1 5
S..G<
1 6
S...G<
5 5
S....
.....
.>v..
.^<..
....G
*/
Read More +
解題區/解題區 - 其他題目

ZJOI 2012 DAY2 灾难

Problem

阿米巴是小强的好朋友。
阿米巴和小强在草原上捉蚂蚱。小强突然想，如果蚂蚱被他们捉灭绝了，那么吃蚂蚱的小鸟就会饿死，而捕食小鸟的猛禽也会跟着灭绝，从而引发一系列的生态灾难。
学过生物的阿米巴告诉小强，草原是一个极其稳定的生态系统。如果蚂蚱灭绝了，小鸟照样可以吃别的虫子，所以一个物种的灭绝并不一定会引发重大的灾难。
我们现在从专业一点的角度来看这个问题。我们用一种叫做食物网的有向图来描述生物之间的关系：
一个食物网有N个点，代表N种生物，如果生物x可以吃生物y，那么从y向x连一个有向边。
这个图没有环。
图中有一些点没有连出边，这些点代表的生物都是生产者，可以通过光合作用来生存； 而有连出边的点代表的都是消费者，它们必须通过吃其他生物来生存。
如果某个消费者的所有食物都灭绝了，它会跟着灭绝。
我们定义一个生物在食物网中的“灾难值”为，如果它突然灭绝，那么会跟着一起灭绝的生物的种数。
举个例子：在一个草场上，生物之间的关系是：

如果小强和阿米巴把草原上所有的羊都给吓死了，那么狼会因为没有食物而灭绝，而小强和阿米巴可以通过吃牛、牛可以通过吃草来生存下去。所以，羊的灾难值是1。但是，如果草突然灭绝，那么整个草原上的5种生物都无法幸免，所以，草的灾难值是4。
给定一个食物网，你要求出每个生物的灾难值。

Input

第一行是一个正整数N，表示生物的种数。生物从1标号到N。
接下来N行，每行描述了一个生物可以吃的其他生物的列表，格式为用空格隔开的若干个数字，每个数字表示一种生物的标号，最后一个数字是0表示列表的结束。

Output

包含N行，每行一个整数，表示每个生物的灾难值。

Sample Input

1
2
3
4
5
6
5
0
1 0
1 0
2 3 0
2 0

Sample Output

1
2
3
4
5
4
1
0
0
0

Solution

解法參照網路各位大神，效率為 O(E log V)，必須為 DAG 圖。

题目大意 ：给你一个有向可拓扑图，入度为零的点成为源点，然后考虑每一个点，假若删掉了他以及对应的边，那么除他外有多少个点不可达源点。

算法 ：按拓扑序遍历N个点，将距每个点最近的必须通过的点设为它的父亲，构造出一棵树。对于每个点，若向它连边的点只有一个，其父亲就是向它连边的点；若向它连边的点不只一个，其父亲是向它连边的所有点的最近公共祖先。删掉每个点后不可达点个数就是其子树的节点个数。

這個做法接近貪婪思路，建造一個瓶頸樹，建造的過程找到最鄰近的瓶頸，而瓶頸的找法根據 LCA 完成。

  • 建造完，利用 dfs 計算子樹大小，發生 stackoverflow，系統恰好沒有抓到，改用 bfs 計算就 A 過。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <stdio.h> 
#include <vector>
#include <queue>
#include <string.h>
#include <algorithm>
#include <assert.h>
using namespace std;
// http://oi.nks.edu.cn/showproblem?problem_id=2646 
#define MAXN 65536
#define LOGMAXN 17
vector<int> g[MAXN], invg[MAXN], tree[MAXN];
int indeg[MAXN] = {};
vector<int> toposort(vector<int> g[], int n) {
    vector<int> ret;
    queue<int> Q;
    int u, v;
    for (int i = 0; i <= n; i++)
        indeg[i] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < g[i].size(); j++)
            indeg[g[i][j]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0)
            Q.push(i);
    }
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        ret.push_back(u);
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i];
            if (--indeg[v] == 0)
                Q.push(v);
        }
    }
    return ret;
}
int depth[MAXN], parent[MAXN][LOGMAXN];
int getLCA(int x, int y) {
    int dist, i;
    if (depth[x] < depth[y])	swap(x, y);
    dist = depth[x] - depth[y];
    for (int i = 0; dist; i++, dist /= 2) {
        if (dist&1)	x = parent[x][i];
    }
    for (i = 0; x != y;) {
        if (parent[x][i] != parent[y][i] || (i == 0 && parent[x][i] == parent[y][i])) {
            x = parent[x][i];
            y = parent[y][i];
            i++;
        } else {
            i--;
        }
    }
    return x;
}
void buildTree(vector<int> &topo, vector<int> g[], int n) {
    for (int i = 1; i <= n; i++)
        tree[i].clear();
    int u, v;
    parent[0][0] = -1, depth[0] = 0;
    for (int i = 0; i < topo.size(); i++) {
        u = topo[i];
        if (g[u].size() == 0) {
            depth[u] = 1, parent[u][0] = 0;
            continue;
        }
        int lca = g[u][0];
        for (int j = 0; j < g[u].size(); j++)
            v = g[u][j], lca = getLCA(lca, v);
        depth[u] = depth[lca] + 1;
        parent[u][0] = lca;
        tree[lca].push_back(u);
        for (int i = 0; parent[u][i]; i++) {
            parent[u][i+1] = parent[parent[u][i]][i];
        }
    }
}
int used[MAXN], subtree[MAXN];
void sumTree(int n) {
    queue<int> Q;
    int u, v;
    for (int i = 1; i <= n; i++) {
        subtree[i] = 1;
        indeg[i] = tree[i].size();
        if (tree[i].size() == 0)	Q.push(i);
    }
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        v = parent[u][0];
        indeg[v]--;
        subtree[v] += subtree[u];
        if (indeg[v] == 0)
            Q.push(v);
    }
}
int main() {	
    int n, x, y, u, v;
    while(scanf("%d", &n) == 1) {
        for (int i = 0; i <= n; i++)
            g[i].clear(), invg[i].clear();
        for (int i = 1; i <= n; i++) {
            while (scanf("%d", &x) == 1 && x) {
                g[i].push_back(x);
                invg[x].push_back(i);
            }
        }
        vector<int> topo = toposort(invg, n);
        buildTree(topo, g, n);
        sumTree(n);
        for (int i = 1; i <= n; i++)
            printf("%d\n", subtree[i] - 1);
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

建造二元搜尋樹 O(n log n)

Problem

參照 Zerojudge d526: Binary Search Tree (BST) 按照插入的順序，建造一棵二元搜尋樹，原則上很簡單，但是很容易遇到極端的偏斜情況，如果插入順序很接近已經排序過的順序，則複雜度最慘為 O(n^2)。

Sample Input

1
2
3
4
11
368 115 121 88 741 762 801 34 41 511 60
6
5 2 10 4 9 15

Sample Output

1
2
368 115 88 34 41 60 121 741 511 762 801
5 2 4 10 9 15

Solution

核心

先稍微認識一下笛卡爾樹 (一種二元樹)，每個節點為 <key, value>，只看 key 時，笛卡爾樹是一棵二元搜尋樹，而看 value 時，它是一個最大堆 (或者是最小堆)。

在建造前，先撇清一點，笛卡爾樹的深度可能到達 n，與一般平衡樹不同。

笛卡爾樹如何建造 ? 假使已經對於 key 值由小到大排序 (升排序)，那麼將點依序插入笛卡爾樹，能保證的是－由於要符合二元搜尋樹，新加入的點一定是這棵樹某個節點的右節點。知道這一點後，再往前考慮前一次插 入的點(它原本也符合再某節點的右節點)，往這個節點往上爬，直到符合最大堆(性質 node.v > new_insert.v)，這時將這個節點的右子樹移到新加入節點的左子樹 (此時符合二元搜尋樹的性質，也保有原本堆的性質)。就這麼持續入點下去。

這麼發現，往上爬的次數不超過節點個數，因為每個節點只會從右子樹換到左子樹。均攤下 O(n) (每個節點只會從右子樹推到左子樹一次，因此最多 n 次)

我們接著將 “按照順序插入的 BST” 轉換成建造笛卡爾樹，key 值依舊為輸入的元素大小，而 value 則訂為輸入順序，根據 key 值為一個二元搜尋樹，根據 value 建造一個最小堆，那麼仔細思考可以得到與原本相同的二元搜尋樹。

建造笛卡爾樹只需要花 O(n) 時間，但建造前必須根據 key 排序 O(n log n)，所以複雜度為 O(n log n)。

在這樣的方式建造有一個缺點，並不知道途中插入的情況，只會在最後得到一樣的二元搜尋樹。假使要得到途中插入的情況，考慮離線處理，將所有操作儲存起來，而二元樹的節點位置並不會更動的情況下，事先建造一個靜態樹，隨後使用一個懶標記存在與否即可。

補充

  • 如何利用這個笛卡爾樹解決最簡單的 RMQ 問題？
    對於 <key, value> = <i, A[i]> 所建造的笛卡爾樹，可以利用 LCA 的 tarjan 算法(離線作法) 在 O(n) 時間內完成。RMQ 假使查找 [l, r] 的最小值，又因為我們根據 value 建造最小堆，則根據 tarjan 的搜索順序，拜訪右子樹時(對於區間的 r 來說)，左子樹將會跟其 LCA 合併，而 LCA 的 index 肯定比左子樹來得大 (大於等於 l)，又根據最小堆保證是大於等於 l 且小於等於 r 的最小值。
  • 只有笛卡爾樹可以做到建造二元搜尋樹嗎？
    其實並不然，還可以藉由一個額外的平衡樹來完成，效率一樣在 O (n log n)，但是親自撰寫平衡樹本身就本末倒置，如果藉由 STL 提供的平衡樹，代碼量會比笛卡爾樹好寫多。具體而言使用 lower_bound 查找當前插入的元素位在哪兩個元素之間，一定符合在右子樹或者是左子樹。
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
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
struct Node {
    int key, value;
    int lson, rson, parent;
};
Node D[65536];
void insertCartesianTree(int index, Node D[]) {
    int p = index - 1;
    while(D[p].value > D[index].value)
        p = D[p].parent;
    D[D[p].rson].parent = index;
    D[index].lson = D[p].rson;
    D[p].rson = index;
    D[index].parent = p;
}
void dfsPrint(int node) {
    if(node == 0)    return;
    printf("%d ", D[node].key);
    dfsPrint(D[node].lson);
    dfsPrint(D[node].rson);
}
int main() {
    int N, x;
    pair<int, int> A[65536];
    while(scanf("%d", &N) == 1 && N) {
        for(int i = 1; i <= N; i++) {
            scanf("%d", &x);
            A[i] = make_pair(x, i);
        }
        sort(A+1, A+1+N);
        D[0].value = -1;
        D[0].lson = D[0].rson = D[0].parent = 0;
        for(int i = 1; i <= N; i++) {
            D[i].lson = D[i].rson = D[i].parent = 0;
            D[i].value = A[i].second, D[i].key = A[i].first;
        }
        for(int i = 1; i <= N; i++) {
            insertCartesianTree(i, D);
        }
        dfsPrint(D[0].rson);
        puts("");
    }
    return 0;
}
Read More +
解題區/解題區 - 其他題目

程序设计实习 MOOC Week 9 DEX

接續上一篇

D - 热血格斗场

題目

总时间限制: 1000ms 内存限制: 65536kB

描述

为了迎接08年的奥运会，让大家更加了解各种格斗运动，facer新开了一家热血格斗场。格斗场实行会员制，但是新来的会员不需要交入会费，而只要同一名老会员打一场表演赛，证明自己的实力。

我们假设格斗的实力可以用一个正整数表示，成为实力值。另外，每个人都有一个唯一的id，也是一个正整数。为了使得比赛更好看，每一个新队员都会选择与他实力最为接近的人比赛，即比赛双方的实力值之差的绝对值越小越好，如果有两个人的实力值与他差别相同，则他会选择比他弱的那个（显然，虐人必被虐好）。

不幸的是，Facer一不小心把比赛记录弄丢了，但是他还保留着会员的注册记录。现在请你帮facer恢复比赛纪录，按照时间顺序依次输出每场比赛双方的id。

输入

第一行一个数n(0 < n <=100000)，表示格斗场新来的会员数（不包括facer）。以后n行每一行两个数，按照入会的时间给出会员的id和实力值。一开始，facer就算是会员，id为1，实力值1000000000。输入保证两人的实力值不同。

输出

N行，每行两个数，为每场比赛双方的id，新手的id写在前面。

样例输入

3
2 1
3 3
4 2

样例输出

2 1
3 2
4 2

解法

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
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <stdlib.h>
#include <set>
using namespace std;
int main() {
#define oo 0x3f3f3f3f
    for(int n, id, power; scanf("%d", &n) == 1;) {
        set< pair<int, int> > S;
        S.insert(make_pair(1000000000, 1));
        for(int i = 0; i < n; i++)	 {
            scanf("%d %d", &id, &power);
            S.insert(make_pair(power, id));
            set< pair<int, int> >::iterator it;
            it = S.find(make_pair(power, id));
            pair<int, int> f1, f2;
            f1 = make_pair(-oo, 0);
            f2 = make_pair(oo, 0);
            if(it != S.begin()) {
                it--;
                f1 = *it;
                it++;
            }
            if(it != S.end()) {
                it++;
                f2 = *it;
                it--;
            }
            if(abs(f2.first - power) < abs(f1.first - power))
                f1 = f2;
            printf("%d %d\n", id, f1.second);
        }
    }	
    return 0;
}

E - priority queue练习题

題目

总时间限制: 2500ms 内存限制: 131072kB

描述

我们定义一个正整数a比正整数b优先的含义是：
*a的质因数数目（不包括自身）比b的质因数数目多；
*当两者质因数数目相等时，数值较大者优先级高。

现在给定一个容器，初始元素数目为0，之后每次往里面添加10个元素，每次添加之后，要求输出优先级最高与最低的元素，并把该两元素从容器中删除。

输入

第一行: num (添加元素次数，num <= 30)

下面10*num行，每行一个正整数n（n < 10000000).

输出

每次输入10个整数后，输出容器中优先级最高与最低的元素，两者用空格间隔。

样例输入

1
10 7 66 4 5 30 91 100 8 9

样例输出

66 5

解法

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
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <set>
using namespace std;
int getPF(int n) {
    int ret = 0;
    for(int i = 2; i*i <= n; i++) {
        if(n%i == 0) {
            while(n /= i, n%i == 0);
            ret++;
        }
    }
    if(n != 1 && ret > 0)	ret++;
    return ret;
}
int main() {
    for(int n; scanf("%d", &n) == 1;) {
        multiset< pair<int, int> > S;
        while(n--) {
            for(int i = 0, x; i < 10; i++) {
                scanf("%d", &x);
                S.insert(make_pair(getPF(x), x));
            }			
            multiset< pair<int, int> >::iterator it;
            multiset< pair<int, int> >::iterator jt;
            it = S.begin();
            jt = S.end();
            jt--;
            printf("%d %d\n", (*jt).second, (*it).second);
            S.erase(it);
            S.erase(jt);
        }
    }
    return 0;
}

X - 思考题最后一题，不计分，供测试

題目

总时间限制: 1000ms 内存限制: 65536kB

描述

请补齐下面程序，使得补齐后的程序，对于下面指定的输入数据，能产生指定的输出。

1
2
3
4
5
6
#include <iostream>
#include <string>
using namespace std;
template <class T>
class CMyistream_iterator
{

// 在此处补充你的代码

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
};
int main()  
{ 
     
     int t;
     cin >> t;
     while (t--) {
     	 CMyistream_iterator<int> inputInt(cin);
         int n1,n2,n3;
         n1 = * inputInt;
         int tmp = * inputInt; 
         cout << tmp << endl;
         inputInt ++;   
         n2 = * inputInt; 
         inputInt ++;   
         n3 = * inputInt; 
         cout << n1 << "," << n2<< "," << n3 << ",";
         CMyistream_iterator<string> inputStr(cin);
         string s1,s2;
         s1 = * inputStr; 
         inputStr ++;     
         s2 = * inputStr; 
         cout << s1 << "," << s2 << endl;
    }
    return 0;  
}

输入

第一行是整数t,表示有t组数据。
每组数据由三个整数和两个字符串组成。整数都是小于220的正整数，字符串中间没有空格

输出

对每组输入数据，输出两行。
第一行是输入的第一个整数。
第二行依次输出输入的各项，用逗号","分隔。

样例输入

2
79 90 20 hello me
21 375 45 Jack good

样例输出

79
79,90,20,hello,me
21
21,375,45,Jack,good

解法

這裡要特別小心串流處理，這裡仍是用指針去維護。

Pointer Type(*) 和 Reference Type(&) 使用上也要明白差別。

  • 假使宣告 istream &mcin;
    一定要用 CMyistream_iterator(istream& m): mcin(m) 搭配 mcin >> front

    • 為什麼 mcin = m 不能取代 mcin(m) ?
      雖然我不太明白，但是 Reference Type 一定要在宣告的時候就決定取的位址，也就是說 mcin 再也不能跟動對應的位址，與指標不同的地方就在這裡。

      通常會這個寫來降低複雜度 int& ret = MAP[index]; 其中 ret 再也不能更動位址，當然也許再 C++11 之後的版本會有所不同。

  • 假使宣告 istream *mcin;
    彈性就很大，但使用時都要用 *mcin >> front

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
#include <iostream>
#include <string>
using namespace std;
template <class T>
class CMyistream_iterator
{
    public:
        CMyistream_iterator(istream& m): mcin(&m) {
            *mcin >> front;
        }
        void operator ++(int) {
            *mcin >> front;
        }
        T operator * () {
            return front;
        }
    private:
        istream *mcin;
        T front;
};
int main()  
{ 
     
     int t;
     cin >> t;
     while (t--) {
     	 CMyistream_iterator<int> inputInt(cin);
         int n1,n2,n3;
         n1 = * inputInt;
         int tmp = * inputInt; 
         cout << tmp << endl;
         inputInt ++;   
         n2 = * inputInt; 
         inputInt ++;   
         n3 = * inputInt; 
         cout << n1 << "," << n2<< "," << n3 << ",";
         CMyistream_iterator<string> inputStr(cin);
         string s1,s2;
         s1 = * inputStr; 
         inputStr ++;     
         s2 = * inputStr; 
         cout << s1 << "," << s2 << endl;
    }
    return 0;  
}
Read More +
解題區/解題區 - 其他題目

程序设计实习 MOOC Week 9 ABC

關於這一周

練習 STL 的語法。 題目來源

好久沒有練 C++ 程序，這是一個訓練 STL 的題單。

練習項目

std::list

  • list.merge(other_list)
    將 other_list 內容搬運到 list 後，other_list 清空。
  • list.sort()
    不依賴 std::sort, 自己內部有一個 sort()。
  • list.unique()
    跟另外一套的有點相似，一樣是要在排序後才能運行當作去重複。

std::set & std::multiset

  • insert()
  • find()
    查找，後回傳 set<>::iterator 的型態。
  • set<>::iterator
    begin() 和 end() 的型態。
  • set<>::reverse_iterator
    rbegin() 和 rend() 的型態。
  • erase()
    特別小心這個，傳入如果是 iterator 的話，就只會刪除單一元素，如果對於 multiset 來說，傳入一般的值(不是迭代器指針) 則會將所有相同的都刪除。

std::string

  • find(str [, start_pos])
    正向搜索 str 這個字串從 start_pos 開始算起。
  • rfind()
    逆向搜索 str 這個字串。
  • substr(start_post, sub_length)
    從某個位置開始，截出一段長度。

A - List

題目

总时间限制: 4000ms 内存限制: 65536kB

描述

写一个程序完成以下命令：
new id ——新建一个指定编号为id的序列(id<10000)
add id num——向编号为id的序列加入整数num
merge id1 id2——合并序列id1和id2中的数，并将id2清空
unique id——去掉序列id中重复的元素
out id ——从小到大输出编号为id的序列中的元素，以空格隔开

输入

第一行一个数n，表示有多少个命令( n <= 200000)。以后 n 行每行一个命令。

输出

按题目要求输出。

样例输入

16
new 1
new 2
add 1 1
add 1 2
add 1 3
add 2 1
add 2 2
add 2 3
add 2 4
out 1
out 2
merge 1 2
out 1
out 2
unique 1
out 1

样例输出

1 2 3 
1 2 3 4
1 1 2 2 3 3 4

1 2 3 4

解法

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
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <algorithm>
#include <map>
#include <list>
using namespace std;
int main() {
    for(int n; scanf("%d", &n) == 1; )  {
        char cmd[10];
        int id, num, aid;
        map< int, list<int> > S;
        while(n--) {
            scanf("%s", cmd);
            if(cmd[0] == 'n') { // new
                scanf("%d", &id);
                S[id] = list<int>();
            } else if(cmd[0] == 'a') { // add
                scanf("%d %d", &id, &num);
                S[id].push_back(num);
            } else if(cmd[0] == 'm') { // merge
                scanf("%d %d", &id, &aid);
                S[id].merge(S[aid]);
            } else if(cmd[0] == 'u') { // unique
                scanf("%d", &id);
                S[id].sort();
                S[id].unique();
            } else { // out
                scanf("%d", &id);
                S[id].sort();
                list<int>::iterator it, jt;
                it = S[id].begin(), jt = S[id].end();
                int f = 0;
                for(; it != jt; it++) {
                    if(f)	putchar(' ');
                    f = 1;
                    printf("%d", *it);
                }
                puts("");
            }
        }
    }
    return 0;
}

B - Set

題目

总时间限制: 5000ms 内存限制: 100000kB

描述

现有一整数集（允许有重复元素），初始为空。我们定义如下操作：
add x 把x加入集合
del x 把集合中所有与x相等的元素删除
ask x 对集合中元素x的情况询问
对每种操作，我们要求进行如下输出。
add 输出操作后集合中x的个数
del 输出操作前集合中x的个数
ask 先输出0或1表示x是否曾被加入集合（0表示不曾加入），再输出当前集合中x的个数，中间用空格格开。

输入

第一行是一个整数n，表示命令数。0<=n<=100000。
后面n行命令，如Description中所述。

输出

共n行，每行按要求输出。

样例输入

7
add 1
add 1
ask 1
ask 2
del 2
del 1
ask 1

样例输出

1
2
1 2
0 0
0
2
1 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
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
int main() {
    for(int n, x; scanf("%d", &n) == 1;) {
        char cmd[10];
        multiset<int> S;
        set<int> I;
        while(n--) {
            scanf("%s", cmd);
            if(cmd[0] == 'a' && cmd[1] == 'd') { // add
                scanf("%d", &x);
                I.insert(x);
                S.insert(x);
                printf("%d\n", S.count(x));
            } else if(cmd[0] == 'a' && cmd[1] == 's') { // ask
                scanf("%d", &x);
                printf("%d %d\n", I.find(x) != I.end(), S.count(x));
            } else { // del
                scanf("%d", &x);
                printf("%d\n", S.count(x));
                S.erase(x);
            }
        }
    }
    return 0;
}

C - 字符串操作

題目

总时间限制: 1000ms 内存限制: 65536kB

描述

给定n个字符串（从1开始编号），每个字符串中的字符位置从0开始编号，长度为1-500，现有如下若干操作：

    copy N X L：取出第N个字符串第X个字符开始的长度为L的字符串。
    add S1 S2：判断S1，S2是否为0-99999之间的整数，若是则将其转化为整数做加法，若不是，则作字符串加法，返回的值为一字符串。
    find S N：在第N个字符串中从左开始找寻S字符串，返回其第一次出现的位置，若没有找到，返回字符串的长度。
    rfind S N：在第N个字符串中从右开始找寻S字符串，返回其第一次出现的位置，若没有找到，返回字符串的长度。
    insert S N X：在第N个字符串的第X个字符位置中插入S字符串。
    reset S N：将第N个字符串变为S。
    print N：打印输出第N个字符串。
    printall：打印输出所有字符串。
    over：结束操作。

其中N，X，L可由find与rfind操作表达式构成，S，S1，S2可由copy与add操作表达式构成。

输入

第一行为一个整数n（n在1-20之间）

接下来n行为n个字符串，字符串不包含空格及操作命令等。

接下来若干行为一系列操作，直到over结束。

输出

根据操作提示输出对应字符串。

样例输入

3
329strjvc
Opadfk48
Ifjoqwoqejr
insert copy 1 find 2 1 2 2 2
print 2
reset add copy 1 find 3 1 3 copy 2 find 2 2 2 3
print 3
insert a 3 2
printall
over

样例输出

Op29adfk48
358
329strjvc
Op29adfk48
35a8

解法

這一題算是裡面最繁瑣的一題，一部分是因為其輸入的規則需要遞歸分析。
而為了實現遞歸分析，需要可以偷看輸入的下一個 token，因此先把每一個 token 切出來放在 queue 裏頭。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <queue>
#include <ctype.h>
using namespace std;
char s[32][512], lineStr[1024];
string str[32];
int strSize;
queue<string> tokenQ;
int str2num(string s) {
    return atoi(s.c_str());
}
string num2str(int n) {
  	string s;
  	stringstream ss(s);
  	ss << n;
    return ss.str();
}
int isValidNum(string s) {
    int ret = 0;
    for(int i = 0; i < s.length(); i++) {
        if(!isdigit(s[i]))
            return -1;
        ret = ret * 10 + s[i] - '0';
        if(ret > 99999)
            return -1;
    }
    return ret;
}
string parsing() {
    string p = tokenQ.front();
    tokenQ.pop();
    if(p == "copy")  {
        string N, X, L;
        int n, x, l;
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            X = parsing();
        } else {
            X = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            L = parsing();
        } else {
            L = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N), x = str2num(X), l = str2num(L);
        
        return str[n].substr(x, l);
    } else if(p == "add") {
        string S1, S2;
        int s1, s2;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S1 = parsing();
        } else {
            S1 = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S2 = parsing();
        } else {
            S2 = tokenQ.front(), tokenQ.pop();
        }
        s1 = isValidNum(S1), s2 = isValidNum(S2);
        if(s1 < 0 || s2 < 0)
            return S1 + S2;
        else
            return num2str(s1 + s2);
    } else if(p == "find") {
        string S, N;
        int s, n;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S = parsing();
        } else {
            S = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N);
        int pos = str[n].find(S);
        
        if(pos != string::npos) {
            return num2str(pos);
        } else {
            return num2str(str[n].length());
        }
    } else if(p == "rfind") {
        string S, N;
        int s, n;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S = parsing();
        } else {
            S = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N);
        int pos = str[n].rfind(S);
        if(pos != string::npos) {
            return num2str(pos);
        } else {
            return num2str(str[n].length());
        }
    } else if(p == "insert") {
        string S, N, X;
        int s, n, x;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S = parsing();
        } else {
            S = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            X = parsing();
        } else {
            X = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N), x = str2num(X);
        str[n].insert(x, S);
    } else if(p == "reset") {
        string S, N, X;
        int s, n, x;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S = parsing();
        } else {
            S = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N);
        str[n] = S;
    } else if(p == "print") {
        string S, N, X;
        int s, n, x;
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N);
        printf("%s\n", str[n].c_str());
    } else if(p == "printall") {
        for(int i = 1; i <= strSize; i++)
            printf("%s\n", str[i].c_str());
    } else if(p == "over") {
        
    }
    return "";
}
int main() {
    for(int n; scanf("%d", &n) == 1;) {
        int N, X, L, S1, S2, S;
        for(int i = 1; i <= n; i++) {
            scanf("%s", s[i]);
            str[i] = s[i];
        }
        strSize = n;
        while(getchar() != '\n');
        while(gets(lineStr)) {
            stringstream sin(lineStr);
            string token;
            while(sin >> token)
                tokenQ.push(token);
            parsing();
        }
    }
    return 0;
}
Read More +