Phần tử trung vị

Điểm: 0,39 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

NUS ACM Training

Dạng bài

Ngôn ngữ cho phép

C, ~~C++~~, Go, ~~Java~~, ~~Kotlin~~, ~~Pascal~~, ~~PyPy~~, ~~Python~~, ~~Rust~~, ~~Scratch~~

Cho một dãy số ~a_1~, ~a_2~, ..., ~a_{n}~ được sinh ngẫu nhiên như sau:

~a_1 = seed~
~a_{i} =(a_{i-1} \times mul + add)\%65536~

Với

Cho một số ~k \leq n~. Dãy đã cho có ~n-k+1~ dãy con độ dài ~k~. Hãy tính tổng tất cả các phần tử trung vị (phần tử nhỏ thứ ~\frac{k+1}{2}~) của ~n-k+1~ dãy con này).

Input

Dòng đầu tiên chứa số test (không quá ~30~). Mỗi dòng tiếp theo chứa ~5~ số nguyên ~seed, mul, add, n, K~. (~0 \leq seed, mul, add \leq 65535~, ~1 \leq n \leq 250000~, ~1 \leq k \leq 5000, k \leq n~)

Output

Với mỗi test in ra số hiệu test (theo mẫu) cùng với tổng các trung vị tìm được.

Sample Input

5
3 1 1 10 3
10 0 13 5 2
4123 2341 1231 7 3
47 5621 1 125000 1700
32321 46543 32552 17 17

Sample Output

Case #1: 60
Case #2: 49
Case #3: 102186
Case #4: 4040137193
Case #5: 25569

Note

Với test 1, dãy sinh ra là ~3, 4, 5, 6, 7, 8, 9, 10, 11, 12~. Các dãy con là ~(3, 4, 5), \dots, (10, 11, 12)~. Các trung vị là ~4, 5, \dots, 11~.

Bình luận

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

vuonghoaitamdz9 đã bình luận lúc 12, Tháng 10, 2025, 15:19

````

include<bits/stdc++.h>

typedef long long ll; typedef unsigned long long ull;

define str string

define el '\n'

define fi first

define se second

using namespace std; const int N=250000+5; const int mod=65536; ll a[N]; ll seed,mul,add,n,k; int main(){ iosbase::syncwithstdio(0);cin.tie(0);cout.tie(0); int t; cin>>t; for (int p=1;p<=t;p++){ multiset<ll> ms; multiset<ll>::iterator mid; cin>>seed>>mul>>add>>n>>k; a[1]=seed%mod; for (int i=2;i<=n;i++){ a[i]=(a[i-1]*mul+add)%mod; } for (int i=1;i<=k;i++){ ms.insert(a[i]); } mid=ms.begin(); for (int i=0;i<(k-1)/2;i++) mid++; ll res=0; res+=*mid; for (int i=k+1;i<=n;i++){ ll x=a[i],y=a[i-k]; ms.insert(x); if (x<*mid) mid--; if (y<=*mid) mid++; ms.erase(ms.lowerbound(y)); res+=*mid; } cout<<"Case #"<<p<<": "<<res<<el return>
````
</el>

0

vuonghoaitamdz9 đã bình luận lúc 12, Tháng 10, 2025, 15:19 ← chỉnh sửa →

kho

-16
nguyenthihai14121980 đã bình luận lúc 4, Tháng 8, 2024, 15:48
include <bits/stdc++.h>

using namespace std;

typedef long long ll; typedef pair<int,int> ii; typedef unsigned long long ull;

define X first

define Y second

define pb push_back

define mp make_pair

define ep emplace_back

define EL printf("\n")

define sz(A) (int) A.size()

define FOR(i,l,r) for (int i=l;i<=r;i++)

define FOD(i,r,l) for (int i=r;i>=l;i--)

define fillchar(a,x) memset(a, x, sizeof (a))

define faster iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL);

const int N = 300000; const int m = 66000; int T, n, k, a[N], t[m+1]; int mul, add, ord; ll ans;

int get(int x) { int ans = 0; for (; x > 0; x -= x&-x) ans += t[x]; return ans; }

void upd(int x, int v) { for (; x <= m; x += x&-x) t[x] += v; }

int main() { // freopen("INP.TXT", "r", stdin); // freopen("OUT.TXT", "w", stdout);

scanf("%d", &T); FOR(test,1,T) { scanf("%d %d %d %d %d", &a[1], &mul, &add, &n, &k); FOR(i,2,n) a[i] = ((ll) a[i-1] * mul + add) % 65536; FOR(i,1,n) a[i]++; ord = (k+1)/2; ans = 0ll; FOR(i,1,m) t[i] = 0; FOR(i,1,k-1) upd(a[i], 1); FOR(i,k,n) { upd(a[i], 1); int L = 1, R = m, x = 0; while (L <= R) { int mid = (L+R)/2; if (ord <= get(mid)) { x = mid; R = mid-1; } else L = mid+1; } ans += (ll) x; upd(a[i-k+1], -1); } printf("Case #%d: %lld\n", test, ans - (n-k+1)); } return 0;

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