Archives for Tháng Sáu 2016


REFORM – SPOJ

15/06/2016 by 2 Comments

Đề bài:

Thuật toán:

    Đề trên SPOJ bị thiếu, bài này có giới hạn n<=10^5, m<=2*10^5.

    Ta có thể phát biểu bài toán dưới dạng đồ thị như sau:

    Cho Một đồ thị vô hướng với n đỉnh và m cạnh, mục tiêu của ta là đếm số
    cách khác nhau để thực hiện 2 bước sau:

    • Loại bỏ một cạnh trong m cạnh của đồ thị
    • Thêm một cạnh mới vào đồ thị (cạnh này phải khác m cạnh lúc đầu) sao cho
      đồ thị mới đảm bảo tính liên thông.

    Ta có nhận xét là do chỉ có thể thêm một cạnh vào đồ thị, do đó số lượng
    thành phần liên thông của đồ thị chỉ có thể tối đa là 2. Ta sẽ chia bài
    toán làm 2 trường hợp: Đồ thị gồm 1 thành phần liên thông và đồ thị gồm
    2 thành phần liên thông.

    Trường hợp thứ nhất – trường hợp đơn giản hơn: Đồ thị gồm 2 thành phần liên thông

    Giả sử 2 thành phần liên thông của đồ thị có số đỉnh lần lượt là C1 và C2
    (tất nhiên C1 = n – C2). Do đồ thị có 2 thành phần liên thông, cạnh ta
    thêm vào phải là cạnh từ thành phần liên thông này sang thành phần liên
    thông kia, có nghĩa là có C1 * C2 cách thêm cạnh, và các cạnh này chắc
    chắn khác với m cạnh lúc đầu. Tuy nhiên ta có thêm nhận xét là cạnh bị
    loại đi không được phép là cầu. Từ đó, giả sử số cầu của đồ thị là c,
    kết quả của ta là (m-c) * C1 * C2.

    Trường hợp thứ hai: Đồ thị có duy nhất một thành phần liên thông

    Cố định cạnh bỏ đi (xét từng cạnh trong m cạnh của đồ t), ta sẽ chia bài
    toán làm 2 trường hợp:

    Trường hợp đầu tiên: cạnh bỏ đi không phải là cầu, khi đó đồ thị vẫn tiếp
    tục liên thông. Tức là ta có thể thêm bất cứ cạnh nào miễn sau cạnh đó khác
    m cạnh lúc đầu là được, như vậy lúc này ta có n(n-1) / 2 – m cách thêm
    cạnh mới.

    Trường hợp thứ hai: cạnh bỏ đi là cầu, khi đó đồ thị sẽ bị chia làm 2 thành
    phần liên thông, và cạnh thêm vào chắc chắn phải nối một đỉnh từ thành phần
    liên thông này sang đỉnh thuộc thành phần liên thông kia (để đảm bảo tính
    chất liên thông của đồ thị). Gọi C1 và C2 là số lượng đỉnh trong 2 thành
    phần liên thông sau khi bỏ đi cạnh đang xét, ta sẽ có C1 * C2 – 1 cách thêm
    cạnh mới vào (-1 do trong C1 * C2 cạnh thì có một cạnh trùng với cạnh vừa bỏ
    đi).

    Lấy tổng số cách trong các trường hợp, ta thu được kết quả của bài toán.

    Độ phức tạp: O(m + n)

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
 
int n, m;
bool a[50][50];
typedef pair<int, int> ii;
vector< ii > s1, s2;
int dem;
bool Free[50];
 
inline void duyet(int u)
{
    //cout<<u<<endl;
    dem++;
    Free[u] = 0;
    FORE(v, 1, n) if (u != v && a[u][v] && Free[v] > 0){
        duyet(v);
    }
}
 
vector< int > adj[MAXN];
int Low[MAXN], Num[MAXN], Count = 0, Pa[MAXN], C[MAXN];
 
