目录
显示
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\) 的最大整数解）
接下来就是分配时间了，我们的原则是：让第一天的时间利用最多。
我们先计算出 \(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;
}