Codeforces Round #652 (Div. 2) – Zechel

A.FashionabLee

题目的大意是一个正多边形,问是否可以找到两条边,一条平行于x轴,一条平行于y轴。

首先,可以观察出,边数为4的倍数的多边形,假如以原点为中心,则是可以分为两条垂直于x的边,两条平行于y轴的边,其余的边可以均匀地分散在四个象限。但是,如果多添加的边不是4的倍数,那么这种状态就会被打破,反之仍然成立。所以边数是4的倍数的四边形是合题的。

对于其他情况,其实要找到这样的边,必然存在两条边相对的夹角的度数为90,我们就可以利用正多边形的内角来否定其他情况不成立。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#define maxn 300005
using namespace std;
typedef long long ll;
int main()
{
   int T,n;
   scanf("%d",&T);
   for(int i=1;i<=T;i++)
   {
       scanf("%d",&n);
       if(n%4==0)cout<<"YES"<<endl;
       else cout<<"NO"<<endl;
   }
}

B. AccurateLee

这个题的关键在于,要发现一个规律,只要0的前面有1,不管有多少的1和0,最终都可以化为0,比如1000100010,100011110010,就都可以化为0。从左边第一位起的所有连续的0不能消除,从右边第一位起的所有连续的1不能消除,为了使字符串尽量短且字典序小,就需要尽量消去从右边第一个0到左边第一个1之间的所以串,消为0。注意判断全0或全1的情况。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#define maxn 100005
using namespace std;
typedef long long ll;
char c[maxn];
int main()
{
   int t;
   int n;
   scanf("%d",&t);
   for(int i=1;i<=t;i++)
   {
       scanf("%d",&n);
       scanf("%s",c);
       if(c[n-1]=='1')
       {
           int L=n-1,R;
           while(L>=0&&c[L]!='0')L--;
           L++;
           R=n-1;
           if(c[0]=='1')
           {
               if(L!=0)printf("0");
           }
           else
           {
               int l=0,r=0;
               while(r<=n-1&&c[r]=='0')r++;
               r--;
               if(r!=L-1)printf("0");
               for(int i=l;i<=r;i++)printf("0");
           }
           for(int i=L;i<=R;i++)printf("1");
       }
       else
       {
           if(c[0]=='1')printf("0");
           else
           {
               int l=0,r=0;
               while(r<=n-1&&c[r]=='0')r++;
               r--;
               if(r!=n-1)
               {
                   printf("0");
               }
               for(int i=l;i<=r;i++)printf("0");
           }
       }
       printf("\n");
   }
}

C. RationalLee

题目大意是将,一些整数序列分成若干份,每一份中的最大值和最小值相加就是这一份的快乐值。现在我们要求某一种分法,是总快乐值最大。

我们通过贪心来分析。显然,无论如何分,整数序列中的最大值和最小值肯定要被加入到最终结果,所以,为了使次小的值尽量不被加入,次大的值尽量被加入,我们可以从最大的那一份开始填充,先将此时序列的最小值和最大值放入,然后用尽量小的值的去填满这个份数。这样,再用剩下的序列重复这个过程。根据前面的分析,这样就可以使总快乐值最大。

但所是,在某些份数只有1的情况下,如果填充最大值到里面,最大值就相当于加了两次,这样最终的结果会更优。所以我们需要先用序列里的最大值填满所有份数为1的情况。

代码如下:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#define maxn 200005
using namespace std;
typedef long long ll;
int inter[maxn];
int much[maxn];
int main()
{
    int n,k,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;i++)scanf("%d",&inter[i]);
        for(int i=1;i<=k;i++)scanf("%d",&much[i]);
        sort(much+1,much+k+1);
        sort(inter+1,inter+n+1);
        int sit=1;
        ll sum=0;
        int L=1,R=n;
        while(sit<=k&&much[sit]==1)
        {
            sum=sum+2*inter[R];
            sit++;
            R--;
        }
        for(int j=k;j>=sit;j--)
        {
            sum=sum+inter[L]+inter[R];
            L=L+much[j]-1;
            R--;
        }
        printf("%lld\n",sum);
    }
}

D. TediousLee

这道题类似与递推。发现规律,每一个 n 的图像,是有一个结点,左右两边连n-2的图形,中间连n-1的图形构成的。

记录这个结点的爪子要涂为黄色为 1,不涂则为零。

是否能够涂这个爪子,取决于它的子结点是否已经涂过,这样就需要之前的状态的0和1。很容易就可以得到最终的公式:

如果涂,则 n涂的情况=n-1不涂的情况+2*n-2不涂的情况。

如果不涂,则 n不涂的情况=max(n-1涂的情况,n-1不涂的情况)+2*max(n-2涂的情况,n-2不涂的情况)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
#define maxn 2000005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll pre[maxn][5];
void _pre()
{
    for(int i=5;i<=2000000;i++)
    {
        pre[i][0]=max(pre[i-1][0],pre[i-1][1])+2*max(pre[i-2][0],pre[i-2][1]);
        pre[i][0]=pre[i][0]%mod;
        pre[i][1]=pre[i-1][0]+2*pre[i-2][0]+4;
        pre[i][1]=pre[i][1]%mod;
    }
}
int main()
{
    pre[1][0]=0;
    pre[1][1]=0;
    pre[2][0]=0;
    pre[2][1]=0;
    pre[3][1]=4;
    pre[3][0]=0;
    pre[4][1]=4;
    pre[4][0]=4;
    _pre();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int k;
        scanf("%d",&k);
        printf("%lld\n",max(pre[k][0],pre[k][1]));
    }
}

 

20 对 “Codeforces Round #652 (Div. 2)”的想法;

  1. Man kann jeden Tag etwas Neues hier lernen. Ich bin ein regelmäßiger für die meisten von denen Blogs, aber immer noch nicht um ein Paar von ihnen wissen. Rosemary Meryl Keegan

  2. Hou la la! Cela pourrait être l’un des blogs les plus utiles que nous ayons jamais vu sur ce sujet. En fait magnifique. Je suis également spécialiste de ce sujet afin que je puisse comprendre vos efforts. Kakalina Corey Reinhardt

  3. I have read several excellent stuff here. Definitely price bookmarking for revisiting. I wonder how so much attempt you place to make such a excellent informative web site. Lee Gareth Jakoba

  4. Wow! This could be one particular of the most beneficial blogs We’ve ever arrive across on this subject. Actually Magnificent. I’m also a specialist in this topic so I can understand your effort. Jennine Sherm Trinidad

  5. Hallo, always great to see other people through the hole world in my searching, I really appreciate the time it should have taken to put together this awesome article. Cheers
    Rebekkah Maurits Nahama

发表评论

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

川公网安备 51130202000337号