inline void dfs(int u)
{
    Count++;
    Num[u] = Count;
    Low[u] = n + 1;
    C[u] = 1;
    FOR(i, 0, adj[u].size()){
        int v = adj[u][i];
        if (Pa[v] == 0){
            Pa[v] = u;
            dfs(v);
            C[u] += C[v];
            Low[u] = min(Low[u], Low[v]);
        } else
            if (Pa[u] != v) Low[u] = min(Low[u], Num[v]);
    }
}
 
long long sd[3];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("REFORM.inp", "r", stdin);
    freopen("REFORM.out", "w", stdout);
    #endif //yeulaptrinh.pw
    cin >> n >> m;
 
    if (n <= 20){
        FORE(i, 1, m){
            int x, y;
            cin >> x >> y;
            a[x][y] = 1;
            a[y][x] = 1;
        }
        long long ans = 0;
        FORE(x, 1, n) FORE(y, x + 1, n) if (a[x][y] == 1){
            s2.push_back(ii(x, y));
        } else s1.push_back(ii(x, y));
        FOR(i, 0, s1.size())
        FOR(j, 0, s2.size()){
            int u1 = s1[i].first, v1 = s1[i].second;
            int u2 = s2[j].first, v2 = s2[j].second;
            a[u1][v1] = 1; a[v1][u1] = 1;
            a[u2][v2] = 0; a[v2][u2] = 0;
            memset(Free, 1, sizeof(Free));
            dem = 0;
           // cout<<u1<<" "<<v1<<" "<<u2<<" "<<v2<<endl;
 
            duyet(1);
            if (dem == n) ans++;
            a[u1][v1] = 0; a[v1][u1] = 0;
            a[u2][v2] = 1; a[v2][u2] = 1;
        }
        cout << ans << endl;
    }
    else
 
    {
        int u, v;
        FORE(i, 1, m){
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int dlt = 0;
        FORE(u, 1, n) if (Pa[u] == 0){
            Pa[u] = -1;
            Count = 0;
            dfs(u);
            dlt++;
            sd[dlt] = Count;
        }
        //cout<<dlt<<"??"<<endl;
        if (dlt > 2){
            cout << 0 << endl;
            return 0;
        }
 
        //FORE(u, 1, n) cout << C[u]<<" ";cout<<endl;
            long long ans = 0, Cau = 0, SZ = 1LL * n * (n - 1) / 2;
            FORE(v, 1, n){
                u = Pa[v];
                if (u == -1 || Low[v] < Num[v]) continue;
                ans += 1LL * C[v] * (n - C[v]) - 1;
                Cau++;
            }
            //cout << Cau<<"??"<<ans<<endl;
            if (dlt == 1){
                ans += 1LL * (m - Cau) * (SZ - m);
                cout << ans;
            } else{
                long long ans = 1LL * sd[1] * sd[2] * (m - Cau);
                cout << ans;
            }
 
    }
    return 0;
}
const   fi='';
        nmax=1000000;
        mmax=400000;
 
type    data=longint;
var
        f:text;
        adj,x,y:array[0..mmax+1] of data;
        head:array[0..nmax+1] of data;
        sl:array[0..nmax+1] of int64;
        low,num,tr:array[0..nmax+1] of data;
        n,m,dinh,lab,sl1,res,khop,cau:int64;
 
procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        read(f,n,m);
        for i:=0 to n+1 do
                head[i]:=0;
        for i:=1 to m do
                begin
                        read(f,x[i],y[i]);
                        inc(head[x[i]]);
                        inc(head[y[i]]);
                end;
        for i:=1 to n+1 do
                head[i]:=head[i-1]+head[i];
        for i:=1 to m do
                begin
                        adj[head[x[i]]]:=y[i];
                        dec(head[x[i]]);
                        adj[head[y[i]]]:=x[i];
                        dec(head[y[i]]);
                end;
        close(f);
 
 
end;
 
function min(a,b:data):data;
begin
        if a<b then exit(a); exit(b);
end;
 
procedure dfs(u:data);
var     v,k,i:data;
        s:boolean;
