Hướng dẫn giải của Tổng bộ phận
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
uses math; const fi=''; maxn=100100; var n,z,k,re,num:longint; a:array[0..maxn*2] of longint; b,c,d:array[0..maxn] of longint; procedure rf; var x,i:longint; begin read(n,k,z); re:=z-1; for i:=1 to n do begin read(x); x:=x mod z; if x>=k then re:=min(re,x); a[i]:=(a[i-1]+x) mod z; d[i]:=i; end; end; procedure sort(l,r:longint); var i,j,x,y,t:longint; begin i:=l; j:=r; x:=a[(i+j) shr 1]; y:=d[(j+i) shr 1]; repeat while (a[i]<x) or ((a[i]=x) and (d[i]<y)) do i:=i+1; while (a[j]>x) or ((a[j]=x) and (d[j]>y)) do j:=j-1; if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; t:=d[i]; d[i]:=d[j]; d[j]:=t; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; function bs(val,l:longint):longint; var r,m,i:longint; begin r:=l+num; while l<=r do begin m:=(l+r) shr 1; if a[m]<val then l:=m+1 else r:=m-1; end; for i:=m-1 to m+1 do if (i>=0) and (i<=num*2+1) and (a[i]>=val) then exit(i mod (num+1)); end; procedure pr; var i,x:longint; begin sort(0,n); num:=0; for i:=1 to n do if a[i]>a[num] then begin num:=num+1; a[num]:=a[i]; b[num]:=d[i]; c[num-1]:=d[i-1]; end; c[num]:=d[n]; for i:=0 to num do a[num+1+i]:=a[i]+z; for i:=0 to num do begin x:=bs(a[i]+k,i); while ((a[x]-a[i]+z) mod z<re) do begin if b[i]<c[x] then begin re:=(a[x]-a[i]+z) mod z; break; end; x:=(x+1) mod (num+1); end; if re=k then break; end; writeln(re); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của happyboy99x
#include<cstdio> #include<set> #include<algorithm> using namespace std; void print(set<int> s) { for(set<int>::iterator it = s.begin(); it != s.end(); ++it) printf("%d ", *it); printf("\n"); } int main() { set<int> s; int n, p, k, sum = 0; scanf("%d%d%d", &n, &k, &p); int res = p; for(int i = 0; i < n; ++i) { int x; scanf("%d", &x); sum = (sum + x) % p; set<int>::iterator it = s.upper_bound(((sum - k) % p + p) % p); if(it != s.begin()) res = min(res, ((sum - *(--it)) % p + p) % p); s.insert(sum); } printf("%d\n", res); return 0; }
Code mẫu của RR
uses math; const FINP=''; FOUT=''; MAXN=1000111; var c,ln,a,sum:array[0..MAXN] of int64; best,sl,n,p,k:int64; test:longint; f1,f2:text; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i:longint; begin read(f1,n,k,p); fillchar(a,sizeof(a),0); fillchar(sum,sizeof(sum),0); fillchar(ln,sizeof(ln),0); fillchar(c,sizeof(c),0); for i:=1 to n do read(f1,a[i]); for i:=1 to n do sum[i]:=(sum[i-1]+a[i]) mod p; sum[n+1]:=0; end; procedure swap(var a,b:int64); inline; var temp:int64; begin temp:=a; a:=b; b:=temp; end; var mid:int64; procedure sort(l,r:int64); inline; var i,j:int64; begin mid:=c[l+random(r-l+1)]; i:=l; j:=r; repeat while c[i]<mid do inc(i); while c[j]>mid do dec(j); if i<=j then begin swap(c[i],c[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure init; var i:longint; begin for i:=1 to n+1 do c[i]:=sum[i]; sort(1,n+1); sl:=1; for i:=2 to n+1 do if c[i]>c[sl] then begin inc(sl); c[sl]:=c[i]; end; end; function get(u:int64):int64; inline; var kq,v:int64; begin if u<=0 then exit(0); kq:=ln[u]; v:=u-u and (-u); if v>0 then kq:=max(kq,get(v)); exit(kq); end; procedure update(u,k:int64); inline; var v:int64; begin ln[u]:=max(ln[u],k); v:=u+u and (-u); if v<=sl then update(v,k); end; function find(x:int64):int64; inline; var l,r,kq:int64; begin l:=1; r:=sl; kq:=0; repeat mid:=(l+r)>>1; if c[mid]<=x then begin kq:=mid; l:=mid+1; end else r:=mid-1; until l>r; exit(kq); end; procedure solve; var u,temp:int64; i:longint; begin best:=maxlongint; for i:=1 to n do begin if sum[i]>=k then begin u:=find(sum[i]-k); best:=min(best,sum[i]-get(u)); end; u:=find(sum[i]+p-k); temp:=get(u); if temp>sum[i] then best:=min(best,sum[i]-temp+p); u:=find(sum[i]); update(u,sum[i]); end; end; procedure ans; begin writeln(f2,best); end; begin openF; // readln(f1,test); test:=1; for test:=1 to test do begin inp; init; solve; ans; end; closeF; end.
Code mẫu của hieult
#include <iostream> #include <cstdio> //#include <conio.h> //#include <algorithm> //#include <alloc.h> using namespace std; class Node { public: int info; Node* left; Node* right; Node (int x) { info = x; left = right = NULL; } }; class BSTree { public: Node* root; BSTree() {root=NULL;} bool isEmpty(){return(root==NULL);} void clear(){ root = NULL;} void visit(Node p) { //System.out.println(p.info); }; void setRoot(int x) { root = new Node(x); } int max(int a,int b) { if(a>b) return a; return b; } /* Node search(Node* p,int x) { if( p == NULL || p->info ==x ) return p; if(x<p->info) return search(p->left,x); else return search(p->right,x); } */ int Search(int x) { int k = tim(root,x); return k; } int tim(Node* p,int x) { if(p==NULL) return 0; if(p->info==x) return x; if(x<p->info) return tim(p->left,x); else return max(p->info,tim(p->right,x)); } /* void insert(int x) { Node q = new Node(x); if(isEmpty()){root = q; return;} Node f,p; f= null; p=root; while(p!=null) { {if(p.info==x) {System.out.println(" The key already exists"); return;} f = p; if(x<p.info) p=p.left; else p=p.right; } if(x<f.info) f.left=q; else f.right=q; } } */ void insert(int x) {Node* q = new Node(x); if(isEmpty()) {root=q;return;} Node *f,*p;f=NULL;p=root; while(p!=NULL) {if(p->info==x) {//System.out.println(" The key already exists"); return;} f = p; if(x<p->info) p=p->left; else p=p->right; } if(x<f->info) f->left=q; else f->right=q; } /* void preOrder(Node p) { if(p==null) return; visit(p); preOrder(p.left); preOrder(p.right); } void inOrder(Node p) { if(p==null) return; inOrder(p.left); visit(p); inOrder(p.right); } void postOrder(Node p) {if(p==null) return; postOrder(p.left); postOrder(p.right); visit(p); } void breadthTraverse() { MyQueue q = new MyQueue(); q.enqueue(root); Node p; while(!q.isEmpty()) { p = (Node) q.dequeue(); visit(p); if(p.left!=null) q.enqueue(p.left); if(p.right!=null) q.enqueue(p.right); } } void dele(int x) { Node f,p; f=null; p=root; while(p!=null) { if(p.info == x) break; f=p; if(x<p.info) p=p.left; else p = p.right; } if (p==null){ System.out.println("...");} if(p.left == null && p.right == null) { if(f==null ){root=null;return;} if(f.left==p)f.left=null; else f.right = null; } if(p.left !=null &&p.right==null) { if(f==null ){root=p.left;return;} if(f.left==p)f.left=p.left; else f.right = p.left; } if(p.left ==null &&p.right!=null) { if(f==null ){root=p.right;return;} if(f.left==p)f.left=p.right; else f.right = p.right; } if(p.left !=null &&p.right!=null) { Node rp ,frp; frp = p;rp =p.left; while(rp.right!=null) { frp = rp;rp=rp.right; } p.info = rp.info; frp.right=rp.left; } } void delebyMerging(int x) { Node f,p; f=null; p=root; while(p!=null) { if(p.info == x) break; f=p; if(x<p.info) p=p.left; else p = p.right; } if (p==null){} //System.out.println("...");} if(p.left == null && p.right == null) { if(f==null ){root=null;return;} if(f.left==p)f.left=null; else f.right = null; } if(p.left !=null &&p.right==null) { if(f==null ){root=p.left;return;} if(f.left==p)f.left=p.left; else f.right = p.left; } if(p.left ==null &&p.right!=null) { if(f==null ){root=p.right;return;} if(f.left==p)f.left=p.right; else f.right = p.right; } if(p.left !=null &&p.right!=null) { Node q=p.right; p.right=null; Node lp = p.left; if(f.left==p) f.left = lp; else f.right=lp; Node rp ; rp = lp; rp =p.left; while(rp.right!=null) { rp=rp.right; } rp.right=q; } } void addMany(int [] a) { for(int i=0;i<a.length;i++) insert(a[i]); } */ }; int main() { //freopen("VPARTSUM.in","r",stdin); int n,k,p,a; int tong = 0; BSTree t; scanf("%d %d %d",&n,&k,&p); int KQ = p; for(int i = 1;i<=n;i++) { scanf("%d",&a); tong = (tong + a)%p; int x = tong-k,y; if(x<0) x+=p; y = t.Search(x); //(tong+" "+x+" "+y); y = tong - y; if(y<0) y+=p; if(y<KQ) KQ = y; t.insert(tong); } printf("%d",KQ); //getch(); }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <iterator> #include <map> #include <queue> #include <set> #include <sstream> #include <string> #include <vector> #define INF 2000000001 typedef long long ll; using namespace std; set<int> s; int n,k,p; int a[100010]; int main() { // freopen("part.in","r",stdin); // freopen("part.ou","w",stdout); scanf("%d %d %d", &n, &k, &p); for (int i = 0; i < n; i++) scanf("%d", &a[i]); int ret = INF; s.insert(-1); s.insert(INF); s.insert(0); int sum = 0; for (int i = 0; i < n; i++) { set<int>::iterator iter; sum = (sum + a[i]) % p; if (sum >= k) { iter = s.upper_bound(sum - k); iter--; if (*iter != -1) ret = min(ret,sum - *iter); }; iter = s.upper_bound(sum + p - k); iter--; if (*iter >= sum) ret = min(ret,sum + p - *iter); s.insert(sum); }; printf("%d\n", ret); };
Code mẫu của skyvn97
#include<stdio.h> #include<set> #define MAX 100100 using namespace std; typedef set<int> si; si st; int a[MAX]; int s[MAX]; int n,k,p; void init(void) { scanf("%d",&n); scanf("%d",&k); scanf("%d",&p); int i; s[0]=0; for (i=1;i<=n;i=i+1) { scanf("%d",&a[i]); s[i]=(s[i-1]+a[i])%p; } k=k%p; } void process(void) { int b=p; int i,t; si::iterator it; for (i=n-1;i>=1;i=i-1) { if (st.find(s[i+1])==st.end()) st.insert(s[i+1]); it=st.end(); it--; if (*it>=s[i]+k) { t=*(st.lower_bound(s[i]+k)); if (t-s[i]<b) b=t-s[i]; } if (*it>=s[i]+k-p) { t=*(st.lower_bound(s[i]+k-p)); if (t-s[i]+p<b) b=t-s[i]+p; } } printf("%d",b); } int main(void) { init(); process(); return 0; }
Code mẫu của khuc_tuan
#include <cstdio> #include <set> using namespace std; int n, k, p, x; int sum[100010]; int main() { scanf("%d%d%d",&n,&k,&p); for(int i=1;i<=n;++i) { scanf("%d",&x); sum[i] = (sum[i-1] + x) % p; } set<int> se; se.insert(0); int res = p+1; for(int i=1;i<=n;++i) { set<int>::iterator si = se.lower_bound((sum[i]-k+1+p) % p); if(si!=se.begin()) --si; else { si = se.end(); --si; } if((sum[i]-*si+p)%p>=k) res <?= (sum[i]-*si+p)%p; se.insert(sum[i]); } printf("%d\n",res); return 0; }
Bình luận