企业官网建设流程全解析

P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi

题目背景

译自 COCI 2024/2025 #5 T3。2s,0.5G \texttt{2s,0.5G}2s,0.5G。满分为90 9090。

题目描述

给定正整数序列h 1 , … , h n h_1,\ldots,h_nh1​,…,hn​。

对于区间[ l , r ] [l,r][l,r]，我们称i ii（l ≤ i ≤ r l\le i\le rl≤i≤r）关于[ l , r ] [l,r][l,r]是好的，当且仅当：h i = gcd ⁡ ( h l , h l + 1 , … , h r ) h_i=\gcd(h_l,h_{l+1},\ldots,h_r)hi​=gcd(hl​,hl+1​,…,hr​)。

对于i ii，定义f ( i ) f(i)f(i)表示：所有i ii关于[ l , r ] [l,r][l,r]是好的区间中，r − l + 1 r-l+1r−l+1的最大值。

对于i = 1 , 2 , … , n i=1,2,\ldots,ni=1,2,…,n，求出f ( i ) f(i)f(i)。

输入格式

第一行，正整数n nn。

第二行，n nn个正整数h 1 , h 2 , … , h n h_1,h_2,\ldots,h_nh1​,h2​,…,hn​。

输出格式

输出n nn个正整数f ( 1 ) , f ( 2 ) , … , f ( n ) f(1),f(2),\ldots,f(n)f(1),f(2),…,f(n)。

输入输出样例 #1

输入 #1

6 3 6 6 6 1 3

输出 #1

4 3 3 3 6 1

输入输出样例 #2

输入 #2

5 10 2 10 15 5

输出 #2

1 3 1 1 3

说明/提示

数据范围

对于100 % 100\%100%的数据，保证1 ≤ n , h i ≤ 10 6 1\le n,h_i\le 10^61≤n,hi​≤106。

特殊性质 A：h i ≤ 100 h_i\le 100hi​≤100。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#defineMAXN1000010intg[MAXN][21],n,b[MAXN];intansl[MAXN],ansr[MAXN];intgcd(intx,inty){return(y==0?x:gcd(y,x%y));}voidinit(){for(intj=1;j<20;j++)for(inti=1;i+(1<<j)-1<=n;i++)g[i][j]=gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]);}intquery(intl,intr){intk=b[r-l+1];returngcd(g[l][k],g[r-(1<<k)+1][k]);}intask(intx,intb){intl=1,r=b==1?x-1:n-x,ans=0;while(l<=r){intmid=(l+r)/2;intnow=(b==1?query(x-mid,x):query(x,x+mid));if(g[x][0]==now)ans=mid,l=mid+1;elser=mid-1;}returnans;}intmain(){scanf("%d",&n);for(inti=2;i<=1e6;i++)b[i]=b[i/2]+1;for(inti=1;i<=n;i++)scanf("%d",&g[i][0]);init();for(inti=n;i>=1;i--)ansl[i]=i-ask(i,1),ansr[i]=i+ask(i,2);for(inti=1;i<=n;i++)printf("%d ",ansr[i]-ansl[i]+1);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容