開(kāi)頭介紹：這場(chǎng)題目的思維考察真的很多，如果思維量不夠的話，做起來(lái)確實(shí)很容易翻車(chē)，大家如果發(fā)揮失常的話，也不用很擔(dān)心，思維題本來(lái)就是方差比較大，然后題解可能寫(xiě)的比較繁瑣，主要是昨天也有同學(xué)有點(diǎn)疑問(wèn)，所以寫(xiě)的稍微長(zhǎng)點(diǎn)。

A題：

題目大意：給你x，y，n的值，你需要構(gòu)造一個(gè)長(zhǎng)度為n的數(shù)組a，其中你的構(gòu)造需要滿(mǎn)足以下幾個(gè)條件：

1、滿(mǎn)足

2、滿(mǎn)足，注意這里使用的是小于號(hào)，所以是嚴(yán)格小于。

3、對(duì)于所有，可以得到，你需要滿(mǎn)足。

注意構(gòu)造可能存在很多種情況，你可以輸出任意一組情況，但是如果沒(méi)有正確的構(gòu)造方式，請(qǐng)輸出-1。

輸入描述：第一行輸入x，y，n，描述如上文。1

輸出描述：若存在構(gòu)造情況，輸出任意一組，如果不存在則輸出-1.

例子解釋?zhuān)?/p>

1 4 3

對(duì)于這個(gè)例子，我們給出1 3 4的構(gòu)造，可以發(fā)現(xiàn)其b的值為2，1滿(mǎn)足嚴(yán)格遞減，a的值為1,3,4也滿(mǎn)足嚴(yán)格遞減。

思路分析：

對(duì)于這個(gè)問(wèn)題，我們可以發(fā)現(xiàn)從點(diǎn)出發(fā)不好解決，因?yàn)槲覀儫o(wú)法假設(shè)的值，以及后面會(huì)怎么樣的變化，在這里我們發(fā)現(xiàn)如果要保證2條件和3條件，那么我們的值得要大于等于n-1,因?yàn)楦鶕?jù)3條件，我們的b每次都要至少下降一個(gè)值，根據(jù)我們的2條件，可以發(fā)現(xiàn)b不能等于0。但是我們無(wú)法確定這樣的做法會(huì)使得最后一個(gè)a是y。所以我們反向思考。

從開(kāi)始思考，顯然我們可以發(fā)現(xiàn)這個(gè)最少為1，而且如果我們的b取小了，那么多余的值可以賽給最前面的b，那么其實(shí)就已經(jīng)發(fā)現(xiàn)了如何構(gòu)造。

構(gòu)造方式：從開(kāi)始，讓以此類(lèi)推，直到最后算出來(lái)使得構(gòu)造滿(mǎn)足的最大的值，如果x小于等于，那么問(wèn)題不大，反正可以增大，如果x大于，那么這樣的構(gòu)造便不存在，直接輸出-1.

代碼部分：

B題：

題目大意：現(xiàn)在存在一個(gè)長(zhǎng)度為n的字符串s，然后你會(huì)知道k的值是多少，現(xiàn)在你可以進(jìn)行任意次數(shù)的下述操作，你需要使得給定的字符串字典序盡可能最小。

1、對(duì)于所有的情況，交換和。

2、對(duì)于所有的情況，將的所有字符全部逆序。

請(qǐng)輸入得到字典序最小的情況。

輸入描述：第一行輸入n，k，代表字符串長(zhǎng)度和k值。第二行輸入字符串。

輸出描述：輸出經(jīng)過(guò)任意次操作得到的上述字典序最小的字符串。

例子解釋?zhuān)海}目例子解釋的很好，不是我偷懶）

4 2

nima

思路分析：首先我們可以思考一下這個(gè)問(wèn)題，乍一看感覺(jué)非常難，因?yàn)閷?shí)際上我們并沒(méi)有什么直觀的貪心做法，但是各位千萬(wàn)別急，想一想這題才只是b題，怎么可能那么難，所以我們可以往簡(jiǎn)單方面考慮。

首先我們發(fā)現(xiàn)第一個(gè)操作，實(shí)際上只能交換下標(biāo)奇偶性質(zhì)相同的字符，那么第二個(gè)操作，如果可以交換下標(biāo)奇偶性質(zhì)不同的字符，那么這個(gè)字符串我們想怎么變化就怎么變化，反正可以變回來(lái)。于是我們分析第二個(gè)操作。

第二個(gè)操作，如果對(duì)于一個(gè)奇數(shù)區(qū)間，可以發(fā)現(xiàn)我們的交換，實(shí)際上還是讓每個(gè)奇偶性質(zhì)相同的元素之間在交換，那么我們最好的構(gòu)造方式，就是分開(kāi)奇偶位置，每次把字典序最小的字符放在最前面，然后再把奇偶合在一起。如果對(duì)于一個(gè)偶數(shù)區(qū)間，我們發(fā)現(xiàn)每次可以交換奇偶性質(zhì)不同的字符，那么我們字符串可以任意構(gòu)造，那實(shí)際上就是對(duì)字符串進(jìn)行排序。

