[CF1072X]Codeforces Round #517 (Div. 2, based on Technocup 2019 Elimination Round 2)

C题调了很久竟然FST了,心碎…

题目链接

http://codeforces.com/contest/1072

A. Golden Plate

大意

给出一个盘子,我们现在需要在盘子上镶金,第一层是在盘子边缘,接下来每一层离上一层相隔2个格子。

我们要镶嵌\(k\)层,求我们需要镶嵌多少格黄金。

题解

按题意计算即可。

#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
 int w,h,k,ans=0;
 scanf("%d%d%d",&w,&h,&k);
 for(int i=1;i<=k;i++)
 {
  ans+=(w+h)*2-4;
  w-=4,h-=4;
 }
 printf("%d\n",ans);
 return 0;
}

B. Curiosity Has No Limits

大意

给出两个序列\(A,B (0 \leq a_i,b_i \leq 3)\),构造一个序列T,要求\( t_i \& t_{i+1} = a_i \)且\( t_i | t_{i+1} = b_i \)。

题解

我们只需枚举\(t_1\)的值就可以利用规律:\(a \& b + a | b = a+b\)来推算序列其余项的值。如果发现出现矛盾,说明枚举的\(t_1\)的值是非法的。

#include <stdio.h>
int a[100005],b[100005],t[100005];
int main()
{
 int n;
 scanf("%d",&n);
 for(int i=1;i<n;i++)
  scanf("%d",&a[i]);
 for(int i=1;i<n;i++)
  scanf("%d",&b[i]);
 for(int i=0;i<=3;i++)
 {
  bool flag=true;
  t[0]=i;
  for(int j=1;j<n;j++)
  {
   t[j]=a[j]+b[j]-t[j-1];
   if((t[j-1]|t[j])!=a[j]||(t[j-1]&t[j])!=b[j])
   {
    flag=false;
    break;
   }
  }
  if(flag)
  {
   puts("YES");
   for(int i=0;i<n;i++)
    printf("%d ",t[i]);
   return 0;
  }
 }
 puts("NO");
 return 0;
}

C. Cram Time

大意

为了备考,你需要抽出两天时间看笔记,两天能够看笔记的时间分别为\(a\)小时和\(b\)小时。看完笔记\(k\)需要\(k\)小时,同一份笔记不能看两次。

现在你需要求出一种方案,使得你两天一共看的笔记尽可能多。

题解

显然,最优的方案是看\(1 \ldots k\)这几份笔记。(其中\(k\)的值应该是满足\(k(k-1)/2 \leq a+b[latex]的最大整数解)

接下来就是分配时间了,我们的原则是:让第一天的时间利用最多。

我们先计算出[latex]k\),然后将耗时最多的几份笔记放入第一天的复习计划,并使得第一天的耗时恰好为\(a\)。

把剩下的笔记放入第二天的复习计划即可。

#include <cstdio>
#include <algorithm>
using namespace std;
int maxt,vis[80005],ans,tot;
int main()
{
 int a,b;
 scanf("%d%d",&a,&b);
 if(a==0&&b==0)
 {
  printf("0\n\n0\n\n");//其实这里是否输出空行并不会产生太大影响
  return 0;
 } 
 for(int i=1;;i++)
 {
  tot+=i;
  if(tot>a+b)
  {
   maxt=i-1; 
   break;
  }
 }
 tot=0;
 for(int i=maxt;i>=1;i--)
 {
  if(i+tot>=a)
  {
   if(a==0)
   {
    printf("0\n");
    ans=maxt;
    break;
   }
   printf("%d\n",min(a-tot,maxt)?maxt-i+1:maxt-i);
   for(int j=i+1;j<=maxt;j++)
    printf("%d ",j),vis[j]=1;
   if(min(a-tot,maxt))printf("%d\n",min(a-tot,maxt));
   else puts("");
   vis[min(a-tot,maxt)]=1;
   ans=min(a-tot,maxt)?i-1:i;
   break;
  }
  tot+=i;
  if(i==1)
  {
   printf("%d\n",maxt);
   for(int i=1;i<=maxt;i++)
    printf("%d ",i);
   puts("");
  }
 }
 printf("%d\n",ans);
 if(ans==0)return 0;
 for(int i=1;i<=maxt;i++)
  if(!vis[i])printf("%d ",i);
 return 0;
}

 

发表评论

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