首页 > 代码库 > hdu5320
hdu5320
好久没写题代码能力简直贫弱
这道题思路不难,写起来有点麻烦
首先以某个点为右端点的区间的gcd种类级别是log的(因为下降最少是除2)
预处理所有的四元组(g,l,r,x)表示以x为右端点,左端点在[l,r]内区间公约数都是g
然后以g为第一关键字,x为第二关键字即可
最多选取不相邻区间数dp+线段树
计算方案要考虑两种情况,dp[i]=dp[j]+1
一是j落在[l,r-1],二是j落在[1,l-1],这两种i选取的方案是不一样的
然后就没了
1 #include<bits/stdc++.h> 2 #define mp make_pair 3 #define fi first 4 #define se second 5 #define pi pair<int,int> 6 using namespace std; 7 typedef long long ll; 8 const int mo=998244353; 9 struct node{int w,l,r,x;} q[100010*30]; 10 struct po{int a,b,c;} mx[100010*4],null; 11 pi g[2][100010]; 12 int st[100010*4],a[100010],n,t,tt,b[5],cas,ans1,ans2; 13 bool v[100010*4]; 14 15 int gcd(int a,int b) 16 { 17 return (b==0)?a:gcd(b,a%b); 18 } 19 20 void inc(int &a,int b) 21 { 22 a+=b; 23 if (a>mo) a-=mo; 24 } 25 26 bool cmp(node a,node b) 27 { 28 if (a.w==b.w) return a.x<b.x; 29 return a.w<b.w; 30 } 31 32 void init() 33 { 34 int p=0; 35 q[1]=(node){a[1],1,1,1}; 36 b[0]=1; 37 g[0][1]=mp(1,a[1]); 38 for (int i=2; i<=n; i++) 39 { 40 p^=1; b[p]=1; g[p][1]=mp(i,a[i]); 41 int gg=a[i]; 42 for (int j=1; j<=b[p^1]; j++) 43 { 44 pi tmp=g[p^1][j]; 45 gg=gcd(tmp.se,gg); 46 if (g[p][b[p]].se==gg) g[p][b[p]].fi=tmp.fi; 47 else g[p][++b[p]]=mp(tmp.fi,gg); 48 } 49 q[++t]=(node){g[p][1].se,g[p][1].fi,i,i}; 50 for (int j=2; j<=b[p]; j++) 51 q[++t]=(node){g[p][j].se,g[p][j].fi,g[p][j-1].fi-1,i}; 52 } 53 sort(q+1,q+1+t,cmp); 54 } 55 56 void up(po &a,po b,po c) 57 { 58 if (b.a>c.a) a=b; 59 else { 60 a=c; 61 if (b.a==c.a) 62 { 63 inc(a.b,b.b); 64 inc(a.c,b.c); 65 } 66 } 67 } 68 69 po ask(int i,int l,int r,int x,int y) 70 { 71 if (y<x||x<1) return null; 72 if (x<=l&&y>=r) return mx[i]; 73 int m=(l+r)>>1; 74 po c; 75 if (x<=m&&y<=m) return ask(i*2,l,m,x,y); 76 else if (y>m&&x>m) return ask(i*2+1,m+1,r,x,y); 77 else { 78 up(c,ask(i*2,l,m,x,y),ask(i*2+1,m+1,r,x,y)); 79 return c; 80 } 81 } 82 83 void add(int i,int l,int r,int f1,int f2,int x) 84 { 85 if (!v[i]) 86 { 87 st[++tt]=i; 88 v[i]=1; 89 } 90 if (l==r) 91 { 92 mx[i]=(po){f1,f2,(ll)l*f2%mo}; 93 return; 94 } 95 int m=(l+r)>>1; 96 if (x<=m) add(i*2,l,m,f1,f2,x); 97 else add(i*2+1,m+1,r,f1,f2,x); 98 up(mx[i],mx[i*2],mx[i*2+1]); 99 } 100 101 void work(int l,int r) 102 { 103 tt=0; 104 if (ans1>r-l+1) return; 105 add(1,1,n,1,q[l].r-q[l].l+1,q[l].x); 106 int s1=1,s2=q[l].r-q[l].l+1; 107 for (int i=l+1; i<=r; i++) 108 { 109 int f1,f2; 110 po m1=ask(1,1,n,1,q[i].l-1); 111 po m2=ask(1,1,n,q[i].l,q[i].r-1); 112 if (!m1.a&&!m2.a) 113 { 114 f1=1; 115 f2=q[i].r-q[i].l+1; 116 } 117 else if (m1.a>m2.a) 118 { 119 f1=m1.a+1; 120 f2=(ll)(q[i].r-q[i].l+1)*m1.b%mo; 121 } 122 else { 123 f1=m2.a+1; 124 f2=(1ll*q[i].r*m2.b%mo-m2.c+mo)%mo; 125 if (m1.a==m2.a) inc(f2,(ll)(q[i].r-q[i].l+1)*m1.b%mo); 126 } 127 if (s1<f1) 128 { 129 s1=f1; 130 s2=f2; 131 } 132 else if (s1==f1) inc(s2,f2); 133 add(1,1,n,f1,f2,q[i].x); 134 } 135 for (int i=1; i<=tt; i++) 136 { 137 int x=st[i]; 138 mx[x]=null; 139 v[x]=0; 140 } 141 if (s1>ans1) {ans1=s1; ans2=s2;} 142 else if (s1==ans1) inc(ans2,s2); 143 } 144 145 void build(int i,int l,int r) 146 { 147 mx[i]=null; 148 if (l!=r) 149 { 150 int m=(l+r)>>1; 151 build(i*2,l,m); 152 build(i*2+1,m+1,r); 153 } 154 } 155 156 int main() 157 { 158 null=(po){0,0,0}; 159 build(1,1,100000); 160 memset(v,0,sizeof(v)); 161 while (scanf("%d",&n)!=EOF) 162 { 163 for (int i=1; i<=n; i++) scanf("%d",&a[i]); 164 t=1; init(); 165 int i=1; ans1=0; ans2=0; 166 tt=0; 167 while (i<=t) 168 { 169 int j=i+1; 170 while (j<=t&&q[j].w==q[i].w) j++; 171 work(i,j-1); 172 i=j; 173 } 174 printf("%d %d\n",ans1,ans2); 175 } 176 }
hdu5320
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。