2019算法分析和复杂性理论课程作业

发表于 | 分类于

没来由地…突然很想记录一下…（XZ 老师的算法课）

第一次上机作业（09.09 - 09.23）：http://algorithm.openjudge.cn/hw201901/
第二次上机作业（10.14 - 10.28）：http://algorithm.openjudge.cn/hw201902/
第三次上机作业（10.28 - 11.18）：http://algorithm.openjudge.cn/hw201903/
第四次上机作业（11.18 - 12.16）：http://algorithm.openjudge.cn/201904/

第一次上机作业代码

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
int a[maxn], b[maxn];

int main()
{
    int n, na, nb;
    scanf("%d%d%d", &n, &na, &nb);
    for(int i = 0; i < na; i++)
        scanf("%d", &a[i]);
    for(int i = 0; i < nb; i++)
        scanf("%d", &b[i]);
    int awin(0), bwin(0), draw(0);
    for(int i = 0; i < n; i++)
    {
        if(a[i % na] == 0 && b[i % nb] == 0) draw++;
        if(a[i % na] == 0 && b[i % nb] == 2) awin++;
        if(a[i % na] == 0 && b[i % nb] == 5) bwin++;
        if(a[i % na] == 2 && b[i % nb] == 0) bwin++;
        if(a[i % na] == 2 && b[i % nb] == 2) draw++;
        if(a[i % na] == 2 && b[i % nb] == 5) awin++;
        if(a[i % na] == 5 && b[i % nb] == 0) awin++;
        if(a[i % na] == 5 && b[i % nb] == 2) bwin++;
        if(a[i % na] == 5 && b[i % nb] == 5) draw++;
    }
    if(awin > bwin) printf("A\n");
    if(bwin > awin) printf("B\n");
    if(awin == bwin) printf("draw\n");

    return 0;
}

B: 汉诺塔问题(Hanoi)：递归

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
#include <bits/stdc++.h>
using namespace std;

int n;
char s[3][2];

void solve(char a, char b, char c, int n)
{
    if(n == 1)
        printf("%d:%c->%c\n", n, a, c);
    else
    {
        solve(a, c, b, n - 1);
        printf("%d:%c->%c\n", n, a, c);
        solve(b, a, c, n - 1);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < 3; i++)
        scanf("%s", s[i]);
    solve(s[0][0], s[1][0], s[2][0], n);

    return 0;
}

C: 二维数组右上左下遍历：模拟

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
int row, col;
int a[maxn][maxn];

bool judge(int x, int y)
{
    if (x < 0 || y < 0) return false;
    if (x > row - 1 || y > col - 1) return false;
    return true;
}

