竞赛总览

CSDN 编程竞赛二十三期：比赛详情 (csdn.net)

竞赛题解

题目1、排查网络故障

A地跟B地的网络中间有n个节点（不包括A地和B地），相邻的两个节点是通过网线连接的。正常的情况下，A地和B地是可以连通的，有一天，A地和B地突然不连通了，已知只有一段网线出问题（两个相邻的节点）小明需要排查哪段网线出问题。他的排查步骤是：1.选择某个中间节点。2.在这个节点上判断跟A地B地是否连通，用来判断那一边出问题。请问小明最少要排查多少次，才能保证一定可以找到故障网线。

题目描述有二分查找的意思，直接输出结果即可。

#include <cstdio>
#include <cmath>int main () {long long int n; scanf ("%lld", &n);printf ("%lld", (long long int) (log2 (n) + 1));return 0;
}

题目2、零钱兑换

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币张数。如果无解，请返回-1。

当背包问题做，套背包问题的DP模板解决。

不过，这道题的输入格式特别不友好，数据格式形如[1,2,3],4。需要逐个字符读入并手动处理输入数据。

bool input (int& t) {int result = 0;char str = getchar ();while (str >= '0' && str <= '9') {result = result * 10 + (str - '0');str = getchar ();}t = result;if (str == ']') {getchar ();return false;}return true;
}

在main函数中，先调用一次getchar函数，吃掉数据开头的左中括号字符。然后使用while循环调用input函数，即可读入前n-1个数据。待input函数返回false时，说明数组已经读完，但此时跳出循环了，还要单独再处理一下列表中最后一个数据。

竞赛中只能使用在线代码编辑器，无法使用本地IDE调试，再加上这个输入格式太可恶，导致此题花费的时间远超预期。这也算是本场竞赛的一个坑了吧，看来以后要多练习一下对异形输入数据的处理过程。

题目3、清理磁盘空间

小明电脑空间满了，决定清空间。为了简化问题，小明列了他个人文件夹（/data）中所有末级文件路径和大小，挑选出总大小为m的删除方案，求所有删除方案中，删除操作次数最小是多少。一次删除操作：删除文件或者删除文件夹。如果删除文件夹，那么该文件夹包含的文件都将被删除。文件夹的大小：文件夹中所有末级文件大小之和。

由于要分割文件路径，这个题涉及大量字符串处理操作。本人对C++的string类不太熟悉，但比赛时调试界面又非常不友好，无法本地调试，因此果断放弃这题。

试了一下，答案都很小，所以直接开启骗分模式。输出2可以通过4个测试点，这里博主选择先骗到其它6个点（基本上都是个位数），然后再输出2结束此题。

题目4、交际圈

小明参加了个大型聚会。聚会上有n个人参加，我们将他们编号为1..n，有些人已经互相认识了，有些人还不认识。聚会开始后，假设A跟B认识，A会给所有他认识的人介绍B，原先跟A认识，但不认识B的人，都会在此时，跟B互相认识。当所有人都把自己认识的人介绍一遍后，此时n个人就会形成k个交际圈，同一个交际圈中，两两互相认识。不同的交际圈之间，互相不认识。问题：当所有人都把自己认识的人介绍一遍后，形成了多少个交际圈？

这道题全篇都在描述一个关键词：认识。看这段描述就知道要用并查集算法，所以直接打并查集模板就可以通过此题了。