Codeforces Round #636 (Div. 3) (部分) – Zechel

A    Candies

寻找一个x使 x+2x+…+(2^(k-1)x = n  (k>1)。我们可以抽象地将等号左边的式子看做x乘上一个数 m,m前k个2的次方的和。我们将m转化为二进制数描述的角度,可以看出m在二进制下一共有k位,且每一位上的数字都为1。那么在给出的n的条件下这样的m是有限的,我们可以直接进行枚举,就可以在很短的时间内把所以可能的m全部检验一遍,如果存在这样的m使m整除n,则商就是所求的x,否则x不存在。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long n;
        cin>>n;
        long long sit=3;//k>1,故m初始值为3
        long long ans;
        while(sit<=n)
        {
            if(n%sit!=0)
            {
                sit=sit*2+1;//枚举所有可能的m的情况
            }
            else {ans=n/sit;break;}
        }
        cout<<ans<<endl;
    }
}

 

B   Balanced Array 

一段数列具有偶数个数,要使前半段之和与后半段之和相等,且前半段全为偶数,后半段全为奇数。此题思维难度很小,我们需要分类讨论一下:

1.当前半段和后半段的元素个数为奇数,那么奇数个偶数之和为偶数,奇数个奇数之和为奇数,故这样的数列是不存在的

2.当前半段和后半段的元素个数仍为偶数,前半段只需要从2开始枚举每一个偶数;后半段从1开始枚举每一个奇数,只需要将最后一个数改为一个可以使前后两段和相等的数就行。可知后半段总和必为偶数,但除最后一个外,其他数是奇数个奇数之和,必为奇数,则最后一个数一定也为奇数,合题。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        if((n/2)%2==1)cout<<"NO"<<endl;
        else
        {
            cout<<"YES"<<endl;
            int len=n/2,num=2;
            for(int i=1;i<=len;i++)
            {
                cout<<num<<" ";
                num+=2;
            }
            num=1;
            for(int i=1;i<len;i++)
            {
                cout<<num<<" ";
                num+=2;
            }
            cout<<num+len;
            cout<<endl;
        }
    }
}

C    Alternating Subsequence

第三题定义了一个序列中的子串,该子串可以跳跃式选择,但不能改变原数列的顺序,且要求子序列中每一个元素都必须与其左右相邻的元素符号相反。我们要求的就是这样一个子串,让子串长度取可能的最大长度,并且求出可能的所有情况下子串的最大的和是多少。

我们把原序列分为一段段全正或全负的区间,为了使字串最长,那么一定要把所有的区间都取一个数出来。然后为了使和最大,我们需要取这个区间内最大的数即可。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define maxn 200005
using namespace std;
inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    } 
    while('0' <= ch && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    } return x * f;
}
int main()
{
    int t;
    t=read();
    while(t--)
    {
        int n;
        n=read();
        long long ans=0;
        long long p=0;//记录此时的区间的正负情况
        for(int i=0;i<n;i++)
        {
            long long k;
            k=read();
            if(p==0){p=k;continue;}
            if(k*p<0)//判断是否进入下一个区间
            {
                ans+=p;
                p=k;
            }
            else
            {
                p=max(p,k);   //挑选区间内最大元素
            }
        }
        ans+=p;
        cout<<ans<<endl;
    }
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

川公网安备 51130202000337号