2025.8.22 NOIP模擬賽

分?jǐn)?shù) 135/400
排名 2/9

T1

題目描述：

(1≤n≤1e7)

開(kāi)局開(kāi)T1
如果沒(méi)有重復(fù)的答案，那么 ans=n*(n+1)/2 ,考慮怎么減去重復(fù)項(xiàng)
設(shè) G1 和 G2 是兩個(gè)字符串，則 （G1G2G1）重復(fù)計(jì)算答案一次，減去1，問(wèn)題變成尋找重復(fù)子串的數(shù)量，
答案減去重復(fù)的子串?dāng)?shù)量，復(fù)雜度O(n²)，還要優(yōu)化
先打了個(gè)暴力哈希驗(yàn)證正確性，似乎是對(duì)的？但是我沒(méi)有證明，大樣例直接就1e4了，測(cè)不了
想了下怎么優(yōu)化，往字典樹(shù)的方向想，感覺(jué)做法不太對(duì)，試著證明正確性，但是沒(méi)有能說(shuō)服我自己的證明方法
然后換方法重新做，不太確定有沒(méi)有后效性
試著用區(qū)間dp，更不對(duì)了（，完全寫(xiě)不了
決定碰運(yùn)氣開(kāi)始找規(guī)律，找了一個(gè)小時(shí)沒(méi)啥想法就去做其他題了
最后半小時(shí)回來(lái)寫(xiě)了個(gè)暴力
寄（

T2

(洛谷 P7871)

第一眼感覺(jué)像差分約束，仔細(xì)想了一下發(fā)現(xiàn)拓?fù)渑判蚰茏觯帜Ａ艘幌聵永l(fā)現(xiàn)我的答案比樣例的字典序還小
看了好幾遍沒(méi)發(fā)現(xiàn)問(wèn)題，就問(wèn)了下教練，教練說(shuō)沒(méi)問(wèn)題，
又瞪了好久，完全找不出問(wèn)題，我當(dāng)時(shí)以為能量傳遞會(huì)給傳遞的對(duì)象賦值，
后來(lái)試著把能量傳遞看成只是一個(gè)東西的位置變化，沒(méi)有對(duì)序列進(jìn)行修改，樣例就對(duì)了
用給定大小關(guān)系建邊，入度為0的點(diǎn)先賦答案，讓字典序最小可以用一個(gè)優(yōu)先隊(duì)列記錄入度為0的點(diǎn)，
按每個(gè)點(diǎn)在序列里的位置升序排序
最后一個(gè)大樣例錯(cuò)了，看了一下輸出的結(jié)果，發(fā)現(xiàn)有一個(gè)位置錯(cuò)了，后面的答案全部和正確答案偏移一位
大概是這樣的
正確答案：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
我的答案：1 2 3 4 5 6 7 8 9 10 11 12 20 13 14 15 16 17 18 19

用一個(gè) mt 數(shù)組記錄每個(gè)點(diǎn)建完邊只會(huì)能到達(dá)的最小的位置，堆的排序方式按每個(gè)點(diǎn)的 mt 升序排序
關(guān)于為什么要用 mt 數(shù)組排
位置靠前點(diǎn)不在堆里是因?yàn)槿攵炔粸?0 ，如果先把位置靠前的點(diǎn)入度變成 0 ，字典序會(huì)更小
數(shù)據(jù)：

3 1
2 3

如果直接用每個(gè)點(diǎn)的位置排序會(huì)先把 1 賦值給第二個(gè)點(diǎn)
答案：3 1 2
如果按mt排，建完邊后3號(hào)點(diǎn)可以到1號(hào)點(diǎn)，mt={1,2,1}
這樣排可以把 1 先給 3 號(hào)點(diǎn)，然后 1 號(hào)點(diǎn)入度變成 0 ，
答案：2 3 1

這樣寫(xiě)大樣例就過(guò)了，此時(shí)時(shí)間只剩半個(gè)小時(shí)，建邊如果不優(yōu)化肯定要T，如果加判重復(fù)邊其他題的暴力可能就沒(méi)時(shí)間打了，
我在調(diào)大樣例的時(shí)候看見(jiàn)好多一樣的 s,t ，然后判了一下碰到重復(fù)的 s,t 就不加邊（居然過(guò)了，還是數(shù)據(jù)太水了）
回去寫(xiě) T1 暴力

T3

題目描述：

(1≤n,m≤100，1≤a_i≤n，保證 S 由 n 個(gè) + 號(hào)和 m 個(gè) - 號(hào)組成且在進(jìn)行 S_i = - 的操作時(shí) P 為空)

沒(méi)時(shí)間了，直接cout<<1

T4

題目描述：

(1≤n,q≤1e6，1≤a_i≤n)

沒(méi)時(shí)間，直接交暴力然后看T3