Python解题 - CSDN周赛第19期 - 醉酒的狱卒

本期题目依然难度不高，可惜状态不佳，未能取得满分，而且解题的思路也没能做到最简，直到赛后才想到还可以有另外的有趣的解法。我想这本身也是比赛的乐趣之一吧，不识庐山真面目，只缘身在此山中。

第一题：幼稚班作业

幼稚园终于又有新的作业了。老师安排同学用发给同学的4根木棒拼接成一个三角形。当然按照正常的逻辑，如果不能拼接成三角形。必然要折断某个木棍来拼接三角形。可是懒惰的小艺当然不会费力了！如果拼接不成三角形小艺就会把它凭借成类似边长 1 1 2的伪三角形。如果伪三角形都拼接不成那就不交作业！

输入：输入四根木棍的长度。

输出：拼接成正常三角形输出”1”，伪三角形输出”0”，否则输出”-1”。

	示例
输入	1 2 3 4
输出	1

分析

作为第一题，通常来讲应该是最简单的，但本题却有明显的误导。题目给了四根木棒，很自然地会让人想到要把四根木棒都用掉，也就是说把其中两根拼在一起，再和另外两根试着组三角形。但是从最后的结果来看，只要检查其中三根是否能够组成三角形就能得到答案了。于是，按照三角形的基本规律，两条短边之和必定大于第三条边，我们只要将四根木棒按照长度排序，检查前三根和后三根能否满足这个条件即可。

其实这里用到了一个小技巧，四根木棒选三根，按照排列组合，应该有4种选择：1/2/3、1/2/4、1/3/4、2/3/4，为什么我们只检查1/2/3和2/3/4两种组合呢？因为1/2/3/4按长度递增，如果1/2/3不能满足条件的话，1/2/4必然也不会满足（1+2如果不大于3的话，更不可能大于4），同理，如果2/3/4不能满足的话，1/3/4也不会满足（2+3如果不大于4的话，1+3更不可能大于4）。所以只要检查1/2/3和2/3/4的组合是否能够组成三角形即可。

参考代码

arr = list(map(int, input().strip().split()))
arr.sort()
if arr[0]+arr[1] > arr[2] or arr[1]+arr[2] > arr[3]:
    print(1)
elif arr[0]+arr[1] == arr[2] or arr[1]+arr[2] == arr[3]:
    print(0)
else:
    print(-1)

第二题：环形单向链表

给一个单向链表，若其中包含环，请完善EntryNodeOfLoop方法找出该链表的环的入口结点，否则，输出null。要求空间复杂度为O(1)。

	示例
输入	4 1 2 2 3 3 4 4 2
输出	2

分析

从以往关于数据结构的考题来看，官方此类考题从来都没有真正的考察过数据结构的构建，所以本题和是不是链表的关系并不大，希望以后能有所改善。另外，此题自相矛盾，题目暗示了有可能存在多个环，但是，单向链表的每个节点都只指向一个节点（要不怎么叫“单向”？），如何存在多个环？

如果链表中存在环，则要么最后一个节点指向了第一个节点，要么有一个节点被指向了两次（术语叫入度为2），根据给出的示例，可以看到每一行给出的两个数a和b，代表了a指向b，所以我们只要判断：① b里是否出现了第一个节点，② b里是否有某个节点出现了2次。但是这样只能通过90%的测试用例（想必这也是大多数人的得分都是97.5的原因）。由于题目描述有问题，只能猜测那10%的数据并不是单向链表，换句话说，a有可能指向了多个节点，甚至可能指向了自己，但是也没有机会进行测试了。反正题目都这样了，那就随便写写吧。

参考代码

n = int(input().strip())
arr = []
for _ in range(n):
    a, b = map(int, input().strip().split())
    arr.append((a,b))
a, b = list(zip(*arr))
if 1 in b:
    print(1)
else:
    r = max(b, key=b.count)
    if b.count(r) > 1:
        print(r)
    else:
        print("null")

第三题：影分身

已知字符串str。字符串str包含字符’x’,’y’。如果相邻的两个字符不同，消除两个字符,优先从左边进行消除。xyyx - > yx -> 

