☆ 「CF 1486A」Shifting Stacks
Link.
考虑最少需要操作多少次后判断。
#include<map>
#include<cstdio>
using namespace std;
int t,n,flag;
long long sum,cum,x;
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
flag=1;
for(int i=1;i<=n;++i)
{
scanf("%lld",&x);
sum+=x;
if(sum-cum<0) flag=0;
cum+=i;
}
printf("%s\n",flag?"YES":"NO");
sum=cum=0;
}
return 0;
}
☆ 「CF 1486B」Eastern Exhibition
Link.
可以发现行列独立，所以用个结论就行了。
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n;
long long one[1010],ano[1010];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld %lld",&one[i],&ano[i]);
sort(one+1,one+n+1);
sort(ano+1,ano+n+1);
printf("%lld\n",(one[(n+2)/2]-one[(n+1)/2]+1)*(ano[(n+2)/2]-ano[(n+1)/2]+1));
}
return 0;
}
☆ 「CF 1486C1」Guessing the Greatest (easy version)
Link.
看到 的限制，想到 Robot Arms，猜想是二分。
然后就完了。
#include<cstdio>
int engoric(int l,int r)
{
int res;
printf("? %d %d\n",l,r);
fflush(stdout);
scanf("%d",&res);
return res;
}
int n;
int main()
{
scanf("%d",&n);
int mxpos=engoric(1,n);
int l=1,r=n;
if(mxpos==1) l=1;
else
{
if(engoric(1,mxpos)==mxpos) r=mxpos;
else l=mxpos;
}
if(l==mxpos)
{
while(l+1<r)
{
int mid=(l+r)>>1;
if(engoric(mxpos,mid)==mxpos) r=mid;
else l=mid;
}
printf("! %d\n",r);
}
else
{
while(l+1<r)
{
int mid=(l+r)>>1;
if(engoric(mid,mxpos)==mxpos) l=mid;
else r=mid;
}
printf("! %d\n",l);
}
return 0;
}
☆ 「CF 1486C2」Guessing the Greatest (hard version)
Link.
同 C1。
☆ 「CF 1486D」Max Median
Link.
☆ 「CF 1486E」Paired Payment
Link.
☆ 「CF 1486F」Pairs of Paths
Link.