Dãy Cấp Số Cộng - VNOJ: VNOI Online Judge

Trang chủ » Cấp Số Cộng Python » Dãy Cấp Số Cộng - VNOJ: VNOI Online Judge

Có thể bạn quan tâm

VI EN Đăng nhập hoặc Đăng ký

Dãy cấp số cộng

Xem dạng PDF Gửi bài giải Danh sách bài nộp Bài nộp tốt nhất Điểm: 1,33 (OI) Giới hạn thời gian: 0.9s Giới hạn bộ nhớ: 512M Input: stdin Output: stdout Nguồn bài: Sưu tầm Dạng bài Ad hoc (không thuộc thể loại nào), Range Minimum Query Ngôn ngữ cho phép C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Một dãy cấp số cộng là một dãy số mà 2 cặp phần tử liên tiếp bất kỳ có hiệu bằng nhau và khác 0. Trường hợp dãy số chỉ gồm 2 số khác nhau vẫn tính là một dãy cấp số cộng

Ví dụ:

  • 2, 5 là dãy cấp số cộng.
  • 8, 3 là dãy cấp số cộng.
  • 1, 2, 3, 4, 5 là dãy cấp số cộng.
  • 11, 8, 5, 2 là dãy cấp số cộng.
  • 1, 2, 4, 5, 7 không phải là dãy cấp số cộng.

Cho một dãy số A gồm N số nguyên dương. Cho Q truy vấn dạng (x, y). Mỗi truy vấn yêu cầu kiểm tra xem đoạn từ x tới y có phải là hoán vị của một dãy cấp số cộng không.

Input

  • Dòng đầu chứa 2 số nguyên ~N~, ~Q~.
  • Số thứ ~i~ trong ~N~ số ở dòng thứ 2 là ~A_{i}~.
  • Dòng thứ ~i~ trong ~Q~ dòng tiếp theo chứa 2 số nguyên ~x~, ~y~ mô tả truy vấn thứ ~i~.

Output

Gồm ~Q~ dòng.

  • Dòng thứ ~i~ trong ~Q~ dòng sẽ trả lời cho truy vấn thứ ~i~.
  • In ra YES nếu đoạn từ ~x~ tới ~y~ là hoán vị của một dãy cấp số cộng. Ngược lại thì ghi ra NO.

Giới hạn

11 test có ~N~, ~Q \le 1000~.

10 test có ~N \le 1000~, ~Q \le 10^{6}~.

10 test có ~N \le 10^{5}~, ~Q \le 10^{5}~.

~A_{i} \le 10^{9}~

Sample Input

5 2 1 3 2 5 4 1 5 2 4

Sample Output

YES NO

Bình luận

