SPOJ

Chia sẻ thuật toán, code bài tập trên SPOJ

VMRR–spoj

Đề bài:

Thuật toán:

  • (Đang cập nhật)

Code:

 

#include <bits/stdc++.h>
using namespace std;
 
main(){
    string s,a;
    getline(cin,s);
    cin>>a;
    int dem=0; int z; long long res; char x,y;
    x=a[0];y=a[1]; res=0;z=0;
    for(int i=s.size()-2;i>=0;--i){
        if(s[i+1]==y) z++;
        if(s[i]==x) res+=z;
    }
    cout<<res;
}

LABUDOVI – spoj

Đề bài:

Thuật toán:

  • BFS
  • Bài này chú ý dùng phương pháp loang đồ thị để làm; chúng ta sẽ dùng 2 mảng nextx, nexty để loang ra 4 ô xung quanh của 1 ô.
  • Đầu tiên đánh dấu vị trí của 2 con thiên nga và đánh dấu tất cả các ô là nước.
  • Sau đó tiến hành loang từ con thiên nga thứ nhất. Nếu gặp con thiên nga thứ hai thì return.
    Nếu không thì tiến hành loang các ô bên cạnh là ô băng; nếu gặp ô băng thì chuyển thành ô nước, đánh dấu lại và tăng biến đếm lên 1. Tiếp tục như vậy cho tới khi gặp được con thiên nga thứ hai.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
 
#define task ""
#define fi first
#define se second
#define maxinp (int)(1500)
#define MODUL (int)(1e9+57)
#define siz(x) (int)(x.size())
#define len(x) (int)(x.length())
#define whole(x) x.begin(), x.end()
#define FOR(i, x, y) for(int i=x; i<=y; ++i)
#define FORl(i, x, y) for(int i=x; i<y; ++i)
#define FORb(i, x, y) for(int i=x; i>=y; --i)
#define FORlb(i, x, y) for(int i=x; i>y; --i)
#define MEMS(x, val) memset(x, val, sizeof(x))
#define FILEOP(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout);
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef queue<ii> qii;
typedef long long ll;
int nextx[4] = {-1, 0, 0, 1};
int nexty[4] = {0, -1, 1, 0};
bool Free[maxinp][maxinp];
int Time[maxinp][maxinp];
char a[maxinp][maxinp];
int m, n, res, nTime;
qii mainq, subq;
ii start[3];
int nInstruction = 0;
void Debug()
{
 
    cout << endl;
    FOR(i, 1, m)
    {
        FOR(j, 1, n)
        {
            cout << Time[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
 
 
}
 
 
void Enter()
{
	int cnt = 1;
	MEMS(Free, true);
 
 
	scanf("%d%d", &m, &n);
 
 
 
 
	FOR(i, 1, m)
	{
	    FOR(j, 1, n)
	    {
 
	        cin >> a[i][j];
 
 
            if(a[i][j] != 'X')
            {
                Time[i][j] = 0;
 
                mainq.push(ii(i, j));
 
                if(a[i][j] == 'L')
                {
                    start[cnt] = ii(i, j);
                    ++cnt;
                }
 
                Free[i][j] = false;
            }
            else Time[i][j] = 1234567890;
 
            ++nInstruction;
 
 
	    }
	}
 
}
 
//Check
bool IsValid(int _x, int _y)
{
    return(_x >= 1 && _y >= 1 && _x <= m && _y <= n && Free[_x][_y]);
}
 
void PreProcess()
{
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        ++nInstruction;
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
 
            if(IsValid(x, y))
            {
                if(a[x][y] == 'X')
                {
                    Free[x][y] = false;
                    mainq.push(ii(x, y));
                    Time[x][y] = min(Time[x][y], Time[curx][cury] + 1);
                }
            }
        }
 
    }
 
    //Debug();
 
 
 
}
void FloodFill1(ii st1, ii st2)
{
    mainq.push(st1);
    Free[st1.first][st1.second] = false;
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        //Time[curx][cury] = nTime;
        ++nInstruction;
 
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
            ii dir = ii(x, y);
 
            if(IsValid(x, y))
            {
                Free[x][y] = false;
                if(dir == st2) return;
                if(Time[x][y] <= res) mainq.push(dir);
                else subq.push(dir);
            }
        }
 
        if(mainq.empty())
        {
            ++res;
            swap(mainq, subq);
        }
 
    }
}
 