begin
        inc(lab);
        low[u]:=lab;
        num[u]:=lab;
        k:=0;
        sl[u]:=1;
        s:=false;
        for v:=head[u]+1 to head[u+1] do
                if tr[u]<>adj[v] then
                        begin
                                if num[adj[v]]=0 then
                                        begin
                                                tr[adj[v]]:=u;
                                                inc(k);
                                                dfs(adj[v]);
                                                if low[adj[v]]>=num[u] then
                                                        s:=true;
                                                sl[u]:=sl[adj[v]]+sl[u];
                                                low[u]:=min(low[u],low[adj[v]]);
                                        end
                                else
                                        low[u]:=min(low[u],num[adj[v]]);
                        end;
        if ((s and (tr[u]<>0)) or ((tr[u]=0) and (k>1))) then inc(khop);
        if (Low[u]=num[u]) and (tr[u]<>0) then inc(cau);
end;
 
procedure ddfs(u:data);
var
        v:data;
begin
        inc(dinh);
        num[u]:=1;
        for v:=head[u]+1 to head[u+1] do
                if num[adj[v]]=0 then
                        ddfs(adj[v]);
end;
 
procedure xuli;
var     i,j:data;
        stplt:int64;
begin
        for i:=1 to n do
                num[i]:=0;
        stplt:=0;
        sl1:=0;
        for i:=1 to n do
                if num[i]=0 then
                        begin
                                dinh:=0;
                                ddfs(i);
                                if sl1=0 then
                                        sl1:=dinh;
                                inc(stplt);
                        end;
        if stplt>2 then
                begin
                        writeln('0');
                        exit;
                end;
        for i:=1 to n do
                num[i]:=0;
        tr:=num;
 
        cau:=0;
        khop:=0;
        lab:=0;
        for i:=1 to n do
                if num[i]=0 then
                        dfs(i);
        if stplt=1 then
                begin
                        res:=(m-cau)*((n*(n-1)) div 2 - m);
                        for i:=2 to n do
                                if low[i]=num[i] then
                                        res:=res+int64(sl[i])*(int64(n-sl[i]))-1;
                        writeln(res);
                        exit;
                end;
        if stplt=2 then
                begin
                        res:=(m-cau)*sl1*(n-sl1);
                        writeln(res);
                end;
end;
 
begin
        docfile;
        xuli;
end.
Chủ đề: DFS Mức độ: ,

BESTSPOT – SPOJ

15/06/2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/BESTSPOT/

Thuật toán:

  • (đang cập nhập)

Code:

{$MODE OBJFPC}
Const
        fi      ='';
        fo      ='';
        maxn    =10000;
        maxm    =100000;
        maxw    =1000000000;
 
Type
        Arr1    =array[0..maxn] of longint;
        Arr2    =array[0..2*maxm] of longint;
        tHeap   =record
          val   :Arr1;
          pos   :Arr1;
          nheap :longint;
        end;
 
Var
        n,m,x   :longint;
        p       :Arr1;
        d       :Arr1;
        head    :arr1;
        link,adj:arr2;
        t       :arr2;
        heap    :theap;
        kq      :longint;
        best    :longint;
        dm      :longint;
        f       :text;
 
Procedure ae(u,v,w:longint);
begin
        inc(dm);
        adj[dm]:=v;
        t[dm]:=w;
        link[dm]:=head[u];
        head[u]:=dm;
end;
 
Procedure Nhap;
var
        i,u,v,w :longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,n,x,m);
        dm:=0;
        best:=maxlongint;
        for i:=1 to n do head[i]:=0;
        for i:=1 to x do readln(f,p[i]);
        for i:=1 to m do
          begin
            readln(f,u,v,w);
            ae(u,v,w);
            ae(v,u,w);
          end;
        close(f);
end;
 
Procedure InitHeap(s:longint);inline;
var
        i       :longint;
begin
        With Heap do
          begin
            nheap:=1;
            for i:=1 to n do
              begin
                pos[i]:=0;
                d[i]:=maxw;
              end;
            val[1]:=s;
            pos[s]:=1;
            d[s]:=0;
          end;
end;
 
Function getmin:longint;inline;
var
        v       :longint;
        cha,con :longint;
