COMNET – spoj

Đề bài:

Tóm tắt đề:

Cho M đường truyền có các chi phí wi, các truy vấn người ta thay đổi trọng số một số cạnh và hỏi xem cạnh thứ k có thể loại bỏ vì nó không thuộc vào cây khung nhỏ nhất của đồ thị hay không.

Thuật toán:

-Sau khi thay đổi trọng số các cạnh theo đề bài (nếu các cạnh có trọng số bằng nhau thì ưu tiên xét cạnh k đứng đầu), tìm cây khung nhỏ nhất của đồ thị và in ra ‘YES’ hay ‘NO’ tương ứng là cây trả lời. ĐPT O(test*nlogn)
-Thuật toán trên sẽ giúp bạn có được 60->70 điểm, đề ăn full bạn cần thay đổi một chút trước khi tìm cây khung: Vẫn thay đổi trọng số các cạnh theo đề bài, nhưng không sort lại các cạnh mà tìm các cạnh có trọng số nhỏ hơn trọng số của cạnh thứ k, hợp nhất các gốc lại.

Kiểm tra xem hai đỉnh của cạnh thứ k đã thuộc vào cây khung hay chưa rồi in ra ‘YES’ hay ‘NO’ tương ứng. ĐPT O(test*n).

Code:

#include <iostream>
#include <vector>
using namespace std;
 
#define LL long long
 
struct universe {
    vector<int> cha, rank;
    universe(int n): cha(n + 1), rank(n + 1, 0) {
        for (int i=1; i<=n; i++) cha[i] = i;
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] > rank[v]) cha[v] = u;
        else cha[u] = v;
        return true;
    }
};
 
struct pack { int u, v; };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m, Q; cin >> n >> m >> Q;
        vector<pack> e(m);
        vector<int> w(m);
        for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
        while (Q--) {
            int id; cin >> id; id--;
            int s; cin >> s;
            vector<int> ww(w);
            while (s--) {
                int t, w; cin >> t >> w;
                ww[t-1] = w;
            }
            universe a(n);
            for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
                a.join(e[i].u, e[i].v);
            }
            if (a.join(e[id].u, e[id].v)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
    return 0;
}

MINROAD – spoj

Đề bài

Thuật toán

Ta lưu 2*n điểm vào mảng T:

  • T[i].d là khoảng cách đến vị trí bắt đầu của con đường
  • T[i].k là 1 nếu là cây tùng, là 2 nếu là cây trúc

Sắp xếp mảng T theo thứ tự tăng dần T[i].d

Với mỗi T[i], ta phải tìm vị trí X sao cho từ T[i] đến T[x] có ít nhất a cây tùng và b cây trúc. Đặt F[i]=X.

Dễ dàng nhận thấy: F[i] <= F[i+1] nên ta có thể sử dụng 2 vòng For để tính toán kết quả như sau:

For i=1 to 2*N do 
 For j=F[i-1] to 2*N do ……..
Thay vì dùng mảng F, bạn hoàn toàn có thể sử dụng biến chạy mà thôi

Độ phức tạp: O(N log N).

Code

uses    math;
const   fi='';
        fo='';
        maxn=300000;
type    arra=array[0..maxn] of longint;
var     tung,cuc,d,tu,cu:arra;
        kieu:array[0..maxn] of byte;
        i,j,n,a,b:longint;
        f:text;
        res,tmp:longint;
procedure QS(l,r:longint);
Var i,j,x,w:longint;
Begin
x:=d[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(d[i]<x) do i:=i+1;
     While (x<d[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=kieu[i];kieu[i]:=kieu[j];kieu[j]:=w;
          w:=d[i];d[i]:=d[j];d[j]:=w;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,a,b);
    for i:=1 to n do
        readln(f,d[i],kieu[i]);
    close(f);
end;
procedure xuly;
var     t,c,k:longint;
begin
    t:=0; c:=0;
    qs(1,n);
    for i:=1 to n do
        if kieu[i]=1 then begin inc(t); tung[t]:=i; end
        else begin inc(c); cuc[c]:=i; end;
    for i:=1 to n do
    begin
        tu[i]:=tu[i-1];
        cu[i]:=cu[i-1];
        if kieu[i]=1 then inc(tu[i]);
        if kieu[i]=2  then inc(cu[i]);
    end;
if (tu[n]<a) or(cu[n]<b) then exit;
    i:=max(tung[a],cuc[b]);
    k:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
    res:=d[i]-d[k];
    inc(i);
    while i<=n do
    begin
        tmp:=min(tung[tu[i]-a+1],cuc[cu[i]-b+1]);
        if d[i]-d[tmp]<res then res:=d[i]-d[tmp];
        inc(i);
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    if res=0 then writeln(f,-1) else
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    xuly;
    xuat;
end.

COLOREC – spoj

Đề bài:

Thuật toán:

Với bài này ta gán mỗi màu cho một bit từ 0 đến 3, sau đó có thể quy hoạch động để đếm như sau:

Cố định 2 dòng i và j, ta đếm số hình chữ nhật 4 màu có cạnh nằm trên dòng i và j như sau:

Gọi F(c) là số cặp đỉnh có màu là c (c là tổng màu của 2 đỉnh đó) thì số hình chữ nhật 4 màu nhận được từ 2 đỉnh đó là F(15 – c).

Từ đó ta có thể dùng 3 vòng for để tính như trong code.

Code:

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector< vector<int> > a(401, vector<int>(401, 0));
    while (n--) {
        int u, v, c; cin >> u >> v >> c;
        a[u + 200][v + 200] = 1 << (c - 1);
    }
#define rep(i, a, b) for (int i=a; i<=b; i++)
#define LL long long
    LL res = 0;
    rep(i, 0, 400) rep(j, 0, i) {
        vector<LL> f(16, 0);
        rep(k, 0, 400) if (a[i][k] && a[j][k] && a[i][k] != a[j][k]) {
            int c = a[i][k] | a[j][k];
            res += f[15 - c];
            f[c]++;
        }
    }
    cout << res;
    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;
}

Tổng hợp đề thi HSGQG môn Tin học các năm

YeuLapTrinh xin được tổng hợp lại đề thi HSGQG các năm để các bạn tiện tham khảo:

 

 

++++++++++++++

(đang tiếp tục cập nhập)

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