Archives for Tháng Tám 2017


VKNIGHTS – spoj

Đề bài:


Thuật toán:


  • Quy hoạch động trạng thái

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 = 200;
const int oo = (1 << 6) - 1;
 
int n, x, ans1, f[MAXN][oo+3], a[5][MAXN], z[MAXN];
ll ans2, t[MAXN][oo+3];
 
bool getbit(int state, int i) {
    return (state >> (6-i) ) & 1;
}
 
int tinh(int state) {
    int res = 0;
    FOR(i,1,6)
    if (getbit(state,i)) res++;
    return res;
}
 
int main() {
    	ios_base::sync_with_stdio(0); cin.tie(0);
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> n;
    FOR(i,1,n) {
        cin >> x;
        if (x) a[x][i] = 1;
    }
    FOR(i,1,3) {
        z[1] = z[1] * 2 + a[i][1];
    }
    FOR(i,2,n) {
        FOR(j,1,3) z[i] = z[i] * 2 + a[j][i-1];
        FOR(j,1,3) z[i] = z[i] * 2 + a[j][i];
    }
    f[0][0] = 0; t[0][0] = 1;
    FOR(j,0,(1<<3)-1)
    if ((z[1]&j)==0) {
        f[1][j] = tinh(j);
        t[1][j] = 1;
    }
    FOR(i,2,n) {
        FOR(state,0,oo)
        if ((z[i]&state)==0)
        FOR(j,0,oo)
        if ((z[i-2]&j)==0)
        if (t[i-2][j]>0)
        if ((i>3||(i==2&j==0))||(i==3&j<(1<<3)))
        {
            // check ma
            bool ok = 1;
            if (getbit(state,1)) {
                if (getbit(state,6)) ok = 0;
                if (getbit(j,6)) ok = 0;
                if (getbit(j,2)) ok = 0;
            }
            if (getbit(state,2)) {
                if (getbit(j,1)) ok = 0;
                if (getbit(j,3)) ok = 0;
            }
            if (getbit(state,3)) {
                if (getbit(state,4)) ok = 0;
                if (getbit(j,2)) ok = 0;
                if (getbit(j,4)) ok = 0;
            }
            if (getbit(state,4)) {
                if (getbit(state,3)) ok = 0;
                if (getbit(j,5)) ok = 0;
            }
            if (getbit(state,5)) {
                if (getbit(j,4)) ok = 0;
                if (getbit(j,6)) ok = 0;
            }
            if (getbit(state,6)) {
                if (getbit(j,5)) ok = 0;
                if (getbit(state,1)) ok = 0;
            }
            // qhd
            if (ok)
            if (f[i][state]<f[i-2][j]+tinh(state)) {
                f[i][state] = f[i-2][j] + tinh(state);
                t[i][state] = t[i-2][j];
            }
                else
            if (f[i][state]==f[i-2][j]+tinh(state)) {
                t[i][state] += t[i-2][j];
            }
        }
    }
    FOR(state,0,oo) ans1 = max(ans1,f[n][state]);
    FOR(state,0,oo)
    if (f[n][state]==ans1) ans2 += t[n][state];
    cout << ans1 << " " << ans2;
	return 0;
}

CROSS12 – spoj

Đề bài:


Thuật toán:


Đầu tiên ta cần tính thời gian qua cầu của mỗi người (khi đi một mình). Có thể tính bằng tham lam như cách được sử dụng trong code ở trên hoặc kết hợp quy hoạch động với deque để tìm min trên đoạn tịnh tiến.

Độ phức tạp khi tính là $O(m)$ cho mỗi người, vì $r$ chỉ dao động từ 1 đến 100 nên ta dùng một mảng phụ để cache giá trị đã tính lại.

Sau khi tính xong, gọi thời gian qua cầu của $n$ người là $A(n)$, ta sắp xếp $A$ tăng dần.

Gọi $F(i)$ là thời gian ít nhất để những người từ 1 đến i qua cầu, ta có công thức:

$ F(1) = A(1) \ F(2) = A(2) \ F(i) = min \begin{cases} F(i-2) + A(1) + 2A(2) + A(i) & \quad (1)\ F(i-1) + A(1) + A(i) & \quad (2)\ \end{cases} $

Trong trường hợp $(1)$, ta cho $A(2)$ quay về, sau đó $A(i)$ và $A(i-1)$ qua cầu, sau đó $A(1)$ từ bên kia cầu quay về, $A(1)$ và $A(2)$ cùng qua cầu.

Trong trường hợp $(2)$, $A(1)$ quay về sau đó cùng $A(i)$ qua cầu.