begin
        With Heap do
          begin
            if nheap=0 then exit(0);
            GetMin:=val[1];
            v:=val[nheap];
            cha:=1;
            dec(nheap);
            repeat
              con:=2*cha;
              if (con<nheap) and (d[val[con]]>d[val[con+1]]) then inc(con);
              if (con>nheap) or (d[val[con]]>=d[v]) then break;
              val[cha]:=val[con];
              pos[val[con]]:=cha;
              cha:=con;
            until false;
            val[cha]:=v;
            pos[v]:=cha;
          end;
end;
 
Procedure Update(v:longint);inline;
var
        cha,con :longint;
begin
        With Heap do
          begin
            con:=pos[v];
            if con=0 then
              begin
                inc(nheap);
                con:=nheap;
              end;
            repeat
              cha:=con div 2;
              if (cha=0) or (d[val[cha]]<=d[v]) then break;
              val[con]:=val[cha];
              pos[val[cha]]:=con;
              con:=cha;
            until false;
            val[con]:=v;
            pos[v]:=con;
          end;
end;
 
Procedure Dijkstra(s:longint);
var
        i,u,v   :longint;
        ss      :longint;
begin
        InitHeap(s);
        repeat
          u:=getmin;
          if u=0 then break;
          i:=head[u];
          while i<>0 do
            begin
              v:=adj[i];
              if d[v]>d[u]+t[i] then
                begin
                  d[v]:=d[u]+t[i];
                  update(v);
                end;
              i:=link[i];
            end;
        until false;
        ss:=0;
        for i:=1 to x do 
          if d[p[i]]=maxw then exit
            else ss:=ss+d[p[i]];
        if (ss<best) or ((ss=best) and (kq>s)) then
          begin
            best:=ss;
            kq:=s;
          end;
end;
 
Procedure Sol;
var
        i       :longint;
begin
        For i:=1 to n do Dijkstra(i);
end;
 
Procedure Xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,kq);
        close(f);
end;
 
begin
        Nhap;
        sol;
        xuat;
end.
Chủ đề: SPOJ

V8SCORE – SPOJ

15/06/2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/V8SCORE/

Thuật toán:

  • (đang cập nhập)

Code:

const   fi='';
        fo='';
        oo=20;
var     i,j,tmp2:longint;
        s,k,n,tong,ss,tmp:longint;
        a:array[1..oo,1..oo] of longint;
        c:array[0..200] of boolean;
        trace:array[0..oo] of longint;
        f:text;
        tim:boolean;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,s,k,n);
    for i:=1 to n do
        for j:=1 to k do read(f,a[i,j]);
    close(f);
end;
function max2(x,y:integer):integer;
begin
    if x>y then max2:=x else max2:=y;
end;
procedure init;
begin
    for i:=1 to n do c[a[i,k]]:=true;
end;
procedure thu(x,y,tong:integer);
var     j,ss:integer;
begin
if not(tim) then
 if y<k then
 begin
   if a[x,y]>=trace[y-1] then
   begin
        tmp:=tong+(k-y+1)*a[x,y];
        if tmp<=s then
                begin
                        tong:=tong+a[x,y];
                        trace[y]:=a[x,y];
                        for j:=1 to n do thu(j,y+1,tong);
                end;
   end;
 end else
        begin
        if (c[s-tong]) and (s-tong>=trace[k-1]) then
                begin
                trace[k]:=s-tong;
                tim:=true;
                end;
        end;
end;
procedure xuly;
begin
    trace[0]:=-1;
    for i:=1 to n do
    begin
        if tim then exit else
        begin
                fillchar(trace,sizeof(trace),0);
                thu(i,1,0);
        end;
    end;
end;
procedure inkq;
begin
    assign(f,fo);
    rewrite(f);
    if tim then
    begin
        writeln(f,'YES');
        for i:=1 to k do write(f,trace[i],' ');
    end
        else writeln(f,'NO');
    close(f);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.
Chủ đề: Đệ quy, SPOJ

QBMARKET – SPOJ

15/06/2016 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/QBMARKET/

Thuật toán:

Gọi  L[j] là số cách mua hàng khi có j đồng .Như vậy khi ta có khi ta mua các mặt hàng từ (1..i-1) hết j đồng và số cách mua là L[j] thì khi xét đến mặt hàng thứ i với k là số lượng mặt hàng i mà ta sẽ mua thì số cách mua hết j+c[i]*k ( S) đồng sẽ tăng thêm một lượng L[j]. Ta có công thức quy hoạch động :

Nếu j+c[i]*k<=S thì L[j+c[i]*k]:=L[j+c[i]*k]+L[j] (j=S..1,i=1..n,k=1..mi). Khởi tạo L[0]=1, L[1..S]=0.

Tại sao vì j+c[i]*k<=S vì nếu lớn hơn S rồi ta không cần quan tâm vì ta chỉ có tối đa S đồng thôi.

Trong qua trình cài đặt ta thấy nếu ta duyệt nếu ta duyệt j tăng dần từ 1 đến S, k tăng dần từ 1 đến mi thì sẽ xảy ra trường hợp như sau:j=0,L[0]=1,i=1,c[1]=1. Đầu tiên k=1 thì L[0+1*1]=L[0]+L[2]=1, k=2 thì L[0+1*2]=L[0]+L[2]=1.
Tăng  j và i giữ nguyên, j=1.Đầu tiên k=1 thì L[1+1*1]=L[1]+L[1]=2 đến đây ta đã thấy vô lí L[2] với i=1 không thể nào bằng 2 được mà L[2]=1. Trường hợp này là do khi j=j1 ta tính L[j1+x], j tăng lên j1+x ta tính L[j1+x+y] ta có

L[j1+x+y]=L[j1+x+y]+L[j1+x] mà khi đó L[j1+x] không còn là số cách mua hết j1+x đồng từ i-1 mặt hàng (1..i-1) mà là mua i mặt hàng (1..i) vì ta vừa tính L[j1+x] khi mua k mặt hàng i mà c[i]*k=x, tất nhiên k>=1.Nói ngắn gọn bạn phải hiểu L[j] trong công thức trên là số cách mua hết j đồng từ i-1 mặt hàng (1..i-1)

Để khắc phục tình trạng này ta duyệt j giảm từ S về 0 .

Code bên dưới nộp sẽ được 85 điểm do chạy quá thời gian. Nếu bài cho time limit 1s thì sẽ được 100 điểm. Tất nhiên thuật toán trên hoàn toàn đúng.

Code:

Const
        fi='';
        fo='';
        maxn=500;
        maxs=100000;
 
Type
        arr1    =array[1..maxn] of longint;
        arr2    =array[0..maxs] of int64;
 
Var
        n,s     :longint;
        c,m     :arr1;
        L       :arr2;
        f       :text;
 
procedure nhap;
var
        i       :longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,s,n);
        for i:=1 to n do readln(f,c[i],m[i]);
        close(f);
end;
 
procedure solution;
var
        i,j,k   :longint;
begin
        L[0]:=1; {Neu co 0 dong thi coi la co mot cach la khong mua gi ca}
        for j:=1 to s do L[j]:=0; { Khoi tao mang L }
        for i:=1 to n do
                for j:=s downto 0 do
                        if L[j]>0 then
                        	for k:=1 to m[i] do
                                if j+k*c[i]<=s then
                                        L[j+c[i]*k]:=L[j]+L[j+c[i]*k];
end;
 
procedure xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,L[s]); {Ket qua nam o L[s]}
        close(f);
end;
 
begin
        nhap;
        solution;
        xuat;
end.
Chủ đề: Quy hoạch động, SPOJ Mức độ:

LINEGAME – SPOJ

15/06/2016 by 2 Comments

Đề bài: http://vn.spoj.com/problems/LINEGAME/

Thuật toán:

Đây là một bài quy hoạch động khá hay. Trước hết ta có thể ăn được 60% số Test bằng duyệt, hoặc Quy hoạch động với độ phức tạp O(n2), thậm chí làm Quy hoạch động với độ phức tạp O(n) mà dùng hai mảng một chiều 106 phần tử chúng ta cũng chỉ đạt 60% số test.

