Codeforces Round #652 (Div. 2) – 一千零一网

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]));
    }
}

 

发表评论

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