int main()
{
    scanf("%d%d", &row, &col);
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            scanf("%d", &a[i][j]);
            
    for(int y = 0; y < col; y++)
    {
        int r = 0;
        int c = y;
        while(judge(r, c))
            printf("%d\n", a[r++][c--]);
    }

    for(int x = 1; x < row; x++)
    {
        int r = x;
        int c = col-1;
        while(judge(r, c))
            printf("%d\n", a[r++][c--]);
    }
    
    return 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
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;

const int maxn = 105;
int a[maxn][maxn];
int n, m;

bool judge(int x, int y)
{
    if(x < 0 || y < 0) return false;
    if(x > n - 1 || y > m - 1) return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            scanf("%d", &a[i][j]);

    int r = 0, c = 0;
    bool state = true;

    while(state)
    {
        printf("%d\n", a[r][c]);
        if(judge(r + 1, c - 1))
        {
            r = r + 1;
            c = c - 1;
        }
        else
        {
            if(judge(0, r + c + 1))
            {
                int tmp = r;
                r = 0;
                c = tmp + c + 1;
            }
            else
            {
                if(judge(r + c + 2 - m, m - 1))
                {
                    r = r + c + 2 - m;
                    c = m - 1;
                }
                else state = false;
            }
        }
    }

    return 0;
}

D: 由中根序列和后根序列重建二叉树：递归

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 <bits/stdc++.h>
using namespace std;

std::vector<int> node;
int tree[65536];

void solve(int l, int r, int rt, int idx)
{
    tree[idx] = node[rt];
    if (l == r)
        return;

    int pos, lson, rson;

    for (pos = l; pos <= r; pos++)
        if (node[pos] == node[rt])
            break;

    if (pos > l)
    {
        lson = rt - r + pos - 1;
        printf(" %d", node[lson]);
        solve(l, pos - 1, lson, idx << 1);
    }

    if (pos < r)
    {
        rson = rt - 1;
        printf(" %d", node[rson]);
        solve(pos + 1, r, rson, (idx << 1) + 1);
    }
}

int main()
{
    int x;
    while (scanf("%d", &x) != EOF)
        node.push_back(x);
    int n = node.size();
    printf("%d", node[n - 1]);
    solve(0, (n >> 1) - 1, n - 1, 1);

    return 0;
}

E: 文本二叉树：先建树/然后遍历/关键是建树

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
std::vector< std::pair<int, char> > v;
std::vector<int> g[maxn];
bool vis[maxn];

void init()
{
	v.clear();
	for(int i = 0; i < maxn; i++)
		g[i].clear();
}

void addedge(int u, int v)
{
	g[u].push_back(v);
}

void build(int n)
{
	for(int i = 1; i < n; i++)
	{
		int dep = v[i].first;
		char key = v[i].second;
		for(int j = i - 1; j >= 0; j--)
			if(g[j].size() < 2 && v[j].first == dep - 1 && v[j].second != '*')
            {
                addedge(j, i);
                break;
            }
	}
}

void PreOrder(int s)
{
	if(v[s].second == '*') return;
    printf("%c", v[s].second);
	for(int i = 0; i < g[s].size(); i++)
        PreOrder((g[s][i]));

	return ;
}

void InOrder(int s)
{
	if(v[s].second == '*') return ;
	if(g[s].size() > 0)
		InOrder(g[s][0]);
    printf("%c", v[s].second);
	if(g[s].size() > 1)
		InOrder(g[s][1]);

	return ;
}

void PostOrder(int s)
{
	if(v[s].second == '*') return;
	for(int i = 0; i < g[s].size(); i++)
		PostOrder(g[s][i]);
    printf("%c", v[s].second);

	return ;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		init();
		char s[maxn];
		scanf("%s", s);
		v.push_back(make_pair(0, s[0]));
		while(scanf("%s", s) != EOF)
		{
			if(s[0] == '0') break;
			int len = strlen(s);
			v.push_back(make_pair(len - 1, s[len - 1]));
		}

		int n = v.size();
		build(n);

		PreOrder(0);
		printf("\n");
		PostOrder(0);
		printf("\n");
		InOrder(0);
		printf("\n");
		if(t) printf("\n");
	}

	return 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
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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
char s[maxn];

struct node
{
    char name;
    node *lson, *rson;
    int len, cnt;
};

node *build()
{
    int top = 1;
    std::stack<node *> stk;
    scanf("%s", s);

    node *root = new node;
    root->name = s[0];
    root->lson = NULL;
    root->rson = NULL;
    root->len = 0;
    root->cnt = 0;
    stk.push(root);

    while (scanf("%s", s) != EOF)
    {
        if (s[0] == '0')
            break;
        int len = strlen(s);

        node *new_Node = new node;
        new_Node->name = s[len - 1];
        new_Node->lson = NULL;
        new_Node->rson = NULL;
        new_Node->len = len - 1;
        new_Node->cnt = 0;

        node *r = stk.top();
        while (new_Node->len - r->len != 1)
        {
            stk.pop();
            r = stk.top();
        }
        if (new_Node->name == '*')
        {
            r->cnt++;
            continue;
        }
        if (r->cnt == 0)
        {
            r->lson = new_Node;
            r->cnt++;
        }
        else if (r->cnt == 1)
        {
            r->rson = new_Node;
            r->cnt++;
        }
        if (r->cnt == 2)
            stk.pop();
        stk.push(new_Node);
    }

    return root;
}
void PreOrder(node *root)
{
    if (!root)
        return;
    printf("%c", root->name);
    PreOrder(root->lson);
    PreOrder(root->rson);
}
void InOrder(node *root)
{
    if (!root)
        return;
    InOrder(root->lson);
    printf("%c", root->name);
    InOrder(root->rson);
}
void PostOrder(node *root)
{
    if (!root)
        return;
    PostOrder(root->lson);
    PostOrder(root->rson);
    printf("%c", root->name);
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        node *root = build();

        PreOrder(root);
        printf("\n");
        PostOrder(root);
        printf("\n");
        InOrder(root);
        printf("\n");
        if (t != 0)
            printf("\n");
    }
    
    return 0;
}

F: 棋盘问题：DFS 计数

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
#include<bits/stdc++.h>

using namespace std;

const int maxn = 25;

char mp[maxn][maxn];
int vis[maxn];
int n, k, ans;

