Archives for Tháng Một 2017


VO17TV – spoj

Đề bài

Thuật toán

  • (đang cập nhập)

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 + 2;
const int base1 = 1e9 + 7;
const int base2 = 1e9 + 289;
const int N = 5000;
 
using namespace std;
struct data
{
    int x1,x2,id;
}dd[MAXN];
int n,k;
int len[MAXN];
ll M1[MAXN],M2[MAXN],h1[51][MAXN],h2[51][MAXN];
 
void build1(ll h[],string s,int n)
{
    FORE(i,1,n)
    h[i] = (h[i-1]*M1[1] + s[i-1])%base1;
}
 
int get1(ll h[],int l,int r)
{
    return (h[r] - h[l-1]*M1[r-l+1] + 1ll*base1*base1)%base1;
}
 
void build2(ll h[],string s,int n)
{
    FORE(i,1,n)
    h[i] = (h[i-1]*M2[1] + s[i-1])%base2;
}
 
int get2(ll h[],int l,int r)
{
    return (h[r] - h[l-1]*M2[r-l+1] + 1ll*base2*base2)%base2;
}
 
int cmp(data a,data b)
{
    if (a.x1 != b.x1) return a.x1 < b.x1;
    if (a.x2 != b.x2) return a.x2 < b.x2;
    return a.id < b.id;
}
 
int check(int r)
{
    int cnt = 0;
    FORE(i,1,n)
    {
        int rr = len[i] - r + 1;
        FORE(j,1,rr)
        {
            int x1 = get1(h1[i] , j , j + r - 1);
            int x2 = get2(h2[i] , j , j + r - 1);
            dd[++cnt].x1 = x1;
            dd[cnt].x2 = x2;
            dd[cnt].id = i;
        }
    }
    sort(dd+1,dd+cnt+1,cmp);
    int dem = 0;
    FORE(i,1,cnt)
    if (dd[i].x1 != dd[i-1].x1 || dd[i].x2 != dd[i-1].x2)
    {
        dem = 1;
    }
    else
    if (dd[i].id != dd[i-1].id)
    {
        ++dem;
        if (dem == k) return 1;
    }
    return 0;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("vo17tv.inp", "r", stdin);
    freopen("vo17tv.ans", "w", stdout);
    #endif
    M1[1] = 2802; M2[1] = 2208;
    cin>>n>>k;
    int lenmi = 0;
    FORE(i,1,n)
    {
        string st;
        cin>>st;
        len[i] = st.size();
        build1(h1[i] , st , len[i]);
        build2(h2[i] , st , len[i]);
        lenmi = max(lenmi , len[i]);
    }
    FORE(i,2,lenmi) M1[i] = M1[i-1]*M1[1]%base1;
    FORE(i,2,lenmi) M2[i] = M2[i-1]*M2[1]%base2;
    int l = 1;
    int r = lenmi;
    int ans = 0;
    while(l <= r)
    {
        int mid = (l+r)>>1;
        if (check(mid))
        {
            l = mid + 1;
            ans = mid;
        }
        else
            r = mid - 1;
    }
    cout<<ans<<endl;
    return 0;
}

VO17PHD – 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 = 5000;
typedef pair<ll,ll> ii;
typedef pair<ii,int> iii;
 
int n,m;
int p[MAXN];
ll d[MAXN],f[MAXN];
priority_queue<iii> h;
vector<int> a[MAXN],c[MAXN];
 
void dijkstra()
{
    FORE(i,1,n) d[i] = 1e15;
    FORE(i,1,n) f[i] = 0;
    d[1] = 0;
    f[1] = p[1];
    h.push(iii(ii(0,p[1]),1));
    while(h.size())
    {
        int u = h.top().Y;
        ll du = -h.top().X.X;
        ll fu = h.top().X.Y;
        h.pop();
        if (du != d[u] || f[u] != fu) continue;
        for(int i = 0; int v = a[u][i]; ++i)
        if (d[v] > d[u] + c[u][i])
        {
            d[v] = d[u] + c[u][i];
            f[v] = f[u] + p[v];
            h.push(iii(ii(-d[v],f[v]),v));
        }
        else
        if (d[v] == d[u] + c[u][i] && f[v] < f[u] + p[v])
        {
            f[v] = f[u] + p[v];
            h.push(iii(ii(-d[v],f[v]),v));
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("vo17phd.inp" , "r" , stdin);
    //("vo17phd.out" , "w" , stdout);
    cin>>n;
    FORE(i,1,n) cin>>p[i];
    cin>>m;
    FORE(i,1,m)
    {
        int u,v,w;
        cin>>u>>v>>w;
        a[u].pb(v); c[u].pb(w);
        a[v].pb(u); c[v].pb(w);
    }
    FORE(i,1,n) a[i].pb(0);
    dijkstra();
    if (d[n] == 1e15) cout<<"impossible"<<endl;
    else cout<<d[n]<<' '<<f[n]<<endl;
    return 0;
}

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

Các kiểu dữ liệu trong Pascal

Kiểu số nguyên

Các kiểu số nguyên

Tên kiểu Phạm vi Dung lượng
Shortint -128 đến 127 1 byte
Byte 0 đến 255 1 byte
Integer -32768 đến 32767 2 byte
Word 0 đến 65535 2 byte
LongInt -2147483648 đến 2147483647 4 byte

int64          -2^63…2^63-1
qword         0…2^64-1

Các phép toán trên kiểu số nguyên

Các phép toán số học:

+, -, *, / (phép chia cho ra kết quả là số thực).

Phép chia lấy phần nguyên: DIV  (Ví dụ : 34 DIV 5 = 6).

Phép chia lấy số dư: MOD (Ví dụ:  34 MOD 5 = 4).

Các phép toán xử lý bit:

Trên các kiểu ShortInt, Integer, Byte, Word có các phép toán:

  • NOT, AND, OR, XOR.
A B A AND B A OR B A XOR B NOT A
1 1 1 1 0 0
1 0 0 1 1 0
0 1 0 1 1 1
0 0 0 0 0 1
  • SHL (phép dịch trái): a SHL n Û a ´ 2n
  • SHR (phép dịch phải): a SHR n Û a DIV 2n

Kiểu logic

– Từ khóa: BOOLEAN

– miền giá trị: (TRUE, FALSE).

– Các phép toán: phép so sánh (=, <, >) và các phép toán logic: AND, OR, XOR, NOT.

Trong Pascal, khi so sánh các giá trị boolean ta tuân theo qui tắc: FALSE < TRUE.

Giả sử A và B là hai giá trị kiểu Boolean. Kết quả của các phép toán được thể hiện qua bảng dưới đây:

A B A AND B A OR B A XOR B NOT A
TRUE TRUE TRUE TRUE FALSE FALSE
TRUE FALSE FALSE TRUE TRUE FALSE
FALSE TRUE FALSE TRUE TRUE TRUE
FALSE FALSE FALSE FALSE FALSE TRUE

Kiểu số thực

Các kiểu số thực:

Tên kiểu Phạm vi Dung lượng
Single 1.5´10-45 ® 3.4´10+38 4 byte
Real 2.9´10-39 ® 1.7´10+38 6 byte
Double 5.0´10-324 ® 1.7´10+308 8 byte
Extended 3.4´10-4932 ® 1.1´10+4932 10 byte

Chú ý: Các kiểu số thực Single, Double và Extended yêu cầu phải sử dụng chung với bộ đồng xử lý số hoặc phải biên dich chương trình với chỉ thị {$N+} để liên kết bộ giả lập số.

Các phép toán trên kiểu số thực:          

+, -, *, /

Chú ý: Trên kiểu số thực không tồn tại các phép toán DIV và MOD.

Các hàm số học sử dụng cho kiểu số nguyên và số thực:

SQR(x):                                  Trả về x2

SQRT(x):                                Trả về căn bậc hai của x (x³0)

ABS(x):                                   Trả về |x|

SIN(x):                                                Trả về sin(x) theo radian

COS(x):                                  Trả về cos(x) theo radian

ARCTAN(x): Trả về arctang(x) theo radian

LN(x):                                     Trả về ln(x)

EXP(x):                                  Trả về ex

TRUNC(x):                Trả về số nguyên gần với x nhất nhưng bé hơn x.

INT(x):                                               Trả về phần nguyên của x

FRAC(x):                               Trả về phần thập phân của x

ROUND(x):                Làm tròn số nguyên x

PRED(n):                               Trả về giá trị đứng trước n

SUCC(n):                               Trả về giá trị đứng sau n

ODD(n):                                 Cho giá trị TRUE nếu n là số lẻ.

INC(n):                                   Tăng n thêm 1 đơn vị (n:=n+1).

DEC(n):                                  Giảm n đi 1 đơn vị (n:=n-1).

Kiểu ký tự

– Từ khoá: CHAR.

– Kích thước: 1 byte.

– Để biểu diễn một ký tự, ta có thể sử dụng một trong số các cách sau đây:

  • Đặt ký tự trong cặp dấu nháy đơn. Ví dụ ‘A’, ‘0’.
  • Dùng hàm CHR(n) (trong đó n là mã ASCII của ký tự cần biểu diễn). Ví dụ CHR(65) biễu diễn ký tự ‘A’.
  • Dùng ký hiệu #n (trong đó n là mã ASCII của ký tự cần biểu diễn). Ví dụ #65.

– Các phép toán: =, >, >=, <, <=,<>.

* Các hàm trên kiểu ký tự:

UPCASE(ch): Trả về ký tự in hoa tương ứng với ký tự ch. Ví dụ: UPCASE(‘a’) = ‘A’.

ORD(ch): Trả về số thứ tự trong bảng mã ASCII của ký tự ch. Ví dụ ORD(‘A’)=65.

CHR(n): Trả về ký tự tương ứng trong bảng mã ASCII có số thứ tự là n. Ví dụ: CHR(65)=’A’.

PRED(ch): cho ký tự đứng trước ký tự ch. Ví dụ: PRED(‘B’)=’A’.

SUCC(ch): cho ký tự đứng sau ký tự ch. Ví dụ: SUCC(‘A’)=’B’.

Tài liệu chuyên đề thuật toán duyệt

Hiện nay chưa có tài liệu chính thức dành cho lớp Chuyên Tin khối THPT. Mà chỉ tồn tại ở dưới dạng tên chuyên đề của Bộ Giáo dục gửi về cho các trường. Do vậy việc dạy và học gặp nhiều khó khăn trong việc thống nhất về nội dung cũng như mức độ về kiến thức chuyên môn. Nên việc nghiên cứu và xây dựng chuyên đề này là thực sự cần thiết.

Mục đích của chuyên đề là truyền tải một cách tổng quát, chi tiết và sự thống nhất về mặt nội dung để người đọc dễ hiểu và thấy được tầm quan trọng của bài toán liệt kê tổ hợp và một số bài tập ứng dụng trong Tin học dành cho học sinh chuyên tin ở trường THPT.

Nội dung của chuyên đề đã được các tác giả chọn lọc qua chương trình đã thực dạy tại trường và tham khảo của một số đồng nghiệp khác trong nước.

Kiến thức là vô hạn, trong chuyên đề này chúng tôi đã có gắng sáng  tạo, sưu tầm và trao đổi một cách tốt nhất có thể về mặt lý thuyết, các bài tập ứng dụng và các bài tập trong các kỳ thi trong nước để tạo thành cuốn tài liệu hiệu quả dành cho giáo viên và các em học sinh đam mê tin học chính thức làm tài liệu cho mình trong quá trình học tập và nghiên cứu.

THPT Chuyên Bắc Giang.

TẢI VỀ: CHUYEN-DE-DUYET-CAU-HINH-TO-HOP-YEULAPTRINH.PW

Các hàm toán học có sẵn trong C++

YeuLapTrinh.pw xin được tóm tắt một số các  hàm toán học hay dùng. Các hàm này đều được khai báo trong file nguyên mẫu math.h.

  1. Các hàm số học
  • abs(x), labs(x), fabs(x) : trả lại giá trị tuyệt đối của một số nguyên, số nguyên dài và số thực.
  • pow(x, y) : hàm mũ, trả lại giá trị x lũy thừa y (xy).
  • exp(x) : hàm mũ, trả lại giá trị e mũ x (ex).
  • log(x), log10(x) : trả lại lôgarit cơ số e và lôgarit thập phân của x (lnx, logx) .
  • sqrt(x) : trả lại căn bậc 2 của
  • atof(s_number) : trả lại số thực ứng với số viết dưới dạng xâu kí tự
  1. Các hàm lượng giác
  • sin(x), cos(x), tan(x) : trả lại các giá trị sinx, cosx,

 

Bạn nên tham khảo bài viết: Các hàm làm tròn số trong C++

 

Các phần mềm lập trình .NET, VB.NET, C#, ASP.NET

Công cụ để lập trình .NET (VB.NET, C#, ASP.NET) gồm có:

1. Visual Studio 2008 Professional Edition

2. Microsoft Visual Studio 2010 Ultimate v10.0.30319.1 Final Full Crack Actived

Bạn hãy chỉ chọn một trong hai công cụ trên.

1. Visual Studio 2008 Professional Edition
Dung lượng: 3.30 GB

http://download.microsoft.com/download/8/1/d/81d3f35e-fa03-485b-953b-ff952e402520/VS2008ProEdition90dayTrialENUX1435622.iso

Sau khi cài đặt xong, vào Start –> Control Panel –> Settings –> Add or Remove Programs
Chọn Visual Studio 2008 Professional Edition – ENU click chọn Change/Remove
Chờ 1 chút cho nó load lên, click Next
Nếu bản của bạn đang là bản dùng thử, nhìn xuống dưới cùng của cửa sổ Microsoft VS 2008 Setup Maintenance sẽ có chỗ Upgrade key.
Bạn điền key sau vào và click vào Upgrade là xong
Khi Crack xong, vào chương trình VS 2008 Pro Edition, click Help –> About nó sẽ hiện ra cửa sổ như sau và mất đi dòng Trial

Key: XMQ2Y-4T3V6-XJ48Y-D3K2V-6C4WT

– Hướng dẫn Crack trên Windows 7:
Trên Windows 7, thì cách trên không hoạt động đc. Bạn hãy làm như sau:
+ Dùng Ultra ISO để mở file VS 2008, tìm tới file setup.sdb (nằm trong thư mục Setup).
+ Mở file setup.sdb bằng Notepad hoặc bất kỳ Editor nào.
+ Tìm tới dòng [Product Key] và sửa giá trị cho nó : XMQ2Y-4T3V6-XJ48Y-D3K2V-6C4WT
Sau khi sửa xong, hãy lưu file setup.sdb lại và tiến hành cài đặt bình thường. Sau khi cài đặt xong, nó sẽ tự động Active cho bạn.

2. Microsoft Visual Studio 2010 Ultimate v10.0.30319.1 Final Full Crack Actived x86:

http://www.fshare.vn/folder/TX9VZR3V3T

Hoặc: Visual Studio 2010 Ultimate x86
http://up.4share.vn/f/66575f54545e5756/en_visual_studio_2010_ultimate_x86_dvd_509116.iso.file

3. Hệ quản trị CSDL:

Hệ quản trị CSDL là phần vô cùng quan trọng trong quá trình lập trình. Microsoft đã phát triển nhiều những phần mềm giúp ta xây dựng CSDL, tôi xin được chia sẻ với bạn ở bên dưới.
a. SQL Server 2005:
Bước 1: Cài phần mềm http://www.microsoft.com/downloads/en/details.aspx?FamilyId=C243A5AE-4BD1-4E3D-94B8-5A0F62BF7796&displaylang=en

Bước 2: Cài thêm http://go.microsoft.com/fwlink/?linkid=65109

b. SQL Server 2008:

SQL Server 2008 có nhiều phiên bản khác nhau, trong đó bản Express   là  bản thấp nhất, được Microsoft cung cấp miễn phí cho người dùng với   mục  đích học tập và ứng dụng vào những ứng dụng nhỏ, không yêu cầu  cao  về  các tính năng khác ngoài việc lưu trữ và xử lý đơn giản.

Yêu cầu về phần cứng và hệ điều hành sử dụng:– Hệ điều hành tối thiểu: Windows XP SP3, Windows Wista SP1, Windows 7, Windows 2003 SP2.
Phần cứng: Pentium IV 2Gb MHz trở lên. Tối thiểu  1 GB RAM. Ổ cứng 10 GB.

Link Download :
– Để cài đặt SQL Server 2008 Express download về tại địa chỉ:
http://www.microsoft.com/en-us/download/details.aspx?id=1695

Để cài đặt SQL Server 2008 Express with management tools download về tại địa chỉ:
http://www.microsoft.com/en-us/download/details.aspx?id=22973

Đối với WinXp bắt buộc phải cài thêm: Bạn phải có Windows PowerShell 1.0
http://go.microsoft.com/fwlink/?LinkId=120552

Ngoài ra: Nếu máy đã cài xong VS2010 thì chỉ cần cài: Microsoft SQL Server 2008 Management Studio Express
tại địa chỉ: http://www.microsoft.com/en-us/download/details.aspx?id=7593

 

Chú ý : đối với máy tính cài Windows XP, khi cài SQL Express 2008, nó sẽ thường báo lỗi máy tính phải có cài .Net Framework 2.0 SP2 và  Windows Installer 4.5 rồi nó mới cho cài SQL Express 2008. Thì các bạn phải down Net framework 2.0 sp2Windows Installer 4.5 ở link trên về cài đặt xong rồi mới cài Sql Express 2008.
Các bước cài đặt :
Bước 1 : Tại màn hình cài đặt SQL Server 2008 bạn chọn mục Installation sau đó chọn New SQL Server stand-alone installation or add features to an existing installation

– Bước 2 : Tại màn hình Setup Support Rules  chọn OK

Bước 3 : Tại màn hình “Product Key“, chọn Next để tiếp tục

– Bước 4 : Tại màn hình License Term, đánh dấu chọn nút “I accept the licence terms”, rồi chọn “Next”

Bước 5 : Tại màn hình “setup support files”  nhấn nút “install” để tiếp tục.

Bước 6 : tại màn hình “Setup Support Rules“, nếu mỗi thứ suôn sẽ, thì nhấn nút “Next” để tiếp tục.

Bước 7 : Trên màn hình “features selection“, nhất nút “Sellect All” để chọn tất cả, sau đó nhấn nút “Next“.

Bước 8 : tại màn hình “instance Configuratio”, có 2 lựa chọn : chọn như hình dưới, rồi nhấn nút Next để tiếp tục ….

Bước 9 : Chọn Next để tiếp tục.

Bước 10 : Chọn “Account Name” và chọn là NT AUTHORITY\NETWORK như trong hình sau đây, sau đó nhấn Next để tiếp tục.

Bước 11 : Trên màn hình “Database Engine Configuration“, trong phần Account Provisioning, ta chọn “Windows Authotication Mode” hoặc “Mixed Mode” đều được cả
+ Chọn “Windows Authotication Mode” không cần nhập PassWord, để đơn giản ta nên chọn “Windows Authotication Mode
+ Chọn “Mixed Mode” thì ta phải nhập PassWord.
+ Sau cùng ta nhấn vào nút “Add Current User“, rồi nhấn nút Next để tiếp tục.

Bước 12 : nhấn nút “Next” để tiếp tục

Bước 13 : nhấn nút “Next” để tiếp tục

Bước 14 : nhấn nút “Install” để tiến hành cài đặt, quá trình cài đặt khoảng 3 phút …

Bước 15 : Nhấn nút “Next” để hoàn thành quá trình cài đặt. Cuối cùng cũng xong