Codeforces Round #713 Div3 题解

F题的DP+贪心还是有点好玩的。G题暴力打表多少有点没意思了。E题写起来稍微有点麻烦。除此之外没啥特别的。


G. Short Task

题意

定义$d(n)=\sum\limits_{k|n}{k}$. 也就是n所有因数的和。现在给你一个$c$求,最小的$n$使$d(n)=c$。

题解

预处理打表。提前预处理出所有的因数和。然后再扫描一次所有数,求出每种可能的和的最小值。

代码

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

F. Education

初看很像背包和DP。但其实如果要背包或者DP的话,每次升级之后剩下的钱不好处理。所以就需要采取贪心策略,如果要升级,就尽快升级。于是问题就迎刃而解了。

Codeforces Round #712 Education DP+贪心
很容易想到这样定义状态:$dp[i][0]$表示级别$i$的工作后不再升级,专心打工挣钱需要凑够钱的天数。$dp[i][1]$表示级别$i$后,我凑够下一级学费需要的天数。很容易想到$dp[i][j]=dp[i-1][1]+something$。
我的具体题解

E. Permutation by Sum

题意

要你构造一个长度为$n$的1-$n$的序列$a$。使得对于给你的$l$,$r$和$s$,有$s=\sum_{i=l}^r{a_i}$。

题解

定义$len=r-l+1$表示区间长度。能构造出来的最小值是$\sum_{i=1}^{len}i$,最大值是$\sum_{i=n-len+1}^{n}i$。只要在这个范围内的都是可以构建的。

构建方式就是从最小的和开始,默认从$l$到$r$就是1-$len$。基于这个排列,依次调整每一个数。每个数都尝试将其改为最大的可能的值,如果改了依然小于$s$。那么就说明改了没毛病。如果改了之后大于等于$s$,那么说明这个就是最后一个需要改的值了,改完就是$s$。

代码

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

D. Corrupted Array

题意

给你一个长度为$n+2$的数组$b$。这个$b$满足:

  1. $b_i=a_i\ (1\leq{i}\leq{n})$.
  2. $b_{n+1}=\sum_{i=1}^{n}{a_i}$.
  3. $b_{n+2}=x$。这个x是任意你喜欢的值。

问是否存在一种$b$的排列,使得这个$b$可以满足某种$a$。输出这个$a$。

题解

显然,既然$b_{n+1}$是$a$的和,那么要么$b_{n+1}$就是$b$里的最大值,要么就是次大值($x$是最大值)。两种情况都试试就好了。

代码

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

要小心Java的Arrays.sort()。根据这篇文章,在排序的时候应该用Long而不是long。


C. A-B Palindrome

题意

给你一个字符串$s$,其中只包含三种字符:‘0’,‘1’和‘?’。你的任务是把‘?’改成‘0’或者‘1’。使得生成的字符串$t$里恰好包含$a$个0,$b$个1,且$t$为回文串。要你输出$t$。

题解

优先满足回文,先确定一部分的0和1。对于剩下的?一定是其对称位上也是?。那就$a$和$b$里面哪个剩下的多就分配什么。

需要注意的是如果长度是奇数,中间那一个需要特别处理一下。

代码

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

B. Almost Rectangle

题意

给你一个$n\times{n}$的地图。图上有两个‘*’,现在要你补两个‘*’来构成一个四边形。

题解

直接求出2对x和y的坐标。对于重复x或者y的直接+1看看,如果超过边界回到0就行。

代码

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

A. Spy Detected!

题意

数组里面有一个数和其他数不一样。要你找出那个不一样的数的下标。

题解

找到只出现一次的那个数。输出下标。

代码

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