void init()
{
    memset(vis, false, sizeof(vis));
    memset(mp, false, sizeof(mp));
    ans = 0;
}

void dfs(int x, int y)
{
    if(y >= k)
    {
        ans++;
        return ;
    }
    for(int i = x; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(!vis[j] && mp[i][j] == '#')
            {
                vis[j] = true;
                dfs(i + 1 , y + 1);
                vis[j] = false;
            }
        }
    }
}

int main()
{
    while(scanf("%d%d", &n, &k) != EOF)
    {
        init();
        if(n == -1 && k == -1)
            break;
        for(int i = 0; i < n; i++)
            scanf("%s", mp[i]);
        dfs(0, 0);
        printf("%d\n", ans);
    }

    return 0;
}

第二次上机作业代码

A: 仙岛求药：最最 naive 的 BFS 搜索

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 25;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int n, m;
char mp[maxn][maxn];
int step[maxn][maxn];

void init()
{
    memset(step, -1, sizeof(step));
}

bool judge(int x, int y)
{
    if (x < 0 || y < 0)
        return false;
    if (x >= n || y >= m)
        return false;
    if (mp[x][y] == '#')
        return false;
    return true;
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF)
    {
        if (m == 0 && n == 0)
            break;

        init();
        for (int i = 0; i < n; i++)
            scanf("%s", mp[i]);

        int sx, sy;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (mp[i][j] == '@')
                {
                    sx = i;
                    sy = j;
                    break;
                }

        std::queue<std::pair<int, int>> Q;
        Q.push(make_pair(sx, sy));
        step[sx][sy] = 0;
        bool state = false;
        int ans;

        while (!Q.empty())
        {
            int xx = Q.front().first;
            int yy = Q.front().second;
            if (mp[xx][yy] == '*')
            {
                state = true;
                ans = step[xx][yy];
                break;
            }
            for (int i = 0; i < 4; i++)
            {
                int tmpx = xx + dx[i];
                int tmpy = yy + dy[i];
                if (judge(tmpx, tmpy) && step[tmpx][tmpy] == -1)
                {
                    Q.push(make_pair(tmpx, tmpy));
                    step[tmpx][tmpy] = step[xx][yy] + 1;
                }
            }
            Q.pop();
        }

        if (!state)
            printf("-1\n");
        else
            printf("%d\n", ans);
    }

    return 0;
}

B: Butterfly：染色判断二分图

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

int n, m, color[maxn];
std::vector<std::pair<int, int>> g[maxn];

void init()
{
    memset(color, 0, sizeof(color));
    for (int i = 0; i < n; i++)
        g[i].clear();
}

void addedge(int u, int v, int w)
{
    g[u].push_back(make_pair(v, w));
    g[v].push_back(make_pair(u, w));
}

bool dfs(int u, int c)
{
    color[u] = c;

    int sz = g[u].size();
    for (int i = 0; i < sz; i++)
    {
        int v = g[u][i].first;
        int w = g[u][i].second;

        if (w == 0) // same color
        {
            if (color[v] == -c)
                return false;
            if (color[v] == 0 && !dfs(v, c))
                return false;
        }
        if (w == 1) // diff color
        {
            if (color[v] == c)
                return false;
            if (color[v] == 0 && !dfs(v, -c))
                return false;
        }
    }

    return true;
}

int main()
{
    while (scanf("%d%d", &n, &m) != EOF)
    {
        init();
        while (m--)
        {
            int a, b, color;
            scanf("%d%d%d", &a, &b, &color);
            addedge(a, b, color);
        }
        if (dfs(0, 1))
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}

C: 区间合并：For 一遍判断是否有不相交

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 <bits/stdc++.h>
using namespace std;

const int maxn = 50005;
const int inf = 0x3f3f3f3f;

std::pair<int, int> x[maxn];

bool inter(std::pair<int, int> x, std::pair<int, int> y)
{
    if (x.first < y.first && x.second < y.first)
        return false;
    if (y.first < x.first && y.second < x.first)
        return false;
    return true;
}

std::pair<int, int> Union(std::pair<int, int> x, std::pair<int, int> y)
{
    return make_pair(min(x.first, y.first), max(x.second, y.second));
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &x[i].first, &x[i].second);

    sort(x, x + n);
    bool state = true;
    for (int i = 1; i < n; i++)
    {
        if (inter(x[0], x[i]))
            x[0] = Union(x[0], x[i]);
        else
        {
            state = false;
            break;
        }
    }

    if (state)
        printf("%d %d\n", x[0].first, x[0].second);
    else
        printf("no\n");

    return 0;
}

