Codeforces Round #713 Div3 题解
F题的DP+贪心还是有点好玩的。G题暴力打表多少有点没意思了。E题写起来稍微有点麻烦。除此之外没啥特别的。
G. Short Task
题意
定义$d(n)=\sum\limits_{k|n}{k}$. 也就是n所有因数的和。现在给你一个$c$求，最小的$n$使$d(n)=c$。
题解
预处理打表。提前预处理出所有的因数和。然后再扫描一次所有数，求出每种可能的和的最小值。
代码
F. Education
初看很像背包和DP。但其实如果要背包或者DP的话，每次升级之后剩下的钱不好处理。所以就需要采取贪心策略，如果要升级，就尽快升级。于是问题就迎刃而解了。
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$。
代码
D. Corrupted Array
题意
给你一个长度为$n+2$的数组$b$。这个$b$满足：
- $b_i=a_i\ (1\leq{i}\leq{n})$.
- $b_{n+1}=\sum_{i=1}^{n}{a_i}$.
- $b_{n+2}=x$。这个x是任意你喜欢的值。
问是否存在一种$b$的排列，使得这个$b$可以满足某种$a$。输出这个$a$。
题解
显然，既然$b_{n+1}$是$a$的和，那么要么$b_{n+1}$就是$b$里的最大值，要么就是次大值（$x$是最大值）。两种情况都试试就好了。
代码
要小心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$里面哪个剩下的多就分配什么。
需要注意的是如果长度是奇数，中间那一个需要特别处理一下。
代码
B. Almost Rectangle
题意
给你一个$n\times{n}$的地图。图上有两个‘*’，现在要你补两个‘*’来构成一个四边形。
题解
直接求出2对x和y的坐标。对于重复x或者y的直接+1看看，如果超过边界回到0就行。
代码
A. Spy Detected!
题意
数组里面有一个数和其他数不一样。要你找出那个不一样的数的下标。
题解
找到只出现一次的那个数。输出下标。