Codeforces Round #745 (Div. 2) ABCDE 题解 (Java/C++)

A. CQXYM Count Permutations

题解

不难想到,一个排列的满足条件的i有x个,那么如果我们把这个排列倒过来排列则其满足条件的i有2n-x个。比如[3,2,1,4]=1,那么[4,1,2,3]=4-1=3。

因此符合条件的i的数目其实是均匀分布的。因此答案为$\frac {2n!} 2$

代码

Java

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

C++

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

B. Diameter of Graph

题解

显然,如果m少于n-1,则无法连通所有点,必为NO。同理如果m多于$\frac {n \cdot (n-1)} 2$,则必然会出现重负的边,也是NO。

显然,如果$k-1\leq 0$,也就是允许的最大直径$\leq -1$,也必然是NO。如果$k-1=1$,也就是直径必须为0时,当且仅当n=1时是YES,否则NO。但是如果$k-1\geq 3$,也就是直径$\geq 2$时,一定有解,我们可以给出下图的构造:

最后,我们只剩下$k-1=2$没有考虑,也就是直径为0或者1。
对于直径为0,刚刚已经考虑过来,此时n=1。
如果直径为1,那么任意两点间必有一条边,因此当且仅当$m=\frac {n \cdot (n-1)} 2$时YES,否则为NO。

代码

Java

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

C++

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

C. Portal

这道题目的关键在于发现最终的答案必然小于等于16。基于这个点暴力搜索即可。

Codeforces Round #745 (Div. 2) Portal 题解 (Java/C++)
题解不难发现当a=5,b=4时,即使是最坏的情况也只需要16步操作。于是我们直接枚举左上角的点,接着从小到大枚举这个portal的大小。不难发现,如果下图中的红色和橙色部分超过了16就不用继续枚举portal的大小了。
点击上面连接查看详细题解

D. Mathematics Curriculum

这个题目的关键在于:想到区间最大值为界,其左边和右边的区间完全互不影响。根据这个结论进行分治,进一步进行DP就是很自然的选择了。

Codeforces Round #745 (Div. 2) Mathematics Curriculum 题解 (Java/C++)
题解首先我们先不考虑good number的数目要恰好等于k这个条件,我们先考虑good number本身的性质。不难发现,无论如何n一定在最大值中。这样一来,很自然的,如果m=1,那么这个x是且只能是n。更进一步,m=1时,当且仅当k=1有解,且解为n!。否则一定没有解。
点击上面连接查看详细题解

E. Train Maintenance

这个题目的关键在于,对于x[i]+x[y]的值很大和很小的情况可以分开处理。以及要相信Codeforce在一秒钟内能处理1亿次计算。

Codeforces Round #745 (Div. 2) Train Maintenance 题解 (Java/C++)
题解首先,我们几乎可以立刻注意到如果x[i]>m,那么这个一定没有任何影响,我们可以直接忽略他。于是x[i]的取值范围就从原先的0~$10^9$降低为了0~$2\cdot 10^5$。
点击上面连接查看详细题解
展示评论