Codeforces Round #746 ABCD 题解 (Java/C++)

A. Gamer Hemose

题解

显然我们只需要选择攻击力最大的两个武器交替攻击即可。

代码

Java

Submission #131063022 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #131063199 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Hemose Shopping

题解

考量三个数a[i],a[j],a[k]。假设i<j<k,且$j-i\geq x$。我们可以做以下操作来实现这三个数的任意互换:

因此,如果[x, n-1]和[0, n-1-x]这两个区间有交集,那么毫无疑问,一定可以将整个数组重新排序。
如果x>n-1,也就是没有可排序的区间,那么整个数组都无法重新排序。
而在上面两种极端情况的中间,[x, n-1]和[0, n-1-x]显然是可以各自重新排序的。但考虑到a[0]可以随时和a[n-1]交换,所以除了[n-1-x, x]之间无法排序之外,其他区间都可以任意排序。

综合上面三种情况,我们得到结论,有且只有[n-1-x, x]这个区间无法排序。(这个区间可能是个无效区间,如第一种情况。也可能是整个区间,如第二种情况。)
我们只需要看排序后发生值发生变化的下标是否落在无法排序的区间内即可。

代码

Java

Submission #131071030 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #131071198 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Bakry and Partitioning

一个XOR性质的应用:a xor a = 0,0 xor a = a。

Codeforces Round #746 Bakry and Partitioning 题解 (Java/C++)
题解首先,如果每个部分的XOR都相同(设为X),那么所有节点的XOR要么是X要么是0。我们先考虑所有节点的XOR是0的情况。这种情况显然是YES,因为我们只需要选择任意一个叶子节点,然后让这个叶子节点独立成一个部分即可。
点击上面连接查看详细题解

D. Hemose in ICPC ?

这个题目的思路很容易想到,就是一个明显的二分。但是在找出一半的边时有一个巧妙的做法。

Codeforces Round #746 Hemose in ICPC ? 题解 (Java/C++)
题解首先,因为gcd(a,b,c)一定小于等于gcd(a,b)或者gcd(b,c)的。因此,这个最大距离必然就是最大的那一条边。
点击上面连接查看详细题解

最近工作又比较忙,E题实在没有时间精力做了。

展示评论