POJ 2585 (拓扑排序)

某位置可能出现窗口的编号是一定的，所以本题只关心窗口的覆盖关系。这个覆盖关系是一个有向图，两窗口覆盖为一条有向边，而且没有环（判断依据）。表示有向图用一个邻接矩阵。

邻接矩阵是表示一个图的常用存储表示。它用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。 阶为 n 的图 G 的邻接矩阵 A 是 n×n 的。将 G 的顶点标签为 v1 v2 ... vn。若 (vi,vj)∈E(G)， Aij=1，否则 Aij=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
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 <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int adjaencymatrix[15][15],screen[6][6];
string cover[6][6];

int visited[15];
int indegree[15];
int type;

void coverinit(){
	int k,i,j;
	for (i=0;i<5;i++) for (j=0;j<5;j++) cover[i][j].erase();
	for (k=1;k<=9;k++) {
		i=(k-1)/3;
		j=(k-1)%3;
		cover[i][j]+=(char)k; cover[i][j+1]+=(char)k; cover[i+1][j]+=(char)k; cover[i+1][j+1]+=(char)k;
	}
}

void buildDmap(){
	int i,j,k;
	for (i=0;i<4;i++) {
		for (j=0;j<4;j++){
			for (k=0;k<cover[i][j].length();k++) {
				if (( !adjaencymatrix[screen[i][j]][cover[i][j][k]] ) && ( screen[i][j]!=cover[i][j][k] ) ){
					adjaencymatrix[screen[i][j]][cover[i][j][k]]=1;
					indegree[cover[i][j][k]]++;
				}
			}
		}
	}
}

int score(){
	int i,j,k;
	for (i=0;i<type;i++) {
		k=1;
		while (!visited[k] || (k<=9 && indegree[k]>0)) k++;
		if (k>9) return 0;
		visited[k]=0;
		for (j=1;j<=9;j++) if (visited[j] && adjaencymatrix[k][j]) indegree[j]--;
	}
	return 1;
}

int main(){
	int count,i,j,temp;
	scanf("%d",&count);
	coverinit();
	while (count--) {
		memset(indegree,0,sizeof(indegree));
		memset(visited,0,sizeof(visited));
		memset(adjaencymatrix,0,sizeof(adjaencymatrix));
		type=0;
		for (i=0;i<4;i++) {
			for (j=0;j<4;j++) {
				scanf("%d",&temp);
				if (!visited[temp]) {
					type++; visited[temp]=1;
				}
				screen[i][j]=temp;
			}
		}
		buildDmap();
		if (score()) printf("Lucky dog!\n"); else printf("BOOM!\n");
	}
	return 0;
}

SCU 4460 (贪心)

话说这题是三个月以前做的。

两个数列排序过后，从最大圈开始贪心即可。 

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
#include <stdio.h>
#include <stdlib.h>

int nlist[100000];
int mlist[100000];

int comp(const void *a, const void *b)
{
        return *(int *)a - *(int *)b;
}

int main(void){
        int t, ti, si, li, m, n, count;
        scanf("%d",&t);
        for (ti=0; ti<t; ti++){
                scanf("%d%d", &n, &m);
                for (si=0; si<n; si++) scanf("%d", &nlist[si]);
                for (si=0; si<m; si++) scanf("%d", &mlist[si]);
                qsort(nlist, n, sizeof(int), comp);
                qsort(mlist, m, sizeof(int), comp);
                li=n-1;
                count=0;
                for (si=m-1; si>=0; si--){
                        while (li>=0) {
                                li--;
                                if (mlist[si]>=nlist[li+1]) {count++;break;}
                        }
                }
                printf("%d\n", count);

        }
}

本文参考了： 1.http://www.cnblogs.com/pony1993/archive/2012/08/16/2641904.html