Editorial for Đoạn cao trào của bản nhạc


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,re:integer;
    a,b,c:array[1..5000] of integer;

procedure rf;
var i:integer; j,k:integer;
begin
     readln(n);
     for i:=1 to n do
     begin
          if eoln then readln;
          read(a[i]);
     end;
end;

procedure pr;
var i,j,t:integer;
begin
     re:=0;
     for i:=2 to n do
     begin
          fillchar(c,sizeof(c),0);
          for j:=0 to n-1 do
          begin
               t:=i+j;
               if t>n then break;
               b[j+1]:=a[t];
               if (j>0) and (b[j+1]-a[j+1]=b[j]-a[j]) then
               begin
                    c[j+1]:=c[j]+1;
                    if c[j+1]>re then
                    begin
                         re:=c[j+1];
                         if re+1>=i-1 then break;
                    end;
               end;
          end;
     end;
end;


procedure wf;
begin
     if re+1>=5 then write(re+1)
     else write(0);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

program theme;
uses    math;
const   fi='';
        maxN=5001;
var     n,res:longint;

        a:array[1..maxN] of longint;
        f:array[1..maxN,1..maxN] of longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        read(inp,a[i]);
        close(inp);
end;

procedure dp;
var     i,j:longint;
begin
        for j:=1 to n do f[1,j]:=1;
        for i:=2 to n-1 do
        for j:=i+2 to n do
        begin
                if (a[i]-a[i-1])=(a[j]-a[j-1]) then
                begin
                        f[i,j]:=f[i-1,j-1]+1;
                        res:=max(res,min(f[i,j],j-i));
                end
                else
                f[i,j]:=1;
        end;
end;

begin
        input;
        dp;
        if res<5 then res:=0;
        write(res);
end.

Code mẫu của RR

{$R+,Q+}
PROGRAM THEME;
CONST
  FINP='';
  FOUT='';
  maxn=5000;
VAR
  d:array[1..maxn,1..maxn] of integer;
  c:array[1..maxn] of integer;
  n,kq:integer;
procedure readInput;
var
  f:text;
  i:integer;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  for i:=1 to n do
    read(f,c[i]);
  for i:=1 to n-1 do
    c[i]:=c[i+1]-c[i];
  close(f);
end;
procedure writeOutput;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  if kq+1>4 then writeln(f,kq+1)
  else writeln(f,0);
  close(f);
end;
procedure solve;
var
  i,j:integer;
begin
  kq:=0;
  for j:=n-1 downto 1 do
    if c[j]=c[n] then d[n,j]:=1 else d[n,j]:=0;
  for i:=n-1 downto 2 do
    for j:=i-kq-2 downto 1 do
      if c[i]=c[j] then
        begin
          d[i,j]:=d[i+1,j+1]+1;
          if d[i,j]>kq then kq:=d[i,j];
        end
      else d[i,j]:=0;
end;
BEGIN
  readInput;
  solve;
  writeOutput;
END.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

int min(int a,int b)
{
    if(a>b) return b;
    else return a;
}

int main()
{
   // freopen("NKTHEME.inp","r",stdin);
    int n,x,y,a[5001];
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d",&x);
        if(i>=2)
            a[i-1]=x-y;
        y = x;
    }
    int max = 0;
    n--;
    int f[n+1][n+1];
    for(int i =0;i<=n;i++)
        f[0][i]=0;
    for(int i = 1;i<=n-4;i++)
        for(int j = i+4;j<=n;j++)
        {
             if(a[i] == a[j])
             {
                  f[i][j] = min(f[i-1][j-1]+1,j-i-1);
             }
             else f[i][j]=0;
             if(f[i][j]>max)
                  max = f[i][j];
        }
    if(max >= 4) printf("%d",max+1);
    else printf("0");
  //  getch();
}

Code mẫu của khuc_tuan

inline bool leq(int a1, int a2,   int b1, int b2) { // lexic. order for pairs
  return(a1 < b1 || a1 == b1 && a2 <= b2); 
}                                                   // and triples
inline bool leq(int a1, int a2, int a3,   int b1, int b2, int b3) {
  return(a1 < b1 || a1 == b1 && leq(a2,a3, b2,b3)); 
}
// stably sort a[0..n-1] to b[0..n-1] with keys in 0..K from r
static void radixPass(int* a, int* b, int* r, int n, int K) 
{ // count occurrences
  int* c = new int[K + 1];                          // counter array
  for (int i = 0;  i <= K;  i++) c[i] = 0;         // reset counters
  for (int i = 0;  i < n;  i++) c[r[a[i]]]++;    // count occurences
  for (int i = 0, sum = 0;  i <= K;  i++) { // exclusive prefix sums
     int t = c[i];  c[i] = sum;  sum += t;
  }
  for (int i = 0;  i < n;  i++) b[c[r[a[i]]]++] = a[i];      // sort
  delete [] c;
}

