競賽程式導論

程式競賽中時間寶貴，執行時間越短越好。所以要減少所花費的時間，以及估算程式的執行時間

複雜度估算

為了評估程式的執行效率，我們可以測量時間

Big O Notation	別名	常見演算法
\(O(1)\)	常數	陣列讀取
\(O(n)\)	線性	Linear search
\(O(logn)\)	對數(Logarithmic )	二分搜尋法
\(O(nlogn)\)	線性	堆積排序，合併排序

Big O Notation	別名	常見演算法
\(O(n^2)\)	平方	氣泡排序，插入排序
\(O(n^3)\)	三次方	三重迴圈枚舉法，高斯消去法求解線性方程組
\(O(2^n)\)	指數	費氏數列
\(O(n!)\)	階層	排列組合，八皇后問題

\(n\)大小	通常使用甚麼方法
\(n>10000\)	\(O(n)\) or \(O(nlog(n))\)
\(n>1000\)	\(O(n^2)\)
\(n>100\)	\(O(n^3)\)
\(20<=n<=26\)	\(O(2^n)\)
\(n=<10\)	\(O(n!)\)

前綴和\(prefix-sum\)

\(ps[i]\)=\(\sum_{n=0}^{i} val[n]\)
\(ps[x]-ps[y]\)=\(\sum_{n=y+1}^{x} val[n]\)

 //一般的前綴和陣列的建立
int val[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//前墜和(ps)陣列可以方便找區間和
int ps[10] = {0};
ps[0] = val[0];   //預處理第一項
for(int i = 1;i < 10;i++) { 
    ps[i]=ps[i-1]+val[i];  
}
//前綴和陣列的第n項=前綴和陣列的前項+原陣列的第n項

\(int\)	\(long-long\)
\(2^{32}-1\)約\(10^9\)	\(2^{64}-1\) 約\(10^{18}\)

1 . 1

競賽程式導論程式競賽中時間寶貴，執行時間越短越好。所以要減少所花費的時間，以及估算程式的執行時間

	int val[3] = {3, 3, 4};
	int ps[3] = {3, 6, 10}; //前綴和陣列
	//對ps進行差分
	int d[3]= {3, ps[1]-ps[0], ps[2]-ps[1]} //變成原陣列

競賽程式導論

競賽程式先備知識

複雜度估算

前綴和\(prefix-sum\)

差分

前綴和與插分的進階技巧

\(overflow\)

\(rounding-error\)

\(I/O\)優化

結束!!!

	//一般的前綴和陣列的建立
	int val[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	//前墜和(ps)陣列可以方便找區間和
	int ps[10] = {0};
	ps[0] = val[0]; //預處理第一項
	for(int i = 1;i < 10;i++) {
	ps[i]=ps[i-1]+val[i];
	}
	//前綴和陣列的第n項=前綴和陣列的前項+原陣列的第n項

	//加上這行即可I/o優化
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);