//Process
void Solve()
{
    res = 0;
    PreProcess();
    MEMS(Free, true);
    FloodFill1(start[1], start[2]);
    printf("%d", res);
 
 
    cerr << endl;
    cerr << nInstruction << endl;
 
}
 
//Main Procedure
int main()
{
    Enter();
    Solve();
    return 0;
}

C11SEQ3 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
        tfi='';//c11seq3.inp';
        tfo='';//c11seq3.out';
 
var
        fi,fo:text;
        n:longint;
        f:array[0..24]of qword;
        t:array[0..5] of qword=(244445,48889, 77789, 155578, 111356, 122227);
 
procedure dao(i:longint);
        var s:string;
                tg:char;
                i1,j,code:longint;
        begin
                str(f[i],s);
                for i1:=1 to length(s)-1 do
                        for j:=i1+1 to length(s) do
                                if s[i1]>s[j] then
                                        begin
                                                tg:=s[i1];
                                                s[i1]:=s[j];
                                                s[j]:=tg;
                                        end;
                val(s,f[i],code);
        end;
 
procedure xuli;
        var i:longint;
        begin
                read(fi,n);
                f[1]:=1;
                for i:=2 to 24 do
                        begin
                                f[i]:=f[i-1]*2;
                                dao(i);
                        end;
                if n<=24 then write(f[n])
                else writeln(fo,t[n mod 6]);
        end;
 
 
begin
        assign(fi,tfi);
        assign(fo,tfo);
        reset(Fi);
        rewrite(fo);
        xuli;
        close(fo);
end.

WS – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi = '';
var
  a : array[1..50000] of longint;
  val,valmax,rem : array[1..200000] of longint;
  n,k,m : longint;
 
 
procedure enter;
  var
    i,j,tmp : longint;
  begin
    n := 0;
    readln(k,m);
    i := 1;
    for j := 1 to k do
      begin
        read(tmp);
        a[i] := 1;
        inc(i,tmp);
        inc(n,tmp);
      end;
    readln;
  end;
 
procedure init(s,l,r : longint);
  var
    mid : longint;
  begin
    if l = r then
      begin
        valmax[s] := 1;
        exit;
      end;
    mid := (l + r) div 2;
    init(2*s,l,mid);
    init(2*s+1,mid+1,r);
    valmax[s] := valmax[2*s] + valmax[2*s+1];
  end;
 
procedure init2(s,l,r : longint);
  var
    mid : longint;
  begin
    if l = r then
      begin
        inc(val[s],a[l]);
        exit;
      end;
    mid := (l + r) div 2;
    init2(2*s,l,mid);
    init2(2*s+1,mid+1,r);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure trans(s,l,r : longint);
  var
    mid : longint;
  begin
    if (s = 0) or (l = r) then exit;
    mid := (l + r) div 2;
    inc(val[2*s],rem[s]*(mid-l+1));
    inc(val[2*s+1],rem[s]*(r-mid));
    inc(rem[2*s],rem[s]);
    inc(rem[2*s+1],rem[s]);
    rem[s] := 0;
  end;
 
procedure Jupdate(s,l,r,u,v : longint);
  var
    mid : longint;
  begin
    if (r < u) or (v < l) then exit;
    if (u <= l) and (r <= v) then
      begin
        if val[s] = valmax[s] then
          begin
            dec(val[s],r-l+1);
            dec(rem[s]);
            exit;
          end;
        if val[s] = 0 then exit;
      end;
    trans(s,l,r);
    mid := (l + r) div 2;
    Jupdate(2*s,l,mid,u,v);
    Jupdate(2*s+1,mid+1,r,u,v);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure Dupdate(s,l,r,u,v : longint);
  var
    mid : longint;
  begin
    if (r < u) or (v < l) then exit;
    if (u <= l) and (r <= v) then
      begin
        if val[s] = 0 then
          begin
            inc(val[s],r-l+1);
            inc(rem[s]);
            exit;
          end;
        if val[s] = valmax[s] then exit;
      end;
    trans(s,l,r);
    mid := (l + r) div 2;
    Dupdate(2*s,l,mid,u,v);
    Dupdate(2*s+1,mid+1,r,u,v);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure query(c : char; u,v : longint);
  begin
    if c = 'J' then Jupdate(1,1,n,u+1,v)
    else Dupdate(1,1,n,u+1,v);
  end;
 