代碼部分：

C題：

題目大意：給你一個(gè)x，現(xiàn)在你需要對(duì)x進(jìn)行操作，使得x最后的值變?yōu)?，對(duì)于操作的描述如下：

選擇任意一個(gè)能夠整除x的值（除了x本身），將這個(gè)值稱(chēng)為d，然后x需要減去d。（需要注意每一個(gè)值，d都只能選擇不超過(guò)2次）

例如 x==5

現(xiàn)在你需要輸出你的構(gòu)造過(guò)程，如果有多個(gè)構(gòu)造，輸出任意一個(gè)構(gòu)造即可。

輸入描述：輸入x的值，描述見(jiàn)上文。

輸出描述：第一行輸出整個(gè)構(gòu)造的長(zhǎng)度（你所輸出的長(zhǎng)度不能超過(guò)1001），第二行輸出每個(gè)操作的時(shí)候x的值。

思路分析：這題也是一道思維題，首先注意到選擇一種類(lèi)型的d，不能超過(guò)兩次，以及這道題目提到的整除，那么我們可以嘗試往二進(jìn)制的方向思考。

首先我隨便胡謅一個(gè)二進(jìn)制數(shù)字，1101101，對(duì)于這個(gè)二進(jìn)制數(shù)字，我們可以發(fā)現(xiàn)我們能夠把右邊的1一個(gè)一個(gè)刪掉，比如1101101可以被1整除，后面變成1101100，然后發(fā)現(xiàn)可以被100整除，然后變?yōu)?101000，以此類(lèi)推，可以變?yōu)?000000，然后對(duì)于這個(gè)數(shù)字實(shí)際上我們可以考慮每次減半，比如1000000可以被100000整除，那么他會(huì)變成100000，以此類(lèi)推，我們發(fā)現(xiàn)一個(gè)值最多選兩次，很好地解決了這個(gè)問(wèn)題。

D題：

題目大意：首先給你一個(gè)n*n的01矩陣，在這個(gè)矩陣中，我們可以對(duì)一個(gè)點(diǎn)進(jìn)行一種操作，對(duì)操作進(jìn)行描述，具體描述如下：

選定（i，j）這個(gè)點(diǎn)，然后對(duì)于所有的點(diǎn)，只要其y坐標(biāo)滿(mǎn)足，那么我們就對(duì)這些點(diǎn)進(jìn)行翻轉(zhuǎn)（0->1，1->0）。

請(qǐng)問(wèn)我們需要最少多少次操作才可以使得這個(gè)01矩陣變成全部為0.

如果你還不理解上述的操作，存在更直觀的方式，看例子。

對(duì)于如上的這個(gè)例子，實(shí)際上就一次操作，也就是選擇第一行的第三個(gè)點(diǎn)，然后下方所有的1點(diǎn)都會(huì)翻轉(zhuǎn)。

輸入描述：第一行輸入n的值，后面輸入整個(gè)矩陣。

輸出描述：請(qǐng)輸出最少需要多少次操作把全的值都變成0.

思路分析：實(shí)際上這道題目非常像一道經(jīng)典的題目，《費(fèi)解的開(kāi)關(guān)》，大家可以去搜索一下，其中有個(gè)很重要的想法，就是每一行的操作實(shí)際上都是知道的，因?yàn)槲覀兊谝恍袑?shí)際上只能影響到第二行以后的，以及自己這個(gè)點(diǎn)，所以我們可以確定哪些點(diǎn)需要進(jìn)行這個(gè)操作。那么問(wèn)題來(lái)一個(gè)點(diǎn)會(huì)影響的點(diǎn)會(huì)非常多，那么我們又怎么去解決多更改情況呢？顯然每次更新一個(gè)點(diǎn)暴力的更新是一定會(huì)超時(shí)的，那么如何解決這個(gè)問(wèn)題？

我們可以發(fā)現(xiàn)對(duì)于一個(gè)點(diǎn)更改，我們可以給一些點(diǎn)打上標(biāo)記，每次訪問(wèn)到的時(shí)候，再對(duì)其進(jìn)行更新，由此我們可以保證其復(fù)雜度。關(guān)于一個(gè)點(diǎn)操作之后，給哪些點(diǎn)打上標(biāo)記，大家可以想一想，代碼部分中我們也會(huì)提到。

代碼部分中，說(shuō)道下下方點(diǎn)抵消影響，實(shí)際上就是當(dāng)左下有點(diǎn)，和右下有點(diǎn)，中間會(huì)有一個(gè)部分被操作兩字，翻轉(zhuǎn)兩次等于沒(méi)有翻轉(zhuǎn)，所以要在下下點(diǎn)進(jìn)行記錄抵消

代碼部分：

E題：

題目大意：現(xiàn)在有一個(gè)長(zhǎng)度為n的數(shù)組a，現(xiàn)在我們從中隨機(jī)選擇兩個(gè)數(shù)字，然后我們進(jìn)行以下操作。（和的值可能相同）

令。

1、將的值告訴Alice

2、將的值告訴Bob