Hãy đọc nội quy trước khi bình luận.
  • 4 thieen đã bình luận lúc 1, Tháng 11, 2025, 14:55

    helo

  • 35 RussVN123 đã bình luận lúc 15, Tháng 6, 2024, 17:28 ← chỉnh sửa →

    Spoil cho bài này

    Để làm bài này thì cần xét các yếu tố sau 1.tổng đoạn L-R phải bằng cấp số cộng r-l+1 phần tử với u1=minL-R và u2=maxL-R 2.Các phần tử chỉ xuất hiện đúng 1 lần duy nhất -> để làm thì chỉ cần tạo mảng b là vị trí gần nhất bên trái có giá trị = a[i] . Lấy max L-R mảng b thì nếu lớn hơn bằng l thì sẽ có trùng . cuối cùng.(a[i]-minLR)%công sai =0 (l<=i<=r). Nghĩa là kiểm tra mỗi a[i] có thể được tạo thành từ minLR không , vì các số tạo thành cấp số cộng phải bằng minLR + d*x. Để kiểm tra cái trên ta cần phân tích tiếp: (a[i]-minLR) % công sai =0 => a[i]%công sai =minLR % công sai. Ta có thể kiểm tra bằng cách lấy đại 1 số trong đoạn L R và check ( đây là đk thứ 1 ). Nhưng mà 1 số đúng thì ko có nghĩa cả dãy đúng. Nên ta cần kiểm tra nhanh các số còn lại ( gọi công sai là d) : a[i]%d=a[i+1]%d=a[i+2]%d=...=a[i+n]%d. Tiếp tục biến đổi thì a[i]%d=a[i+1]%d => (a[i]-a[i+1])%d =0 ( tương tự là cặp a[i+1] và a[i+2]). Như vậy cần check xem các abs(a[i]-a[i+1])có chia hết d hay không và cần kiểm r-l cặp có i trong khoảng L->R-1. Để kiểm nhanh thì chỉ cần lấy GCD là được vì nếu có thỏa hết thì các abs sẽ luôn là bội của d .

    • -5 imdabetbaby đã bình luận lúc 29, Tháng 12, 2024, 16:32 ← sửa 3 →

      .

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

    • -10 englishthaonguyendethuong đã bình luận lúc 6, Tháng 10, 2024, 15:21

      bạn cho mình xin link facebook đc không ạ

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

      • 3 RussVN123 đã bình luận lúc 7, Tháng 10, 2024, 8:38

        Code mình đây, nếu bạn muốn tham khảo:

        include <bits/stdc++.h>

        using namespace std; const int maxn=1e5+1; int n,q,x,y,pospre[maxn]; long long pre[maxn],a[maxn],pregcd[maxn],pow2[21],rgcd[maxn][21],rmin[maxn][21],rmax[maxn][21],check[maxn][21]; long long get(int l,int r,int type,long long rmq[][21]) { long long res; if (type==0) res=0; if (type==1) res=1e10; int k = log2(r-l+1); if (type==0) res=max(rmq[l+pow2[k]-1][k],rmq[r][k]); if (type==1) res=min(rmq[l+pow2[k]-1][k],rmq[r][k]); if (type==2) res=gcd(rmq[l+pow2[k]-1][k],rmq[r][k]); return res; } int main() { iosbase::syncwithstdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>q; map<int,int> mp; pre[0]=0; pow2[0]=1; pregcd[n]=1; rgcd[n][0]=1; for (int i=1;i<=20;++i) pow2[i]=pow2[i-1]2; for (int i=1;i<=n;++i) cin>>a[i]; for (int i=1;i<=n;++i) { pospre[i]=mp[a[i]]; pre[i]=pre[i-1]+a[i]; if (i<n) pregcd[i]=abs(a[i]-a[i+1]); rmin[i][0]=a[i]; rmax[i][0]=a[i]; check[i][0]=pospre[i]; rgcd[i][0]=pregcd[i]; mp[a[i]]=i; } for (int k=1;k<=18;++k) for (int i=1;i<=n;++i) if (i-pow2[k]>=0) { rmin[i][k]=min(rmin[i][k-1],rmin[i-pow2[k-1]][k-1]); rmax[i][k]=max(rmax[i][k-1],rmax[i-pow2[k-1]][k-1]); check[i][k]=max(check[i][k-1],check[i-pow2[k-1]][k-1]); rgcd[i][k]=gcd(rgcd[i][k-1],rgcd[i-pow2[k-1]][k-1]); } for (int i=1;i<=q;++i) { int l,r; long long val,ds,f1,f2; long double d,tong,minv,maxv; cin>>x>>y; l=x; r=y; f1 =get(l,r,1,rmin); f2 =get(l,r,0,rmax); minv = static_cast<long double>(f1); maxv = static_cast<long double>(f2); tong=(r-l+1)(minv+maxv)/2.0; d=(maxv-minv)/(r-l); if (d==0 || r-l+1<2 ) { cout<<"NO\n"; continue; } if (get(l,r,0,check)>=l) { cout<<"NO\n"; continue; } if (tong!=pre[r]-pre[l-1]) { cout<<"NO\n"; continue; } ds = (f2-f1)/(r-l); if (ds!=d) { cout<<"NO\n"; continue ;} // dk : A i (l<=i<=r) %d==minv%d val=f1%ds; // check a i %d == a i+1 %d hay khong -> a i - a i+1 % d==0 if (get(l,r-1,2,rgcd)%ds!=0) { cout<<"NO\n"; continue ;} // check 1 so bat ky trong doan l r co a i %d = minv % d hay khong if (a[r]%ds!=val) { cout<<"NO\n"; continue ;} cout<<"YES\n"; } return 0; }

    • -8 englishthaonguyendethuong đã bình luận lúc 6, Tháng 10, 2024, 5:54 ← chỉnh sửa →

      gdfgdgdfgdg

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

      • 2 RussVN123 đã bình luận lúc 7, Tháng 10, 2024, 8:35

        Bạn xem điều kiện 1 á bạn, tổng trên là 2+5+8+14+17, còn tổng cấp số cộng với u1=2 và un=17 thì là 2+5+8+11+14+17

  • -12 chithien19112008 đã bình luận lúc 17, Tháng 2, 2024, 9:27 ← chỉnh sửa →

    segmentree co ban

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -5 wipad0310 đã bình luận lúc 2, Tháng 2, 2024, 17:23

    Bài này làm được bằng segment tree không vậy mọi người :> Ý tưởng của mình là tìm giá trị lớn nhất và lớn nhất của đoạn cần truy vấn, sau đó tính tổng bằng công thức cấp số cộng và tổng của đoạn đó (mảng cộng dồn). Tất nhiên là mình vẫn chưa làm được :(

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

    • 0 RussVN123 đã bình luận lúc 15, Tháng 6, 2024, 17:31 ← chỉnh sửa →

      Được bạn ạ. Bạn có thể xem sol của mình bên trên.

  • -36 chunguyen2k8 đã bình luận lúc 1, Tháng 2, 2024, 1:53

    Ae downvote mk đi :))

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

    • -5 yuriFiona_ đã bình luận lúc 1, Tháng 2, 2024, 2:25 ← chỉnh sửa →

      anh nguyen ton noi chi phai

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -13 Winboy423minhkhoi đã bình luận lúc 23, Tháng 7, 2023, 2:16

    oh god, dính bug 2 test, fix mất 15 phút cuộc đời

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

    • -4 dawacola đã bình luận lúc 1, Tháng 3, 2024, 11:12

      Bài này làm như nào vậy bạn

  • -23 tuanminhdt đã bình luận lúc 29, Tháng 6, 2023, 3:51 ← chỉnh sửa →

    *đã xóa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

  • -99 nthquan_1505 đã bình luận lúc 27, Tháng 3, 2023, 2:51

    Bài dễ vl

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

Từ khóa » Cấp Số Cộng Python