VO17LAN – spoj

Đề bài

Thuật toán

  • (đang cập nhập)

Code

#include <bits/stdc++.h>
using namespace std;
#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)
#define pb push_back
#define endl '\n'
#define ll long long
#define X first
#define Y second
 
const int MAXN = 1e5 * 5;
const int base = 1e9 + 7;
const int N = 55000;
 
int t,n;
int ans;
int a[N];
 
int gcd(int a,int b)
{
    if (b == 0) return a;
    else return gcd(b,a%b);
}
 
void upd(int d)
{
    if (d <= ans) return;
    int gcd1 = a[1];
    int gcd2 = 0;
    FORE(i,2,n)
    {
        if (a[i]%d == 0) gcd1 = gcd(gcd1 , a[i]);
        else
        {
            if (gcd2 == 0) gcd2 = a[i];
            else gcd2 = gcd(gcd2 , a[i]);
        }
        if (gcd2 && min(gcd1 , gcd2) <= ans) return;
    }
    if (gcd2 == 0) gcd2 = gcd1;
    ans = max(ans , min(gcd1 , gcd2));
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("vo17lan.inp" , "r" , stdin);
    //freopen("vo17lan.out" , "w" , stdout);
    cin>>t;
    while(t--)
    {
        cin>>n;
        FORE(i,1,n) cin>>a[i];
        sort(a+1,a+n+1);
        ans = 1;
        int xx = sqrt(a[1]);
        FORD(d,xx,2)
        if (a[1]%d == 0)
        {
            upd(d);
            upd(a[1]/d);
        }
        upd(a[1]);
        cout<<ans<<endl;
    }
    return 0;
}

SEQ198 – spoj

Đề bài:

Thuật toán:

  • Sử dụng phương pháp quy hoạch động kết hợp với bitmask.
  • Sắp xếp lại mảng A.
  • f[i,state] là số phần tử cần loại bỏ của dãy A[1..i] khi có state là trạng thái giữ hoặc chọn của 10 số cuỗi của dãy.

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)
#define X first
#define Y second
#define ll long long
#define mp make_pair
#define pb push_back
#define endl '\n'
 
const int MAXN = 1e5 * 5;
const int inf = 1024;
const int N = 5000;
 
using namespace std;
int n,p[N],a[N],b[N],l[N],ans,ss,c[N],f[2001][1025];
 
void update()
{
    int cnt = 0;
    int dem = 0;
    FORE(i,1,min(n,10))
    if (l[i])
            c[++cnt] = a[i],dem += b[i];
    sort(c+1,c+cnt+1);
    FORE(i,1,cnt)
    FORD(j,i-1,1)
    if (c[i] - c[j] > 9) break;
    else
    {
        if (c[i] - c[j] == 1) return;
        if (c[i] - c[j] == 8) return;
        if (c[i] - c[j] == 9) return;
    }
    f[10][ss] = dem;
    ans = max(ans , dem);
}
 
void duyet(int i)
{
    FORE(j,0,1)
    {
        ss = ss*2 + j;
        l[i] = j;
        if (i == min(n,10)) update();
        else duyet(i+1);
        ss /= 2;
    }
}
 
int ok(int u,int v)
{
    if (u - v == 1) return 1;
    if (u - v == 8) return 1;
    if (u - v == 9) return 1;
    return 0;
}
 
int check(int s,int i)
{
    FORE(j,0,8)
    {
        int xx = (s >> j)&1;
        if (xx && ok(a[i],a[i - j - 1])) return 1;
    }
    return 0;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("", "r", stdin);
    freopen("", "w", stdout);
    #endif //yeulaptrinh.pw
    cin>>n;
    int lx = n;
    FORE(i,1,n) cin>>p[i];
    sort(p+1,p+n+1);
    int po = -1;
    int n1 = 0;
    FORE(i,1,n)
    if (p[i] != po)
    {
        po = p[i];
        ++n1;
        a[n1] = p[i];
        ++b[n1];
    }
    else ++b[n1];
    n = n1;
    duyet(1);
    if (n <= 10)
    {
        cout<<lx - ans;
        return 0;
    }
    FORE(i,10,n-1)
    FORE(x,0,1023)
    {
        int xx = (2*x)%inf;
        f[i+1][xx] = max(f[i+1][xx] , f[i][x]);
        if (check(x,i+1)) continue;
        xx = (2*x + 1)%inf;
        f[i+1][xx] = max(f[i+1][xx] , f[i][x] + b[i+1]);
    }
    int kq = 0;
    FORE(i,10,n)
    FORE(x,0,1024)
        kq = max(kq , f[i][x]);
    cout<<lx - kq;
    return 0;
}
uses math;
const
  fi = '';
