CF1548B Integers Have Friends

題意：

給定 n 和一個(gè)長(zhǎng)度為 n 的數(shù)組 a，求一個(gè)最長(zhǎng)的區(qū)間 $\left[l,r\right]$，使得存在 $m\ge 2和k$，對(duì)于所有 $l\le i\le r$,$a_i\equiv k(\mathrm{m}\mathrm{o}\mathrm{d}m)$（即區(qū)間內(nèi)所有數(shù)對(duì) m 取模余數(shù)相等），輸出最長(zhǎng)區(qū)間長(zhǎng)度（區(qū)間長(zhǎng)度定義為 r-l+1）。
有多組測(cè)試數(shù)據(jù)。

題解：

題目問所有數(shù)對(duì)m取模余數(shù)相等，說明對(duì)于所有數(shù)都是$x_i=k_{i}m+w$，那么我們讓相鄰的$x_i$相減，這樣得到$b_i=(k_i?k_{i?1})?m$，也就是說所有的b數(shù)組都是m的倍數(shù)，其gcd為b
那么問題就變成找最長(zhǎng)的子區(qū)間，使得子區(qū)間的gcd>1
gcd是滿足單調(diào)性的，所以我們可以單調(diào)的尋找區(qū)間，如何快速求區(qū)間的gcd，可以用st表

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=2e5+9; ll a[maxn];ll gcd(ll a,ll b){if(b)return gcd(b,a%b);return a; } ll b[maxn];ll lg[maxn]; void init(){lg[0]=-1;for(int i=1;i<=200005;i++){lg[i]=lg[i>>1]+1;} } ll f[maxn][40]; void st(int n){for(int i=1;i<=n;i++)f[i][0]=b[i];for(int k=1;k<=lg[n];k++){for(int i=1;i<=n-(1<<k)+1;i++){f[i][k]=gcd(f[i][k-1],f[i+(1<<(k-1))][k-1]);}} } ll query(int l,int r){int k=lg[r-l+1];return gcd(f[l][k],f[r-(1<<k)+1][k]); } int main() { // rd_test();int t;read(t);init();while(t--){int n;read(n);for(int i=1;i<=n;i++)read(a[i]);if(n==1){cout<<1<<endl;continue;}for(int i=1;i<n;i++){b[i]=abs(a[i+1]-a[i]);}n--;st(n);int ans=0;for(int i=1;i<=n;i++){ // if(b[i]==1)continue;int l=i,r=n;while(l<r){int mid=l+r+1>>1;if(query(i,mid)==1)r=mid-1;else l=mid;}if(query(i,l)!=1)ans=max(ans,l-i+1);}cout<<ans+1<<endl;}//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的CF1548B Integers Have Friends的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。