D: Radar Installation：贪心

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

int n, d;
std::pair<int, int> p[maxn];
std::pair<double, double> r[maxn];

double dis(int x)
{
    return (double)sqrt((double)(d * d - x * x));
}

int main()
{
    int cas(0);
    while (scanf("%d%d", &n, &d) != EOF)
    {
        if (n == 0) break;

        bool state = true;
        for (int i = 0; i < n; i++)
        {
            scanf("%d%d", &p[i].first, &p[i].second);
            if (p[i].second > d)
                state = false;
        }
        
        if (state)
        {
            for (int i = 0; i < n; i++)
            {
                r[i].first = p[i].first - dis(p[i].second);
                r[i].second = p[i].first + dis(p[i].second);
            }

            sort(r, r + n);
            int res(0), p(0);
            while (p < n)
            {
                double rx = r[p].second;
                p++;
                while (p < n && (double)(r[p].first) <= rx)
                {
                    rx = min(rx, r[p].second);
                    p++;
                }
                res++;
            }

            printf("Case %d: %d\n", ++cas, res);
        }
        else  printf("Case %d: -1\n", ++cas);
    }

    return 0;
}

E: The Unique MST：判断 mst 唯一性/求次小并与之比较即可

Kruskal 求出 mst 并存起来，枚举 mst 中的边，将其删掉并在剩余图中求 mst，这些 mst 中最小者即为次小生成树。

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
const int inf = 0x3f3f3f3f;

int fa[maxn];
std::vector<int> mst;

struct Edge
{
    int u, v, w;
    Edge() {}
    Edge(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {}
};

std::vector<Edge> e;

void addedge(int u, int v, int w)
{
    e.push_back(Edge(u, v, w));
}

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

int Find(int x)
{
    while(fa[x] != x)
        x = fa[x];
    return x;
}

void init()
{
    e.clear();
    mst.clear();
}

int Kruskal(int n)
{
    for(int i = 1; i <= n; i++)
        fa[i] = i;
    sort(e.begin(), e.end(), cmp);
    int cnt(0), ans(0);

    for (int i = 0; i < e.size(); i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        int t1 = Find(u);
        int t2 = Find(v);

        if (t1 != t2)
        {
            ans += w;
            fa[t1] = t2;
            cnt++;
            mst.push_back(i);
        }
        if (cnt == n - 1)
            break;
    }

    if (cnt < n - 1)
        return -1;
    else
        return ans;
}

int fuckyou(int n, int skip)
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    int cnt(0), ans(0);

    for (int i = 0; i < e.size(); i++)
    {
        if (i == skip)
            continue;

        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        int t1 = Find(u);
        int t2 = Find(v);

        if (t1 != t2)
        {
            ans += w;
            fa[t1] = t2;
            cnt++;
        }
        if (cnt == n - 1)
            break;
    }

    if (cnt < n - 1)
        return -1;
    else
        return ans;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        init();

        int n, m;
        scanf("%d%d", &n, &m);

        while (m--)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            addedge(a, b, c);
        }

        int x = Kruskal(n), y = inf;
        for (int i = 0; i < mst.size(); i++)
        {
            int tmp = fuckyou(n, mst[i]);
            if (tmp != -1 && tmp < y) y = tmp;
        }

        if (x == y)
            printf("Not Unique!\n");
        else
            printf("%d\n", x);
    }

    return 0;
}

F: Sorting It All Out：拓扑排序并判断排序是否唯一

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 30;

int n, m;
int vis[maxn], indeg[maxn], in[maxn];
std::vector<int> g[maxn];
std::vector<int> ans;

void addedge(int u, int v)
{
    g[u].push_back(v);
}

void init()
{
    for(int i = 0; i < maxn; i++)
        g[i].clear();
    memset(indeg, 0, sizeof(indeg));
    ans.clear();
}

