本文是刷《王道論壇考研機試上機指南》的筆記、遇到的一些坑的記錄，大部分是JAVA實作，文末有C++的部分筆記，希望可以幫助到你～
一些有用的連結：
算法第四版代碼https://github.com/jimmysuncpt/Algorithms
算法第四版代碼中文目錄https://github.com/jimmysuncpt/Algorithms
官方代碼https://algs4.cs.princeton.edu/code/
刷書java版本https://github.com/godfanmiao/JobDu_OJ_Tutorial_Ex_Java
算法可視化https://visualgo.net/zh
算法讀書筆記https://www.jianshu.com/u/24d715499bcf
JAVA部分
輸入輸出
1.輸入(Scanner)
import java.io.*;
import java.util.*;
public class InOutDemo {
public static void main(String args[]){
Scanner cin = new Scanner(new BufferedInputStream(System.in));
}
}
2. 讀入一個整數
int n = cin
3. 讀入一個字元串
String s=cin.next();
4. 讀入一個浮點數
double d=cin.nextDouble();
5. 讀入一行
String s1=cin.nextLine();
如果把next（）或者nextInt（），nextDouble() 、 nextFloat()用在nextLine的前面時。nextLine會把前者的結束符“換行符”作為字元串讀入，進而不需要從鍵盤輸入字元串nextLine已經轉向下一條語句執行
修正方法：在next()或nextInt()方法使用Enter鍵之後，填充一個無用的nextLine()
6. 輸出
System.out.println();
System.out.printf("%d %10.5f\n", a, b);
7. 浮點數保留幾位小數，DecimalFormat類
0 表示如果位數不足則以 0 填充，# 表示隻要有可能就把數字拉上這個位置。這裡0指一位數字，#指除0以外的數字。
DecimalFormat f=new DecimalFormat("#.##%");
DecimalFormat f=new DecimalFormat(",###.##");
System.out.println(f.format(d));
8. 大數BigInteger BigDecimal
存儲任意精度的數，運算速度比較慢
add,substract,multiply,divide,remainder,compareTo()
divideAndRemainder：a[0]=this / val; a[1]=this % val
pow,gcd,abs,negate,signum,mod,shiftLeft(this<<n),shiftRight(this>>n),and,or,xor
BigInteger bi=new BigInteger("2");
BigInteger bi=new BigInteger("-101",2);
System.out.println(bi.toString(10));
toString()會使用科學計數法，toPlainString()直接顯示
stripTrailingZeros()傳回數值上等于此小數，移除末尾的0的BigDecimal
9. 進制轉換
String st = Integer.toString(num, base);
int num = Integer.parseInt(st, base);
10. BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
//scanf不能過的一個例子
public class Main {
public static void main(String[] args) throws IOException {
// Scanner cin = new Scanner(new BufferedInputStream(System.in));
BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
String line;
while ((line=cin.readLine())!=null) {
int n = Integer.parseInt(line);
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
line = cin.readLine();
String[] items = line.split(" ");
if (Integer.parseInt(items[0]) == 1) {
priorityQueue.offer(Integer.parseInt(items[1]));
} else {
System.out.println(priorityQueue.poll());
}
}
}
}
}
字元串
1. 基本操作
charAt(),substring()
ch = st.toCharArray(); // 字元串轉換為字元數組.
2. 比較
if(!this.name.equals(s1.name)){
return this.name.compareTo(s1.name);
}
3.StringBuilder比較
s1.toString().equals(s2.toString())
調用
1. main中調用非靜态方法時候，先建立類對象，再調用
Main e = new Main();
e.dfs(0);
數組
1. 相對于array，ArrayList特點：
動态改變大小，如果事先知道大小，并且不會改變可以使用Array
存儲需要的空間更多
編譯時檢查類型是否正确
隻能儲存封裝類
可以通過iterator周遊
size擷取存儲元素的個數,array中length擷取數組長度
不支援多元
2. list接口
add(),get(int index),remove(int index),set(),clear()
ArrayList類的特點：底層是數組結構，查詢快，增删慢；線程不安全，效率高
Vector類的特點：底層是數組機構，查詢快，增删慢；線程安全，效率低
LinkedList類的特點：底層是連結清單結構，增删快，查詢慢；線程不安全，效率低
removeall:比較參數collection的對象是否包含，如果包含則删除，複雜度O(n^2)
clear：将所有元素置為空
2. array操作
memset：Arrays.fill()
sort:Arrays.sort()
bsearch: binarySearch(),must be sorted
int ind = Arrays.binarySearch(students, 0,N,student);//類中需要重構equals函數和compareTo函數
public int compareTo(Student student) {
return sid.compareTo(student.sid);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return Objects.equals(sid, student.sid);
}
int dir[][]={{1,0},{-1,0},{0,1},{0,-1}};
3. 數組申明寫在裡面
public static void main(String args[]){
Scanner cin = new Scanner(new BufferedInputStream(System.in));
Student[] students = new Student[1000];
}
4. 數組反轉
Collections.reverse(buf);
5. 初始化
6. 尋找一個集合的最大元素
1. Arrays.sort()然後取第一個元素
2. Collection.max()
7. 兩種複制方法
System.arraycopy(arr1, 0, arr2, 0, arr1.length);
arr2 = Arrays.copyOf(arr1, arr1.length * 2);
8. arraylist不要固定索引插入，很不經濟。
資料結構
1. Map
HashMap<Integer, String> hmap = new HashMap<Integer, String>();
/*Adding elements to HashMap*/
hmap.put(12, "Chaitanya");
hmap.put(2, "Rahul");
hmap.put(7, "Singh");
hmap.put(49, "Ajeet");
hmap.put(3, "Anuj");
/* Get values based on key*/
String var= hmap.get(2);
/* Remove values based on key*/
hmap.remove(3);
Set<Character> set=priority.keySet();
2. Stack
peek( ):檢視棧頂元素
search(Object element)：傳回對象在堆棧中的位置，以 1 為基數。
3. PriorityQueue
插入方法（offer()、poll()、remove() 、add() 方法）時間複雜度為O(log(n)) ；
remove(Object) 和 contains(Object) 時間複雜度為O(n)；
檢索方法（peek、element 和 size）時間複雜度為常量。
構造函數：PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
4. 隊列：
Queue<String> queue = new LinkedList<String>();
//添加元素
queue.offer("a");
queue.poll(); //傳回第一個元素，并在隊列中删除
queue.element(); //傳回第一個元素
queue.peek(); //傳回第一個元素
//add()和remove()方法在失敗的時候會抛出異常(不推薦)
排序
class Student implements Comparable<Student>{
public int compareTo(Student s1){
return this.name.compareTo(s1.name);
}
}
1. 如果參數字元串等于此字元串，則傳回值 0；
2. 如果此字元串小于字元串參數，則傳回一個小于 0 的值；
3. 如果此字元串大于字元串參數，則傳回一個大于 0 的值。
class CMP implements Comparator<Student>
Arrays.sort(students,0,N,cmp);
一些注意事項
1. 使用Netbeans寫Java程式的時候用自動添加package main;交題的時候要去掉這句話。
2. 主類必須命名為 Main
交題時，你的代碼應該是如下架構
import ……//相當于c++的include
public class Main {
public static……//一些自己定義的函數
public static void main（String[] args） {
Scanner cin = new Scanner（System.in）；
}
}
多線程
1. 優化時間常數
2. 對于單檔案多case的題，開多線程，每個線程跑一個case（轉發注記：或者是一部分case），之後再調用收尾的任務輸出
3. 對于單case且可以并行的情況，開若幹線程處理之後，調用收尾函數來最後處理、輸出
問題
1. 所有的方法、變量都要申明成static嗎
日期
初始化SimpleDateFormat
SimpleDateFormat simpleFormat = new SimpleDateFormat("yyyy-MM-dd hh:mm");//如2016-08-10 20:40
1.計算天數差。
String fromDate = simpleFormat.format("2016-05-01 12:00");
String toDate = simpleFormat.format("2016-06-01 12:00");
long from = simpleFormat.parse(fromDate).getTime();
long to = simpleFormat.parse(toDate).getTime();
int days = (int) ((to - from)/(1000 * 60 * 60 * 24));
eclipse注意
1. equals函數的快捷鍵
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return Objects.equals(sid, student.sid);
}
2. 頭函數不會自己補充
import java.io.*;
import java.util.*;
3. source->generate可以自動生成
4. window->preference->java->editor->content assist->auto trigger更改自動補全.換成.abcdefg
數學問題
1. %運算符 a%b
1. 符号與a相同，與b無關，b不能為0
2. 進制轉換
1. 十進制數x的k進制表示，不斷地重複對x求餘%k，求商/k，即可以由低到高一次得到各個數位上的數。
2. 要求得由k進制表示的數字的十進制時，我們需要依次計算各個數位上的數字，與該位權重的積，第位權重為k(n-1),然後将它們依次累加即可以得到十進制值。
3. 最大公約數
a%c=0、b%c=0的最大正整數c，能夠同時整除a和b的最大正整數c。
樸素算法：周遊不大于a和b的最大正整數，依次試驗它是否同時滿足兩個十字，并且在所有滿足兩個式子的正整數中挑選最大的那個。如果a，b其中有一個為0，那麼最大公約數為a，b中非零的值。如果a，b都為0，則最大公約數不存在。
歐幾裡得算法：b、(a mod b)的公約數就是a、b的公約數
a,b全為0則它們的最大公約數不存在
若a,b其中之一為0，則它們的最大公約數為a,b中非零的那個
若a,b都不為0，使新的a=b,新b=a%b然後重複該過程。
while (a!=0&&b!=0){
int temp=a%b;
a=b;
b=temp;
}
int res=a;
4. 最小公倍數LCM c%a=0&&c%b=0: a*b/最大公約數
5. 素數判定,判斷從2到sqrt(n)有沒有能夠整除n的數字，如果沒有則是素數。注意1不是素數
1. 使用 int bound = (int)Math.sqrt(n)+1;//計算枚舉上界，放置double值帶來的精度損失，采用根号值取整吼再加1，甯願多枚舉一個值。
2. for循環中的判别條件會計算多次，sqrt是比較耗時的函數之一，strlen也相同。
3. 擷取1000000以下的所有素數：從2開始周遊到n，每次擷取素數後标記其所有倍數為非素數，然後繼續周遊完剩下的所有數，如果沒有被比其小的數字标記為非素數，則為素數。
4. 注意：
标記的時候不從2*i開始标記而是從i*i開始标i
注意判定i*i是不是在[0，n]之間
j每次增加i
6. 分解素因數
1. 分解因數可以不斷的除以這個數，目前的數量的指數增加
2. 輸入為1-10的9次方，是以大于10的5次方的因子隻可能有1個，是以預處理可以隻計算100000個數
3. 對于所有的數字，都隻用算到sqrt(n)，剩餘隻能剩餘1個，并且指數為1
4. 被分解的整數的個數為(e1+1)*(e2+1)*...*(en+1),根據每個因子出現的次數的排列組合（可以出現0次）
7. 二分求幂
求a的2^k次方，是可以由a的1次不斷求平方取得的。我們的目标就是分解a的b次方變為若幹個a的2^k次方的積
a^b=a^1*a^2*...*a^k
b=1+2+...+k=2^0+2^1+...+2^i
i...10就是b的二進制表示中為1的位置
隻保留最後三位數字：
求a的b次幂的時候，随時可以用二分求幂
求餘數的坑：加法，乘法都要做
矩陣快速幂：
矩陣快速幂：
基本類型
int（整型） 4 -2147483648～2147483647
long（長整型） 8 -9223372036854775808 ~ 9223372036854775807
float（浮點型） 4 -3.4E38～3.4E38
double（雙精度型） 8 -1.7E308～1.7E308
char（字元型） 2 從字元型對應的整型數來劃分，其表示範圍是0～65535
byte (位元組) 1 -128-127
1. int轉成long：buf[size1++]=(int)(res%M);
2. int轉成char：ch = (char)('0'+temp);
矩陣（待補坑）
圖論
1. 圖的表示：
鄰接矩陣：稠密圖，且頻繁判斷特定的節點對是否相鄰
優點：
1. 确定某對結點之間是否存在關系時，通路二維數組的相關單元即可
2. 可以查找任意結點為弧頭和弧尾的所有弧
缺點：
1. 稀疏圖儲存時候浪費空間
2. 儲存結點數量為n的圖，空間複雜度為n^2
鄰接表：為每個結點建立一個單連結清單，第i個單連結清單中儲存與界定啊Vi相鄰的所有結點或者所有以結點Vi為弧尾的弧指向的節點。
優點：
1. 周遊的結點個數即是有效的結點個數，大大節省時間，空間複雜度是O(n+e)
缺點：
1. 判斷兩個結點是否存在關系時顯得比較繁瑣，需要周遊V和Vj間是否存在關系時顯得比較繁瑣，需要周遊Vi和Vj所有的鄰接結點
應用場景：存在大量周遊結點的操作而較少判斷兩個特定結點的關系時，使用鄰接表比較合适
資料結構：
1. 結構體儲存結點和邊權值
2. 為每一個結點都建立一個單連結清單儲存相鄰的邊權值和結點的資訊，使用ArrayList來模拟這些單連結清單。
3. 建立一個大小為N的數組，數組彙總儲存的元素即是vector對象，edge[i]的vector表示結點i履歷的單連結清單
2. 并查集：表示集合資訊
用樹表示集合中的數字，每個節點在數組中儲存雙親結點的資訊，跟節點儲存為-1
1. 判斷是否為同一個集合：判斷是否在同一棵數中，尋找雙親結點，判斷是否相同
2. 合并兩個集合：其中一棵樹變成另一棵樹根節點的子樹
3. 判斷根節點與樹深度有關，極端情況退化成單連結清單
4. 路徑壓縮：避免因為樹退化而産生額外的時間消耗，盡可能保持較低的樹高。為了達到這一個目的，我們可以在查找某個特定結點的根節點時，将其餘根節點之間的所有節點都指向根節點。
5. 代碼：
1. 并查集的壓縮是不是一定要做：如果不做就會逾時
2. 在沒有0編号的時候，判斷數組為0即是根節點
3. 測試極端資料：輸入為0，為最大值，可能為0的時候需要輸出1，注意數組要比最大值大
4. 注意結束條件，是不是輸入0就結束
5. 輸出最大值可以Arrays.sort()排序以後，輸出倒數第一個元素
6. 從大到小排序需要用Integer數組，但是Integer隻能循環賦初值。int[]初值為0
7. Collection.max，可以選出list中最大的元素
8. Arrays.asList可以将array轉換成list，但是類型需要相同
9. 建立數組的長度是常量才會有初始的值???
10. (char)(i-'a')
帶權圖分為有向和無向，無向圖的最短路徑又叫做最小生成樹，有prime算法和kruskal算法；有向圖的最短路徑算法有dijkstra算法和floyd算法。
3. 最小生成樹：如果存在一個聯通子圖包含原圖中所有的節點和部分邊，且這個子圖不存在回路，那麼我們稱這個子圖為原圖的一顆生成樹。在帶權圖中，所有的生成樹中邊權的和最小的那棵(或幾棵)被稱為最小生成?。
應用：尋找最低代價
· 1. Kruskal算法：
1. 初始時所有結點屬于孤立的集合(并查集)
2. 按照邊權遞增順序周遊所有的邊，若周遊到的邊兩個頂點仍然分屬于不同的集合，則确定該邊為最小生成樹上的一條邊，并将這兩個頂點分屬的集合合并。
3. 周遊完所有邊後，原圖上所有的節點屬于同一個集合，則被選中的邊和原圖中所有的結點構成最小生成樹。否則原圖不連通，最小生成樹不存在。
4. 代碼：
1. 總共需要選擇（點的數量-1）條邊
2. 可以對于每一個點建立一個int下标，然後做并查集
3. 排序傳回負數的是需要的順序
2. prime算法的基本思想：
4. 最短路徑問題旨在尋找圖中兩節點之間的最短路徑，常用的算法有：floyd算法和dijkstra算法。
應用：确定某兩個城市之間的最短行車長度
1. Floyd算法：适合求解多個節點對之間的最短路徑長度，全源最短路徑。不考慮權值為負值
1. 用鄰接矩陣儲存原圖，edge[i][j] 的值表示從i到j，中間不經過任何結點時距離的最小值 (如果有多條邊，取最小權值儲存至鄰接矩陣。無窮代表不可達)
2. 更新所有值為可以經過結點1的最短路徑長度，相似的依次更新為允許經過的節點添加節點2、節點3、節點4......直到節點N，添加完這些節點後，edge[i][j]就是全局最短路徑長度。
3. 令ans[k][i][j]為從節點i到節點j允許經過編号小于等于k的節點時的最短路徑長度。k=0時代表edge[i][j]，直接距離。
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(ans[i][k]==-1||ans[k][j]==-1)continue;
if(ans[i][j]==-1||ans[i][k]+ans[k][j]<ans[i][j]){
ans[i][j]=ans[i][k]+ans[k][j]
}
}
}
}
4. 注意：時間複雜度是O(n^3)，要求節點的數量不大于200個，否則逾時
5. 如果原圖中兩個結點之間有多餘一條邊時，我們選擇長度最小的邊權值存入鄰接矩陣
6. 當Floyd算法完成後，圖中所有節點之間的最短路徑都将被确定。
2. 迪傑斯特拉算法：隻可以求出特定節點到其他所有節點的最短路徑，單源最短路徑問題
1. 按照最短路徑長度遞增的順序确定每一個結點的最短路徑長度，先确定節點的最短路徑長度不大于後确定每一個結點的最短路徑長度，
2. 求從1出發到其他所有節點的最短路徑長度。
1. 初始化，集合 K 中加入結點 1，結點 1 到結點 1 最短距離為 0，到其它結點為無窮(或不确定)。
2. 周遊與集合 K 中結點直接相鄰的邊(U，V，C)，其中 U 屬于集合 K，V不屬于集合 K，計算由結點 1 出發按照已經得到的最短路到達 U，再由 U 到達 V 時的路徑長度。比較所有與集合 K 中結點直接相鄰的非集合 K 結點該路徑長度，其中路徑長度最小的結點被确定為下一個最短路徑确定的結點，其最短路徑長度即為這個路徑長度，最後将該結點加入集合 K。
3. 若集合 K 中已經包含了所有的點，算法結束;否則重複步驟 2。 我們使用 Dijstra 算法重寫例 4.5。
3. 自己寫的代碼的bug：
1. 初始化完成後要添加N-1個點：while (num < N) {//再加入N-1個點
2. dis[temp.get(i).name] = dis[curr] + temp.get(i).weight;//加的是經過的路徑
3. for (int i = 1; i <= N; i++) {//從1開始到N才結束，周遊所有點找最小值
4. if (K[i] == false && dis[i] != -1 && dis[i]<minn){//判斷可達
5. 加入的點要标記
6. 更新值的時候如果distance相等，cost比較小也要進行更新
7. 巨大的坑 ：輸入會有相同兩個點的多次輸入
8. 寫不對的時候可以考慮再讀一遍題目，想想不符合正常的想法,如果有重複插入，不能繼續插入，而是更新成為更小的值
4. 代碼邏輯：
初始化：
1. dis數組，初始化為-1，代表距離源點距離未确定，否則為經過K數組中的點到源點的距離
2. K數組，代表該點是否加入了K集合
3. 使用ArrayList<Node> arr[]=new ArrayList[maxn];模拟連結清單
1. 找到一個新增加的點curr，該點距離源點距離最近，第一次是源點
2. 更新所有新增點直接連接配接點的距離
3. 重複1，直到所有點都加入了K
5. 空間複雜度為O(N^2),如果用堆進行優化，時間複雜度降低到O(n*logn)
5. 拓撲排序：對于一個有向無環圖，對其進行拓撲排序即求其中節點的一個拓撲序列，對于所有有向邊(U、V)，在該序列中，節點U都排列在V之前。滿足該要求的節點序列，被稱為滿足拓撲次序的序列。求這個序列的過程，被稱為拓撲排序。
1. 求法：
1. 選擇一個入度為0的結點，作為序列的第一個節點。從圖中删除，同時删除以該點為弧尾的所有邊，得到一個新圖。
2. 重複第一步，當圖中還剩下點，但是找不到入度為0的結點的情況，則剩餘的結點形成一個環路，無拓撲排序。
2. 應用：判斷是否有環
3. 實作：可以使用一個隊列來儲存所有入度為0的點
4. 時間複雜度：O(N,E)，N代表每個點進入隊列，E代表周遊所有相連的邊改變度數
5. 代碼的邏輯：
1. 初始化：
1. 度數儲存數組
2. 連結清單儲存數組
2. 構造連結表：對于所有輸入的邊，a中加入b，b入度增加1
3. 将所有入度為0的入隊列
4. 取出隊列中的元素，将其為尾弧的邊删除，并首弧的點入度減一，如果為0，入隊列
5. 如果最後隊列中彈出的數量是總數量，則是正确的有向無環圖
搜尋
1. 枚舉法：注意時間複雜度，例如兩層循環O(n^2)保證n不大于1000
2. 查找要素：
1. 查找空間不遺漏、不重複
2. 查找目标：對枚舉出來的解進行判定
3. 查找方式：枚舉、廣搜、深搜、二叉
3. 廣度優先搜尋：(BFS)(應用很廣泛)
1. 構造搜尋樹：每一層的狀态相同，初始點為根節點
2. 剪枝：因為後通路的狀态一定比先通路的遠，是以每個點隻用通路一次。
3. 使用隊列儲存每一層
4. 關鍵字：
1. 狀态。确定求解問題中的狀态，通過狀态轉移擴充，查找周遊所有的狀态，進而從中尋找我們要的答案。
2. 狀态擴充方式。廣度擴充，先擴充的狀态先進行下一次擴充，在解答樹上展現為，按照層次周遊所有的狀态。
3. 有效狀态。直接舍棄不可能經過的狀态，而不進行擴充。
4. 隊列。實作先進先出的狀态可擴充。
5. 标記。标記有效的狀态。
6. 有效狀态數，決定了時間複雜度
7. 最優。廣搜通常被用來解決最優值問題。最少、最短、最優
4. 深度優先搜尋：DFS，用于求解有或者沒有的問題，沒有逐層周遊的特性
1. 代碼：
1. 數組：
1. 原來資料的數組
2. 狀态數組
3. 方向數組
2. 初始狀态更新
3. 判斷是否滿足
4. 狀态更新
5. 周遊
6. 狀态回溯更新
小技巧
1. 位運算：
1. 取模運算：a&1==1,不能a&1!=0
2. 除2運算：a>>=1
2.
C++
1. scanf報錯問題：_CRT_SECURE_NO_WARINGS
方法一：在VS2015界面中，選擇菜單欄“項目->XXX屬性”，接下來在XXX屬性頁的視窗左側中選擇“配置屬性->C/C++->預處理器”，之後将“_CRT_SECURE_NO_WARINGS”加入到視窗右側的“預處理器定義”中
方法二：加一行代碼 #pragma warning(disable: 4996)
2. 預編譯頭檔案，在其前面的内容都不編譯：
#include "stdafx.h"
4. priority要用c++
優先輸出大資料：priority_queue<int> p;
優先輸出小資料：priority_queue<int, vector<int>, greater<int> >p;
priority_queue<Node, vector<Node>, cmp>p;
struct cmp{
bool operator()(Node a, Node b){
if(a.x == b.x) return a.y>b.y;
return a.x>b.x;
}
};
動态規劃
1. 最長w遞增子序列(LIS)：從已知的序列中取出若幹數組成新的序列，其中新序列的下标和數字都保持遞增(保持先後順序)
1. F[x]=max{1,F[i]+1|ai <ax && i < x};
2. 最長公共子序列(LCS)：順序不改變，能夠取出的兩個字元串的最長公共子序列。
1. dp[i][j]表示 S1 中前 i 個字元與 S2 中前 j 個字元分别組成的兩個字首字元串的最 長公共子串長度
dp[0][j](0 ≤ j ≤ m)=0;
dp[i][0](0 ≤ i ≤ n) = 0;
dp[i][j] = dp[i −1][j −1]+1;(S1[i] == S2[j])
dp[i][j] = max{dp[i −1][j],dp[i][j −1]};(S1[i] ≠ S2[j])
3. 動态規劃時間複雜度分析：由兩個部分組成，狀态數量和狀态轉移複雜度的乘積
4. 解題方法：
1. 考慮相鄰兩個數字之間的關系
5. 代碼坑：不用Math.pow,用*，因為pow會把整數換成浮點數運算，增加了運算的時間。
6. 背包問題
1. 0-1背包問題
1. dp[i][j] = max{dp[i −1][ j − w] + v, dp[i −1][ j]}
2. 周遊所有的物品，周遊所有可能的時間取值，考慮每個物品放入或者不放入背包中的背包中的重量和價值的改變情況。
3.考慮到二維數組中本行隻與上一行相關，是以可以将二維數組換成1維。dp[ j] = max{dp[ j − list[i].w] + v, dp[ j]}
1. 相當于每次更新一輪數組，倒叙周遊保證使用到的位置的值還未被更新
4. 時間複雜度：n*s
3. 完全背包問題：每種物品有無限個，每個物品均有各自的體積，求物品價值總和。
1. 初始狀态，dp[0][0]=0,但是dp[0][1]=負無窮。
2. 求最小的解：初始值為最大值
3. 求最大的解：初始值為最小值
4. 多重背包問題：每種物體可選的數量不再為無窮或者1，而是介于其中的一個确定的數k。
1. 技巧性的拆分：将原數量為k的物品拆分為若幹組，每組物品看成是一件物品，價值和重量為該組的所有物品的價值重量綜合，每組物品包含的原物品個數分别為1、2、4...2^c 最後加上剩下的k-2^c+1，其中 c 為使 k-2^c+1 大于 0 的最大整數。O(s*∑log2(ki));
DataBase
1. 在classpath中設定驅動程式JAR文檔
2. 注冊Driver操作對象
3. 取得Connection操作對象
4. 關閉Connection操作對象
C++部分
string[]
1. 輸入
int main() {
string aa;
aa.resize(100);
scanf("%s",&aa[0]);
printf("%s",aa.c_str());
return 0;
}
2. 必須resize，但是如果resize，在後期比較的時候使用==會為false，如果用compare會永遠為true，如果用strcmp會為false
char[]
1. 使用char*沒有确定長度，scanf會出錯
2. 不能直接指派，strcpy(word, "Jump");
3. 參數中不能使用char[]
4. 不能直接比較strcmp(name,"")==0，傳回結果代表第一個值減去第二個值，頭函數為<string.h>
5. 不會自動初始化，需要手動指定數組結束，test[2]=0;要轉成數字的時候不要複制0
6. 周遊for (int i=0; i<int(strlen(oplist)); i++),頭檔案 #include <string.h>
類
1. 申明
Student student = Student();
Student *student = new Student();
2. 重載
bool operator < (const Student &stu)const{
return studentnumber<stu.studentnumber;
}
3. 申明類數組
1. 對象需要有public構造函數
2. Student buf[10010];
sort
1. 頭函數
#include <algorithm>
輸入輸出
1. 輸入帶空格的一行字元串：while (gets(equation)){}
2. 檔案重定向
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
字元串轉數字
int atoi ( const char * str );
double atof ( const char * str );
long int atol ( const char * str );
隊列
1. 優先隊列
priority_queue<int> Q;
priority_queue<int, vector<int>, greater<int>> Q;
![CSP認證-201412-1-門禁系統[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)