Tôi xin trình bày ngắn gọn công thức sau với độ phức tạp O(n).

Gọi F[i,1] là số điểm lớn nhất có thể đạt được khi xét tới ô thứ i và ô cuối cùng mang dấu ‘+’, tương tự F[i,2] là số điểm lớn nhất có thể đạt được khi xét tới ô thứ i và ô cuối cùng mang dấu ‘-’ ta thấy:

F[i,1]=Max(F[i-1,2]+a[i],F[i-1,1]).

F[i,2]=Max(F[i-1,1]-a[i],F[i-1,2]).

Với công thức trên chương trình có thể chạy với n=106 trong 1s là cùng, nhưng đối với Time Limit nhỏ hơn như 0.5s thì rất dễ quá thời gian một cách đáng tiếc.

Ta để ý như sau: Tính F[i,1] và F[i,2] chỉ phụ thuộc vào F[i-1,1] và F[i-1,2] như vậy ta có thể dùng 3 biến m1,m2,m3 với vai trò như sau: m1 lưu F[i-1,1], m2 lưu F[i-1,2], m3 là trung gian và sau khi tính xong F[i,1] và F[i,2] thì m1,m2 lại được ghi đè lên giá trị của m1 và m2 lúc trước. Trong quá trình tính ta luôn cập nhật m1 và m2 với Max.

Trong chương trình chính ta tính luôn m1,m2 song song với đọc mảng a. Nói chung chương trình dưới đây chỉ sử dụng 7 biến kiểu nguyên và 1 biến tệp. Rất tiết kiệm bộ nhớ và CT ngắn gọn.

Độ phức tạp của thuật toán: O(n)
Code:

Const
        fi='';
        fo='';
 
Var
        n,a,i   :longint;
        m1,m2,m3:int64;
        max     :int64;
        f       :text;
Begin
        assign(f,fi);
        reset(f);
        max:=0;m1:=0;m2:=0;
        readln(f,n);
        for i:=1 to n do
                begin
                        read(f,a);{Doc a[i]}
                        m3:=m1;{Giu lai F[i-1,1] de tinh m2}
                        if m1<m2+a then m1:=m2+a;{m1=F[i,1]=Max(F[i-1,2]+a[i],F[i-1,1])}
                        if m2<m3-a then m2:=m3-a;{m2=F[i,2]=Max(F[i-1,1]+a[i],F[i-1,2])}
                        if m1>max then max:=m1;{Cap nhat F[i,1] voi Max}
                        if m2>max then max:=m2;{Cap nhat F[i,2] voi Max}
                end;
        close(f);
        assign(f,fo);
	      rewrite(f);
        write(f,max);
        close(f);
End.
Chủ đề: Quy hoạch động Mức độ:

PARIGAME – SPOJ

15/06/2016 by Leave a Comment

Đề bài:

Thuật toán:

Gọi L[i,j] là trạng thái thắng (TRUE) hay thua (FALSE) khi bảng trò chơi có kích thước i x j của người đi trước.

Ta thấy:

  • L[i,j]=TRUE tương đương L[i-1,j]=FALSE nếu tổng các số trên hàng i chẵn, hoặc L[i,j-1]=FALSE nếu tổng các số trên cột j chẵn.
  • L[i,j]=FALSE tương đương L[i-1,j]=TRUE hoặc tổng các số trên hàng i lẻ và L[i,j-1]=TRUE hoặc tổng các số trên cột j lẻ.

Tóm lại ta có: L[i,j]= x or y;

x=TRUE nếu tổng các số trên hàng i chẵn và L[i-1,j]=FALSE; x=FALSE trong trường hợp còn lại.

y=TRUE nếu tổng các số trên cột j chẵn và L[i,j-1]=FALSE ; y=FALSE trong trường hợp còn lại.

Vấn đề còn lại là việc tính tổng các số trên hàng i và cột j:

Gọi S[i,j] là tổng các số trên bảng trò chơi kích thước i x j Ta tính S[i,j] tương tự bài BONUS:

S[i,j]:=S[i-1,j]+S[i,j-1]+a[i,j]-S[i-1,j-1];

Gọi h là tổng các số trên hàng i, ta có : h=S[i,j]-S[i-1,j];

Gọi c là tổng các số trên cột j, ta có : c=S[i,j]-S[i,j-1];

Từ việc tính trước mảng S ta đưa bài toán có độ phức tạp O(n2) tốt hơn rất nhiều nếu tính trực tiếp sẽ có độ phức tạp O(n3)

Code:

Const
        tfi='';
        tfo='';
        maxn=500;
 
Type
        arr1    =array[1..maxn,1..maxn] of longint;
        arr2    =array[0..maxn,0..maxn] of qword;
        arr3    =array[0..maxn,0..maxn] of boolean;
 
Var
        n       :longint;
        k       :longint;
        a       :arr1;
        s       :arr2;
        L       :arr3;
        fi,fo   :text;
 
Procedure nhap;
var
        i,j     :longint;
begin
        readln(fi,n);
        for i:=1 to n do
                for j:=1 to n do
                        read(fi,a[i,j]);
end;
 
Procedure Init;
var
        i,j     :longint;
begin
        for i:=0 to n do
                begin
                        s[0,i]:=0;
                        s[i,0]:=0;
                end;
        for i:=1 to n do
                for j:=1 to n do
                        s[i,j]:=s[i-1,j]+s[i,j-1]+a[i,j]-s[i-1,j-1];
        for i:=1 to n do
                begin
                        if s[i,1] mod 2=0 then L[i,1]:=true
                                else L[i,1]:=false;
                        if s[1,i] mod 2=0 then L[1,i]:=true
                                else L[1,i]:=false;
                end;
end;
 
Procedure solution;
var
        i,j     :longint;
        x,y     :boolean;
        h,c     :qword;
begin
        for i:=2 to n do
                for j:=2 to n do
                        begin
                                h:=s[i,j]-s[i-1,j];
                                c:=s[i,j]-s[i,j-1];
                                if (h mod 2=0) and (L[i-1,j]=false) then x:=true
                                        else x:=false;
                                if (c mod 2=0) and (L[i,j-1]=false) then y:=true
                                        else y:=false;
                                L[i,j]:=x or y;
                        end;
end;
 
Procedure xuat;
begin
        if L[n,n]=true then writeln(fo,'YES')
                else writeln(fo,'NO');
end;
 
Procedure Process;
var
        i       :longint;
begin
        assign(fi,tfi);
        reset(fi);
        assign(fo,tfo);
        rewrite(fo);
        readln(fi,k);
        for i:=1 to k do
                begin
                        nhap;
                        Init;
                        solution;
                        xuat;
                end;
        close(fi);
        close(fo);
end;
 
begin
        Process;
end.
Chủ đề: Quy hoạch động Mức độ: ,

MMOD29 – SPOJ

15/06/2016 by 2 Comments

Đề bài: http://vn.spoj.com/problems/MMOD29/

Thuật toán:

  • (đang cập nhập)

Code:

const   fi      ='';
        fo      ='';
 
var     f1, f2       :text;
        x       :longint;
        a, b, c :longint;
function get(a, b:longint):longint;
var     tmp     :longint;
begin
        if b = 0 then exit(1);
        if b mod 2 = 0 then exit(sqr(get(a, b div 2)) mod 29 )
        else exit( (sqr(get(a, b div 2))*a) mod 29 );
end;
 
BEGIN
        assign(f1, fi);
        reset(f1);
        assign(f2, fo);
        rewrite(f2);
        while not eof(f1) do
                begin
                        readln(f1, x);
                        if x = 0 then break;
                        a:=(get(2, 2*x + 1) - 1 ) mod 29;
                        b:=(get(3,   x + 1) - 1 ) mod 29;
                        c:=(get(167, x + 1) - 1 ) mod 29;
                        writeln(f2,(a*b*c*9) mod 29);
                end;
        close(f1);
        close(f2);
END.
Chủ đề: SPOJ