爆炸！！！！！

上午：emmmm我今天要爭(zhēng)取進(jìn)前40（flag 1）
拿到試題，瞬間感受到了zhx長(zhǎng)者的惡意......兩道方案數(shù)題，我要涼了啊。
T1:這是道傻逼題，我20分鐘就能切掉（flag2），T2的50分貌似可做？（flag 2）T3感覺(jué)也就45吧。
開(kāi)始碼，寫(xiě)了30min，T1過(guò)了樣例，測(cè)了幾組就不管了（為什么我不多測(cè)幾組強(qiáng)力的？？），T2剛了20min，發(fā)現(xiàn)剛不動(dòng)，只會(huì)20分爆搜，5min應(yīng)該能寫(xiě)完，就放了放。出去上個(gè)廁所，回來(lái)發(fā)現(xiàn)
9：30了（慌得一批），考慮T3，瞎jb化柿子發(fā)現(xiàn)了30分的沙雕dp，10min寫(xiě)完，但是 ai=i 怎么做啊，還有ai的值能對(duì)算法起什么作用呢？？？？？一直想到11：20，剩下的時(shí)間就碼完T2的暴力+輸出隨機(jī)數(shù)（emmm）+掃雷。提交。

預(yù)計(jì)得分 100+20+30+rand（），實(shí)際得分 20+30+30，gg

當(dāng)時(shí)LYY巨佬先出來(lái)成績(jī)，150，感覺(jué)很開(kāi)心，因?yàn)槲乙彩?50，而且我的名字為AK選手LYY，這一定很棒。看了看他rank9，難道今天奶中了？結(jié)果一看成績(jī)傻眼了，細(xì)細(xì)檢查發(fā)現(xiàn)T1的m打成n了，mmp，直接從rank9掛成rank......

題解：T1 傻逼題
T2 一道矩陣乘法神題，不會(huì)，NOIP出矩乘直接暴力了感覺(jué)。
T3, 如果點(diǎn)權(quán)很小，我們可以?xún)?yōu)化轉(zhuǎn)移：令g[i][j]= sigma (k=1 -> i) (Ak==j ) f[k],那么f[i]=sigma (j==0 - >maxval) num(Ai & j ) g[i-1][j]; 復(fù)雜度 N*maxval。
至于正解：參考起床困難綜合征，位運(yùn)算要考慮他的微觀表形式，可以將之前存權(quán)值改一改。

講課：

T1
CF 160D

我們隨意地構(gòu)造一顆最小生成樹(shù)，枚舉一個(gè)非樹(shù)邊，考慮這條邊對(duì)兩端點(diǎn)形成的樹(shù)上簡(jiǎn)單路徑的貢獻(xiàn)。用樹(shù)鏈剖分或并茶幾

T2 BZOJ 2238

我們還是建造一顆最小生成樹(shù)，枚舉非樹(shù)邊，在樹(shù)上加上他的貢獻(xiàn)，最后對(duì)于每次查詢(xún)，取所有貢獻(xiàn)中的min就好了。

T3 Luogu P2423 [HEOI2012]朋友圈

這道題有點(diǎn)神奇，圖上的最大團(tuán)問(wèn)題是個(gè)NPC問(wèn)題（就是只能暴力），但是有一種圖不滿(mǎn)足，就是二分圖，我們一看那么大的數(shù)據(jù)范圍，絕壁是二分圖問(wèn)題！！！！我們發(fā)現(xiàn)一下規(guī)律：
1、A國(guó)就是奇數(shù)和偶數(shù)才能成為朋友，大小只能是二，暴力枚舉。B國(guó)發(fā)現(xiàn)奇數(shù)和奇數(shù)成為朋友，偶數(shù)和偶數(shù)成為朋友，部分奇數(shù)和偶數(shù)也是朋友......貌似不是個(gè)二分圖？我們轉(zhuǎn)化一下，建它的補(bǔ)圖，這樣你會(huì)發(fā)現(xiàn)他是個(gè)二分圖，只需要求他的最大點(diǎn)權(quán)獨(dú)立集就好了。這里有一個(gè)結(jié)論：二分圖的最大點(diǎn)權(quán)獨(dú)立集為n+m-k，k為二分圖最大匹配的值

轉(zhuǎn)載于:https://www.cnblogs.com/bullshit/p/9740813.html

總結(jié)

以上是生活随笔為你收集整理的清北学堂Day 3 游记的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。