一些应该记住的东西(持续更新？再也不会更新了)
沒什么用的目錄
1.積性函數(shù)與杜教篩
2.搜索的幾種優(yōu)化與考試期望得分
3.亂講
4.模擬退火系列
5.生成函數(shù)系列
?
2018.1.18
首先寫寫數(shù)學方面的吧(因為現(xiàn)在在學)……畢竟這里面的公式浩如煙海……
對著表推了十分鐘愣是沒發(fā)現(xiàn)……明明上午還證明過……
還有就是通過算貢獻化簡一些東西：
可以通過換元成d的倍數(shù)來證。
以及上面那對的第一個式子可以變換成
有了這個就好杜教篩了對吧……
第二個有時也可以構(gòu)造成杜教篩……
?
2018.1.19
杜教篩的套路：求g(i)的前綴和G(i)，可以構(gòu)造
其中f(i)和h(i)都是比較好求前綴和的函數(shù)，比如id(i)=i，id2(i)=i2，或者別的
然后求f(i)的前綴和：
即
于是就有
把右邊的h(1)·G(n)提出來，就變成了：
因為之前說過f和h應該都是很好算前綴和的函數(shù)，比如i^2，比如[i==1]等。
預處理出G的前n2/3項，然后哈希+記憶化搜索爆算即可。
?
?2018.1.26
說起來最近考的幾場試里面有幾題的暴力得分是這樣的：
如果你寫一個裸的搜索，你將獲得10分。
如果你加上最優(yōu)性剪枝、估價函數(shù)等一系列手段，你將獲得20分？？
如果你再加上卡時這個東西，你將獲得30分？？？
這都是些什么玩意兒……
話說回來，我在聯(lián)賽之前看見過這么一套理論并且好像還是對的：
在有最優(yōu)性剪枝的搜索(找最小值)中，應該把大的先拿去搜索，因為這樣更快剪枝。
這又是個什么玩意兒……
反正考場上看見搜索題，要順著下面的思路想：
優(yōu)秀的估價函數(shù)>不優(yōu)秀的估價函數(shù)>可行性剪枝>最優(yōu)性剪枝>搜索順序剪枝。
沒錯估價函數(shù)就是這么神奇……
?
2018.2.2
[OI無關][pkuwc血的教訓]
網(wǎng)站上在動的時間并不一定是準的……隔一會刷新一次你會發(fā)現(xiàn)你的幾分鐘沒了(-1s)
特別是某ku的百練，可以1個小時差4分鐘……
下考我一臉懵逼看著旁邊小哥，旁邊的小哥：“確實已經(jīng)6點半了呀”也是一臉懵逼看著我。
這都是些什么東西吧……
?
2018.2.9
模擬退火系列
精髓思想：溫度越高，越不穩(wěn)定，越容易發(fā)生躍動。
寫一個接受函數(shù)判斷，p=nowans-lastans：
inline bool Access(double p,double temp){if(p<=0)return true;return rand()<exp(-p/temp)*RAND_MAX; } 接受函數(shù)具體而言，如果p<0，即當前答案比之前答案小，肯定接受。
如果p>0，exp(x)計算的是e的x次方，圖像是這樣的：
在x<0時返回一個(0,1)的實數(shù)。
p>0，當p越大，此時躍動越虧，(-p/temp)越小，exp越小。
當temp越小，(-p/temp)越小，exp越小。
是一種很合理的接受判斷。
網(wǎng)上還有什么rand()%初始溫度<當前溫度就躍動之類的
都沒有很好地利用p和temp兩個量。
本來式子是這樣的，兩邊都是0～1的實數(shù)：
因為除法常數(shù)太大，RAND_MAX移到右邊去就可以了。
算法顯然是非完美的，于是下面這一句話就很重要了：
模擬退火初溫可以低，但一定要多燒。
實例：燒1000次，每次退10000下 = WA，燒10000次，每次退1000下=AC
也許燒出來的東西還是和初始狀態(tài)關系很大吧……
然后就是退火時的判斷。
因為溫度很高時很不穩(wěn)定，這個時候各種亂搞反而不容易進入正解。
于是可以摻一點貪心的東西進去，讓p盡量<=0。
溫度低了，稍微穩(wěn)定了，這個時候常規(guī)退火效果可能更好。
比如說 BZOJ2428 均分數(shù)據(jù) 第一眼沒人想的到退火
反倒很容易想到扔進和最小的組的貪心策略。
在溫度大的時候用這個貪心可以提高正確率。
(事實上只要燒得夠多(10086次選手)不用也能過)
?
2018.2.10再開一坑
生成函數(shù)/母函數(shù)系列
先引著幾個東西：
(1)：廣義組合數(shù)
一般組合數(shù)都是C(n,m)=n!/m!/(n-m)!，其中n,m均為非負整數(shù)且n>=m。
廣義組合數(shù)也差不多，n可以是任意實數(shù)。
比如說C(-1.4,2)=(-1.4)*(-2.4)/2!=1.68。
于是引申開來這樣的式子：
?
由此我們可以得出一個重要規(guī)律：
1/(1-x)k (即(1-x)-k)在xn項的系數(shù)為C(n+k-1,n)。
稍作推廣可得：
也可以寫成
組合數(shù)上面的那個東西就不變了。
很多生成函數(shù)都會化到這種形式。
?
(2)：指數(shù)型母函數(shù)的兩個重要等式
? ? ? ? ??
所以有這么個東西(要背的好多啊)
序列<1,1,1,1,1...>的指數(shù)型母函數(shù)是ex
序列<1,-1,1,-1,1...>的指數(shù)型母函數(shù)是e-x
然后再附贈兩個：
序列<0,1,0,1,0...>的指數(shù)型母函數(shù)是(ex-e-x)/2
序列<1,0,1,0,1...>的指數(shù)型母函數(shù)是(ex+e-x)/2
好難記啊
放縮求導什么的……考場自己推吧……
?
2018年03月17日
感覺好久沒碰博客園這個東西了……
看見網(wǎng)格圖網(wǎng)絡流想到黑白染色難道不是公理么？我這個××，×，×××。
?
好吧正事。?
(x,y)每次可以上下左右走的題目，可以轉(zhuǎn)化為(x+y,x-y)。
這樣，不管怎么走，橫縱坐標都會改變，而且兩維互不影響，就可以分開考慮了。
方案數(shù)也可以直接相乘什么的。
相當于坐標系旋轉(zhuǎn)45°。
?
題面看見排列應該怎么想：
1.二分圖，二分圖上的連通塊。
2.不用考慮重復元素的情況。
3.位置和值一一對應，從位置的改變映射到值的改變。
4.從小往大插入。
……
?
2018年04月07日之后
二階差分(加一個等差)是可以只開一個數(shù)組的......
高斯消元……要判0……有些是自由元……(特別是異或消元！)
?
?
跟什么人說什么話，有些人的有些話不要聽，有些話不要信，世界并非你心中一樣真誠。
轉(zhuǎn)載于:https://www.cnblogs.com/fenghaoran/p/remember.html
總結(jié)
以上是生活随笔為你收集整理的一些应该记住的东西(持续更新？再也不会更新了)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： modscan36--my milest
- 下一篇： listView 多布局