var
  a,b,cnt : array[0..2001] of longint;
  f : array[0..2001,0..511] of longint;
  dd : array[0..2001,0..511] of boolean;
  n,n1 : longint;
 
procedure enter;
  var
    i : longint;
  begin
    assign(input,fi);
    reset(input);
    readln(n);
    for i := 1 to n do
      read(b[i]);
    close(input);
  end;
 
 
procedure qsort(l,r : longint);
  var
    i,j,k,tmp : longint;
  begin
    i := l;
    j := r;
    k := b[l + random(r - l + 1)];
    while i < j do
      begin
        while b[i] < k do inc(i);
        while b[j] > k do dec(j);
        if i <= j then
          begin
            tmp := b[i];
            b[i] := b[j];
            b[j] := tmp;
            inc(i);
            dec(j);
          end;
      end;
    if l < j then qsort(l,j);
    if i < r then qsort(i,r);
  end;
 
function getbit(x,i : longint) : longint;
  begin
   exit(1 and (x shr (i - 1)));
  end;
 
function check(stt : longint) : boolean;
  begin
    if (getbit(stt,1) = 1) or (getbit(stt,8) = 1) or (getbit(stt,9) = 1) then exit(false);
    exit(true);
  end;
 
function batbit(x,i : longint) : longint;
  begin
    exit(x or (1 shl (i - 1)));
  end;
 
function sttnext(tt,stt,i : longint) : longint;
  var
    res,kc,j : longint;
  begin
    kc := a[i+1] - a[i];
    res := 0;
    for j := 0 to 9 - kc do
      if j = 0 then
        begin
          if tt = 1 then res := batbit(res,kc)
        end
      else
        if getbit(stt,j) = 1 then
          res := batbit(res,kc + j);
    exit(res);
  end;
 
procedure init;
  var
    i,j : longint;
  begin
    qsort(1,n);
    a[1] := b[1];
    j := 1;
    cnt[1]:=1;
    for i := 2 to n do
      if b[i] <> a[j] then
        begin
          inc(j);
          a[j] := b[i];
          cnt[j] := 1;
        end
      else inc(cnt[j]);
    n1:=j;
    a[n1+1] := high(longint)
  end;
 
function cal(i,stt: longint) : longint;
  var
    ff : longint;
  begin
    if dd[i,stt] then exit(f[i,stt]);
    dd[i,stt] := true;
    if i = n1 + 1 then
      ff := 0
    else
      begin
        ff := cal(i + 1,sttnext(0,stt,i)) + cnt[i];
        if check(stt) then
          ff := min(ff,cal(i + 1,sttnext(1,stt,i)));
      end;
    f[i,stt] := ff;
    exit(ff);
  end;
 
procedure print;
  begin
    writeln(cal(1,0));
  end;
 
begin
  enter;
  init;
  print;
end.

ROBOCON – vn.spoj.com

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

Thuật toán:

  • Bạn loang con robot 1 trong khi loang robot 1 bạn cũng đồng thời loang robot 2. Ta phải suy luận ra một số trường hợp để mà dừng loang
  • Bạn có thể đọc code của mình để hiểu thêm. Mình viết rất dễ hiểu, bạn đọc có thể hiểu ngay

Code:

const
  fi='';
  fo='';
  maxn=501;
  maxq=20*maxn*maxn;
  oo=trunc(1e9);
type
  point = record
    x,y,d : longint;
  end;