示例：

	示例一	示例二
输入	xyyyy	xxxyyyy
输出	yyy	y

分析

本题比较简单，按照题意模拟字符串的消除即可得到答案。需要注意的是，如果x和y消除了，左右的字符串要合在一起再进行比较，比如xxxyyyy，中间的xy消除后，还要继续比较左边第二个x和右边第二个y合并在一起的情况，也就是继续消除，直到最后不存在相邻的x和y为止。

参考代码1

s = input().strip()
i = 1
while i < len(s):
    if s[i-1] != s[i]:
        s = s[:i-1] + s[i+1:]
        i = max(i-2, 0)
    i += 1
print(s)

此外，也不难看出，因为相同个数的“x”和“y”相互抵消，最终的结果必然只有一种字符，那么其实我们只要统计出字符串中“x”和“y”分别出现了多少次，然后将出现次数多的那个字符打印出来即可，打印的个数就等于两者出现次数的差值。如果是0，也不用特判，打印空字符串即可。

参考代码2

s = input().strip()
from collections import Counter
r = Counter(s)
d = r["x"] - r["y"]
if d < 0:
    print("y"*(-d))
else:
    print("x"*d)

第四题：醉酒的狱卒

某监狱有一个由n个牢房组成的大厅，每个牢房紧挨着。每个牢房里都有一个囚犯，每个牢房都是锁着的。一天晚上，狱卒感到无聊，决定玩一个游戏。在第一轮，他喝了一杯威士忌，然后跑下大厅，打开每个牢房的锁。在第二轮比赛中，他喝了一杯威士忌，然后跑下大厅，锁上每隔一个的牢房的锁（牢房2、4、6…）。在第三轮比赛中，他喝了一杯威士忌，然后跑下大厅。他每隔三个牢房（第3、6、9号牢房）就去一次。如果牢房被锁上了，他就把它打开；如果牢房门打开了，他就锁上牢房。他重复 n 轮，喝最后一杯，然后昏倒。一些囚犯（可能为零号）意识到他们的牢房被解锁且狱卒丧失了行动能力。他们就可以立即逃跑。现在根据牢房数量，确定有多少囚犯越狱。

输入：

第一行输入包含一个正整数 t ，表示有 t 行数据，下面每一行都包含一个介于5和100之间（含5和100）的整数，即轮数 n 。

输出：

对于每一行，必须打印出监狱有 n 个牢房时越狱的囚犯人数。

示例：

	示例
输入	2 5 100
输出	2 10

分析

此题描述十分冗长，但其实十分简单，可以说也是一道脑筋急转弯。按照题意，狱卒会依次操作1到 n 的倍数的牢房（关上、打开的状态切换），所以如果一个牢房的数字存在偶数个因数，比如牢房6，存在4个因数：1/2/3/6，也就是说狱卒会在第1、2、3、6次喝醉的时候去操作牢房6，那么该牢房打开、关闭、打开、关闭，最终状态就是关闭。而如果一个整数存在奇数个因数，则此数必然是完全平方数，比如牢房16，存在5个因数：1/2/4/8/16，则其最终的状态必然是打开。于是此题就变成了求 n 之内的整数有多少个完全平方数，也就是  。

参考代码1

t = int(input().strip())
result = []
for _ in range(t):
    n = int(input().strip())
    result.append(int(n**0.5))
for i in result:
    print(i)

但是，其实问哥在比赛中并没有想到这一点，刷题的人很容易会将题目与刷过的题目联想在一起，此题让我瞬间想到了洛谷的另外一道题（现在看来，本题更加简单），于是没来得及细想，就直接套用了集合异或运算的解法。

算法复杂度自然比不上前面  的常数阶解法，但也算是拓宽了一种思路吧。

参考代码2

t = int(input().strip())
result = []
for _ in range(t):
    n = int(input().strip())
    cell = set(range(1, n+1))
    for i in range(2, n+1):
        cell ^= set(range(i, n+1, i))
    result.append(len(cell))
for i in result:
    print(i)