Codeforces Round #638 (Div. 2) – Zechel

A. Phoenix and Balance

一个数组里共有n个数,每一个数都是2的k次方,k是从1到n的数,且保证n是偶数。现在要将其均分为两堆,要求使两堆的和的差值最小,求最小的差值。

如果我们将2^n加入任意一个堆,则必然这个堆是更大的。为了使二者差值尽量的小,那么就要使另外一个堆尽量地大,所以需要将小于2^n且尽量大的n/2个数加到另一个堆里。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int len=n/2;
        long long a=0,b=0,ans=0;
        long long sit=1;
        for(int i=1;i<n;i++)
        {
            sit=sit*2;
            if(i<len)a+=sit;
            else b+=sit;
        }
        sit=sit*2;
        a+=sit;
        ans=abs(a-b);
        cout<<ans<<endl;
    }
}

B. Phoenix and Beauty

给一段数组,要求通过添加数组里的元素,来使任意长度为k的连续元素段和是相同的,如果不能完成,则输出-1。

如果使整个数组里的元素的周期为k,即每隔k个元素一个循环。显然,这样每k个元素的和是相同的。我们需要先确定数组里到底有多少种不同的元素,如果要使周期为k,那么元素的种类必然要不大于k,否则就不可能满足题意,输出-1。

所以我们先确定有多少种元素,放到一个集合里,如果不足k则通过将前面的数补充到后面来使该集合里共有k个数,用来作为标准周期T。然后将原数组添加元素成为k周期,就是我们要求的答案。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<set>
#define maxn 20005
using namespace std;
int one[maxn],two[maxn];
vector<int>tr;
set<int>Q;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(one,0,sizeof(one));
        memset(two,0,sizeof(two));
        tr.clear();
        Q.clear();
        int n,k;
        scanf("%d %d",&n,&k);
        for(int j=0;j<n;j++){scanf("%d",&one[j]);Q.insert(one[j]);}
        int u=Q.size();
        if(u>k){cout<<"-1"<<endl;continue;}//种类数多于k
        int sit=0,tot=0;
        set<int>::iterator it;
        for(it=Q.begin();it!=Q.end();it++)
        {
            tr.push_back(*it);//转移到数组里
        }
        for(int i=0;tr.size()<k;i++)
        {
            tr.push_back(tr[i]);//补齐长度k
        }
        for(int i=0;i<n;i++)
        {
            while(tr[sit]!=one[i])//往two数组里添加元素,使周期为k,
            {
                two[tot]=tr[sit];
                tot++;
                sit=(sit+1)%k;//循环
            }
            two[tot]=one[i];
            tot++;
            sit=(sit+1)%k;
        }
        cout<<tot<<endl;
        for(int i=0;i<tot;i++)cout<<two[i]<<" ";
        cout<<endl;   
    }
}

C. Phoenix and Distribution

题意:将n个字符分配到k个组里,求所以可能的情况下,在 字典序最大的组 中字典序最小的情况。

我们先将所有字符排序,分情况讨论。如果k==n,那么输出最后一个字符即可。如果k==1,则输出所有字符即可。其他情况,如果前k个数不完全相同,那么只需要第k个字符即可,因为我们相当于把第k个字符和其后的字符接在 以比第k个字符小的字符开头的组 后面,这样就保证了第k个数是最大的,且所有情况里最小的最大字符串。

当前k个数相同时,则所有组开头字符无区别:

如果后面的数全部相同,那么我尽量平均分配所有字符,最长的字符串即最大。可知这样的分配下没有更小的最大字符串;

若后面的数不相同,无论任何情况下的最大字符串组,必然都在其后接有最大的字符,那么为了构造最小的最大字符串组,只需要将后续所有字符接到某一个组之后即可,即可得到最大字符串。这样就可以让最大字符尽量靠后,得到的最大最长串也就相对更小了。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
char str[100005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d %d %s",&n,&k,str);
        sort(str,str+n);
        if(k==1)printf("%s\n",str);
        else
        {
            if(str[k-1]!=str[0]||n==k)cout<<str[k-1]<<endl;
            else
            {
                if(str[k]==str[n-1])
                {
                    cout<<str[k-1];
                    int len=(n-k)/k+((n-k)%k?1:0);
                    while(len--)cout<<str[k];
                }
                else
                {
                    for(int i=k-1;i<n;i++)cout<<str[i];   
                }
                cout<<endl;
            }
        }
    }
}

D. Phoenix and Science

题意:在第一天给定一个细胞,每一个细胞可以在白天分裂成两个质量减半且相同的新细胞,而每个细胞在晚上都会质量增加一,现在要求在最短的天数内使细胞和为n,并输出每天细胞分裂的次数。

我们设a[i]为第 i 天晚上细胞的增量。显然,如果当天白天所以细胞分裂 a[i]=2*a[i-1];如果没有一个细胞分裂,则 a[i]=a[i-1]。所以a[i]的大小是介于这之间。我们可以假设初始质量为0,a[0]=1,那么为了尽快达到n,可以令a[1]=2,a[2]=4….a[k]=2^k。如果和恰好是n,那么就结束运算了。如果不是,只能小于其的话,那么n的多余部分可以插入到之前的任何一天,通过排序保证a序列是从小到大的,当然,这样必然满足任何一个元素a[k],都满足a[k]>=a[k-1]且a[k-1]<=2*a[k-1],所以这样的情况是成立的。这时a序列的和即为n。

要求每一天的分裂数,我们可以发现,每分裂一次,当晚的质量增加数将会比前一天多1,所以当天分裂数即为   a[i]-a[i-1]。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
vector<int>ans;
void cul(int x)
{
    ans.clear();
    for(int i=1;i<=x;i=i*2)
    {
        ans.push_back(i);
        x=x-i;
    }
    if(x>0)
    {
        ans.push_back(x);
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()-1<<endl;
    for(int i=1;i<ans.size();i++)cout<<ans[i]-ans[i-1]<<" ";
    cout<<endl;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cul(n);
    }
}

 

发表评论

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

川公网安备 51130202000337号