3 Conuter Strike
时间限制：5000ms 空间限制：256MB
3.1 题目描述
SPY likes useful algorithms, while Markyyz always learns useless algorithms. Although they learn
dierent type of algorithms, they both like a computer game called Counter Strike (”CS” for short,
dierent from the game with the same name in reality). It is a two-player competition. One player acts
as a terrorist (”T ” for short), responsible for planting bombs. The other one acts as a counter terrorist
(”CT ” for short), responsible for defusing bombs.
At the start of each game, the system generates a bomb with a circuit in it. The circuit consists of n
hubs (numbered from 1 to n) and m wires. Each wire connects two dierent hubs, any two hubs could be
directly or indirectly connected by wires, and no two hubs are directly connected by more than one wire.
In other word, the circuit can be regarded as an undirected graph with n vertices and m edges, without
multiple-edges or self-loops.
The game is divided into three stages:
1. Bomb planting stage: T will receive k activating components numbered from 1 to k. T needs
to select k dierent hubs h
1
, h
2
, ..., h
k
, and set the i-th activating component on the h
i
-th hub. 2.
Bomb defusing stage: CT will receive a useful kit for free, and buy q useless kits numbered from 1 to q.
A useful kit can remove an arbitrary hub, while a useless kit can only remove a hub with an activating
component in order, which means the i-th useless kit can only remove the h
i
-th hub. Once a hub is
removed, all wires directly connected to it will be cut o. 3. Bomb activating stage: If any two activating
components are connected directly or indirectly by wires, the bomb will be activated and T will win.
Otherwise, the bomb will be defused and CT will win.
For example, the picture above shows a bomb with a circuit consisting of 19 hubs and 27 wires. T
obtained 6 activating components and set them on hub 16, 17, 2, 18, 12, 9. CT can buy 2 useless kits
5
剩余22页未读，继续阅读
小嗷犬
- 粉丝: 3w+
- 资源: 1347
我的内容管理
展开
最新资源
- 多模态联合稀疏表示在视频目标跟踪中的应用
- Kubernetes资源管控与Gardener开源软件实践解析
- MPI集群监控与负载平衡策略
- 自动化PHP安全漏洞检测：静态代码分析与数据流方法
- 青苔数据CEO程永：技术生态与阿里云开放创新
- 制造业转型： HyperX引领企业上云策略
- 赵维五分享：航空工业电子采购上云实战与运维策略
- 单片机控制的LED点阵显示屏设计及其实现
- 驻云科技李俊涛：AI驱动的云上服务新趋势与挑战
- 6LoWPAN物联网边界路由器：设计与实现
- 猩便利工程师仲小玉：Terraform云资源管理最佳实践与团队协作
- 类差分度改进的互信息特征选择提升文本分类性能
- VERITAS与阿里云合作的混合云转型与数据保护方案
- 云制造中的生产线仿真模型设计与虚拟化研究
- 汪洋在PostgresChina2018分享：高可用 PostgreSQL 工具与架构设计
- 2018 PostgresChina大会：阿里云时空引擎Ganos在PostgreSQL中的创新应用与多模型存储
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
