CFR618

CFR618 div1

CF1299A Anu Has a Function

请先思考后再展开
1
2
3
4
int n=qread();fo(i,1,n) a[i]=qread();
fo(i,1,n) pre[i]=pre[i-1]|a[i];fd(i,n,1) suf[i]=suf[i+1]|a[i];
pii mx={0,0};fo(i,1,n) chmax( mx,{ (pre[i-1]|suf[i+1]|a[i])-(pre[i-1]|suf[i+1]),i } );
write1(a[mx.SE]);fo(i,1,n) if(i!=mx.SE) write1(a[i]);

CF1299B Aerodynamic

请先思考后再展开
1
2
3
4
5
6
7
8
int n=qread();fo(i,0,n-1) p[i].x=qread(),p[i].y=qread();
if(n%2) gg2();
fo(i,0,n/2-1)
{
int j=i+n/2;
V A=p[(i+1)]-p[i],B=p[(j+1)%n]-p[j];
if(A.x+B.x!=0 or A.y+B.y!=0) gg2();
}puts("yes");

CF1299C Water Balance

题意:给出长度为$n \le 1e6$的序列,任意多次修改一段区间为平均数,最小化序列字典序

请先思考后再展开

我的思路:先设三个块的大小与和,然后推个不等式发现直接操作三个永远比先操作后两个再操作前两个优秀,即操作区间不会重叠。从左到右依次确定,发现每次就是在右边的下凸壳上找斜率最小那个点

1
2
3
4
5
6
7
int n=qread();fo(i,1,n) S[i]=S[i-1]+qread();qq[1]=0;int top=1;
fo(i,1,n)
{
while(top>=2 and (S[qq[top]]-S[qq[top-1]])*(i-qq[top])>=(S[i]-S[qq[top]])*(qq[top]-qq[top-1]) ) top--;
qq[++top]=i;
}
fo(i,1,top) fo(j,qq[i-1]+1,qq[i]) printf("%.10lf\n", 1.0*(S[qq[i]]-S[qq[i-1]])/(qq[i]-qq[i-1]) );

别人的思路非常奥妙啊

剩下的题有空补

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/400095af.html
转载请注明出处,谢谢!