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