文章目录
排座位题意题解代码
7-12 分而治之题意题解代码
排座位
作者 陈越 单位 浙江大学 代码长度限制 16KB 时间限制 200 ms 内存限制 64 MB
题意
输入n,k,m，n表示一共有n个人要进行排座位，m条关系条数（A B
S
i
S_i
Si）表示A和B之间的关系为
S
i
S_i
Si，然后进行k次查询，问两人是否能连着坐在一起
关系为1表示是朋友，-1表示是死对头
对每个查询输出一行结果：
如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but…；如果他们之间只有敌对关系，则输出No way。
题解
通过二维数组存储两人之间的关系，由于两人之间的关系是唯一的，所以可以看做是 双向边
纯枚举做法不管怎么改都过不去,而最好的情况也会有全联通的测试点无法通过，因此判断是后能满足条件
因此，上网查询了一下并查集做法
未得分点：最大N，全连通环，全查询
acwing并查集 模板题
find(x) 是找会祖宗节点， p[x] 数组存放的是父节点
代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std
;
const int MAXN
= 111;
int p
[MAXN
];
int find(int x
) {
if (p
[x
] == x
) return p
[x
];
return p
[x
] = find(p
[x
]);
}
void merge(int x
, int y
){
int t1
= find(x
);
int t2
= find(y
);
if (t1
!= t2
){
p
[t1
] = t2
;
}
}
int gx
[MAXN
][MAXN
];
int main(){
int n
, m
, k
; scanf("%d%d%d", &n
, &m
, &k
);
for(int i
= 1; i
<= n
; i
++) p
[i
] = i
;
for(int fi
= 1; fi
<= m
; ++fi
) {
int a
, b
, c
; scanf("%d%d%d", &a
, &b
, &c
);
gx
[a
][b
] = c
; gx
[b
][a
] = c
;
if (c
== 1) merge(a
, b
);
}
for(int qu
= 1; qu
<= k
; ++qu
){
int qa
, qb
; scanf("%d%d", &qa
, &qb
);
if (gx
[qa
][qb
] == 1) puts("No problem");
else if (gx
[qa
][qb
] == -1){ if (find(qa
) == find(qb
))puts("OK but..."); else puts("No way");}
else {if (find(qa
) == find(qb
)) puts("No problem"); else puts("OK");}
}
}
7-12 分而治之
题意
我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。
题解
建图，数据大小和多边的存在，因此更适合vector的动态二维数组去建立邻接表，像最短路那样建
处理，通过vis去进行标记，vis[x] = 1说明这个城市已经被攻下了
访问，通过两层for循环去进行遍历，外层城市总数，内层该城市所连接的v[i].size()座城市
当
v
i
s
[
i
]
=
=
0
且
v
i
s
[
v
[
i
]
[
j
]
]
=
=
0
vis[i] == 0 且 vis[v[i][j]] == 0
vis[i]==0且vis[v[i][j]]==0的时候就说明存在城市不是孤立无援的，因此直接标记为策略失败
代码
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std
;
const int maxn
= 1e5 + 1111;
const int N
= 111;
int vis
[maxn
];
vector
<int> v
[maxn
];
void init1(){
memset(vis
, 0, sizeof vis
);
}
int main(){
int n
, m
; cin
>> n
>> m
;
for(int si
= 1; si
<= m
; si
++){
int a
, b
; cin
>> a
>> b
;
v
[a
].push_back(b
);
v
[b
].push_back(a
);
}
int k
; cin
>> k
;
for(int sk
= 1; sk
<= k
; ++sk
){
bool flag
= true;
init1();
int np
; cin
>> np
;
for(int sp
= 1; sp
<= np
; ++sp
){
int x
; cin
>> x
; vis
[x
] = 1;
}
for(int i
= 0; i
< n
; i
++){
for(int j
= 0; j
< v
[i
].size(); j
++){
if (vis
[i
] == 0 && vis
[v
[i
][j
]] == 0){
flag
= false;
}
}
}
(flag
) ? puts("YES") : puts("NO");
}
}
