開頭介紹：這場比賽感覺還不錯，本人寫出來前六題，最后一題確實想歪了。首先前面的題目很正常，屬于是標準的div3題目。

然后到e題，很多同學(xué)剛看到e題一般都會認為是什么線段樹之類的維護更新，這確實可以做，但是div3一般不會這么早讓你去用線段樹，所以可以往簡單的方向考慮。

然后f題是一個基環(huán)樹那種感覺，只要找到環(huán)就很好做。

最后這個g題，乍一看感覺很難，但是其實是一個詐騙題目。

A題：

題目大意：現(xiàn)在有兩個容量無限的杯子1,2，還有一個容量為c的杯子3，杯子1中裝有克水，杯子2裝有克水，杯子3中開始無水，現(xiàn)在告知你的值，你可以進行一個操作，操作描述為下：

1. 選擇克水，，注意可以不為整數(shù)。

2. 將升水從一個杯子移動到另外一個杯子里面。

請計算最少需要多少步操作，才能使得杯子1和杯子2中的水相等。

輸入描述：第一行輸出，含義見題面介紹。

輸出描述：輸出最少的操作次數(shù)。

（實際上杯子3是中轉(zhuǎn)用的，不過我也不清楚為什么都可以隨便選擇倒多少了，還搞個杯子出來，反正題目也不是我出的（doge））

思路分析：

可以發(fā)現(xiàn)，每次操作使得兩邊杯子的差值變化最大為，如果差值少于2*c的話那我們可以通過一次操作去解決，因為移動的水可以不是整數(shù)，那么一次取一半，一定可以使得平衡。

代碼部分：

B題：

題目大意：現(xiàn)在有個走廊，從坐標1開始到無窮遠處，每在坐標上移動一個位置便會過去一秒鐘，你的目標是走的盡可能遠，然后再返回1點，現(xiàn)在有個陷阱，第個陷阱的位置為，然后在經(jīng)過該陷阱的秒之后，會將陷阱所放置的位置直接封死，即不可以通過。

請計算出你從1位置開始，最遠可以走到哪一個位置。

輸入描述：第一行輸出描述陷阱的數(shù)量，之后的行，每行輸入。

輸出描述：輸出可以到達的最遠位置。

思路分析：

首先我們可以發(fā)現(xiàn)，陷阱之間是獨立的，只有我們到達陷阱之后，陷阱才會啟動，而且每個陷阱的觸發(fā)時間決定了我們應(yīng)該什么時候回到這個位置，所以我們可以算出來每個陷阱最遠可以到達哪里，然后再選擇最近的那個點，因為不能跑更遠了。

代碼部分：

C題：

題目大意：給你，現(xiàn)在你需要找到，滿足一下要求：

1、

2、

若a,b有多組答案，你可以輸出其中任意一種，若不存在解輸出-1。

輸入描述：第一行輸入和，含義如上文。，最多500組測試樣例

輸出描述：請輸出一組和作為答案。

思路分析：

分類討論做法：我們可以發(fā)現(xiàn)對于一個偶數(shù)，我們可以選擇這個偶數(shù)，然后在選擇2，這樣得到的gcd就是2，那么這樣的組合只要存在一個大于4的偶數(shù)，我們就可以湊出來，顯然當和都小于4的時候，肯定無解，而當時，一定可以找到一個大于4的偶數(shù)，那么剩下就是l和r相同的情況，我們可以將其分解因子去找到答案。

暴力做法：我們其實不用去慢慢分析答案，可以直接枚舉中的數(shù)字，由于大于4的偶數(shù)一定可以分解，所以可以發(fā)現(xiàn)這樣的枚舉最多枚舉兩個，哪怕小于4，那么枚舉到4實際上就可以算出答案了，那么我們可以枚舉數(shù)字，然后分解因子，找到答案就輸出。

代碼部分：

分類討論：

暴力做法：

D題：

題目大意：給你，現(xiàn)在你需要計算：

用語言描述，就是所有下標為的值總和減去所有下標為的值總和。你需要找到一個排列，使得這樣得到的結(jié)果，答案盡可能大。

輸入描述：第一行輸出，其含義見上文。，最多1e4組測試樣例

輸出描述：輸出你可以得到的最大值。

思路分析：

可以發(fā)現(xiàn)對于數(shù)組中有多少個被加的值，有多少個被減的值我們都知道，那么實際上我們也可以算出來有多少個是同樣被加被減的，這些值無影響，然后剩下的加值盡可能大，減值盡可能小?？梢杂嬎愕玫?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=n%2Fx" alt="n%2Fx">是增加的值，是減少的值，是又增加減少的值，注意在計算答案的時候需要用等差數(shù)列的求和公式，直接暴力添加時間會超時。

注：lcm為最小公倍數(shù)

代碼部分：

E題：

題目大意：給你一個長度為的數(shù)組，然后你得到一個01字符串，然后有q次詢問，詢問類型分為兩種：

1、，將之間的字符串全部翻轉(zhuǎn)，指0變?yōu)?，1變?yōu)?。

2、，若等于0，則需要輸出值為0的下標對應(yīng)的中值的異或和，同理，等于1也是一樣。

輸入描述：第一行輸出表示數(shù)組長度，第二行輸出數(shù)組，第三行輸出01字符串，第四行輸出詢問次數(shù)，后續(xù)行輸出詢問內(nèi)容。

輸出描述，對于詢問中每個計算詢問，輸出答案。

樣例解釋可以去看原題，解釋部分所占篇幅較多。

思路分析：

這題有疑問的同學(xué)很多，我們來說一下這題的想法是怎么想出來的。

