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.

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

Please read the guidelines before commenting.


There are no comments at the moment.