1.??? 洋洋的小目標(biāo)

Tip: 1.正如題目所述 輸出“洋洋的小目標(biāo)”，考察點(diǎn)：“hello world！”

參考代碼：

2.??? 洋洋的基因鎖

Tip：1.簡(jiǎn)單的比較后計(jì)數(shù)，考察點(diǎn)：字符串，簡(jiǎn)單的循環(huán)和分支結(jié)構(gòu)

參考代碼：

3.??? 洋洋的舞會(huì)

Tip：1.將來(lái)賓作為一個(gè)節(jié)點(diǎn)考慮，相互認(rèn)識(shí)關(guān)系為無(wú)向邊，這樣所有來(lái)賓就構(gòu)成了一個(gè)圖，考慮其中的數(shù)個(gè)極大連通子圖，對(duì)于一個(gè)節(jié)點(diǎn)數(shù)為n的極大連通子圖能使得熱烈度放大

k^（n-1）倍

2.容易發(fā)現(xiàn)，實(shí)際上無(wú)需保存每個(gè)節(jié)點(diǎn)之間的連接關(guān)系，只需要知道哪些點(diǎn)之間是相通的即可，使用并查集可以避免圖論解法帶來(lái)的復(fù)雜數(shù)據(jù)結(jié)構(gòu)

3.注意數(shù)據(jù)很大，使用64位或更高的數(shù)據(jù)類型來(lái)保存，并且每次乘法操作后對(duì)1000000007求余

4.考察點(diǎn)：貪心法，并查集，圖論，稀疏圖存儲(chǔ)（鏈?zhǔn)角跋蛐牵?，深度?yōu)先搜索，寬度優(yōu)先搜索，基本數(shù)論常識(shí)

參考代碼：

4.??? 洋洋的決斗

Tip:? ?1.雙方依次插入當(dāng)前不在集合中的奇數(shù)/偶數(shù)的最小值，到最后檢查奇數(shù)的最小值小還是偶數(shù)的最小值小即可判斷勝利者

2. 注意，如果使用暴力解法，你的時(shí)間復(fù)雜度可能是由于n最大為1e5，你可能會(huì)得到TLE，使用快速排序，指針，二叉搜索樹(shù)，空間換時(shí)間等方式來(lái)將時(shí)間復(fù)雜度優(yōu)化至可以接受的程度

3. 考察點(diǎn)：博弈論，時(shí)空優(yōu)化

參考代碼：

5.??? NO ONE WIN!

Tip：????? 1.由于總的血量分配方案數(shù)容易計(jì)算，所以既可以直接算無(wú)人獲勝的方案，也可以計(jì)算有人獲勝的方案然后從總數(shù)中扣除

????????????? 2.當(dāng)采用計(jì)算有人獲勝的方案時(shí)，容易想到，獲勝時(shí)場(chǎng)上剩下一個(gè)人，這個(gè)人的血量可以為任意值，當(dāng)血量為j時(shí)，此種情況對(duì)應(yīng)了唯一一種血量狀態(tài)，該狀態(tài)為對(duì)應(yīng)的有人獲勝的分配方案的最后一回合的狀態(tài)，反推出前一個(gè)回合能夠造成k點(diǎn)傷害（即場(chǎng)上剩余k+1人時(shí)），最大血量為k+j情況可以有幾種不同的狀態(tài)到該最終狀態(tài)

????????????? 3.由于出現(xiàn)了當(dāng)前條件推導(dǎo)下一狀態(tài)，且無(wú)回溯性的明顯特性，顯然本題采用動(dòng)態(tài)規(guī)劃算法解題

????????????? 4.當(dāng)采用計(jì)算有人獲勝方案數(shù)的解法時(shí)有DP[i][j]，“i”代表當(dāng)前剩余人數(shù)“j”代表當(dāng)前場(chǎng)上最大血量

初始化：dp[1][j]=1剩余狀態(tài)為0

動(dòng)態(tài)規(guī)劃遞推公式為：

ps：C為組合數(shù)k為上個(gè)回合扣掉的血量

????????????? 5.考察點(diǎn)：動(dòng)態(tài)規(guī)劃，基礎(chǔ)數(shù)論

參考代碼：