Codeforces Round 1027 (Div. 3)-G

题目链接

题目翻译：

思路：贪心，就是尽可能把数组里的每个数展开（也就是让操作次数尽可能达到k次这个要求），比如12，可以这样展开：

容易观察到奇数是无法展开的，然后展开有条件，比如我的12展开成4个3，会不会跟数组右边那个数字是一样的呢？所以这样的分支有可能是不合法的，那我右分支就只能保留6这个数字，然后左边正常展开，左边为什么正常展开？这就需要考虑枚举哪一个数字是一开始填的了，如果我这个12在一开始填的数字的左边，那我当然不需要考虑左分支是不是合法的，因为一定合法，我可以展开12这个数字之后再去填数组里面在12左边的数字，右分支有可能不合法是因为我12右边已经填了数字了，如果12在一开始填的数字右边，就是一样的道理。

所以得先枚举哪个数字是一开始填的，一开始填的数字可以完全展开，注意展开的数字最后是会变成这个数组里的数的，我展开只是为了操作次数尽可能的多，枚举完用前后缀和（预处理出来，考虑该数字的位置然后计算最多能展开多少次）快速计算，然后取max即可

代码：

package cx3;
import java.util.*;
import java.io.*;
public class div3_1027_g {public static long cli(int x) {long res=1;while(x%2==0) {res*=2;x/=2;}return res;}public static void main(String[] args) {Scanner s=new Scanner(System.in);int t=s.nextInt();while(t-->0) {int n=s.nextInt(),k=s.nextInt();int a[]=new int [n+10];for(int i=1;i<=n;i++) a[i]=s.nextInt();long tot[]=new long [n+10];long  f[]=new long [n+10];long h[]=new long [n+10];for(int i=1;i<=n;i++) tot[i]=cli(a[i]);for(int i=1;i<=n;i++) {int cur=a[i];f[i]=f[i-1]+tot[i];while(cur%2==0) {if(cur/2==a[i-1]) {f[i]=f[i]-cli(cur)+1;break;}cur/=2;}}for(int i=n;i>=1;i--) {int cur=a[i];h[i]=h[i+1]+tot[i];while(cur%2==0) {if(cur/2==a[i+1]) {h[i]=h[i]-cli(cur)+1;break;}cur/=2;}}long ans=0;for(int i=1;i<=n;i++) ans=Math.max(ans,tot[i]+h[1]-h[i]+f[n]-f[i]);if(ans>=k) System.out.println("YES");else System.out.println("NO");}}}