var
  dau1,cuoi1,dau2,cuoi2,i,j,n,m : longint;
  a : array[0..maxn,0..maxn] of boolean;
  q1,q2 : array[1..maxq] of point;
  d1,d2 : array[1..maxn,1..maxn] of longint;
  nowd,res : longint;
  kt : boolean;
 
procedure enter;
var u,v : longint;
begin
  assign(input,fi);reset(input);
  fillchar(a , sizeof(a) , false);
  readln(n,m);
  for i:=1 to n do for j:=1 to n do a[i,j] := true;
  for i:=1 to m do
    begin
      read(u,v);
      a[u,v] := false;
    end;
end;
procedure push1(x,y,z : longint);
begin
  inc(cuoi1);
  q1[cuoi1].x := x;
  q1[cuoi1].y := y;
  q1[cuoi1].d := z;
  d1[x,y] := z;
  if d2[x,y]=z then
    begin
      res := z;
      kt:=true;
      exit;
    end;
end;
procedure push2(x,y,z : longint);
begin
  inc(cuoi2);
  q2[cuoi2].x := x;
  q2[cuoi2].y := y;
  q2[cuoi2].d := z;
  d2[x,y] := z;
end;
procedure bfs2(dd : longint);
var u : point;
    i,j : longint;
begin
  while dau2<=cuoi2 do
    begin
      u := q2[dau2]; inc(dau2);
      if u.d>dd then begin dec(dau2); exit; end;
      i:=u.x;j:=u.y;
      if a[i,j-1] and (d2[i,j-1]<>dd+1) then push2(i,j-1,dd+1);
      if a[i+1,j] and (d2[i+1,j]<>dd+1) then push2(i+1,j,dd+1);
      if a[i+1,j-1] and (d2[i+1,j-1]<>dd+1) then push2(i+1,j-1,dd+1);
    end;
end;
procedure bfs1;
var u : point;
    i,j : longint;
begin
  fillchar(d1,sizeof(d1),255);
  fillchar(d2,sizeof(d2),255);
  kt := false;
  dau1 :=1; cuoi1 := 0;
  dau2 := 1; cuoi2 := 0;
  push1(1,1,0); push2(1,n,0);
  nowd := 0;
  while dau1<=cuoi1 do
    begin
      if kt then break;
      u := q1[dau1]; inc(dau1);
      if u.d=nowd then
        begin
          bfs2(nowd);
          inc(nowd);
        end;
      i := u.x ; j:=u.y;
      if a[i+1,j] and (d1[i+1,j]<>u.d+1) then push1(i+1,j,u.d+1);
      if a[i,j+1] and (d1[i,j+1]<>u.d+1) then push1(i,j+1,u.d+1);
      if a[i+1,j+1] and (d1[i+1,j+1]<>u.d+1) then push1(i+1,j+1,u.d+1);
    end;
end;
procedure process;
begin
  res := oo;
  bfs1;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(res);
  close(output);
end;
begin
  enter;
  process;
  print;
end.

REFORM – SPOJ

Đề 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.

PARIGAME – SPOJ

Đề 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.

VODIVIDE – SPOJ

Đề bài:

Thuật toán:

Bài này có thể giải bằng phương pháp Quy hoạch động hoặc CTDL Heap. Ở đây giải theo phương pháp Quy hoạch động.

  • Gọi F[i,j] là tổng số tiền lớn nhất mà Sơn nhận được khi xét i đồng và Sơn được j đồng
  • F[i,j]:=max(F[i-1,j],F[i-1,j-1]+b[i]);

Code:

uses    math;
const   fi='';
        fo='';
        maxn=5000+2;
var     f:array[0..maxn,0..maxn] of longint;
        a,b,cs:array[1..maxn] of longint;
        res:array[1..maxn] of longint;
        dem,n,i,j:Longint;
        free:array[1..maxn] of boolean;
procedure nhap;
begin
    assign(input,fi);reset(Input);
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do read(b[i]);
    close(input);
end;
procedure init;
begin
    for i:=1 to n do cs[i]:=i;
