Gợi ý PTIT round 6

  • Published on
    20-Jul-2016

  • View
    494

  • Download
    0

Embed Size (px)

DESCRIPTION

Algorithm

Transcript

  • Mt vi gi PTIT round 6

    Bi A: Chuyn i

    Duyt tt c cc on ri tnh th s lng cc s 1 c th c. Tnh sn s lng s 1 t ban

    u thc hin cho vic tnh ton nhanh hn.

    Bi B: Tp v

    Thc hin nh yu cu ca bi.

    Bi C: Ngi vn chuyn

    M hnh ha bi ton v th c hng.

    Chi ph t nh i n nh j l d * (khong cch manhattan ij) a[j].

    Sau s dng thut ton v ng i ngn nht nh Dijkstra, Floy gii quyt.

    Bi D: Kim tra bi tp

    C nhiu cch x l bi ton ny, mt trong s l s dng cy IT, x l update 1 phn t.

    Gi tree[i] l kt qu ca dy s m nt i ang qun l. Tree[1] qun l on 1 2^n.

    Gi height l s ln lp thu c kt qu ca dy s ca nt i.

    Nu height chn tree[i] = tree[2*i] ^ tree[2*i + 1];

    Nu height l tree[i] = tree[2*i] | tree[2*i +1];

    Khi thay i 1 s, ta thy rng n s ch nh hng 1 trong 2 dy s con ca dy ang xt. T

    xt trng hp update theo nt con.

    Bi E: Xa nh.

    Bi ton yu cu xa ln lt cc nh, ta s c cc th con mi v ta phi tnh ng i ngn

    nht ca tt c cc cp nh trong th ny.

    Nhn ngc li qu trnh, th li l thm ln lt cc nh v cnh vo th c trc. Bi

    ton s c gii quyt mt cch nhn n gin hn.

    S dng Floy tm ng i ngn nht gia tt c cc nh.

    Bi F: Dy s k diu

    Brute force (tru b). Thc hin kim tra cho n khi cc ch s t 0->9 xut hin y trong

    dy s n, 2n, ..., k*n.

    Bi G: V tranh

    Bi ton khng c g kh khn.

  • Bi H: ua thuyn

    Quy hoch ng.

    Gi s d l ng knh ln nht ca chic thuyn sao cho n c th i c t b bn tri sang

    b bn phi.

    Thm cc im ti cc v tr c ta bng vi cc vin (cc im nh hnh v). Xt tt

    c cc ng i t b di ln b trn (gi l ng ln), ta thy hnh trnh ca chic thuyn s

    ct tt c cc ng i ny. Vi mi ng ln ny, chic thuyn s i qua on c khong cch

    ln nht.

    Vy gi cost ca mi ng ln bng di cnh di nht trong ng ln , ta cn tm ng

    ln c cost nh nht.

    Cch x l khc: Cht nh phn tm gi tr d. Vi mi gi tr d, tm xem c th tm c

    ng ln, i t b di ln b trn hay khng? Nu c th chic thuyn c ng knh d khng

    th i qua, nu khng th d l mt gi tr tha mn.

    Bi I: Cy khung

    Tm cy khung nh nht. Thut ton Prim-set hoc Krusal.

    Vi mi cp nh ca th, ch cn lu li mt cnh c trng s nh nht.

    Bi J: Nh tr

    2 SAT problem

    S dng cht nh phn tm gi tr T nh nht tha mn yu cu (c th s dng vng FOR).

    Gi bin x_i l bin logic cho a tr th i. Mi a tr c 2 s la chn gio vin mi, x_i = 1

    nu a tr hc lp gio vin th nht, x_i = 0 nu hc lp ca gio vin cn li.

  • Vi mt gi tr T, ta dng th cha cc cung i khng. Vi mi nt, v cc cung ti cc nt

    i khng (cc a tr nm ngoi danh sch top T) ca n. Mt gi tr T tha mn nu nh tn

    ti mt b nghim (t_1, t_2, ..., t_n) sao cho khng vi phm cung i khng no.

    Mi cung i khng l mt biu thc logic. X l phn cn li nh mt bi ton 2-SAT thng

    thng.

    Bi ton 2-SAT pht biu nh sau:

    Cho m bin logic: a1, a2, ... , am v mt biu thc logic C c dng:

    C = (u1|v1) & ... & (un|vn)

    Trong ui v vi (1 i n) c thay bng bin logic a_j hoc (!a_j) no (1 j m).

    Hy gn gi tr TRUE/FALSE cho cc bin a1, a2, ..., a_m sao cho biu thc C nhn gi tr

    TRUE, hoc thng bo khng th lm c.

    Bi ton ny c gii hn n nh, v vy cng th x l bng cch duyt th sai. Ln lt th chn

    gi tr cho cc x_i, da vo th dng update gi tr cho cc nt k. Nu khng c vi phm

    no xy ra, th dng tha mn v T l mt gi tr ng.

    Tham kho thm v bi ton 2 SAT: http://www.cs.umd.edu/~gasarch/TOPICS/sat/