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.

P152SUMI – ptit

Đề bài:


Thuật toán:


Tạo một mảng quy hoạch có dạng
xau[i]==xau[i+1]? arr[i+1]=arr[i]+1 : arr[i+1]=arr[i];
với arr[0]=0;
VD: #..###
ta có;
arr[0] = 0;
arr[1] = 0; (#.)
arr[2] = 1; #(..)
arr[3] = 1; #.(.#)
arr[4] = 2; #..(##)
arr[5] = 3; #..#(##)

arr[i+1] = số cặp kí tự giống nhau từ xâu[0 -> i];
-> Với mỗi truy vấn ta có:
Số cặp giống nhau từ l->r = arr[r-1] – arr[l-1];

Code:


#include <iostream>
#include <string>
using namespace std;
 
int main ()
{
	string xau;
	cin>>xau;
	int arr[100005];
	arr[0]=0;
	for (int i=0; i<xau.size()-1; i++)
	{
		if (xau[i]==xau[i+1])
			arr[i+1]=arr[i]+1;
		else
			arr[i+1]=arr[i];
	}
	int m;
	cin>>m;
	for (int i=1; i<=m; i++)
	{
		int l, r;
		cin>>l>>r;
		cout<<arr[r-1]-arr[l-1]<<endl;
	}
	return 0;
}

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.