2020-05-22 — 习题训练二

A - Candies

题意：
$x + 2 x + 4 x + \dots + 2^{k - 1} x = n$

$x + 2 x + 4 x + \dots + 2^{k - 1} x = n$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int t;
    ll n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=2;i<n;i++){
            ll a=pow(2,i);
            if(n%(a-1)==0){
                cout<<n/(a-1)<<endl;
                break;
            }
        }
    }
    return 0;
}

B - Balanced Array

题意：

给定一个n要求是否有一个这样的式子前面n/2是偶数，后面n/2是奇数，前面n/2的数的和等于后面n/2的数的和

题解：

首先可以判断如果n/2是奇数的话是不可能有这样的式子的，因为左边就是奇数个，右边也是奇数个，右边加起来还是奇数。所以前n/2个从2开始加（2，4，6……），后n/2-1个从1开始加，最后一个数就是前n/2的和-后n/2-1的和。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n,k,l,sum1,sum2;
    cin>>t;
    while(t--){
        cin>>n;
        k=2,l=1;
        sum1=0,sum2=0;
        if((n/2)%2!=0){
            cout<<"NO"<<endl; 
        }
        else{
            cout<<"YES"<<endl;
            while(k<n+1){
                cout<<k<<" ";
                sum1+=k;
                k+=2;
            }
            while(l<=n-2){
                cout<<l<<" ";
                sum2+=l;
                l+=2;
            }
            cout<<sum1-sum2<<endl;
        } 
    }
    return 0;
}

C - Ichihime and Triangle

题意：

给定一个abcd和x，y，z的范围，问是否存在有x，y，z构成三角形。

题解：

a<=x<=b,b<=y<=c,c<=z<=d,根据三角形定理两边之和大于第三边，只要有两个长的边相等，那么另外一个边不论多少都可以。所以就取y=c，z=c，x=a就可以了。

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int t;
    ll a,b,c,d;
    cin>>t;
    while(t--){
        cin>>a>>b>>c>>d;
        cout<<b<<" "<<c<<" "<<c<<endl;//要2个大的相加一定大于第3个边 
    }
    return 0;
}

D - Kana and Dragon Quest game

题意：

对一个x血量的怪物，有两个技能一个是对它的血量x/2+10，还有一个是x-10，给定x和y的次数问能否打败怪兽。

题解：

可知当x血量越少的时候第一个技能扣去的越少，到后面还有可能使怪物血量变多- -。所以只要一直使用1技能直到不能再使怪物血量变少的时候（x/2+10-x>=0时就用二技能)，再用二技能就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    int x,n,m;
    int sum;
    cin>>t;
    while(t--){
        cin>>x>>n>>m;
        while(n--){
            sum=x/2+10;
            if(sum-x>=0){  
                break;
            }
            else{
                x=sum;
            } 
        }
        if(x-m*10>0){
            cout<<"NO"<<endl;
        }
        else{
            cout<<"YES"<<endl; 
        }
    }
    return 0;
}

E - Candies and Two Sisters

题意：

给一个n，把他分成a和b，要求a>b，问有几种可能使a>b.

题解：

如过n是奇数就有n/2种，如果是偶数就有n/2-1种，再特判一下n<=2的时候.

代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    int t;
    ll n,sum;
    cin>>t;
    while(t--){
      cin>>n;
      sum=n/2;
      if(n<=2){
          cout<<0<<endl;
          continue;
      }
      else{
          if(n%2==0){
              sum--;
          }
      }    
      cout<<sum<<endl;
    }
    return 0;
}

F - Construct the String

题意：

在一个长度n的字符串中每个a长度的子串中都有b个元素，答案一定存在，让我们写一种。

题解：

其实先得到含有b个元素的子串，然后再一直循环排列就好，因为a>b，所以在a中最少都有b的一个子串，就都含有这些元素了。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    int n,a,b,l,k;
    string p;
    cin>>t;
    while(t--){
        cin>>n>>a>>b;
        p="";
        for(int i='a';i<='a'+b-1;i++){
            p+=i;//得到b长度有b个不同字符的子串。
        }
        l=n%p.size();//剩余几个元素。
        k=n/p.size();//在n中能循环几次子串
        while(k--){
            cout<<p;
        }
        for(int i=0;i<l;i++){
            cout<<p[i];
        }
        cout<<endl;
    }
    return 0;
}