A. Sorting with Twos

题意：

给一个长度为n的数组，可以做任意次以下操作：选择一个整数m，将1-2^m 的数减1。若能使数组变为一个单调递增的数组则输出YES，否则输出NO

分析：

只需要保证2^m+1 -2^m+1单调递增即可

代码：

#include <bits/stdc++.h>
using namespace std ;
const int max_N=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;

void solve(){
	int n;
    cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int flag=1;
    for(int i=4;i<=4&&i<=n;i++){
        if(a[i]<a[i-1]){
            flag=0;
            break;
        }
    }
    for(int i=6;i<=8&&i<=n;i++){
        if(a[i]<a[i-1]){
            flag=0;
            break;
        }
    }
    for(int i=10;i<=16&&i<=n;i++){
        if(a[i]<a[i-1]){
            flag=0;
            break;
        }
    }
    for(int i=18;i<=20&&i<=n;i++){
        if(a[i]<a[i-1]){
            flag=0;
            break;
        }
    }
    if(flag==1){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
    
}

int main(){
	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

B. Deja Vu

题意：

给一个长度为n的数组，做q次询问，若这个数能被2^xi整除，则这个数加上2^xi-1

分析：

一个数能被2^xi整除且加上2^xi-1后仍然能被2^k（1<=k<xi)整除，但反之则不行，所以处理x数组，若x[i-1]<=x[i]则删去x[i]，从后往前求2^x[i]-1的前缀和，然后对于一个数就可以用二分查找求能被整除的最大的xi，找到后加上前缀和，时间复杂度O（n*logn)。但好像不需要二分查找，O(nm)也能过？

代码：

#include <bits/stdc++.h>
using namespace std ;
const int max_N=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;

long long ksm(long long a, long long b)
{ 
    long long res = 1; 
    while(b) 
    { 
        if(b & 1)  
            res = res * a ; 
            a = a * a ; 
            b >>= 1; 
    } 
    return res; 
}

void solve(){
	int n,q;
    cin>>n>>q;
    ll a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int x[q+1];
    for(int i=1;i<=q;i++){
        cin>>x[i];
    }
    vector< int > xc;
    xc.push_back(x[1]);
    for(int i=2;i<=q;i++){
        if(x[i]<xc[xc.size()-1]){
            xc.push_back(x[i]);
        }
    }
    ll presum[q+1];
    ll xcksm[q+1];
    presum[xc.size()-1]=ksm(2,xc[xc.size()-1]-1);
    xcksm[xc.size()-1]=ksm(2,xc[xc.size()-1]);
    for(int i=xc.size()-2;i>=0;i--){
        xcksm[i]=ksm(2,xc[i]);
        presum[i]=presum[i+1]+xcksm[i]/2;
    }
    for(int i=1;i<=n;i++){
        if(a[i]%xcksm[xc.size()-1]!=0){
            cout<<a[i]<<" ";
            continue;
        }
        int left=0,right=xc.size()-1;
        while(left<right){
            int mid=(left+right)/2;
            if(a[i]%xcksm[mid]==0){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        int ind=right;
        a[i]+=presum[ind];
        cout<<a[i]<<" ";
    }
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

C. Smilo and Monsters

题意：

有一组怪物，每个怪物有血量，你可以使用一次普通攻击并积累一次连击，也可以使用终极攻击，并清空连击，求最少的攻击次数

分析：

积累的连击优先攻击血量最大的怪物，先求总血量，并除以2得到连击伤害，将怪物排序，从后往前遍历，若连击伤害大于等于怪物血量，则连击伤害减去怪物血量，怪物血量清零，并增加一次攻击次数；若连击伤害小于怪物血量，怪物血量减去连击伤害，连击伤害清零，增加一次攻击次数。最后攻击次数加上剩下的怪物血量

代码：

#include <bits/stdc++.h>
using namespace std ;
const int max_N=1e5+7;
const int INF = 0x3f3f3f3f;
typedef long long ll;

void solve(){
	int n;
    cin>>n;
    ll a[n+1];
    ll sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    sort(a+1,a+1+n);
    sum>>=1;
    ll ans=0;
    for(int i=n;i>=1;i--){
        if(sum>=a[i]){
            sum-=a[i];
            a[i]=0;
            ans++;
        }else if(sum){
            a[i]-=sum;
            sum=0;
            ans++;
            break;
        }
    }
    for(int i=1;i<=n;i++){
        ans+=a[i];
    }
    cout<<ans<<endl;
}

int main(){
	int t=1;
	
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}