3、，將的值告訴Alice和Bob（|表示按位或）

然后以Alice率先開(kāi)始，隨后Bob循環(huán)回合。

Alice和Bob要做的事情就只有一個(gè)，就是猜對(duì)面的數(shù)字和自己數(shù)字的大小關(guān)系，換句話說(shuō)，假如我們是Alice，只要我們可以確定a<b，a>b，a=b其中一種，那么游戲就結(jié)束。

在每個(gè)人的回合中，如果一個(gè)人已經(jīng)確定了大小關(guān)系，他就會(huì)說(shuō)出來(lái)，然后游戲結(jié)束，如果不確定大小關(guān)系的話，那么就會(huì)告訴對(duì)方我不知道大小關(guān)系。

現(xiàn)在你需要算出來(lái)游戲結(jié)束的期望輪數(shù)。

結(jié)果對(duì)于998244353取模。

輸入描述：第一行輸入n，第二行輸入數(shù)組中的元素，

輸出描述：輸出游戲結(jié)束的期望輪數(shù)。

思路分析：很好發(fā)現(xiàn)的是，我們要算期望，實(shí)際上我們知道有多少種組合，那么我們只用把所有組合情況的輪次和算出來(lái)，最后再用分?jǐn)?shù)取模，就可以計(jì)算出答案。但是為了解決計(jì)算所有組合情況下輪次和，我們其實(shí)需要分析清楚兩個(gè)問(wèn)題。

問(wèn)題1：知道了兩個(gè)數(shù)字如何計(jì)算他們要進(jìn)行多少輪？

問(wèn)題2：這題的數(shù)據(jù)范圍是2e5，兩兩個(gè)數(shù)字組合一共有4e10種，顯然得要有更高效的解決方式。

首先考慮問(wèn)題1，以Alice的視角來(lái)看，我們得到兩個(gè)數(shù)字，那么什么時(shí)候我們可以立刻判斷出關(guān)系呢？我們將數(shù)字分解為二進(jìn)制來(lái)看，顯然當(dāng)中存在一個(gè)沒(méi)有的高位1，那么這個(gè)1只可能來(lái)自于，因?yàn)槭歉呶坏?，那么自然也就知道。我們將這個(gè)想法延伸，我們可以發(fā)現(xiàn)，如果一開(kāi)始不能判斷，實(shí)際上就是和的最高位置1在同一位置，不確定中是否存在這個(gè)高位的1。然后輪次交換，實(shí)際上大家都已經(jīng)互相知道對(duì)方的最高位是幾了，所以每次回合都是在判斷目前的高位1，自己手上的元素，在這里是不是1，如果是就結(jié)束，如果不是就輪換。

我們來(lái)介紹一個(gè)例子，a=2,b=3,c=3。

先轉(zhuǎn)化為二進(jìn)制a=10，b=11，c=11。

Alice：首先a和c的第一個(gè)位置都是1，無(wú)法確定b的第一個(gè)位置是幾，Alice說(shuō)不知道

Bob：由于上面Alice說(shuō)不知道，所以a的第一個(gè)位置肯定是1，但是b的第一個(gè)位置也是1，無(wú)法確定，然后再看第二個(gè)位置，我們發(fā)現(xiàn)b和c的第二個(gè)位置都是1，無(wú)法確定a的第一個(gè)位置是幾，Bob說(shuō)不知道。

Alice：首先Bob說(shuō)不知道，那么b的第二個(gè)位置一定是1，現(xiàn)在我們確定了b的值，所以Alice說(shuō)出了我知道！

上述例子的過(guò)程為3個(gè)輪次，判斷輪次過(guò)程大概就是這樣子的思路。

然后我們考慮問(wèn)題2，首先不可能兩個(gè)兩個(gè)全部枚舉出來(lái)，但是我們發(fā)現(xiàn)，由于我們解決問(wèn)題1中得到的性質(zhì)，我們發(fā)現(xiàn)先枚舉一個(gè)數(shù)字，他和別的數(shù)字之間的輪次是多少，其實(shí)和二進(jìn)制的形式有關(guān)，比如說(shuō)10和所有大于等于100的值，永遠(yuǎn)都是10可以立刻發(fā)現(xiàn)大小關(guān)系，實(shí)際上我們可以通過(guò)二分去解決這個(gè)問(wèn)題，快速找出一個(gè)次數(shù)下有多少個(gè)情況滿(mǎn)足。需要注意的是，要經(jīng)過(guò)多少個(gè)輪次，實(shí)際上和現(xiàn)在前面有多少個(gè)1有關(guān)，因?yàn)橛?直接判斷出來(lái)，有1的話，則是不確定。

那么根據(jù)這個(gè)想法就可以寫(xiě)出代碼了。

代碼部分：

E題應(yīng)該也有其他的解法，但是up比較菜雞，只能想出這種方法，希望大家見(jiàn)諒。

注意第四個(gè)例子的答案實(shí)際上是187，大家可以去根據(jù)這個(gè)例子改一改。

F題：

還沒(méi)看，如果會(huì)寫(xiě)就去補(bǔ)了