关于类倍增求法

P3146 [USACO16OPEN] 248 G

如果是能够向右拓展的最右端点代码应该可写成: ```cpp #include<bits/stdc++.h> using namespace std; int f[60][300000],ans,n; int main(){ cin>>n; for(int i=1;i<=n;i++) { int a; cin>>a; f[a][i]=i; } for(int i=2;i<=58;i++) { for(int j=1;j<=n;j++) { if(!f[i][j]) // if (f[i-1][f[i-1][j] + 1] >= j) if(f[i - 1][j] != 0) f[i][j]=f[i-1][f[i-1][j] + 1]; if(f[i][j]) { ans=i; // if (ans == 3) cout << "DEBUG:" << i << ' ' << j << ' ' << f[i - 1][j] << ' ' << f[i][j] << '\n'; } } } cout<<ans; return 0; } ```
by Acerakoi @ 2023-04-15 10:17:39


总之,这是一种很新奇的做法
by Acerakoi @ 2023-04-15 10:18:18


@[Acerkaio](/user/514850) usaco的题是这样的,银组及以上几乎每道题都能看到一个新颖的trick
by SkyWave @ 2023-04-15 10:19:36


我喜欢
by SkyWave @ 2023-04-15 10:19:45


@[一扶苏一](/user/65363)
by Texas_the_Omertosa @ 2023-04-16 21:37:38


太对了哥
by LukeLuke @ 2023-07-24 22:39:54


|