end;
procedure swap(var x,y:longint);
var     w:longint;
begin
    w:=x;x:=y;y:=w;
end;
procedure qs(l,r:longint);
var     i,j,x:longint;
begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
        while x<a[i] do inc(i);
        while x>a[j] do dec(j);
        if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    swap(cs[i],cs[j]);
                    inc(i);dec(j);
                end;
    until i>j;
    if i<r then qs(i,r);
    if j>l then qs(l,j);
end;
procedure xuly;
begin
    {f[1,0]:=b[1];}
    qs(1,n);
    for i:=2 to n do
        for j:=1 to i div 2 do
                begin
                    f[i,j]:=max(f[i-1,j],f[i-1,j-1]+b[i]);
                end;
end;
procedure trace;
begin
    i:=n; j:=n div 2;
    while (i<>0) and (j<>0) do
        begin
            if f[i,j]=f[i-1,j-1]+b[i] then
                begin
                        inc(dem);
                        res[dem]:=i;
                        free[i]:=true;
                        dec(i);dec(j);
                end else dec(i);
        end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(f[n,n div 2]);
    for i:=1 to dem do
        begin
 
            for j:=res[i]-1 downto 1 do
                if free[j]=false then
                        begin
                            write(cs[j],' ');
                            free[j]:=true;
                            break;
                        end;
            write(cs[res[i]],' ');
            writeln;
        end;
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    trace;
    inkq;
end.

TFIELD – SPOJ

Đề bài:


Thuật toán:


    Ngay từ đầu đề bài đã đề cập đến phần hình học.

    – Ta cần biết vị trí của các khoang theo đúng thứ tự (ví dụ từ trong ra ngoài). Ta có nhận xét là đa giác của khoang trong luôn có diện tích nhỏ hơn đa giác của khoang ngoài. Vì thế, ta chỉ cần sắp xếp các đa giác theo diện tích của chúng. Công thức tính diện tích 1 đa giác bất kì:

    S=1/2 ∑(x[i]-x[i+1])*(y[i]+y[i+1]) (với i=[1..n], quy ước điểm thứ n+1 chính là điểm 1).

    – Sau khi sắp xếp, ta có thể tính được diện tích từng khoang (diện tích khoang thứ i=s[i]-s[i-1]).

    – Bài toán đặt ra bây giờ là tìm đoạn khoang có diện tích lớn nhất nằm giữa 2 đa giác. Ta dùng đếm phân phối để giải quyết. Đầu tiên, ta cố định điểm trái của vùng cần xét O(m). Từ điểm này, tìm điểm phải nhất có số khoang cần đổi màu không quá k (nói cách khác là c-st<=k, với c là tổng số khoang của vùng, st là số khoang cùng màu của vùng) O(m). – Kết quả bài toán là kết quả tối ưu trong các giá trị đã xét. Độ phức tạp ~O(m^2).

Code:


uses    math;
const   fi='';
        fo='';
        maxn=1000+3;
type
        dinh    =record
                        x,y:longint;
                        end;
        arr1    =array[1..maxn] of dinh;
var     a       :array[1..maxn,1..maxn] of dinh;
        s       :array[1..maxn] of int64;
        i,j,n,m,k       :longint;
        c       :array[1..maxn] of longint;
        sodinh  :array[1..maxn] of longint;
        khoang  :array[1..maxn] of int64;
        res     :int64;
        dem     :array[1..maxn] of longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        read(m,k);
        for i:=1 to m do
                begin
                        read(sodinh[i],c[i]);
                        for j:=1 to sodinh[i] do read(a[i,j].x,a[i,j].y);
                end;
        close(input);
