Editorial for Dãy con dài nhất có tổng chia hết cho K
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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
var n,i,k,t,j,p:longint; f:array[0..1,0..51] of longint; begin readln(n,k); fillchar(f,sizeof(f),0); f[0,0]:=1; for i:=1 to n do begin p:=i mod 2; read(t); for j:=0 to k-1 do f[p,j]:=0; for j:=0 to k-1 do if (f[1-p,j]>0) then begin if (f[p,j]<f[1-p,j]) then f[p,j]:=f[1-p,j]; if (f[p,(j+t) mod k]<=f[1-p,j]) then f[p,(j+t) mod k]:=f[1-p,j]+1; end; end; write(f[p,0]-1); end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; typedef long long LL; #define sz(a) (int((a).size())) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 1005 #define KK 55 int f[N][KK], n, k, a[N]; int main() { #ifndef ONLINE_JUDGE freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); #endif LL s = 0; scanf("%d%d",&n,&k); fo(i,1,n) { scanf("%d",a+i); s = (s+a[i])%k; } //f[i][j], chon ra it nhat f[i][j] phan tu trong doan a[1..i] de co tong chia k du i f[0][0] = 0; fo(i,1,k-1) f[0][i] = INF; fo(i,1,n) rep(j,k) f[i][j] = min(f[i-1][j], f[i-1][((j-a[i])%k+k)%k]+1); printf("%d\n", n-f[n][s%k]); return 0; }
Code mẫu của ladpro98
program qbseq; uses math; const fi=''; var f:array[0..1001,0..51] of longint; a:array[1..1000] of longint; inp:text; n,i,k:longint; check:array[0..1001,0..51] of boolean; procedure input; var i:longint; begin assign(inp,fi); reset(inp); readln(inp,n,k); for i:=1 to n do read(inp,a[i]); close(inp); end; function qhd(i,t:longint):longint; begin if check[i,t] then exit(f[i,t]); f[i,t]:=max(qhd(i-1,t),1+qhd(i-1,(t+k-(a[i] mod k)) mod k)); check[i,t]:=true; exit(f[i,t]); end; begin input; f[0,0]:=0; check[0,0]:=true; for i:=1 to k-1 do begin f[0,i]:=low(integer); check[0,i]:=true; end; write(qhd(n,0)); end.
Code mẫu của RR
uses math; var a:array[1..1011] of longint; f:array[1..1011,0..50] of longint; next,n,k,i,j:longint; begin read(n,k); for i:=1 to n do read(a[i]); fillchar(f,sizeof(f),$FF); f[1,0]:=0; f[1,a[1] mod k]:=1; for i:=2 to n do begin for next:=0 to k-1 do f[i,next]:=f[i-1,next]; for j:=0 to k-1 do if f[i-1,j]>=0 then begin next:=(j+a[i]) mod k; f[i,next]:=max(f[i,next],f[i-1,j]+1); end; end; writeln(f[n,0]); end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> main() { int n,k,a[1001],b[1001][51],m,l; long x=0; scanf("%d %d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[i]= a[i]%k ; x+=a[i]; } m=x%k ; if(m==0) printf("%d",n); else { for(int i=0;i<k;i++) b[0][i]=1001; for(int i=1;i<=n;i++) { for(int j=0;j<k;j++) { if(j!=a[i]) { l=j-a[i]; if(l<0) l=l+k; if(b[i-1][l]+1>=b[i-1][j]) b[i][j]=b[i-1][j]; else b[i][j]=b[i-1][l]+1; } else b[i][j]=1; } } printf("%d",n-b[n][m]); } //getch(); }
Code mẫu của ll931110
Program QBSEQ; Const input = ''; output = ''; max = 1000000000; Var a: array[1..1000] of longint; F: array[0..1000,0..1000] of longint; n,k: longint; Procedure enter; Var fi: text; i: longint; Begin Assign(fi, input); Reset(fi); Readln(fi, n, k); For i:= 1 to n do read(fi, a[i]); Close(fi); End; Function sub(x,y: longint): longint; Var tmp: longint; Begin sub:= (x - y) mod k; If sub < 0 then sub:= sub + k; End; Function min(x,y: longint): longint; Begin If x < y then exit(x) else exit(y); End; Procedure optimize; Var i,t: longint; Begin F[0,0]:= 0; For t:= 1 to k - 1 do F[0,t]:= max; For i:= 1 to n do For t:= 0 to k - 1 do F[i,t]:= min(F[i - 1,t], F[i - 1, sub(t, a[i])] + 1); End; Procedure solve; Var fo: text; sum,i: longint; Begin sum:= 0; For i:= 1 to n do sum:= sum + a[i]; Assign(fo, output); Rewrite(fo); Writeln(fo, n - F[n, sum mod k]); Close(fo); End; Begin enter; optimize; solve; End.
Code mẫu của skyvn97
#include<stdio.h> int opt[2000][100]; int a[2000]; int n,k,i,j,s; int f(int x) { if (x>=0) return (x); return (x+k); } int min(int a,int b) { if (a<b) return (a); else return (b); } int main(void) { scanf("%d",&n); scanf("%d",&k); s=0; for (i=1;i<=n;i=i+1) { scanf("%d",&a[i]); a[i]=a[i]%k; s=(s+a[i])%k; } opt[0][0]=0; for (i=1;i<k;i=i+1) opt[0][i]=32000; for (i=1;i<=n;i=i+1) for (j=0;j<k;j=j+1) opt[i][j]=min(opt[i-1][j],opt[i-1][f(j-a[i])]+1); printf("%d",n-opt[n][s%k]); return 0; }
Code mẫu của khuc_tuan
#include <stdio.h> #include <iostream> #include <set> using namespace std; int n, k; int f1[55], f2[55]; int main() { scanf("%d%d", &n, &k); int *f = f1, *q = f2; for(int i=0;i<55;++i) f1[i] = -1000000; f1[0] = 0; for(int i=0;i<n;++i) { int x; scanf("%d", &x); for(int j=0;j<55;++j) q[j] = -1000000; for(int du=0;du<k;++du) q[(du+x)%k] >?= (f[du]+1) >? (f[(du+x)%k]); swap( f, q); } printf("%d\n", f[0]); return 0; }
Comments