procedure main;
  var
    i,u,v : longint;
    c : char;
  begin
    init(1,1,n);
    init2(1,1,n);
    for i := 1 to m do
      begin
        read(c);
        if c = 'C' then
          begin
            writeln(val[1]);
            readln;
          end
        else
          begin
            readln(u,v);
            query(c,u,v);
          end;
      end;
  end;
 
 
begin
  assign(input,fi);
  reset(input);
  enter;
  main;
  close(input);
end.

NKTICK – spoj

Đề bài:


Thuật toán:


  • Quy hoạch động

Code:


const   fi='';
        fo='';
        max=30000;
var n,i:longint;
t:array[1..60000] of integer;
f:array[-1..60000] of longint;
r:array[0..59999] of integer;
w:text;
function min(x,y:longint):longint;
begin
    if x>y then min:=y else min:=x;
end;
procedure nhap;
begin
    assign(w,fi);
    reset(w);
    readln(w,n);
    for i:=1 to n do read(w,t[i]);
    for i:=1 to n-1 do read(w,r[i]);
    close(w);
end;
procedure xuly;
begin
        f[0]:=0; f[-1]:=0; r[0]:=max;
        for i:=1 to n do
        f[i]:=min(f[i-1]+t[i],f[i-2]+r[i-1]);
end;
procedure inkq;
begin
        assign(w,fo);
        rewrite(w);
        writeln(w,f[n]);
        close(w);
end;
begin
    nhap;
    xuly;
    inkq;
end.

DTTUI1 – spoj

Đề bài:


Thuật toán:


  • Duyệt phân tập kết hợp Chặt nhị phân
  • Bạn có thể tham khảo thuật toán Duyệt phân tập tại đây

Code:


Program DTtui1;
CONST
        fin='';
        fon='';
        maxn=40;
        maxth=1048576;
Type
        Opt=Record
                kl,gt:longint;          //Khoi luong, Gia tri
        End;
        ToHop=array [1..maxth] of Opt;
Var
        o:array [1..2] of ToHop;
        dem:array [1..2] of longint;
        amax:array [1..maxth] of longint;
        w,v:array [1..maxn] of longint;   //Weight, Value
        m,i,j,sw,sv,sum:longint;
        n,mid:byte;
        f:text;
//--------------------------------------------------
        Procedure Nhap;
        Var i:byte;
        Begin
                Assign(f,fin);
                Reset(f);
                Readln(f,n,m);
                For i:=1 to n do
                        Readln(f,w[i],v[i]);
                Close(f);
        ENd;
        //------------------------------------------
 
                Procedure Sort(l,r:longint);
                Var i,j,x:longint;
                        y:Opt;
                Begin
                        i:=l;
                        j:=r;
                        x:=o[2,l+random(r-l+1)].kl;
                        Repeat
                                While o[2,i].kl<x Do inc(i);
                                While o[2,j].kl>x do dec(j);
                                If not(i>j) Then
                                        Begin
                                        y:=o[2,i];
                                        o[2,i]:=o[2,j];
                                        o[2,j]:=y;
                                        inc(i);
                                        dec(j);
                                        ENd;
                        Until i>j;
                        If i<r Then sort(i,r);
                        If l<j Then sort(l,j);
                End;
        //-----------------------------------------
        Procedure Luu(x:byte);
        Var k:longint;
        Begin
                inc(dem[x]);
                k:=dem[x];
                o[x,k].kl:=sw;
                o[x,k].gt:=sv;
        End;
        //----------------------------------------
        Procedure Duyet(bit,i,k:byte);
        Var j:byte;
        Begin
                If sw>m Then Exit;
                For j:=0 to 1 do
                        Begin
                        sw:=sw+j*w[i];
                        sv:=sv+j*v[i];
                        If i=k Then
                                Begin
                                If sw<=m Then Luu(bit);
                                End
                        else Duyet(bit,i+1,k);
                        sw:=sw-j*w[i];
                        sv:=sv-j*v[i];
                        End;
        End;
        //-------------------------------------
        Procedure CheckMax;
        Var i,max:longint;
        Begin
                amax[1]:=1;
                max:=1;
                For i:=2 to dem[2] do
                        Begin
                        If o[2,i].gt>o[2,max].gt Then max:=i;
                        amax[i]:=max;
                        End;
        End;
        //-----------------------------------
        Function Find(bit:byte; x:longint):longint;
        Var dau,giua,cuoi:longint;
        Begin
                dau:=1;
                cuoi:=dem[bit]+1;
                Repeat
                        giua:=(dau+cuoi) div 2;
                        If o[bit,giua].kl <= x Then dau:=giua
                        else cuoi:=giua;
                Until dau+1=cuoi;
                Exit(dau);
        End;
        //------------------------------------
        Procedure Xuat;
        Begin
                Assign(f,fon);
                Rewrite(f);
                Writeln(f,sum);
                Close(f);
        End;
