>  기사  >  웹 프론트엔드  >  Codeforces Round #271 (Div. 2) F题 Ant colony(线段树)_html/css_WEB-ITnose

Codeforces Round #271 (Div. 2) F题 Ant colony(线段树)_html/css_WEB-ITnose

WBOY
WBOY원래의
2016-06-24 11:56:491086검색

题目地址:http://codeforces.com/contest/474/problem/F

由题意可知,最后可以留下来的一定是区间最小gcd。那就转化成了该区间内与区间最小gcd数相等的个数。区间最小gcd一定小于等于区间最小值,所以只要求最小值的个数。然后用r-l+1-个数即可。

对于以上信息,可以用线段树来维护。分别维护区间gcd,区间最小值以及区间最小值的个数。

代码如下:

#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64#define lson l, mid, rtminv[rt>1;    build(lson);    build(rson);    PushUp(rt);}void query(int ll, int rr, int l, int r, int rt){    if(ll=r)    {        q_gcd=getgcd(q_gcd,gcd[rt]);        if(minv[rt]==q_minv)        {            q_num+=num[rt];        }        else if(minv[rt]<q_minv q_num="num[rt];" q_minv="minv[rt];" return int mid="l+r">>1;    if(llmid) query(ll,rr,rson);}int main(){    int n, m, i, l, r;    scanf("%d",&n);    build(1, n, 1);    /*for(i=1;i  <br>  <br>  <p></p> </q_minv></algorithm></set></map></queue></ctype.h></math.h></stdlib.h></cstring></string></cstdio></iostream>
성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.