Chybeta

ACM-OJ[长期更新]

发表于 | 分类于 | 阅读次数

最近更新日期：2017-08-11
干脆把自己平日做的题放在一篇文章里吧。不然太分散了。
POJ: 1163 1182 1258 1273 1979 2236 2388 3069 3176 3253 3617
XOJ: 1004 1005 1022 1061 1062 1075 1078 1316

POJ

1163

题目

http://poj.org/problem?id=1163

思路

见下面POJ-3176题分析

提交

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
#include <iostream>
#include <memory>
#include <cstdio>
#include <cstdlib>
#define MAX 355
int way[MAX][MAX] = {0};
int triangle[MAX][MAX] = {0};
int n;
using namespace std;
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d",&triangle[i][j]);
    way[0][0] = triangle[0][0];
    for (int i = 1; i < n; i++)
        for (int j = 0; j <= i; j++)
        {
            if ( j == 0 )
            {
                way[i][j] = way[i-1][j] + triangle[i][j];
            }
            else if ( j == i )
            {
                way[i][j] = way[i-1][j-1] + triangle[i][j];
            }
            else
            {
                way[i][j] = max(way[i-1][j],way[i-1][j-1]) + triangle[i][j];
            }
        }
    int lastrow = n - 1;
    int res = way[lastrow][0];
    for (int j = 1; j < n; j++){
        if (way[lastrow][j] > res )
            res = way[lastrow][j];
    }
    printf("%d\n", res);
    return 0;
}

1182

题目

http://poj.org/problem?id=1182

思路

并查集使用。输入的x，有三种种类A,B,C，分别用x，x+n,x+2n来代表。
输入后，先判断x，y是否符合范围要求。
第一种关系中：x和y是同一种种类。即union_set(x,y),union_set(x+n,y+n),union_set(x+2n,y+2n)。在执行union_set()之前，要看是否存在矛盾关系，即判断same_set(x,y+n) || same_set(x,y+2n) || same_set(x+n,y) || same_set(x+n,y+2n) || same_set(x+2n,y) || same_set(x+2n,y+n)。
第二种关系中；x吃y。即union_set(x,y+n),union_set(x+n,y+2n),union_set(x+3n,y).。在执行union_set()之前，要看是否存在矛盾关系，即判断same_set(x,y)|| same_set(x,y+2n) || same_set(x+n,y+n) ||same_set(x+n,y) || same_set(x+2n,y+n) || same_set(x+2n,y+2n)。

另外数组如果开小的话，会导致runtime error。。。

