【正文】 【數(shù)據(jù)規(guī)?！? 對于 30%的數(shù)據(jù)， N ≤ 10000； 對于 100%的數(shù)據(jù)， N ≤ 202200； 對于所有的數(shù)據(jù)， Wi, Ci 不超過 231。 如果掛綴長度 L 與答案一致，而最小重量和 W 與答案不一致，該測試點則得4 分。第二行包含一個整數(shù) W，表示可以找到的長度為 L 的穩(wěn)定掛綴中的最小重量和。 【輸出文件】 輸出文件 包行兩行。 【輸 入文件】 輸入文件 第一行包含一個正整數(shù) N，表示商店擁有的珠綴數(shù)目。一個掛綴是穩(wěn)定的，當(dāng)且僅當(dāng)對于其上的每一個珠綴，它下方所有珠綴的重量和（不包含自身）不超過其掛鉤的承受能力。小 Q 想買一根足夠 長的掛綴，這樣顯得更有韻味 ? 然而商店的老板告訴小 Q，掛綴是不可能做到任意長的，因為每一個珠子都受到重力作用，對其上方的掛鉤有一定的拉力，而掛鉤的承受能力是有限的。每一個綴珠由三部分組成：分別是珠子、珠子上方的連接環(huán)與珠子下方的掛鉤（如下圖）。而我們的主人公小 Q，正想買一條漂亮的掛綴放 33 在寢室里作為裝飾。. Output For each input instance your program should print in one line the chain 27 with the largest possible number of exons, by enumerating the exons in the chain. The exons must follow the order of appearance (as defined in the statement of the problem). If there is more than one chain with the same number of exons, your program can print anyone of them. Sample Input 6 340 500 220 470 100 300 880 943 525 556 612 776 3 705 773 124 337 453 665 0 2 Sample Output 3 1 5 6 4 2 3 1 （ 例題 1） North America – Northeast 2022 Problem E Who is Still Alive? At various points in history a number of presidents (former and the current president) have been alive. For example, currently there are six living presidents: Ford, Carter, Reagan, Gee the Second (Gee H. Bush), Clinton, and Gee the Third (Gee W. Bush). Note: Gee 28 Washington was Gee the First. Write a program that takes as input the name, inauguration date, and date of death (if appropriate) of several presidents and produces as output the periods of time when the maximum number of current or former presidents are alive, together with the names of those presidents in alphabetical order. Note, there may be several such intervals and all must be listed in chronological order. Input The input to your program will start with a line that contains a single integer, N, that specifies the number of presidents to be considered. Each of the following N lines of input describes a single president. An input line for a president will consist of an identifier consisting of letters only. The identifier will be followed by the inauguration date, and by an optional date of death. Dates will be expressed in the form yyyy mm dd where yyyy represents a year, mm represents a month, and dd represents a day. If the president is still alive, no death date will be given. One or more white space characters will separate tokens on the input line. Note that if a president was inaugurated more than once, they may appear in the input more than once。va Tardos 著 清華大學(xué)出版社 4．《廣東省大學(xué)生程序設(shè)計競賽試題（ 20222022年）》 郭嵩山 黎俊瑜 林祺穎 著 電子工業(yè)出版社 5． CTSC 2022 Reports, By Guo Huayang 6．汪汀《〈 turtle〉解題報告》 2022集訓(xùn)隊作業(yè) 7. 朱晨光《基本數(shù)據(jù)結(jié)構(gòu)在信息學(xué)競賽中的應(yīng)用》 2022集訓(xùn)隊論文 26 【附錄】 Latin America South America 2022 Problem A Gene Assembly With the large amount of genomic DNA sequence data being made available, it is being more important to find genes (parts of the genomic DNA which are responsible for the synthesis of proteins) in these sequences. It is known that for eukaryotes (in contrast to prokaryotes) the process is more plicated, because of the presence of junk DNA that interrupts the coding regions of genes in the genomic sequence. That is, a gene is posed by several pieces (called exons) of coding regions. It is known that the order of the exons is maintained in the protein synthesis process, but the number of exons and their lengths can be arbitrary. Most gene finding algorithms have two steps: in the first they search for possible exons。要學(xué)會在解題過程中發(fā)現(xiàn)更好的規(guī)律，用編程復(fù)雜度和時間效率俱佳的方法進(jìn)行優(yōu)化，如利用決策的單調(diào)性，或運用一些簡單數(shù)據(jù)結(jié)構(gòu)維護等。雖然后者能解決更多的問題，但往往前者擁有更好的時間效率，實現(xiàn)或優(yōu)化起來更加容易。只有選擇了合適的關(guān)鍵字，才更容易解決這類問題。由于每個折點最多進(jìn)出棧一次，棧的維護需要的時間為 ? ?MO ，故預(yù)處理時間復(fù) 雜度為：棧操作 ? ?MO +二分查找 ? ? ? ?NOMO log? = ? ?NMO log ，總時間復(fù)雜度也就降為 ? ?? ?NMMO log 。其實可以用棧將預(yù)處理的時間復(fù)雜度進(jìn)一步降低： 先從左往右掃描，確定每個折點能被最左邊的哪個燈泡照到。 24 優(yōu)化： 若確定了區(qū)間，則接下來選點的復(fù)雜度顯然為 )log( MMO ,時間效率的優(yōu)劣取決于預(yù)處理每個折點能被哪段燈泡照到的時間。將剩余區(qū)間按位置重新排序，順序處理各區(qū)間。維護一個值 t ，記錄當(dāng)前已處理區(qū)間左端點坐標(biāo)的最大值，初始值為 ?? 。 顯然那些包含其它區(qū)間的區(qū)間已不必考慮，可以刪去。于是題目轉(zhuǎn)化為：給定 M 個區(qū)間，以及 N 個點，區(qū)間的兩端點都是這 N個點之一。我們可以在? ?2NMO 的時間內(nèi)算出某燈泡是否能照亮某折點。山景是一條折線，折點數(shù) 200?M 。如果山的邊界上某一點與燈 i 的連線不經(jīng)過山上的其他點，我們稱燈 i可以照亮該點。轉(zhuǎn)化后的問題和原問題完全一樣，這里就不再寫算法了。求團隊和旅行線路的最大配對數(shù)。 例題 ： CEOI 2022 trips 題目大意： 有 n 個團隊和 m 條旅行線路，每個團隊最多只能選一條旅行線路，每條旅行線路至多只能供一個團隊選擇。用二叉堆實現(xiàn)該優(yōu)先隊列，則每次操作的時間復(fù)雜度降為 ? ?nOlog 。處理某點時，先插入左端點小于等于該點坐標(biāo)且從未進(jìn)入過隊列的區(qū)間（插入?yún)^(qū)間順序和有序表一致，故每次可在 ??1O 時間內(nèi)判斷是否需要插入），再刪除右端點小于該點坐標(biāo)的區(qū)間，將優(yōu)先隊列里的區(qū)間中右端點 坐標(biāo)最小的與該點匹配并刪除。維護一個優(yōu)先隊列，以區(qū)間的右端點作為關(guān)鍵字。 實 現(xiàn)： 選點時直接模擬的時間復(fù)雜度為 ? ?nmO ，可用與例題 3相似的方法來對該算法進(jìn)行優(yōu)化。因此解 S 可經(jīng)過一系列的轉(zhuǎn)化變成解 S? ，且由于轉(zhuǎn)化時匹配數(shù)始終保持不變，所以 S? 也為最優(yōu)解，因此該算法中的所有匹配都在其中。⑶若 P 和 I 都出現(xiàn)在 S 里，設(shè) S 中 P 與 I? 匹配、 I 與 P? 匹配。⑵若 I 出現(xiàn)在 S 里、 P 未出現(xiàn)在 S 里，設(shè) S 中 I 與 P? 匹配。 仍然考慮該算法求出的任意匹配 ? ?IP, ，若 ? ? SIP ?, ，則可分以下三種情況討論：⑴若 P 出現(xiàn)在 S 里、 I 未出現(xiàn)在 S 里，設(shè) S 中 P 與 I? 匹配。 假設(shè)它們都不出現(xiàn)在 S 里，則 S 中還可以加上一對新的匹配 ? ?IP, ，與 S 為最優(yōu)解矛盾。 證明： 設(shè)某最優(yōu)解的匹配集合為 S ，該算法求出的一對匹配是第 P 個點和第 I 個區(qū)間。 算法： 將所有的點按坐標(biāo)從小到大排序， 順序處理每個 點。選出最while ? ?? ? ? ?ifkstackf ? {pop} push i 21 多的區(qū)間和相同數(shù)量的點，使對應(yīng)的區(qū)間和點構(gòu)成匹配關(guān)系。 有 n 個區(qū)間， m 個點。用二叉堆實現(xiàn)該優(yōu)先隊列，插入和刪除操作的時間復(fù)雜度都是? ?NOlog ，因此總時間復(fù)雜度為：排序 ? ?NNO log +動態(tài)規(guī)劃 ? ?NO +維護二叉堆? ? ? ?NONO log? = ? ?NNO log 。狀態(tài)轉(zhuǎn)移后，將區(qū)間 i 插入優(yōu)先隊列。處理區(qū)間 i 時，只要最小關(guān)鍵字區(qū)間的右端點坐標(biāo)小于 11?iT ，就刪除。 第三種優(yōu)化： 以左端點為關(guān)鍵字從小到大排序，按順序依次處理每個區(qū)間。綜上所述，該方法的總時間復(fù)雜度為 ? ? ? ? ? ? )l o g(l o g NNONONONO ??? 。由于一共 N 個區(qū)間，每個區(qū)間進(jìn)棧、出棧最多一次，故棧的維護的時間復(fù)雜度為 ? ?NO 。每次要將第 i 個區(qū)間壓入棧中時，做這樣的操作： 20 計算 ??if 的值時，可以借助棧找到一個區(qū)間 j ，使 ij TT 112 ?? 且 ??jf 最小，進(jìn)行狀態(tài)轉(zhuǎn)移。 第二種優(yōu)化： 建立一個棧 stack ， ??istack 表示處在棧中第 i 個位置的區(qū)間。 這樣做編程復(fù)雜度較高，且時間效率亦不是很好（雖然可以通過離散化稍微降低一點時間復(fù)雜度，但仍然系數(shù)巨大）。計算 ??if 的值時只要選取區(qū)間 ? ?12,11 ?? ii TT 中 f 的最小值進(jìn)行狀態(tài)轉(zhuǎn)移即可。建立一棵范圍是? ?EM, 的線段樹， 葉子節(jié)點是一個個整點坐標(biāo)。 則狀態(tài)轉(zhuǎn)移方程為： ? ? ? ? ? ?? ???? ?????? ??iiiiiiijij TTMifS TTMifSTTjfM i nif 2,1 2,1112|][1 ,最后的結(jié)果就是 ? ?]2,1[|][1 iiNi TTEifM in ???。 將所有區(qū)間按右端點坐標(biāo)從小到大排序，順序處理每個區(qū)間。則問題轉(zhuǎn)化為：選出一些區(qū)間，使它們覆蓋 ?