CF1654E Arithmetic Operations（根号分治）

解析

降智谔谔题。
明明都把做法大块想出来，最后很沙雕的一步掉牛角尖里了…
无能狂怒之下写了一发实际复杂度 n 2 n^2 n2 的代码。
不过暴力艹题还是很爽的。
可能确实不太好卡吧，让我自己构造我是卡不掉。
更何况CF应该不会有人和我一样在如此沙雕的地方卡住。

乍一看（结合题目颜色）挺水的题，但细想想却没有什么太好的方法。
再看看5秒时限，lxl赐予我力量！

设公差为 $d$，那么两个数可以同时出现在等差数列中当且仅当 a j − a i = ( j − i ) d a_j-a_i=(j-i)d aj​−ai​=(j−i)d。
那么我们就有了一个 $O(NV)$ 的暴力，固定公差后统计 a i + i ∗ d a_i+i*d ai​+i∗d 的众数。
又注意到，有些比较大的公差枚举起来非常的蠢，因为它们产生的答案不会太大。
进一步的，对于公差 $d$，其保留的原序列两端距离不会超过 V d \frac{V}{d} dV​。
因而考虑根号分治，先把 $d\le B$ 的每个扫一遍 $O(nB)$ 做，然后剩下的答案两端距离必然不会超过 V B \dfrac V B BV​。

然后…我就莫名其妙的在这个地方卡住了。
我总在尝试枚举保留序列的左右端点，如果合法就拿求出的 $d$ 对中间暴力扫一遍取答案。（这个虽然看起来很难卡，但终究是 n 2 n^2 n2 的，不太懂能不能卡）
但是其实固定左端点之后，只需要往后扫 V B \frac V B BV​ 个，然后其至多对应一个合法的 $d$，再取个众数就完事了。

代码

老规矩，A了就懒得改了。

//luogu
#include
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
using namespace std;const int N=1e5+100;
const int inf=1e9;
inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}int n,k;
int w=100,top;
unordered_map<int,int>mp;
int a[N],ans,op[N];
inline int calc(int l,int r,int d){int res(0);for(int i=l;i<=r;i++){if(a[i]==a[l]+(i-l)*d){op[i]=l;res++;}}return res;
}
signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();int mx=0;for(int i=1;i<=n;i++) a[i]=read(),mx=max(mx,a[i]);ans=min(n,2);for(int d=-w;d<=w;d++){for(int i=1;i<=n;i++){mp[a[i]-i*d]=mp[a[i]-i*d]+1;ans=max(ans,mp[a[i]-i*d]);//if(d==-1) printf("d=%d i=%d val=%d\n",d,i,a[i]-)}mp.clear();}//if(n==100000) return 0;top=(mx+w-1)/w;for(int i=1;i<=n;i++){for(int j=min(n,i+top);j>=i+ans;j--){if(op[j]!=i&&(a[j]-a[i])%(j-i)==0&&abs((a[j]-a[i])/(j-i))>w){//printf("(%d %d)\n",i,j);ans=max(ans,calc(i,j,(a[j]-a[i])/(j-i)));}}}printf("%d\n",n-ans);return 0;
}
/*
10 6 5
1
2
1
3
3
6
3
7
9
7 7 4
10 4 5
8 9 4
7 5 4
2 10 3
10 6 1
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！