提交

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 <iostream>
#include <cstdlib>
#include <cstdio>
#define MAX_N 500000
using namespace std;
int ans;
int par[MAX_N];
int ran[MAX_N];
void init_set(int n){
    for (int i=1; i <= n ; i++){
        par[i] = i;
        ran[i] = 0;
    }
}
int find_set(int x){
    int i = x;
    while(par[i] != i) {
        i = par[i];
    }
    while(par[x] != i){
        int next;
        next = par[x];
        par[x] = i;
        x = next;
    }
    return i;
}
int same_set(int x,int y){
    return find_set(x) == find_set(y);
}
void union_set(int x,int y){
    int root_x = find_set(x);
    int root_y = find_set(y);
    if (root_x == root_y)
        return;
    if (par[root_x] > par[root_y]){
        par[root_y] = root_x;
    }else{
        par[root_x] = root_y;
        if (ran[root_x] == ran[root_y])
            ran[root_y]++;
    }
}
int main()
{
    int n,k;
    ans = 0;
    scanf("%d%d",&n,&k);
    init_set(n*3);
    for (int i = 0; i < k; i++){
        int d,x,y;
        scanf("%d%d%d",&d,&x,&y);
        if (x < 1 || x > n || y < 1 || y > n){
            ans++;
            continue;
        }
        if ( d == 1){
            if ( same_set(x,y+n) || same_set(x,y+2*n) || same_set(x+n,y) || same_set(x+n,y+2*n) || same_set(x+2*n,y) || same_set(x+2*n,y+n) ){
                ans++;
            }else{
                union_set(x,y);
                union_set(x+n,y+n);
                union_set(x+2*n,y+2*n);
            }
        }else{
            if (same_set(x,y)|| same_set(x,y+2*n) || same_set(x+n,y+n) ||same_set(x+n,y) || same_set(x+2*n,y+n) || same_set(x+2*n,y+2*n)){
                ans++;
            }else{
                union_set(x,y+n);
                union_set(x+n,y+2*n);
                union_set(x+2*n,y);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

1258

题目

http://poj.org/problem?id=1258

思路

最小生成树。

提交

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define MAX 105
#define INF 0xFFFFFF
using namespace std;
int n;
int cost[MAX][MAX] ;
int mincost[MAX];
bool used[MAX];
int prim() {
    for ( int i = 0; i < n; i++){
        mincost[i] = INF;
        used[i] = false;
    }
    mincost[0] = 0;
    int res = 0;
    while ( true ){
        int v = -1;
        for ( int u = 0; u < n; u++){
            if ( !used[u] && ( v == -1 || mincost[u] < mincost[v]))
                v = u;
        }
        if ( v == -1 )
            break;
        used[v] = true;
        res += mincost[v];
        for (int u = 0; u < n; u++)
            mincost[u] = min(mincost[u], cost[v][u]);
    }
    return res;
}
int main()
{
    while(scanf("%d",&n) != EOF ){
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cost[i][j] = INF;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n ; j++)
                scanf("%d", &cost[i][j]);
        printf("%d\n",prim());
    }
    return 0;
}

1273

题目

http://poj.org/problem?id=1273

思路

模板题目，直接求最大流就可以。
我用了vector来构造邻接表，而这题的输入时一次包含了很多个测试例子。所以每次读完后都需要对邻接表进行初始化，即进行下面的操作：

1
2
for (int i = 1; i <= m; i++ )
	G[i].clear();

方法是网上找的，网上说这样清空了元素，但不会回收内存。

提交

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <memory.h>
#define MAX 205
#define INF 0x7fffffff
using namespace std;
struct edge {int to ,cap, rev;};
vector<edge> G[MAX];
bool used[MAX];
int n,m;
void add_edge(int from, int to,int cap){
    edge one,two;
    one.to = to;
    one.cap = cap;
    one.rev = (int)(G[to].size());
    G[from].push_back(one);
    two.to = from;
    two.cap = 0;
    two.rev = (int)(G[from].size()-1);
    G[to].push_back(two);
}
int dfs(int v, int t, int f){
    if ( v == t)
        return f;
    used[v] = true;
    for ( int i = 0; i < (int)G[v].size(); i++){
        edge &e = G[v][i];
        if ( !used[e.to] && e.cap > 0){
            int d = dfs(e.to,t, f > e.cap?e.cap:f);
            if ( d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s, int t){
    int flow = 0;
    for (;;){
        memset(used, 0, sizeof(used));
        int f = dfs(s,t,INF);
        if (f == 0) return flow;
        flow += f;
    }
}
int main()
{
    while (scanf("%d%d",&n,&m) != EOF){
        for (int i = 1; i <= m; i++ )
            G[i].clear();
        for (int i = 0; i < n; i++){
            int s, t,c;
            scanf("%d%d%d",&s,&t,&c);
            add_edge(s,t,c);
        }
        printf("%d\n",max_flow(1,m));
    }
    return 0;
}

1979

题目

http://poj.org/problem?id=1979

思路

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define X 20
#define Y 20
using namespace std;
int x,y;
int nx,ny;
int sx,sy;
int num;
char maze[X][Y];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
void dfs(int r, int s){
    num += 1;
    maze[r][s] = '#';
    for (int i = 0; i < 4; i++){
        int t1 = r+dx[i];
        int t2 = s+dy[i];
        if (0 <= t1 && t1 < x && 0 <= t2 && t2 < y && maze[t1][t2] == '.'){
            dfs(t1,t2);
        }
    }
}
int main()
{
    scanf("%d%d",&y,&x);
    while( x != 0 && y != 0){
        num  = 0;
        for (int i = 0; i < x; i++){
            for (int j = 0; j < y; j++){
                scanf("\n%c",&maze[i][j]);
                if (maze[i][j] == '@'){
                    sx = i;
                    sy = j;
                }
            }
        }
        dfs(sx,sy);
        printf("%d\n",num);
        scanf("%d%d",&y,&x);
    }
    return 0;
}

2236

题目

http://poj.org/problem?id=2236

思路

并查集。用结构体数组来作为节点，repair表示是否已经修理过，par表示其父节点。其余利用并查集即可。

提交

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
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define MAX_N 1002
using namespace std;
struct node{
    int repair;
    int par;
}computer[MAX_N];
int ran[MAX_N];
struct loc{
    int x;
    int y;
}zuobiao[MAX_N];
int n,d;
int p,q;
char op;
void init_set(int n){
    for(int i=1; i <= n; i++){
        computer[i].repair = 0;
        computer[i].par = i;
        ran[i] = 0;
    }
}
int find_root(int q){
    int i = q;
    while(computer[i].par != i){
        i = computer[i].par;
    }
    while(computer[q].par != i){
        int temp = computer[q].par;
        computer[q].par = i;
        q = temp;
    }
    return i;
}
int same_set(int p,int q){
    return find_root(p) == find_root(q);
}
void union_set(int p, int q){
    int p_root = find_root(p);
    int q_root = find_root(q);
    if (p_root == q_root)
        return;
    if(ran[p_root] > ran[q_root]){
        computer[q_root].par = p_root;
    }else{
        computer[p_root].par = q_root;
        if (ran[p_root] == ran[q_root]){
            ran[q_root]++;
        }
    }
}
int cal_distance(int p,int q){
    return (zuobiao[p].x-zuobiao[q].x)*(zuobiao[p].x-zuobiao[q].x)+(zuobiao[p].y-zuobiao[q].y)*(zuobiao[p].y-zuobiao[q].y);
}
int maxdistance;
int main()
{
    scanf("%d%d",&n,&d);
    maxdistance = d * d;
    for (int i = 1;i <= n; i++){
        scanf("%d%d",&zuobiao[i].x,&zuobiao[i].y);
    }
    init_set(n);
    while(scanf("\n%c",&op) != EOF){
        if (op == 'O'){
            scanf("%d",&p);
            computer[p].repair = 1;
            for (int j = 1; j <= n; j++){
                if (computer[j].repair == 1)
                    if (cal_distance(p,j) <= maxdistance){
                        union_set(p,j);
                    }
            }
        }else{
            scanf("%d%d",&p,&q);
            if (same_set(p,q)){
                printf("SUCCESS\n");
            }else{
                printf("FAIL\n");
            }
        }
    }
    return 0;
}

2387

题目

http://poj.org/problem?id=2387

思路

最短路径 +　队列优先　。
这题竟然是先读入边数再读入顶点数，Ｏrz
另外会有 重边， 不过如果用邻接表实现的话，可以不用管，如果邻接矩阵来实现的话，最后矩阵中存储的是从点到点的多条边的最小值。

提交

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
#include <iostream>
#include <stdio.h>
#include <memory.h>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX_V 200000
#define INF 0xFFFFFF
using namespace std;
struct edge { int to, cost, flag ;};
typedef pair<int, int> P;
int V;
int E;
vector<edge> G[MAX_V];
int d[MAX_V];
void dijkstra(int s);
int main()
{
    scanf("%d%d", &E,&V);
    for (int i = 0; i < E; i++){
        int s, t, cost;
        edge temp1,temp2;
        scanf("%d%d%d", &s, &t, &cost);
        temp1.to = t;
        temp1.cost = cost;
        G[s].push_back(temp1);
        temp2.to = s;
        temp2.cost = cost;
        G[t].push_back(temp2);
    }
    dijkstra(1);
    printf("%d",d[V]);
    return 0;
}
void dijkstra(int s){
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d+1,d + V+1, INF);
    d[s] = 0;
    que.push(P(0,s));
    while ( !que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second;
        if ( d[v] < p.first)
            continue;
        for (int i = 0; i < G[v].size(); i++){
            edge e = G[v][i];
            if ( d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

2388

题目

http://poj.org/problem?id=2388

思路

先排序，之后打印出中间值。水题。

提交

stl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define MAX 100005
using namespace std;
int n;
int arr[MAX];
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%d",&arr[i]);
    }
    sort(arr,arr+n);
    printf("%d",arr[n/2]);
    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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define MAX 100005
using namespace std;
int n;
int arr[MAX];
void quick_sort(int l,int h)
{
    if(h<l+2)return ;
    int e=h,p=l;
    while(l<h)
    {
        while(++l<e && arr[l]<=arr[p]);
        while(--h>p && arr[h]>=arr[p]);
        if(l<h) swap(arr[l],arr[h]);
    }
    swap(arr[h],arr[p]);
    quick_sort(p,h);
    quick_sort(l,e);
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%d",&arr[i]);
    }
    quick_sort(0,n);
    printf("%d",arr[n/2]);
    return 0;
}

3069

题目

http://poj.org/problem?id=3069

思路

贪心算法。在 while( i < n ) 循环中，第一个while循环，找到距离当前点（未覆盖）大于r的第一个点，该点的前一个（i—）做上标记。第二个while循环，从已经标记的点出发，找到距离当前点（已经覆盖）大于r的第一个点，并将其作为下一次大循环的起点。

提交

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define N 1005
using namespace std;
int n;
int r;
int loc[N];
int marknum;
int main()
{
    scanf("%d%d",&r,&n);
    while ( n != -1 && r != -1){
        for (int i = 0; i < n; i++)
            scanf("%d",&loc[i]);
        sort(loc,loc+n);
        marknum = 0;
        int i = 0;
        int j = 0;
        while ( i < n ){
            while ( i < n && loc[j] + r >= loc[i] )
                i++;
            i--;
            marknum++;
            j = i;
            while ( i < n && loc[j] + r >= loc[i])
                i++;
            j = i;
        }
        printf("%d\n",marknum);
        scanf("%d%d",&r,&n);
    }
    return 0;
}

3176

题目

http://poj.org/problem?id=3176

思路

二维数组triangle用于保存三角形，二维数组way用于保存路径。
以题目数据为例：

1
2
3
4
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

分为三种情况：

  • 最左边，只能从上一行的同列来，way[i][j] = way[i-1][j] + triangle[i][j]
  • 最右边，只能从上一行的斜对角线来，way[i-1][j-1] + triangle[i][j];
  • 中间，可以从上一行的左边或者右边来，way[i][j] = max(way[i-1][j],way[i-1][j-1]) + triangle[i][j];

填表完成后，对最后一行way[n-1][]找出最大值即为答案。

提交

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
#include <iostream>
#include <memory>
#include <cstdio>
#include <cstdlib>
#define MAX 355
int way[MAX][MAX] = {0};
int triangle[MAX][MAX] = {0};
int n;
using namespace std;
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= i; j++)
            scanf("%d",&triangle[i][j]);
    way[0][0] = triangle[0][0];
    for (int i = 1; i < n; i++)
        for (int j = 0; j <= i; j++)
        {
            if ( j == 0 )
            {
                way[i][j] = way[i-1][j] + triangle[i][j];
            }
            else if ( j == i )
            {
                way[i][j] = way[i-1][j-1] + triangle[i][j];
            }
            else
            {
                way[i][j] = max(way[i-1][j],way[i-1][j-1]) + triangle[i][j];
            }
        }
    int lastrow = n - 1;
    int res = way[lastrow][0];
    for (int j = 1; j < n; j++){
        if (way[lastrow][j] > res )
            res = way[lastrow][j];
    }
    printf("%d\n", res);
    return 0;
}

3253

题目

http://poj.org/problem?id=3253

思路

霍夫曼树的变形。
重点在于对两个最小值相加后对数组的处理。

提交

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
int n;
int k;
int len[20005];
int total;
void solve(){
    long long ans = 0;
    while ( n > 1 ){
        int mii1 = 0;
        int mii2 = 1;
        if (len[mii1] > len[mii2])
            swap(mii1,mii2);
        for (int i = 2; i < n; i++){
            if (len[i] < len[mii1]){
                mii2 = mii1;
                mii1 = i;
            }
            else if (len[i] < len[mii2]){
                mii2 = i;
            }
        }
        int t = len[mii1] + len[mii2];
        ans += t;
        if (mii1 == n-1)
            swap(mii1,mii2);
        len[mii1] = t;
        len[mii2] = len[n-1];
        n--;
    }
    printf("%lld\n",ans);
}
int main()
{
    total = 0;
    k = 0;
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf("%d",&len[i]);
    }
    solve();
    return 0;
}

3617

题目

http://poj.org/problem?id=3617

思路

贪心算法，每次选择排序靠前的字母加到字符串t中。如果两个排序相同，则看它们的下一个字母的顺序，可以使用一个递归函数来判断。

提交

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 <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n;
char s[2005];
char t[2005];
int sp,ep;
int compare(int i,int j){
    if (s[i] > s[j]){
        return 1;
    }
    else if (s[i] < s[j]){
        return 0;
    }
    else if (s[i] == s[j]){
        i++;
        j--;
        return compare(i,j);
    }
}
int main()
{
    scanf("%d",&n);
    for (int i = 0; i < n; i++){
        scanf(" %c",&s[i]);
    }
    sp = 0;
    ep = n-1;
    int lenoft = 0;
    while (lenoft != n){
        int p = compare(sp,ep);
        if (p == 0){
            t[lenoft] = s[sp];
            sp++;
            lenoft++;
        }
        else if (p == 1){
            t[lenoft] = s[ep];
            ep--;
            lenoft++;
        }
    }
    for (int i = 1; i <= n; i++){
        printf("%c",t[i-1]);
        if (i % 80 == 0)
            printf("\n");
    }
    printf("\n");
    return 0;
}

XOJ

1004

想法

冒泡等可能会超时。堆排序和快排的复杂度都是 O(nlogn)。课上为了节约时间所以：）

提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int arrays[1000004];
int main()
{
    int n;
    scanf("%d",&n);
    int i,j;
    for(i = 0;i < n;i++)
        scanf("%d",&arrays[i]);
    sort(arrays,arrays+n);
    for(j = 0;j < n - 1;j++)
        printf("%d ",arrays[j]);
    printf("%d",arrays[n - 1]);
    return 0;
}

oj对格式要求好严格…

1005

此题另写一篇文章了。

1022

想法

直接用普通的矩阵乘法就过了，
时间复杂度 O()

提交

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 <iostream>
#include <stdio.h>
int main(){
    int n1,m1;
    int n2,m2;
    int matrix1[100][100];
    int matrix2[100][100];
    scanf("%d%d",&n1,&m1);
    int i,j;
    for(i = 0;i < n1;i++)
        for(j = 0;j < m1;j++)
            scanf("%d",&matrix1[i][j]);
    scanf("%d%d",&n2,&m2);
    for(i = 0;i < n2;i++)
        for(j = 0;j < m2;j++)
            scanf("%d",&matrix2[i][j]);
    int matrix3[100][100];
    for(i = 0;i < n1;i++)
        for(j = 0;j < m2;j++)
            matrix3[i][j]=0;
    int i1,j2;
    for(i1 = 0;i1 < n1;i1++)
        for(j2 = 0;j2 < m2;j2++)
            for(j = 0;j < n2;j++)
              matrix3[i1][j2] += matrix1[i1][j] * matrix2[j][j2];
    for(i = 0;i < n1;i++)
    {
        for(j = 0;j < m2 - 1;j++)
            printf("%d ",matrix3[i][j]);
        printf("%d\n",matrix3[i][m2-1]);
    }
    return 0;
}

1061

想法

贪心算法。其实就是任务选择问题。

  • 按照约会完成时间从早到晚排序
  • 选择具有最早完成时间的girl
  • 将此girl加入到约会列表中
  • 对子问题重复上述问题
  • 强烈谴责Ckp

提交

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 <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef struct info{
    char  name[16];
    char  starttime[6];
    char  endtime[6];
}info;
void quick_sort(info * s, int l, int r,int n);
int main()
{
    int n;
    static info mm[1005] ;
    static info mmcopy[1005];
    scanf("%d",&n);
    int i,j;
    for (i = 1; i <= n; i++){
        scanf("%s%s%s",mm[i].name,mm[i].starttime,mm[i].endtime);
    }
    quick_sort(mm,1,n,n);
    strcpy(mmcopy[1].endtime,mm[1].endtime);
    strcpy(mmcopy[1].name,mm[1].name);
    strcpy(mmcopy[1].starttime,mm[1].starttime);
    int cal = 1;
    for (i = 2; i <= n; i++){
        if (strcmp(mmcopy[cal].endtime,mm[i].starttime) <= 0){
            cal++;
            strcpy(mmcopy[cal].endtime,mm[i].endtime);
            strcpy(mmcopy[cal].name,mm[i].name);
            strcpy(mmcopy[cal].starttime,mm[i].starttime);
        }
    }
    printf("%d\n",cal);
    for ( i = 1; i < cal; i++){
        printf("%s ",mmcopy[i].name);
    }
    printf("%s",mmcopy[i].name);
    return 0;
}
void quick_sort(info* s, int l, int r,int n)
{
    if (l < r){
        int i = l, j = r;
        int temp;
        info x;
        strcpy(x.endtime,s[l].endtime);
        strcpy(x.name,s[l].name);
        strcpy(x.starttime,s[l].starttime);
        while (i < j)
        {
            while(i < j && strcmp(s[j].endtime,x.endtime) >= 0)
                j--;
            if(i < j){
                strcpy(s[i].endtime,s[j].endtime);
                strcpy(s[i].starttime,s[j].starttime);
                strcpy(s[i].name , s[j].name);
                i++;
            }
            while(i < j && strcmp(s[i].endtime,x.endtime) < 0)
                i++;
            if(i < j){
                strcpy(s[j].endtime,s[i].endtime);
                strcpy(s[j].starttime,s[i].starttime);
                strcpy(s[j].name,s[i].name);
                j--;
            }
        }
        strcpy(s[i].endtime,x.endtime);
        strcpy(s[i].starttime,x.starttime);
        strcpy(s[i].name,x.name);
        quick_sort(s, l, i - 1,n);
        quick_sort(s, i + 1, r,n);
    }
}

1062

想法

贪心算法。背包问题。尽量选择面值大的。
将元转换为角，这样都是整数，进行处理更方便。

提交

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
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
typedef struct zhibi{
    int number;
    int value;
}zhibi;
int main()
{
    int stat = 0;
    int n;
    scanf("%d",&n);
    zhibi arr[7];
    int i;
    for (i = 1; i < 7; i++){
        scanf("%d",&arr[i].number);
    }
    arr[1].value = 500;
    arr[2].value = 100;
    arr[3].value = 50;
    arr[4].value = 10;
    arr[5].value = 5;
    arr[6].value = 1;
    int remainMoney;
    remainMoney = 1000 - n * 25;
    for (i = 1; i < 7; i++){
        if (remainMoney == 0){
            break;
        }
        else
        {
            int j = remainMoney / arr[i].value;
            int number = j>arr[i].number?arr[i].number:j;
            remainMoney = remainMoney - number*arr[i].value;
            stat = stat + number;
        }
    }
    if (remainMoney == 0){
        printf("%d",stat);
    }
    else
    {
        printf("-1\n");
    }
    return 0;
}

1075

思路

直接dijkstra。 采用邻接矩阵存储。

提交

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
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdbool.h>
#define MAXN 100
#define INF 0xfffff
int cost[MAXN+2][MAXN+2]; //  保存 图 （各权值）
int n; // 顶点数
int d[MAXN]; // 从初始点出发 的最短距离
bool used[MAXN]; // 已经使用过的图
void dijkstra(int s);
int min(int a,int b);
int main()
{
    int i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &cost[i][j]);
    dijkstra(1);
}
void dijkstra(int s){
    int i,j;
    for (i = 1; i <= n; i++)
        d[i] = INF;
    memset(used, false, sizeof(bool) * (n+1));
    d[s] = 0;
    while (true){
        int v = -1;
        int u;
        for (u = 1; u <= n; u++)
            if ( !used[u] && ( v == -1 || d[u] < d[v]))
                v = u;
        if (v == -1)
            break;
        used[v] = true;
        for (u = 1; u <= n; u++)
            d[u] = min( d[u], d[v] + cost[v][u]);
    }
    printf("%d",d[n]);
}
int min(int a,int b){
    return a>b?b:a;
}

1078

思路

任意两点间的最短路径问题的变体吧。一旦找出了从某个源点（人）到其他所有人需要的层数时，记录下来，如果有的人与其他所有人都不认识，则该层数是 无穷大（INF）。之后通过循环，找出从每个源点出发所需要的层数，并取最大值。要注意的是 算法求得最短路径 是 经过了几条路径（路径权为 1 ，路径权和即有几条路径），而题目的 层数M 是指 两个人之间还有多少人，即经过了多少个 点， 所以在最后的结果中记得减一。

提交

dijkstra算法

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
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <stdbool.h>
#define MAXN 100
#define INF 0xfffff
int cost[MAXN+2][MAXN+2]; //  保存 图 （各权值）
int n; // 顶点数
int d[MAXN]; // 从初始点出发 的最短距离
bool used[MAXN]; // 已经使用过的图
void dijkstra(int s);
int min(int a,int b);
int main()
{
    int i, j;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            scanf("%d", &cost[i][j]);
    dijkstra(1);
}
void dijkstra(int s){
    int i,j;
    for (i = 1; i <= n; i++)
        d[i] = INF;
    memset(used, false, sizeof(bool) * (n+1));
    d[s] = 0;
    while (true){
        int v = -1;
        int u;
        for (u = 1; u <= n; u++)
            if ( !used[u] && ( v == -1 || d[u] < d[v]))
                v = u;
        if (v == -1)
            break;
        used[v] = true;
        for (u = 1; u <= n; u++)
            d[u] = min( d[u], d[v] + cost[v][u]);
    }
    printf("%d",d[n]);
}
int min(int a,int b){
    return a>b?b:a;
}

Floyd-Warshall 算法

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
#include <stdio.h>
#include <stdlib.h>
#define MAX 102
#define INF 0xfffff
int G[MAX][MAX];
int n;
void warshall_floyd();
int min(int a, int b);
int max(int a, int b);
int main()
{
    int i, j;
    int M = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++){
            scanf("%d", &G[i][j]);
            if ( G[i][j] == 0)
                G[i][j] = INF;
            if  ( i == j )
                G[i][j] = 0;
        }
    warshall_floyd();
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            M = max(M, G[i][j]);
    if ( M  == INF)
        printf("%d",-1);
    else
        printf("%d\n", M-1);
    return 0;
}
void warshall_floyd(){
    int k, i, j;
    for (k = 1; k <= n; k++)
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
}
int min(int a, int b){
    return a > b ? b : a;
}
int max(int a, int b){
    return a > b ? a : b;
}

1316

想法

贪心算法。背包问题。有别于0/1背包问题。
每次选取尽量多的单位价值高的物体。

提交

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
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef struct unit{
    double unitValue;
    int id;
    double weight;
    double value;
}unit;
void quick_sort(unit s[], int l, int r);
int main()
{
    double m,n;
    static unit valuesor[100010];
    scanf("%lf%lf",&m,&n);
    int i;
    for (i = 1; i <= n; i++){
        scanf("%lf%lf",&valuesor[i].weight,&valuesor[i].value);
        valuesor[i].unitValue = (double)valuesor[i].value / (double)valuesor[i].weight;
        valuesor[i].id = i;
    }
    quick_sort(valuesor,1,n);
    double remainSpace = m;
    double allValue = 0;
    i = 1;
    for (i = 1; i <= n ; i++){
        if (remainSpace <= 0)
            break;
        if (valuesor[i].weight <= remainSpace){
            remainSpace = remainSpace - valuesor[i].weight;
            allValue += valuesor[i].value;
        }else{
            allValue += remainSpace *valuesor[i].unitValue;
            remainSpace = 0;
        }
    }
    printf("%lf\n",allValue);
    return 0;
}
void quick_sort(unit s[], int l, int r)
{
    if (l < r)
    {
        int i = l, j = r;
        unit x = s[l];
        while (i < j)
        {
            while(i < j && s[j].unitValue <= x.unitValue)
                j--;
            if(i < j){
                s[i].unitValue = s[j].unitValue;
                s[i].id = s[j].id;
                s[i].value = s[j].value;
                s[i].weight = s[j].weight;
                i++;
            }
            while(i < j && s[i].unitValue >= x.unitValue)
                i++;
            if(i < j){
                s[j].unitValue = s[i].unitValue;
                s[j].id = s[i].id;
                s[j].value = s[i].value;
                s[j].weight = s[i].weight;
                j--;
            }
        }
        s[i].id = x.id;
        s[i].unitValue = x.unitValue;
        s[i].value = x.value;
        s[i].weight = x.weight;
        quick_sort(s, l, i - 1);
        quick_sort(s, i + 1, r);
    }
}
微信扫码加入知识星球【漏洞百出】
chybeta WeChat Pay

点击图片放大，扫码知识星球【漏洞百出】

本文标题:ACM-OJ[长期更新]

文章作者:chybeta

发布时间:2017年06月19日 - 16:06

最后更新:2017年08月28日 - 18:08

原始链接:http://chybeta.github.io/2017/06/19/ACM-OJ-长期更新/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。