锐客网

  1. 首页 > it技术 > >

Codeforces Round #514 (Div. 2) C. Sequence Transformation D. Nature Reserve

cf

div2第一次出C...虽然是最后两分钟才pp的
B题写成了大模拟 写了8个if1h才过 赛后看long1代码当场自闭
D题结束之后还写了20分钟没调出来 细节下面讲
【Codeforces Round #514 (Div. 2) C. Sequence Transformation D. Nature Reserve】
C题题意：给1~n n个数 每次求所有数的gcd 然后删一个数 求这些gcd组成的字典序最大
手动模拟到12了 发现了规律 除了3 其他情况都是优先走偶数 然后剩下的偶数怎么走 然后又发现2468其实就是2*1234 那么就可以得到一个贪心策略了

#include using namespace std; int main() { int n,m,k,flag; while(scanf("%d",&m)!=EOF) { if(m==1) { puts("1"); continue; } if(m==3) { puts("1 1 3"); continue; } n=m; k=1; flag=0; while(n) { if(n==3) { printf("%d %d ",k,k); while(m%k)m--; printf("%d\n",m); break; } if(n&1) { flag=1; n++; } n>>=1; if(n&&!flag||n>1&&flag) { for(int i=0; i

D题题意：找个最小的圆和x轴相切，然后圆周和圆内部包含给定的点
做C之前瞄了一眼D 没想到比较好的办法 之后又推出来了r和圆心的横坐标xo的关系 那么对于n个点我们就得到了n个不等式 不等式的右边是个二次函数 那么利用三分求解即可
但是 在自己做的时候 发现了 对于每个不等式 三分求得最值 这样的结果会是不准确的 因为每个不等式取得的最值不同 但是每个不等式取到最值的三分找到的位置也不同并且每个不等式都应该满足
想了挺久没想清楚 去看了别人的写法
把n个点看做是一个函数 在每次三分的过程中求得一个满足所有不等式的值 对这个值的大小进行比较和取舍
（此处还没有想明白它的正确性 就是对于这样的一个函数 它为什么还是单峰的 或者说为什么可以用三分去求它的最值）
#include #define double long double using namespace std; const int N=1e5+10; const double eps=1e-7; double sqr(double x){return x*x; } struct Point{ double x,y; bool operator<(const Point&b)const { return yeps) { m1=(r-l)/3+l; m2=r-(r-l)/3; if(f(m1)>f(m2))l=m1; else r=m2; } return f(l); } int main() { double r,xmi,xma,ymi,yma; while(cin>>n) { xmi=ymi=1e100; xma=yma=-1e100; for(int i=0; i>p[i].x>>p[i].y; xmi=min(xmi,p[i].x); xma=max(xma,p[i].x); ymi=min(ymi,p[i].y); yma=max(yma,p[i].y); } if(ymi*yma<0) { cout<<-1<

    推荐阅读


    上一篇：基于|基于 PageSpeed 的性能优化实践

    下一篇：C语言for循环打印各种字符三角形+菱形的方法