int toposort()
{
    ans.clear();
    int ret_state(1);
    for(int i = 0; i < n; i++)
        in[i] = indeg[i];

    std::queue<int> Q;
    for(int i = 0; i < n; i++)
        if(in[i] == 0) Q.push(i);
    
    while(!Q.empty())
    {
        if(Q.size() > 1) ret_state = 0;

        int u = Q.front();
        for(int i = 0; i < g[u].size(); i++)
        {
            int v = g[u][i];
            if(--in[v] == 0) Q.push(v);
        }

        ans.push_back(u);
        Q.pop();
    }

    if(ans.size() < n) return -1;

    return ret_state;
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(n == 0 && m == 0) break;

        init();
        int state(0);
        for(int step = 1; step <= m; step++)
        {   

            char s[5];
            scanf("%s", s);
            if(state != 0) continue;
            
            int u = s[0] - 'A';
            int v = s[2] - 'A';
            // u < v ====> Edge u -> v
            addedge(u, v);
            indeg[v]++;

            state = toposort();

            if(state == 1)
            {
                printf("Sorted sequence determined after %d relations: ", step);
                for(int i = 0; i < ans.size(); i++)
                    printf("%c", 'A' + ans[i]);
                printf(".\n");
            }
            if(state == -1)
                printf("Inconsistency found after %d relations.\n", step);
        }
        if(state == 0)
            printf("Sorted sequence cannot be determined.\n");
    }

    return 0;
}

第三次上机作业代码

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
#include <bits/stdc++.h>
using namespace std;

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

const int maxn = 20000 + 5;

int sum[maxn << 2];
std::vector< std::pair<int, int> > v;

void pushup(int rt)
{
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void update(int p, int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt]++;
        return;
    }
    int m = (l + r) >> 1;
    if (p <= m) update(p, lson);
    else update(p, rson);
    pushup(rt);
}

int query(int ll, int rr, int l, int r, int rt)
{
    if (ll <= l && rr >= r) return sum[rt];

    int ret = 0;
    int m = (l + r) >> 1;

    if(ll <= m) ret += query(ll, rr, lson);
    if(rr > m) ret += query(ll, rr, rson);
    return ret;
}

int main()
{
    int n;
    while (scanf("%d", &n), n)
    {
        memset(sum, 0, sizeof(sum));
        v.clear();

        for (int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            v.push_back(make_pair(x, i));
        }
        stable_sort(v.begin(), v.end());
        int res = 0;
        for (int i = 0; i < v.size(); i++)
        {
            update(v[i].second, 1, maxn, 1);
            res += query(v[i].second + 1, maxn, 1, maxn, 1);
        }
        printf("%d\n", res);
    }

    return 0;
}

B: Raid：暴力求解最近点对

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

struct Point
{
    double x, y;
} p[maxn], q[maxn];

double d(Point a, Point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        for(int i = 0; i < n; i++)
            scanf("%lf%lf", &q[i].x, &q[i].y);
        
        double res = 1e15;
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                res = min(res, d(p[i], q[j]));
        printf("%.3f\n", res);
    }

    return 0;
}

C: 公共子序列：LCS 动态规划

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 205;

char s1[maxn], s2[maxn];
int dp[maxn][maxn], n1, n2;

void init()
{
    for(int i = 0; i < maxn; i++)
        dp[i][0] = 0;
    for(int i = 0; i < maxn; i++)
        dp[0][i] = 0;
    for(int i = 1; i <= n1; i++)
        for(int j = 1; j <= n2; j++)
        {
            if(s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
}


int main()
{
    while(scanf("%s %s", s1, s2) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        n1 = strlen(s1), n2 = strlen(s2);
        init();
        printf("%d\n", dp[n1][n2]);
    }

    return 0;
}

D: 股票买卖：动态规划

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;
int t, n, a[maxn];
int dp1[maxn], dp2[maxn];

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        memset(dp1, 0, sizeof(dp1));
        memset(dp2, 0, sizeof(dp2));

        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);

        int head = a[0],  tail = a[n - 1];
        for(int i = 0; i < n; i++)
        {
            dp1[i] = max(dp1[i - 1], a[i] - head);
            head = min(head, a[i]);
        }
        for(int j = n - 1; j >= 0; j--)
        {
            dp2[j] = max(dp2[j + 1], tail - a[j]);
            tail = max(tail, a[j]);
        }

        int res(0);
        for(int i = 0; i < n; i++)
            res = max(res, dp1[i] + dp2[i + 1]);

        printf("%d\n", res);
    }
    
    return 0;
}

E: 最大子矩阵：动态规划

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 <bits/stdc++.h>
using namespace std;

const int maxn = 105;
int a[maxn][maxn], sum[maxn], dp[maxn];