end;
procedure swap(var x,y:int64);
var     tg      :int64;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure swap2(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x:extended;
        i,j:longint;
begin
        i:=l;j:=r;
        x:=s[(l+r) div 2];
        repeat
                while x<s[i] do inc(i);
                while x>s[j] do dec(j);
                if i<=j then
                        begin
                                swap(s[i],s[j]);
                                swap2(c[i],c[j]);
                                inc(i);dec(j);
                        end;
        until i>j;
        if i<r then qs(i,r);
        if j>l then qs(l,j);
end;
function dientich(p:arr1;n:longint):int64;
var     i       :longint;
begin
        dientich := 0;
        p[n+1] := p[1];
        for i:=1 to n do
                dientich:= dientich + int64( (p[i+1].x-p[i].x) )*(p[i+1].y+p[i].y);
        dientich:= abs(dientich){/2};
end;
procedure tinhs;
var     i:longint;
begin
        for i:=1 to m do
                s[i]:=dientich(a[i],sodinh[i]);
end;
procedure chuanbi;
begin
        sodinh[n+1]:=4;
        a[n+1,1].x:=1;
        a[n+1,1].y:=1;
        a[n+1,2].x:=1;
        a[n+1,2].y:=1;
        a[n+1,3].x:=1;
        a[n+1,3].y:=1;
        a[n+1,4].x:=1;
        a[n+1,4].y:=1;
end;
procedure process;
var     maxc,sokhoang        :longint;
        dientich        :int64;
begin
        tinhs;
        s[m+1]:=0;
        qs(1,m+1);
        for i:=1 to m do
                khoang[i]:=s[i]-s[i+1];
        for i:=1 to m do
                begin
                        fillchar(dem,sizeof(dem),0); dientich := 0; maxc :=1; sokhoang :=1;
                        inc(dem[c[i]]);
                        dientich := dientich + khoang[i]; if dientich>res then res := dientich;
                        for j := i+1 to m do
                        begin
                                inc(dem[c[j]]); inc(sokhoang);
                                maxc := max(maxc,dem[c[j]]);
                                if sokhoang-maxc<=k then
                                        begin
                                                dientich := dientich + khoang[j];
                                                if dientich>res then res := dientich;
                                        end else break;
                        end;
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        write(res{:0:1} div 2);
        if odd(res) then
                write('.5') else write('.0');
        close(output);
end;
begin
        enter;
        process;
        print;
end.
#include<bits/stdc++.h>
#define db double
#define fs first
#define sc second
#define maxn 1005
#define ll long long
using namespace std;
int n,k,d[maxn],sum[maxn];
struct data
{
            ll s;
            int c;
};
data a[maxn];
ll res;
typedef pair<int,int> II;
II c[maxn][maxn];
void tinh(int k)
{
            d[k]++;
            c[k][d[k]].fs=c[k][1].fs;
            c[k][d[k]].sc=c[k][1].sc;
            for (int i=2; i<=d[k]; ++i)
            {
                        a[k].s+=((ll)(c[k][i].fs-c[k][i-1].fs)*(c[k][i].sc+c[k][i-1].sc));
            }
            if (a[k].s<0) a[k].s=-a[k].s;
}
bool cmp(const data &a,const data &b)
{
            return a.s<b.s;
}
int main()
{
            //freopen("TFIELD.inp","r",stdin);
            ios::sync_with_stdio(0);
            cin.tie(0);
            cout.tie(0);
            cin>>n>>k;
            for (int i=1; i<=n; ++i)
            {
                        cin>>d[i]>>a[i].c;
                        for (int j=1; j<=d[i]; ++j)
                                    cin>>c[i][j].fs>>c[i][j].sc;
            }
            for (int i=1; i<=n; ++i) tinh(i);
            sort(a+1,a+n+1,cmp);
            sum[n+1]=1000000000;
            for (int i=1; i<=n; ++i)
            {
                        sum[0]=0;
                        for (int j=1; j<=n; ++j)
                                    if (a[j].c!=i) sum[j]=sum[j-1]+1;
                                    else sum[j]=sum[j-1];
                        int r=1;
                        for (int l=1;l<=n;++l)
                        {
                                    while(sum[r+1]-sum[l-1]<=k)
                                                ++r;
                                    res=max(res,a[r].s-a[l-1].s);
                        }
            }
            cout<<res/2;
            if (res%2) cout<<".5";
            else cout<<".0";
            return 0;
}