1.1/2序列

Tip:? 1.答案顯然只與2出現(xiàn)的位置有關(guān)

?????? 2.記錄每一個(gè)2出現(xiàn)的位置與2的總數(shù)sum，若2的總數(shù)為奇數(shù)輸出-1否則輸出第sum/2個(gè)2的位置，

?????? 3.記得初始化第0個(gè)2出現(xiàn)的位置或者進(jìn)行特判.

4.考察點(diǎn)：指針

參考代碼：

2.默契測(cè)試

Tip:? 1.每有一個(gè)相同的數(shù)字默契值乘2

?????? 2.每輪游戲的默契值不重置

?????? 3.當(dāng)超過(guò)上限時(shí)應(yīng)當(dāng)停止計(jì)算

?????? 4.若使用暴力搜索，時(shí)間復(fù)雜度將可能達(dá)到O*10^8導(dǎo)致TLE，使用平衡二叉樹(shù)記錄每輪的數(shù)字將時(shí)間復(fù)雜度優(yōu)化至最大O*10^6，或使用空間換時(shí)間的方式，開(kāi)一張10^6大小的表，每輪重置一次時(shí)間復(fù)雜度最大O*10^5*2

?????? 5.考察點(diǎn) 二叉搜索，時(shí)空優(yōu)化

參考代碼：

3.A+B？

Tip:? 1.高精度計(jì)算

?????? 2.做不出來(lái)要想想是不是平時(shí)代碼寫(xiě)少了

參考代碼：

4.南京工業(yè)大學(xué)之旅

Tip:? 1.從這題開(kāi)始上難度了

?????? 2.顯然是求最短哈密頓路徑的有向圖版本

?????? 3.求最短哈密頓路徑?jīng)]有高效算法，所以題目給的n只有18

?????? 4.你可以嘗試剪枝dfs和狀壓dp兩種思路，剪枝能不能剪到不TLE就看你的本事了

5.初始化所有位為不可能達(dá)到的大值，狀壓dp第一維記錄到達(dá)的點(diǎn)，第二位記錄最后到達(dá)的點(diǎn)，dp[1][1]=0，dp數(shù)組中保存的是當(dāng)前到達(dá)這些點(diǎn)的最短路勁長(zhǎng)度，不包括回初始點(diǎn)的路徑長(zhǎng)。dp公式為dp[i][j]=min(dp[i][j],dp[pre][k]+path[k][j])pre為i的第j位置零后的值。完成dp后找出dp[(1<<n)-1][i]+a[i][1]的最小值，輸出答案即可。

?????? 6.考察點(diǎn)：狀壓dp，剪枝dfs，圖論

參考代碼：

5.開(kāi)學(xué)考試

Tip:? 1.純粹的數(shù)論題，巨大的數(shù)據(jù)以及模數(shù)是質(zhì)數(shù)是告訴你要用快速冪和乘法逆元了

?????? 2.考察點(diǎn)：遞推公式轉(zhuǎn)通項(xiàng)，矩陣快速冪，乘法逆元

參考代碼：

感謝AlexZhang提供的第四題源代碼