int solve(int m, int n)
{
    int res = a[0][0];
    for (int i = 0; i < n; i++)
    {
        for (int r = 0; r < m; r++)
            sum[r] = a[r][i];
        dp[0] = sum[0];
        for (int r = 1; r < m; r++)
            dp[r] = max(dp[r - 1] + sum[r], sum[r]);
        for (int r = 0; r < m; r++)
            res = max(res, dp[r]);

        for (int j = i + 1; j < n; j++)
        {
            for (int r = 0; r < m; r++)
                sum[r] += a[r][j];
            dp[0] = sum[0];
            for (int r = 1; r < m; r++)
                dp[r] = max(dp[r - 1] + sum[r], sum[r]);
            for (int r = 0; r < m; r++)
                res = max(res, dp[r]);
        }
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)        
            scanf("%d", &a[i][j]);
    printf("%d\n", solve(n, n));

    return 0;
}

F: Multiplication Puzzle：类似背包

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
const int inf = 0x3f3f3f3f;

int a[maxn], dp[maxn][maxn];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    memset(dp, 0, sizeof(dp));

    for(int i = 2; i < n; i++)
        for(int j = 0; j < n - i; j++)
            for(int k = j + 1; k < j + i; k++)
            {
                if(dp[j][j + i] == 0)
                    dp[j][j + i] = dp[j][k] + dp[k][j + i] + a[j] * a[k] * a[j + i];
                else
                    dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k][j + i] + a[j] * a[k] * a[j + i]);
            }

    printf("%d\n", dp[0][n-1]);
        
    return 0;
}

第四次上机作业代码

A: Currency Exchange：BellmanFord 判断负环

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;

struct Edge
{
    int a, b;
    double r, c;
    Edge(){}
    Edge(int _a, int _b, double _r, double _c): a(_a), b(_b), r(_r), c(_c) {}
};

int n, m, beg;
double s, d[maxn];
std::vector<Edge> e;

bool bellman_ford()
{
    memset(d, 0, sizeof(d));
    d[beg] = s;

    for (int i = 1; i < n; i++)
    {
        bool state = false;
        for (int j = 0; j < e.size(); j++)
        {
            if (d[e[j].b] < (d[e[j].a] - e[j].c) * e[j].r)
            {
                d[e[j].b] = (d[e[j].a] - e[j].c) * e[j].r;
                state = true;
            }
        }
        if (!state) break;
    }

    for (int k = 0; k < e.size(); k++)
    {
        if (d[e[k].b] < (d[e[k].a] - e[k].c) * e[k].r)
            return true;
    }

    return false;
}