首先我們忽略復(fù)雜度考慮一下暴力做法的過程，我們以計算0的異或和為例子，首先每次更新我們從更新的區(qū)間中找到0的位置，然后往0的異或和中刪除當前0位置這個點的貢獻，然后將當前點變?yōu)?，再將當前點的貢獻加給1的異或和。那么計算1的異或和也是一樣的，這個每次更新的時間復(fù)雜度為O(n)。

那么顯然上述的做法是一個n2的做法不足夠通過這道題目，那么問題來到了如何優(yōu)化這個區(qū)間更新，常有的區(qū)間查詢數(shù)據(jù)結(jié)構(gòu)有線段樹，我們考慮通過用線段樹去維護區(qū)間中0和1的異或和，然后在更新的時候添加的時候0的給1,1的給0，再消除之前的影響，那么這個過程可以使用懶標記來節(jié)省時間，總體復(fù)雜度為O(logn)，那么這樣子的做法是足夠解決問題的。

最后來到了最快的做法，異或前綴和。首先我們得要理解前面暴力和線段樹部分對答案進行的操作，我們可以發(fā)現(xiàn)一個區(qū)間中1的異或和在翻轉(zhuǎn)后不僅要添加給0的異或和，還要添加給1的異或和。為什么呢？因為這段區(qū)間1的異或和需要被消除，好比現(xiàn)在這個區(qū)間1的異或和是，但是這個同樣存在1的異或和這個答案里面，他沒有被刪去，而考慮到異或有著的性質(zhì)，所以我們可以直接把這個異或到1異或和的答案里面去消除這個影響。現(xiàn)在我們其實就發(fā)現(xiàn)，我們不需要理清楚一個區(qū)間內(nèi)到底誰是1，誰是0，理由也就是上述的樣子，因為不存在要添加，需要加進來異或，存在的話要消除，也需要加進來異或，所以我們只用知道區(qū)間的異或和為多少就好，那么這個做法是O(1)的更新，可以很快速地解決問題。

代碼部分：

F題：

題目大意：現(xiàn)在動物園一共有n個動物，每個動物都有自己害怕的天敵，當然一個自己的天敵的天敵也可能是自己。但是動物園破產(chǎn)了，需要賣出所有的動物，那么自然每個動物都有自己的價格，現(xiàn)在規(guī)定如果你賣出一個動物，該動物的天敵還在動物園里面，那么該動物會賣出雙倍價錢也就是，現(xiàn)在你需要找到使得動物園收益最高的賣動物順序。

輸入描述：第一行輸入n，第二行輸出數(shù)組，代表第個動物害怕的天敵，第三行輸出數(shù)組，代表第個動物的價格。

輸出描述：輸出一個答案代表最多動物園可以獲得的錢。

思路分析：首先我們發(fā)現(xiàn)一共有n個點，以及n個邊，那么這樣的圖我們稱為基環(huán)樹，這種樹一般長這個樣子。

這種樹一般是有個環(huán)，然后環(huán)上的每個點會有一個子樹。

由于這題沒有規(guī)定所有的天敵關(guān)系形成一個圖，所以這個題目的天敵關(guān)系是多個基環(huán)樹，然后再思考我們要求得的答案，我們發(fā)現(xiàn)，每一個葉子節(jié)點，在賣出的時候一定可以賣到雙倍價格，這其實我們就可以做一個拓撲排序，然后我們最終會得到一個環(huán)。然后我們考慮環(huán)從哪一個點出發(fā)，我們發(fā)現(xiàn)最后賣出的點一定沒法賣出雙倍價格，而其他的點都可以賣出最高價格，所以我們可以找到環(huán)中最小的點，然后找到賣出方式。

注：拓撲排序是十分重要的知識點，算法在于找到所有沒有入度的點，然后計算，然后刪除有關(guān)這個點的邊，在重復(fù)上述操作。

代碼部分：

用了jiangly大佬的代碼，我自己的代碼寫的很冗余，寫了三遍while循環(huán)。

如果大家不知道內(nèi)部函數(shù)怎么開的話，可以看看這個實現(xiàn)的過程，其實所有代碼都是刪葉子節(jié)點，找環(huán)上最小點，然后拆掉整個環(huán)。

G題：

題目大意：給你一個長度為的數(shù)組，然后你進行一次操作，操作描述為：

1、選擇，然后區(qū)間中的所有值，全部相乘得到。

2、將剩余沒有被選擇的值全部相加得到。

3、。

要求請輸出操作的區(qū)間，使得我們得到的值最大，如果有多個區(qū)間，可以輸出任意一種。

輸入描述：第一行輸入，第二行輸入數(shù)組，。

輸出描述：請輸出使得答案最大的區(qū)間，若有多組可以輸出任意一組。

例子解釋：

思路分析：

首先直覺的感受，1這個數(shù)字很重要，因為乘1不會改變答案，那么我們可以發(fā)現(xiàn)兩端的連續(xù)1一定是不會在相乘區(qū)間的，因為不改變區(qū)間答案，還讓答案最后少加了幾個1。然后繼續(xù)思考問題，我們考慮非1點，顯然非1點只要有20個就能很容易打到2e5這個值，這個時候一定是要讓所有非1點都乘起來的，因為乘起來的增加的答案遠比中間浪費的幾個1提供的多，我們特判掉這種情況，之后就可以發(fā)現(xiàn)剩下的情況非1點一定很少，最多也就20個左右，那么考慮一下暴力做法，每次的左右區(qū)間邊界一定是這20個點的下標，那么我們可以考慮直接枚舉出所有答案去比較計算。

代碼部分：