A. Sorting with Twos
题意：
给一个长度为n的数组，可以做任意次以下操作：选择一个整数m，将1-2m 的数减1。若能使数组变为一个单调递增的数组则输出YES，否则输出NO
分析：
只需要保证2m+1 -2m+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次询问，若这个数能被2xi整除，则这个数加上2xi-1
分析：
一个数能被2xi整除且加上2xi-1后仍然能被2k（1<=k<xi)整除，但反之则不行，所以处理x数组，若x[i-1]<=x[i]则删去x[i]，从后往前求2x[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;
}