Begin
        Randomize;
        Nhap;
        mid:=n div 2;
        Duyet(1,1,mid);
        Duyet(2,mid+1,n);
        sort(1,dem[2]);
        CheckMax;
 
        For i:=1 to dem[1] do
                Begin
                j:=Find(2,m-o[1,i].kl);
                If o[1,i].gt + o[2,amax[j]].gt > sum Then sum:=o[1,i].gt + o[2,amax[j]].gt;
                End;
        Xuat;
End.

STABLE – spoj

Đề bài:

Thuật toán:

  • BFS từ đỉnh S
  • Gọi bac[i] là đồ dài đường đi ngắn nhất từ s đến i
    • bac[i] = bac[j] + 1
    • với i kề j và j duyệt BFS trước i
  • ok[i] = 1 nếu i ổn định, ok[i] = 0 nếu i không ổn định.
  • Hãy tham khảo code để biết cách kiểm tra xem i có ổn định không

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E4+3;
const int oo = 1e9+3;
 
int n, m, s, u, v, res, bac[MAXN],adj[MAXN][MAXN];
bool ok[MAXN];
queue<int> q;
vector<int> a[MAXN];
 
int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> n >> m >> s;
    FOR(i,1,m) {
        cin >> u >> v;
        if (!adj[u][v])
            a[u].push_back(v);
        adj[u][v] = 1;
    }
    q.push(s); bac[s] = 1;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for(int i=0; i<a[u].size(); i++)
        {
            v = a[u][i];
            if (!bac[v])
            {
                if (ok[u]) ok[v] = 1;
                bac[v] = bac[u] + 1;
                q.push(v);
            }
            else
            if (bac[v] == bac[u] + 1) ok[v] = 1;
        }
    }
    FOR(i,1,n) if (ok[i]) res++;
    cout << res;
	return 0;
}
const
  fi='stable.inp';
  fo='stable.out';
  maxn=10000;
  maxm=50000;
var
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,st,ans,s,dau,cuoi,u,v : longint;
  q,bac : array[1..maxn] of longint;
  ok : array[1..maxn] of boolean;
  a : array[1..maxn,1..maxn] of boolean;
procedure push(x : longint);
  begin
    inc(cuoi);
    q[cuoi] := x;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
begin
//  assign(input,fi);reset(input);
//  assign(output,fo);rewrite(output);
  read(n,m,s);
  for i := 1 to m do
    begin
      read(u,v);
      if a[u,v] = false then
      add(i,u,v);
      a[u,v] := true;
    end;
  dau := 1; cuoi := 0;
  push(s);
  bac[s] := 1;
  while (dau <= cuoi) do
    begin
      u := q[dau];
      inc(dau);
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          if bac[v] = 0 then
            begin
              if ok[u] then ok[v] := true;
              bac[v] := bac[u] + 1;
              push(v);
            end
            else
          if bac[v] = bac[u] + 1 then
            begin
              ok[v] := true;
            end;
          i := link[i];
        end;
    end;
  for i := 1 to n do
    if ok[i] then inc(ans);
  writeln(ans);
//  close(input);close(output);
end.