Code:


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int time(int r, int m, const char *bridge) {
    int i = 0, res = 1;
    while (i + r <= m) {
        res++;
        i += r;
        while (bridge[i] == '1') i--;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (auto &x: a) cin >> x;
    string bridge; cin >> bridge;
    bridge = '0' + bridge + '0';
    vector<int> cache(101, 0);
    for (auto &x: a) {
        if (!cache[x]) x = cache[x] = time(x, m, bridge.data());
        else x = cache[x];
    }
    sort(a.begin(), a.end());
    if (n == 1) cout << a[0];
    else if (n == 2) cout << a[1];
    else {
        int f0 = a[0], f1 = a[1];
        for (int i=2; i<n; i++) {
            int f2 = min(f0 + a[0] + 2*a[1] + a[i], f1 + a[0] + a[i]);
            f0 = f1, f1 = f2;
        }
        cout << f1;
    }
    return 0;
}

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;
}

BCISLAND – ptit

Đề bài:


Thuật toán:


- Bài này chia ra làm các bước như sau:
+ B1: Tìm độ cao lớn nhất so với mặt nước biển. (Hmax)
+ B2: Với độ cao tăng thêm: extra = 1-&gt;Hmax ta sẽ loang bắt đầu từ các cạnh là biển loang vào những nới có độ (độ cao &lt;= extra).
VD: có bản đồ:
5 5 5 5 7
4 1 1 1 4
4 1 2 1 3
7 1 0 0 4
7 3 4 4 4
với extra=1 ta thu được check[][]:
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

+B3: Đếm số thành phần liên thông tại check[][] với các check[][]==0 bằng DFS;
Số thành phần liên thông &gt; 1 thì tại độ cao extra đó đảo bị chia cắt;
VD: ở bản đồ trên tại extra = 3 ta có check[][]:
0 0 0 0 0
0 1 1 1 0
0 1 0 1 1
0 1 1 1 0
0 1 0 0 0

Code:


#include <iostream>
using namespace std;
 
int n, m;
int seawater[102][102];
int Hmax=0;
void read ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			cin>>seawater[i][j];
			if (seawater[i][j]>Hmax) Hmax=seawater[i][j];
		}
	}
}
 
int check[102][102];
int check_connect[102][102];
void init ()
{
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
		{
			check[i][j]=0;
			check_connect[i][j]=0;
		}
	}
}
 
int extra;
int x_ar[]={+1, +0, -1, +0};
int y_ar[]={+0, -1, +0, +1};
void loang (int i, int j)
{
	check[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check[Y][X]==0 && seawater[Y][X]<=extra) loang (Y, X);
		}
	}
}
 
void DFS (int i, int j)
{
	check_connect[i][j]=1;
	for (int k=0; k<4; k++)
	{
		int X=j+x_ar[k];
		int Y=i+y_ar[k];
		if (X>=1 && X<=m && Y>=1 && Y<=n)
		{
			if (check_connect[Y][X]==0 && check[Y][X]==check[i][j]) DFS (Y, X);
		}
	}
}
 
int main ()
{
	int t=0;
	while (1)
	{
		cin>>n>>m;
		if (n==0 && m==0) break;
		t++;
		read ();
		int kt=0;
		for (int k=0; k<=Hmax; k++)
		{
			extra=k;
			init ();
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if ((i==1 || i==n || j==1 || j==m) && seawater[i][j]<=k && check[i][j]==0) loang (i, j);
				}
			}
			//dem lien thong?
			int count_connect=0;
			for (int i=1; i<=n; i++)
			{
				for (int j=1; j<=m; j++)
				{
					if (check_connect[i][j]==0 && check[i][j]==0)
					{
						count_connect++;
						DFS (i, j);
					}
				}
			}
			if (count_connect>1)
			{
				kt=1;
				break;
			}
		}
		if (kt==1) cout<<"Case "<<t<<": Island splits when ocean rises "<<extra<<" feet."<<endl;
		else cout<<"Case "<<t<<": Island never splits."<<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.

25 cách phối màu đẹp nhất cho website

Decode

Gimme Delivery

Kitchen Sink Studios

Stephen Gacheru

Craig Morrison

IFYC

Leaders – The Conference


Code Slingers

Tom, Dick & Harry


Atticus Pet Design Studio

Red Bowl Challenge


Viljami Salminen

La Moulade

Hello Studios


Mea Cuppa


Cheese Survival Kit


Tree House


Bloom


Half Of Us


Fuel


Shady Acres


Web Toolbar


Cloudberry


Enlightening Quotes


Kite Studio Architecture