Thuật toán

MULONE – spoj

26/03/2018 by meoluoi2918 Leave a Comment

Đề bài:

http://vn.spoj.com/problems/MULONE/

Thuật toán:

(đang cập nhập)

Code:

C++ : https://ideone.com/0efsA9

const
  fi = '';//MULONE.INP';
  fo = '';//MULONE.OUT';
  maxn = 10000000;
var
  n,test,t : longint;
  kq : array[1..maxn] of longint;
 
procedure sol;
var
  i,nho,tong : longint;
  count : longint;
begin
  tong:=0; nho:=0; count:=0;
  for i:=1 to n do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=n-1 downto 1 do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=count downto 1 do write(kq[i]);
  writeln;
end;
 
BEGIN
  assign(input,fi); reset(input);
  assign(output,fo); rewrite(output);
  readln(T);
  for test:=1 to T do
    begin
      readln(N);
      sol;
    end;
  close(input);
  close(output);
END.

Chủ đề: Toán học Mức độ: quite hard

C11PNUM – spoj

26/03/2018 by meoluoi2918 Leave a Comment

Đề bài:

http://vn.spoj.com/problems/C11PNUM/

Thuật toán:

Sàng nguyên tố
Tính các tích k số nguyên tố liên tiếp để cập nhập cho kết quả

Code:

C++ : https://ideone.com/W6J79q

const   fi='';
        fo='';
        oo=3000000;
var     k,t,i,j,tt:longint;
        tam,n,res:qword;
        f:text;
        tmp:array[2..oo] of boolean;
        ngto:array[1..oo] of longint;
        d	:longint;
function max(a,b:qword):qword;
begin
        if a>b then exit(a) else exit(b);
end;
procedure xl;
var     i,j :longint;
begin
	for i:=1 to d-k+1 do
		begin
			tam :=1;
			for j:=i to i+k-1 do
			begin
				tam := tam*ngto[j];
			end;
                        if tam>n then break else res := max(res,tam);
		end;
end;
procedure init;
begin
        for i:=2 to trunc(sqrt(oo)) do
                if tmp[i]=false then
                        begin
                            j:=i*i;
                            while j<=oo do
                                begin
                                    tmp[j]:=true;
                                    j:=j+i;
                                end;
                        end;
        d:=0;
        for i:=2 to oo do
                if tmp[i]=false then begin inc(d); ngto[d]:=i; end;
        j:=d;
end;
procedure nhap;
begin
    assign(f,fi);reset(f);
    assign(output,fo);rewrite(output);
    read(f,t);
    for tt:=1 to t do
        begin
            read(f,n,k);
            res := 0;
            xl;
            if res=0 then writeln(-1) else writeln(res);
        end;
    close(f);close(output);
end;
begin
    init;
    nhap;
end.

Chủ đề: Sàng nguyên tố

Ứng dụng của đồ thị

26/03/2018 by meoluoi2918 Leave a Comment

Ta đang sống trong một thế giới mà mọi vật được liên kết, các thành phố được liên kết với nhau bởi các con đường, con người liên kết với nhau trên mạng xã hội… những liên kết như vậy chính là hình hài của đồ thị. Một trong những đồ thị lớn mà ai trong chúng ta cũng biết đó chính là Internet hay là mạng tìm kiếm Google.

Đồ thị được sinh ra từ nhu cầu giải quyết những vấn đề thực tế của đời sống. Ví dụ như là bài toán ‘7 cây cầu Königsberg’ từ những năm 1720. Đồ thị là một phần quan trọng trong Toán học rời rạc, là cơ sở của Tin học. Ứng dụng của nó vô cùng rộng, áp dụng vào trong nhiều lĩnh vực. Trong phạm vi bài viết, tác giải chỉ đề cập đến một vài ứng dụng thực tế cơ bản.

Bài toán bảy cây cầu

Tìm đường đi ngắn nhất

Trong thực tế, ta luôn phải lựa chọn đường đi ngắn nhất để đi sao cho tiết kiệm xăng. Đầu tiên là biểu diễn mạng giao thông dưới dạng đồ thị rồi sử dụng thuật toán tìm đường đi ngắn nhất. Thường thì mọi người sử dụng thuật toán Dijkstra nhưng giả dụ với dữ liệu không lồ như của Google Map thì thuật toán này không thể đáp ứng. Google đang sử dụng một thuật toán có tộc độ nhanh hơn nhiều thuật toán Dijkstra.

Tìm đường trên Google Maps

Nhưng nếu muốn tìm đường giữa Hà Nội và New York thì sao? Giữa chúng có hàng tỉ tỉ giao lộ thì phải làm thế nào?

Tô màu đồ thị

Ứng dụng điển hình của tô màu đồ thị là bài toán tô màu bản đồ. Làm sao để tô màu bản đồ sao cho không có hai vùng kề nhau có cùng màu và số màu cần dùng là ít nhất.

Biểu diễn bài toán dưới dạng đồ thị:

Coi mỗi vùng là một đỉnh
Hai đỉnh có cạnh nối với nếu hai vùng tương ứng kề nhau

Bài toán trở thành tô màu các đỉnh của đồ thị, giải quyết sẽ đơn giản hơn bài toán ban đầu.

Bài toán tô màu bản đồ

Một ứng dụng khác là trong bài toán xếp lịch ở UET, làm sao để xếp lịch thi cho sinh viên sao cho nếu sinh viên học môn A và môn B thì hai môn này không thi cũng lúc, ngoài ra kì thi cần kết thúc sớm nhất.

Với bài này ta giải quyết thế nào?

Gọi mỗi môn học là một đỉnh, hai đỉnh được nỗi với nhau nếu tồn tại học sinh học cả 2 môn này. Bài toán giờ trở thành bài toán tô màu cho các đỉnh.

Đồ thị hai phía

graph-yeulaptrinh.pw

Đồ thị ghép cặp hẹn hò

Đồ thị hai phía thường được dùng để mô hình các bài toán ghép cặp, quan hệ hôn nhân giữa tập những người đàn ông và tập những người phụ nữ, sinh viên chọn trường, thầy giáo chon tiết dạy trong thời khóa biểu v.v…

Chủ đề: Đồ thị Mức độ: ứng dụng

NKLUCK – spoj

22/03/2018 by Khanh Nguyen Leave a Comment

Đề bài:

http://vn.spoj.com/problems/NKLUCK/

Thuật toán:

A là số đoạn nhận X là phần tử trung vị
B là số đoạn nhận X + 1 là phần tử trung vị

=> Result = (A – B) / (n * (n + 1) / 2) ;

Để tính số đoạn nhận X là phần tử trung vị ta chuyển đổi mảng A về, nếu A[i] >= X => A[i] = 1 ngược lại A[i] = 0.

Một đoạn nhận X là trung vị khi và chỉ khi tổng của đoạn đó ko âm. Đến đây, ta dùng cây BIT để tính toán .

Code:

C++ : https://ideone.com/D2dy0F

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define long long long
 
const int N = 1e6+10;
 
class FenwickTree {
private:
    long t[N][2];
public:
    void update(int x, int type) {
        for (; x <= N; x += x & -x)
            t[x][type]++;
    }
    long get(int x, int type) {
        long res = 0;
        for (; x > 0; x -= x & -x)
            res += t[x][type];
        return res;
    }
} BIT;
 
int n, m, k;
int a[N], f[N], b[N];
 
void Enter() {
    scanf("%d%d", &n, &k);
    FOR(i, 1, n) scanf("%d", &a[i]);
}
 
long calc(int x, int type) {
    m = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i-1] + (a[i] >= x);
        b[++m] = 2 * f[i] - i - 1;
        b[++m] = 2 * f[i-1] - i;
    }
 
    sort(b + 1, b + m + 1);
 
    long res = 0;
    FOR(i, 1, n) {
        int cur = lower_bound(b + 1, b + m + 1, 2 * f[i - 1] - i) - b;
        BIT.update(cur, type);
        cur = lower_bound(b + 1, b + m + 1, 2 * f[i] - i - 1) - b;
        res += BIT.get(cur, type);
    }
    return res;
}
 
void Process() {
    long res = calc(k, 0) - calc(k + 1, 1);
    double ans = 1ll * n * (n + 1) / 2;
    ans = res / ans;
    printf("%.6lf", ans);
}
 
int main() {
 //   freopen("input.in", "r", stdin);
 
    Enter();
    Process();
 
    return 0;
}

Chủ đề: BIT, Tìm kiếm nhị phân

LATGACH4 – spoj

14/03/2018 by Khanh Nguyen Leave a Comment

Đề bài:

http://vn.spoj.com/problems/LATGACH4/

Thuật toán:

Code:

C++ : https://ideone.com/aZhwVM

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 111539786;
 
map <ll, ll> f;
 
ll get(ll n)
{
    if (f.count(n)) return f[n];
    ll k=n / 2;
    if (!(n % 2))
        return f[n]=(get(k)*get(k) + get(k-1)*get(k-1)) % mod;
    else
        return f[n]=(get(k)*get(k+1) + get(k-1)*get(k)) % mod;
}
main()
{
    int t, n;
    cin>>t;
    while (t--)
    {
        cin>>n;
        f[0]=f[1]=1;
        cout<<get(n)<<endl;
    }
}

Chủ đề: Khác

QHROAD – spoj

14/03/2018 by Khanh Nguyen Leave a Comment

Đề bài:

http://vn.spoj.com/problems/QHROAD/

Thuật toán:

Kruskal những đoạn đường không bị phá.
Duyệt các truy vấn từ Q về 1. Nếu join thì giảm số tplt

Code:

C++ : https://ideone.com/qG1hZ4

#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 = 1E5+3;
const ll oo = 1e18+3;
 
struct  edge {
	int u,v;
} e[MAXN];
int n, m, q, pa[MAXN], u , v, x, a[MAXN], tplt, ans[MAXN];
bool dt[MAXN];
 
int find(int u) {
	if (pa[u]!=u) pa[u] = find(pa[u]);
	return pa[u];
}
 
bool join(int u, int v) {
	int i = find(u);
	int j = find(v);
	if (i==j) return 0;
	else
	pa[i] = j;
	return 1;
}
 
int main() {
	cin >> n >> m >> q;
	FOR(i,1,m) {
		cin >> e[i].u >> e[i].v;
	}
	FOR(i,1,q) {
		cin >> x;
		dt[x] = 1;
		a[i] = x;
	}
	tplt = n;
	FOR(i,1,n) pa[i] = i;
	FOR(i,1,m)
	if (!dt[i]) {
		if (join(e[i].u,e[i].v)) tplt--;
	}
	FORD(i,q,1) {
		ans[i] = tplt;
		int id = a[i];
		if (join(e[id].u,e[id].v)) tplt--;
	}
	FOR(i,1,q) cout << ans[i] << endl;
   	return 0;
}

Chủ đề: Kruskal

Map (ánh xạ) trong C++

22/02/2018 by Aida Nana Leave a Comment

Map là một loại associative container. Mỗi phần tử của map là sự kết hợp của khóa (key value) và ánh xạ của nó (mapped value). Cũng giống như set, trong map không chứa các khóa mang giá trị giống nhau.

Trong map, các khóa được sử dụng để xác định giá trị các phần tử. Kiểu của khóa và ánh xạ có thể khác nhau.

Và cũng giống như set, các phần tử trong map được sắp xếp theo một trình tự nào đó theo cách so sánh.

Map được cài đặt bằng red-black tree (cây đỏ đen) – một loại cây tìm kiếm nhị phân tự cân bằng. Mỗi phần tử của map lại được cài đặt theo kiểu pair (xem thêm ở thư viện utility).

Khai báo:

#include <map>

…

map <kiểu_dữ_liệu_1,kiểu_dữ_liệu_2>

// kiểu dữ liệu 1 là khóa, kiểu dữ liệu 2 là giá trị của khóa.

Sử dụng class so sánh:

Dạng 1:

struct cmp{

bool operator() (char a,char b) {return a<b;}

};

.....

map <char,int,cmp> m;

Truy cập đến giá trị của các phần tử trong map khi sử dụng iterator: Ví dụ ta đang có một iterator là it khai báo cho map thì:

(*it).first;   // Lấy giá trị của khóa, kiểu_dữ_liệu_1

(*it).second;  // Lấy giá trị của giá trị của khóa, kiểu_dữ_liệu_2

(*it)          // Lấy giá trị của phần tử mà iterator đang trỏ đến, kiểu pair

it->first;  // giống như (*it).first

it->second; // giống như (*it).second

Capacity:

size : trả về kích thước hiện tại của map. ĐPT O(1)

empty : true nếu map rỗng, và ngược lại. ĐPT O(1).

Truy cập tới phần tử:

operator [khóa]: Nếu khóa đã có trong map, thì hàm này sẽ trả về giá trị mà khóa ánh xạ đến. Ngược lại, nếu khóa chưa có trong map, thì khi gọi [] nó sẽ thêm vào map khóa đó. ĐPT O(logN)

Chỉnh sửa

insert : Chèn phần tử vào map. Chú ý: phần tử chèn vào phải ở kiểu “pair”. ĐPT O(logN).
erase :

o xóa theo iterator ĐPT O(logN)

1. xóa theo khóa: xóa khóa trong map. ĐPT: O(logN).

clear : xóa tất cả set. ĐPT O(n).
swap : đổi 2 set cho nhau. ĐPT O(n).

Operations:

find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy iterator trỏ về “end” của map. ĐPT O(logN).

lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).
upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của map. ĐPT O(logN).

count : trả về số lần xuất hiện của khóa trong multiset. ĐPT O(logN)

Chương trình demo:

#include <iostream>

#include <map>

#include <vector>

using namespace std;

main() {

    map <char,int> m;

    map <char,int> :: iterator it;

    m['a']=1;
    m.insert(make_pair('b',2));
    m.insert(pair<char,int>('c',3) );

    // m={{'a',1}}
    // m={{'a',1};{'b',2}}
    // m={{'a',1};{'b',2};{'c',3}}

    cout << m['b'] << endl; m['b']++;     // In ra 2

    // m={{'a',1};{'b',3};{'c',3}}

    it=m.find('c');    // it trỏ tới phần tử khóa 'c'

    cout << it->first << endl; 
    cout << it->second << endl;
    // In ra 'c'
    // In ra 3

    m['e']=100;
    //m={{'a',1};{'b',3};{'c',3};{'e',100}}

    it=m.lower_bound('d'); 
    cout << it->first << endl; 
    cout << it->second << endl;
    // it tỏ tới phần tử khóa 'e'
    // In ra 'e'
    // In ra 100
    system("pause");
}

Chủ đề: Khác Mức độ: stl in c++

MULONE – spoj

Đề bài:

Thuật toán:

Code:

C11PNUM – spoj

Đề bài:

Thuật toán:

Code:

Ứng dụng của đồ thị

Tìm đường đi ngắn nhất

Tô màu đồ thị

Đồ thị hai phía

NKLUCK – spoj

Đề bài:

Thuật toán:

Code:

LATGACH4 – spoj

Đề bài:

Thuật toán:

Code:

QHROAD – spoj

Đề bài:

Thuật toán:

Code:

Map (ánh xạ) trong C++

Khai báo:

Sử dụng class so sánh:

Chuyên mục

THEO DÕI CHÚNG TÔI TRÊN FACEBOOK

BÀI VIẾT MỚI

BÌNH LUẬN MỚI

Quản lý blog

Đôi điều về YeuLapTrinh.pw

Các chủ đề:

Sử dụng Website

MULONE – spoj

Đề bài:

Thuật toán:

Code:

C11PNUM – spoj

Đề bài:

Thuật toán:

Code:

Ứng dụng của đồ thị

Tìm đường đi ngắn nhất

Tô màu đồ thị

Đồ thị hai phía

NKLUCK – spoj

Đề bài:

Thuật toán:

Code:

LATGACH4 – spoj

Đề bài:

Thuật toán:

Code:

QHROAD – spoj

Đề bài:

Thuật toán:

Code:

Map (ánh xạ) trong C++

Khai báo:

Sử dụng class so sánh:

Chuyên mục

THEO DÕI CHÚNG TÔI TRÊN FACEBOOK

Chọn mục bạn muốn xem!

BÀI VIẾT MỚI

BÌNH LUẬN MỚI

Quản lý blog

Đôi điều về YeuLapTrinh.pw

Các chủ đề:

Sử dụng Website