int main()
{
    while (scanf("%d%d%d%lf", &n, &m, &beg, &s) != EOF)
    {
        e.clear();
        while(m--)
        {
            int a, b;
            double R_ab, R_ba, C_ab, C_ba;
            scanf("%d%d%lf%lf%lf%lf", &a, &b, &R_ab, &C_ab, &R_ba, &C_ba);
            e.push_back(Edge(a, b, R_ab, C_ab));
            e.push_back(Edge(b, a, R_ba, C_ba));
        }

        if (bellman_ford()) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

B: Shopping Offers：动态规划

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
const int inf = 1e9;

int idx[6], cnt[6], price[6];
int b, s;
int dp[6][6][6][6][6];
int special_combine[maxn][6];
int special_price[maxn];

int main()
{
    scanf("%d", &b);
    for (int i = 0; i < b; i++)
        scanf("%d %d %d", &idx[i], &cnt[i], &price[i]);
    scanf("%d", &s);
    for (int i = 0; i < s; i++)
    {
        int tmp;
        scanf("%d", &tmp);
        for (int j = 0; j < tmp; j++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            for (int k = 0; k < 6; k++)
            {
                if (idx[k] == a)
                {
                    special_combine[i][k] = b;
                    break;
                }
            }
        }
        scanf("%d", &special_price[i]);
    }

    memset(dp, -1, sizeof(dp));

    dp[0][0][0][0][0] = 0;
    for (int i = 0; i <= cnt[0]; i++)
    {
        for (int j = 0; j <= cnt[1]; j++)
        {
            for (int k = 0; k <= cnt[2]; k++)
            {
                for (int x = 0; x <= cnt[3]; x++)
                {
                    for (int y = 0; y <= cnt[4]; y++)
                    {
                        int FinalPrice = inf;
                        int TempPrice = inf;
                        for (int si = 0; si < s; si++)
                        {
                            if (i >= special_combine[si][0] && j >= special_combine[si][1] && k >= special_combine[si][2] && x >= special_combine[si][3] && y >= special_combine[si][4])
                            {
                                TempPrice = dp[i - special_combine[si][0]][j - special_combine[si][1]][k - special_combine[si][2]][x - special_combine[si][3]][y - special_combine[si][4]] + special_price[si];
                                FinalPrice = min(FinalPrice, TempPrice);
                            }
                        }
                        if (FinalPrice != inf)
                        {
                            dp[i][j][k][x][y] = FinalPrice;
                        }
                        else
                        {
                            dp[i][j][k][x][y] = i * price[0] + j * price[1] + k * price[2] + x * price[3] + y * price[4];
                        }
                    }
                }
            }
        }
    }

    printf("%d\n", dp[cnt[0]][cnt[1]][cnt[2]][cnt[3]][cnt[4]]);

    return 0;
}

C: The Perfect Stall：二分图最大匹配

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300;

char map[maxn][maxn];
int col[maxn][maxn], row[maxn][maxn];
int linker[maxn], head[maxn];
bool vis[maxn];
int cnt, n, m;
int R, C;

struct Edge
{
    int to;
    int next;
};

Edge edge[maxn * maxn];

void Init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    memset(col, 0, sizeof(col));
    memset(row, 0, sizeof(row));
}

void add(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

bool dfs(int u)
{
    for(int i=head[u]; ~i; i=edge[i].next)
    {
        int v = edge[i].to;
        if(!vis[v])
        {
            vis[v] = 1;
            if(linker[v] == -1 || dfs(linker[v]))
            {
                linker[v] = u;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int ans = 0;
    memset(linker, -1, sizeof(linker));
    for(int i=1; i<=R; i++)
    {
        memset(vis, 0, sizeof(vis));
        if(dfs(i)) ans++;
    }
    return ans;
}

int main()
{
    while(cin >> R >> C)
    {   
        Init();
        for (int i = 1; i <= R; i++)
        {
            int s;
            cin >> s;
            for (int j = 0; j < s; j++)
            {
                int a;
                cin >> a;
                add(i, a);
            }
        }
        cout << hungary() << endl;
    }

    return 0;
}

D: Drainage Ditches：最小割

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 205;

const int inf = 0x3f3f3f3f;
int n, m;
int fl[maxn][maxn], dis[maxn];

bool bfs()
{
    for(int i = 1; i <= maxn; i++)
        dis[i] = -1;
    dis[1] = 0;
    queue<int> Q;
    Q.push(1);
    while(!Q.empty())
    {
        int k = Q.front(); Q.pop();
        for(int i = 1; i <= m; i++)
        {
            if(fl[k][i]>0 &&dis[i]<0)
            {
                dis[i] = dis[k] + 1;
                Q.push(i);
            }
        }
    }
    if(dis[m] > 0) return true;
    else return false;
}

int dfs(int q, int mx)
{
    if(q == m) return mx;
    int i, a;
    for(i = 1; i <= m; i++)
    {
        if(fl[q][i]>0 && dis[i] == dis[q] + 1 && (a = dfs(i, min(fl[q][i], mx))) )
        {
            fl[i][q] += a;
            fl[q][i] -= a;
            return a;
        }
    }
    return 0;
}

int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(fl, 0, sizeof(fl));
      
        for(int i = 1; i <= n; i++)
        {
            int u, v, d;
            scanf("%d%d%d", &u, &v, &d);
            fl[u][v] += d;
        }
        int ans = 0, tmp;
        while(bfs())
        {
            while(tmp = dfs(1, inf))
                ans += tmp;
        }

        printf("%d\n", ans);
    }

    return 0;
}

E: Dual Core CPU：最小割

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
#include <bits/stdc++.h>
using namespace std; 

const int maxn = 20005; 
const int maxm = 2000005; 
const int INF = 0x3f3f3f3f; 

int head[maxn], cur[maxn], d[maxn], st[maxm], s, e, no, n; 

struct point
{
    int u, v, flow, nxt; 
    point(){}; 
    point(int x, int y, int z, int w):u(x), v(y), nxt(z), flow(w){}; 
} p[maxm]; 

void add(int x, int y, int z)
{
    p[no] = point(x, y, head[x], z);  
    head[x] = no++; 
    p[no] = point(y, x, head[y], 0);  
    head[y] = no++; 
}

void init()
{
    memset(head, -1, sizeof(head)); 
    no = 0; 
}

bool bfs()
{
    int i, x, y;
    queue < int>q;
    memset(d, -1, sizeof(d)); 
    d[s] = 0;  
    q.push(s); 
    while(!q.empty())
    {
        x = q.front();     
        q.pop(); 
        for(i = head[x]; i != -1; i = p[i].nxt)
        {
            if(p[i].flow && d[y = p[i].v] < 0)
            {
                d[y] = d[x] + 1; 
                if(y == e)    
                    return true; 
                q.push(y); 
            }
        }
    }
    return false; 
}
int dinic()
{
    int i, loc, top, x = s, nowflow, maxflow = 0; 
    while(bfs())
    {
        for(i = s; i <= e; i++)   
            cur[i] = head[i]; 
        top = 0; 
        while(true)
        {
            if(x == e)
            {
                nowflow = INF; 
                for(i = 0; i < top; i++)
                {
                    if(nowflow > p[st[i]].flow)
                    {
                        nowflow = p[st[i]].flow; 
                        loc = i; 
                    }
                }
                for(i = 0; i < top; i++)
                {
                    p[st[i]].flow -= nowflow; 
                    p[st[i]^1].flow += nowflow; 
                }
                maxflow += nowflow; 
                top = loc;     
                x = p[st[top]].u; 
            }
            for(i = cur[x]; i != -1; i = p[i].nxt)
                if(p[i].flow&&d[p[i].v] == d[x] + 1) 
                    break; 
            cur[x] = i; 
            if(i != -1)
            {
                st[top++] = i; 
                x = p[i].v; 
            }
            else 
            {
                if(!top)    
                    break; 
                d[x] = -1; 
                x = p[st[--top]].u; 
            }
        }
    }
    return maxflow; 
}

int main()
{
    int N, M;
    while(scanf("%d%d", &N, &M) != EOF)
    {
        init(); 
        s = 0; 
        e = N + 1; 
        for(int i = 1; i <= N; i++)
        {
            int ai, bi; 
            scanf("%d%d", &ai, &bi); 
            add(s, i, ai); 
            add(i, e, bi); 
        }
        while(M--)
        {
            int a, b, c; 
            scanf("%d%d%d", &a, &b, &c); 
            add(a, b, c); 
            add(b, a, c); 
        }
        printf("%d\n", dinic()); 
    }

    return 0; 
}

F: PIGS：最大流

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 105;
const int maxp = 1e3 + 5;
const int maxm = 1e5 + 5;
const int inf = 0x3f3f3f3f;

int m, n, T, cnt = 1;
int h[maxn], q[maxn], last[maxn], cur[maxn];
int pig[maxp];
vector<int> a[maxn];
int L[maxp];

struct Edge
{
    int nxt, v, to;
} e[maxm];

void addedge(int u, int v, int w)
{
    e[++cnt].to = v;
    e[cnt].nxt = last[u];
    last[u] = cnt;
    e[cnt].v = w;
    e[++cnt].to = u;
    e[cnt].nxt = last[v];
    last[v] = cnt;
    e[cnt].v = 0;
}

bool bfs()
{
    int head = 0, tail = 1;
    memset(h, -1, sizeof(h));
    q[0] = 0;
    h[0] = 0;
    while (head != tail)
    {
        int now = q[head];
        head++;
        for (int i = last[now]; i; i = e[i].nxt)
            if (e[i].v && h[e[i].to] == -1)
            {
                h[e[i].to] = h[now] + 1;
                q[tail++] = e[i].to;
            }
    }
    return h[T] != -1;
}

int dfs(int x, int f)
{
    if (x == T)
        return f;
    int w, used = 0;
    for (int i = cur[x]; i; i = e[i].nxt)
        if (h[e[i].to] == h[x] + 1)
        {
            w = dfs(e[i].to, min(f - used, e[i].v));
            e[i].v -= w;
            e[i ^ 1].v += w;
            if (e[i].v)
                cur[x] = i;
            used += w;
            if (used == f)
                return f;
        }
    if (!used)
        h[x] = -1;
    return used;
}

int dinic()
{
    int tmp = 0;
    while (bfs())
    {
        for (int i = 0; i <= T; i++)
            cur[i] = last[i];
        tmp += dfs(0, inf);
    }
    return tmp;
}

int main()
{
    cin >> m >> n;
    T = n + 1;
    for (int i = 1; i <= m; i++)
        cin >> pig[i];
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        while (x--)
        {
            int y;
            cin >> y;
            a[i].push_back(y);
        }
        int z;
        cin >> z;
        addedge(i, T, z);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < a[i].size(); j++)
        {
            int v = a[i][j];
            if (!L[v])
            {
                L[v] = i;
                addedge(0, i, pig[v]);
            }
            else
            {
                addedge(L[v], i, inf);
                L[v] = i;
            }
        }
    printf("%d\n", dinic());

    return 0;
}