Heim > Web-Frontend > HTML-Tutorial > 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
Freigeben: 2016-06-24 11:56:49
Original
1121 Leute haben es durchsucht

题目地址: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>
Nach dem Login kopieren
Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage