Gợi ý PTIT Summer Round 1

  • Published on
    21-Jul-2016

  • View
    546

  • Download
    0

Embed Size (px)

Transcript

  • Mt vi gi PTIT Summer Round 1

    Problem A: i ng no. Hm ccw (counter-clockwise) gia 3 im A, B, C. ccw(point A, B, C) cho bit hng quay ca

    vector AB ti vector AC.

    Hm ccw c tnh bng tch c hng ca vector AB v AC.

    Nu ccw = 0, c ngha l 3 im thng hng (gc quay bng 0).

    Nu ccw > 0, c ngha l quay sang tri (ngc chiu kim ng h).

    Nu ccw < 0 c ngha quay sang phi (theo chiu kim ng h).

    Hm ccw l mt trong nhng cng c rt hu hiu trong cc bi ton hnh hc, chng hn nh

    bi ton tm bao li ca mt tp hp im cho trc.

    Problem B: Hon v. Cn tm xem nhng s no cha xut hin trong hon v th thay n bng php bin i.

    Problem C: Cc triu i. Gii thut quy hoch ng.

    Gi F[i][j] l tn triu i di nht c th bt u bng ch ci i v kt thc bng ch ci j.

    Gi y, khi ta c mt ci tn S mi, xt ci tn ny c th ghp vi triu i no m ang c

    kt thc trng vi ch ci u ca S. T y ta xy dng c cng thc QH.

    Kt qu: max (F[i][i]) vi i l cc ch ci t a ti z.

    Problem D: on con c K phn t bng nhau. Gi s on con ny bt u ti v tr i v j l v tr u tin m dy a[ij] tha mn bi r

    rng cc v tr sau j s tha mn.

    Xt on con tip theo, l dy t a[i+1] ti a[k] vi k >= j+1 tha mn. K tha kt qu t on

    con trc, ta ch cn duyt t v tr j+1 k. T tng bi ton ny l duyt theo khung ca s.

    kim tra xem on c K phn t bng nhau khng, ta s m s lng ca mt gi tr trong

    on, c th dng map hoc ri rc ha d liu thc hin.

    Bi E: in tm . Ch , hin th k t \ ta phi vit l \\. Hoc c th in ra k t \ da vo m ASCII ca n.

  • Bi F: Nm . Bi ton khng kh. Ch cn vit mt hm quy m t cc bc i ca vin t trn xung

    di nh m t ca bi.

    Bi G: Tr chi vi nhng con s. Trng hp 1: Nu X >= 10^6, s c ti a B/X (max = 10^5) s l bi ca X. V vy, s dng

    mt vng FOR t A ti B tm tt c cc s chia ht cho X, sau kim tra thm iu kin cc

    ch s phi tha mn xut hin trong tp hp yu cu.

    Trng hp 2: X < 10^6, quy hoch ng c nh.

    Gi dp(n, prefix) l s bi ca X nm trong on [A, B] vi tin t l prefix v cn phi thm

    vo n ch s. Vi mi cp n, prefix, ta cn xt cc s nm trong on [prefix * 10^n (cn di),

    prefix*10^(n+1)-1 (cn trn)].

    Cng thc QH:

    FOR(i,0,9) if(isNum[i]) dp(n, prefix) += dp(n-1, prefix*10+i).

    Trong isNum[i] tr v true nu i l mt trong nhng ch s ca tp hp cho.

    Nu A

  • Vi loi 2, gi s xt cp X-Y(mt phng x = x1 v y = y1), chiu hcn loi Y ln mt phng x =

    x1, s ch cn l mt on thng. Xt tt c cc hnh ch nht nm trn mt phng x = x1, ta cn

    tm xem c bao nhiu hcn giao nhau vi on thng kia?

    Bi I: m s min. Hnh hc + th phng.

    nh l Euler trong th phng: n-m+r = 2, trong n l s nh, m l s cnh v r l s min

    to bi th phng ny.

    Vi n hnh ch nht cho, tm tt c cc giao im. Sau dng nn th mi t tt c cc

    im c trn mt phng. Duyt DFS tm cc thnh phn lin thng, vi mi thnh phn lin

    thng, p dng cng thc Euler tm ra s min.

    Bi J: Dy tng di nht. 3 bi ton sau k tha nhau.

    Bi ton trn khng gian 1 chiu: Dy con tng di nht (LIS).

    Gi dp[i] l di dy con tng di nht kt thc ti phn t a[i].

    Gi L[i] l tp hp tt c cc phn t x c dp[x] = i. Thc ra ta ch cn quan tm ti gi tr nh

    nht trong tp hp L[i].

    Duyt t u ti cui, ti phn t th i, ta cn cht nh phn, tm di leng ln nht sao cho tp

    hp L[leng] != rng, sau push a[i] vo tp hp L[leng+1].

    di ca dy con tng di nht bng ch s i ln nht sao cho L[i] c t nht 1 phn t.

    Khng gian 2 chiu: tm mt tp hp sao cho c th to thnh dy tng di nht:

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

    u tin cn sort cc im theo th t x tng dn.

    Gi dp[i] l di dy tng di nht kt thc ti im a[i], L[i] l tp hp tt c cc im x c

    dp[x] = i.

    Vi bi ton trong khng gian 1D, coi mi im gm 2 thnh phn, th vi mi honh x ch

    c mt tung y duy nht. iu khc bit l trong khng gian 2D, c th c nhiu im c

    chung honh x.

    Trong tp hp L[i], ta cng ch cn quan tm ti phn t nh nht, v thnh phn x c sp

    xp theo th t tng dn nn ch cn quan tm ti im c thnh phn y nh nht trong tp hp

    L[i].

  • Mt trong nhng cch x l kh hiu qu l sort cc im c chung thnh phn x theo th t

    gim dn ca thnh phn y. Khi s khng phi x l trng hp trng thnh phn x do thao

    tc push a[i] vo tp hp L[leng+1].

    Khng gian 3 chiu:

    trnh trng hp x l trng, trc ht cng sort cc im theo u tin x tng dn, y gim

    dn, z gim dn.

    Ti im a[i], cn tm L[leng] vi leng ln nht sao cho L[leng] c mt phn t P no tha

    mn P.x < a[i].x && P.y < a[i].y && P.z < a[i].z .

    Ch quan tm ti thnh phn y v z, ta s thy L[leng] khng tn ti 2 im P, Q no sao cho P <

    Q. (Tht vy, nu tn ti im P v Q theo th t sao cho P.y < Q.y v P.z < Q.z, do P xut hin

    trc Q nn P.x < Q.x. Do , im Q s phi nm trong tp hp L[leng+1] ch khng phi tp

    hp L[leng]).

    gii quyt c bi ton, ta cn tng tc cho thao tc kim tra v push im a[i], nh vy

    cn phi duy tr tp hp L[leng] theo th t. V ch cn quan tm ti cc im c thnh phn y, z

    nh nht, mi ta y ch lu li mt im duy nht.

    Thao tc update khi push im a[i] vo tp hp L[leng]: cn xa b cc im Q >= a[i].