Codeforces Round #276 (Div. 2) 解题报告

题目地址http://codeforces.com/contest/485

A题.Factory

模拟。判断是否出现循环,如果出现,肯定不可能。

代码:

 #include<cstdio>
#include<stdbool.h> using namespace std; int main()
{
int a,m;
int flag[]={}; scanf("%d%d",&a,&m);
while(true) { if(a%m==){
printf("Yes\n");
return ;
}
if(flag[a]==) {
printf("No\n");
return ;
}
flag[a]=;
a=(a+a)%m;
} return ;
}

B题:Valuable Resources

找出横纵坐标的最大最小值,然后求最小面积。

 #include<cstdio>
#include<algorithm>
#include<iostream> const int INF=(int)1e9+; using namespace std; int main()
{
int n,x,y,maxx=-INF,maxy=-INF,minx=INF,miny=INF; scanf("%d",&n);
while(n--) {
scanf("%d%d",&x,&y);
maxx=max(maxx,x);
minx=min(minx,x);
maxy=max(maxy,y);
miny=min(miny,y);
} int len;
len=max((maxx-minx),(maxy-miny));
cout<<(long long )len*len<<endl;
return ;
}

C题:Bits

位运算。给定一个区间[L,R],问在本区间内哪个整数的二进制1的数量最多,有多个解输出最小数。

要求二进制的1尽量多,还要求尽量小,运用位运算从低位开始把0变成1。

从左边界开始,从低位向高位按位或(0变成1,1也还是1),直到比R大停止,输出前一个(即比R小的最后一个数)。

 #include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream> #define LL long long using namespace std; int main()
{
int n;
LL l,r,t,p; scanf("%d",&n);
while(n--) {
p=;
cin>>l>>r;
for(int i=;i<;i++) {
t=l|p;
if(t>r) break;
p<<=; l=t;
}
cout<<l<<endl;
} return ;
}

D题:Maximum Value

考虑到可能会出现大量相同的数,所以先排序,去掉相同的数,重新建立数列b[i]。

对于x来说,在k*x~(k+1)*x这段范围内,余数最大的肯定是最接近(k+1)*x的数。枚举每个数的倍数,并不断更新即可。数列有序,可以通过二分查找最接近(k+1)*x的数。

 #include<cstdio>
#include<iostream>
#include<algorithm> const int N=2e5+;
using namespace std; int main()
{
int i,j,n,a[N],b[N],p,ans,val; scanf("%d",&n);
for(int i=;i<=n;i++) {
scanf("%d",&a[i]);
} sort(a+,a+n+);
b[p=]=a[];
for(int i=;i<=n;i++) {
if(a[i]!=a[i-]) b[++p]=a[i];
} ans=;
for(int i=;i<p;i++) {
int val=b[i],j=i;
while(j<=p) {
val+=b[i];
j=lower_bound(b+,b+p+,val)-b;
ans=max(ans,b[j-]%b[i]);
} } printf("%d\n",ans);
return ;
}
上一篇:sdut 1592转置矩阵【稀疏矩阵的压缩存储】【快速转置算法】


下一篇:Ambari server:无法显示内存,CPU等使用率