// find the suffix array SA of s[0..n-1] in {1..K}^n
// require s[n]=s[n+1]=s[n+2]=0, n>=2
void suffixArray(int* s, int* SA, int n, int K) {
  int n0=(n+2)/3, n1=(n+1)/3, n2=n/3, n02=n0+n2; 
  int* s12  = new int[n02 + 3];  s12[n02]= s12[n02+1]= s12[n02+2]=0; 
  int* SA12 = new int[n02 + 3]; SA12[n02]=SA12[n02+1]=SA12[n02+2]=0;
  int* s0   = new int[n0];
  int* SA0  = new int[n0];

  // generate positions of mod 1 and mod  2 suffixes
  // the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
  for (int i=0, j=0;  i < n+(n0-n1);  i++) if (i%3 != 0) s12[j++] = i;

  // lsb radix sort the mod 1 and mod 2 triples
  radixPass(s12 , SA12, s+2, n02, K);
  radixPass(SA12, s12 , s+1, n02, K);  
  radixPass(s12 , SA12, s  , n02, K);

  // find lexicographic names of triples
  int name = 0, c0 = -1, c1 = -1, c2 = -1;
  for (int i = 0;  i < n02;  i++) {
    if (s[SA12[i]] != c0 || s[SA12[i]+1] != c1 || s[SA12[i]+2] != c2) { 
      name++;  c0 = s[SA12[i]];  c1 = s[SA12[i]+1];  c2 = s[SA12[i]+2];
    }
    if (SA12[i] % 3 == 1) { s12[SA12[i]/3]      = name; } // left half
    else                  { s12[SA12[i]/3 + n0] = name; } // right half
  }

  // recurse if names are not yet unique
  if (name < n02) {
    suffixArray(s12, SA12, n02, name);
    // store unique names in s12 using the suffix array 
    for (int i = 0;  i < n02;  i++) s12[SA12[i]] = i + 1;
  } else // generate the suffix array of s12 directly
    for (int i = 0;  i < n02;  i++) SA12[s12[i] - 1] = i; 

  // stably sort the mod 0 suffixes from SA12 by their first character
  for (int i=0, j=0;  i < n02;  i++) if (SA12[i] < n0) s0[j++] = 3*SA12[i];
  radixPass(s0, SA0, s, n0, K);

  // merge sorted SA0 suffixes and sorted SA12 suffixes
  for (int p=0,  t=n0-n1,  k=0;  k < n;  k++) {
#define GetI() (SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2)
    int i = GetI(); // pos of current offset 12 suffix
    int j = SA0[p]; // pos of current offset 0  suffix
    if (SA12[t] < n0 ? 
        leq(s[i],       s12[SA12[t] + n0], s[j],       s12[j/3]) :
        leq(s[i],s[i+1],s12[SA12[t]-n0+1], s[j],s[j+1],s12[j/3+n0]))
    { // suffix from SA12 is smaller
      SA[k] = i;  t++;
      if (t == n02) { // done --- only SA0 suffixes left
        for (k++;  p < n0;  p++, k++) SA[k] = SA0[p];
      }
    } else { 
      SA[k] = j;  p++; 
      if (p == n0)  { // done --- only SA12 suffixes left
        for (k++;  t < n02;  t++, k++) SA[k] = GetI(); 
      }
    }  
  } 
  delete [] s12; delete [] SA12; delete [] SA0; delete [] s0; 
}

#include "stdio.h"

#define maxn 5050
#define Rep(i,n) for(int i=0,lll=(n);i<lll;++i)
#define For(i,a,n) for(int i=(a),lll=(n);i<=lll;++i)
#define Ford(i,a,n) for(int i=(a),lll=(n);i>=lll;--i)

int a[maxn], n, SA[maxn], lcp[maxn];

void init_lcp() {
    int *inv=new int[maxn];
    int h=0;
    Rep(i,n-1) inv[SA[i]]=i;
    Rep(i,n-1) if(inv[i]>0) {
        int j=SA[inv[i]-1];
        while(a[i+h]==a[j+h]) ++h;
        lcp[inv[i]]=h;
        --h;
        if(h<0) h=0;
    }    
}    

bool testok(int len) {
    for(int i=0;i<n-1;) {
        int j=i+1, mm=100000, MM=-1;
        while((j<n-1) && (lcp[j]>=len-1)) ++j;
        For(k,i,j-1) {
            if(mm>SA[k]) mm=SA[k];
            if(MM<SA[k]) MM=SA[k];
        }    
        if(MM-mm>=len) return true;
        i=j;
    }    
    return false;
}    

int main() {
    scanf("%d",&n);
    Rep(i,n) scanf("%d",a+i);
    Rep(i,n-1) a[i]=a[i+1]-a[i]+90;
    a[n-1]=0;
    suffixArray(a,SA,n-1,200);
    init_lcp();
    int L=4, R=n,mid;
    for(;L<R;mid=(L+R)/2+1, testok(mid) ? (L=mid) : (R=mid-1));
    if(L==4) printf("0\n");
    else printf("%d\n",L);
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.