普及組算法匯總

2022 年 9 月 4 日
筆記
普及組, 筆記

名詞

OI: olympiad in informatics 信息學奧林匹克競賽

IOI: international olympiad in informatics 國際信息學奧林匹克競賽

NOI: national olympiad in informatics 全國信息學奧林匹克競賽

NOIP: national olympiad in informatics in province 全國信息學奧林匹克競賽省賽

CSP: 非專業計算機能力認證 -J, -S。

J: junior: 低級的

S: senior: 高級的

進入提高組複賽，且得分非0的選手可以參加NOIP

CCF: China computer fundation 中國計算機協會

SMTP: 簡單郵件傳輸協議(simple mail transport protocol)

POP3: 郵局協議版本3(Post Office Protocol – Version 3)

IMAP: 交互郵件訪問協議（Internet Message Access Protocol)

小知識

面向過程: 只有C語言面向對象: 除了C語言的所有語言(C++, python, Java)

編譯型語言和解釋型語言編譯型語言: C,C++,Pascal解釋型語言: python, Java, PHP

計算機系統windows系統類unix系統: 除了windows系統以外的所有系統: android, ios, macOS, linux…

碼

原碼、反碼、補碼：8位二進制數表示的有符號整數

最左邊一位是符號位(1:負數,0:正數)

反碼: 原碼的符號位不變，其他位取反

補碼: 反碼+1

補碼:10101011

反碼:10101010

原碼:11010101

==> -85

-52

原碼:10110100

反碼:11001011

補碼:11001100

運算符

$x<<y= x\times 2^y$

$x>>y=\frac{x}{2^y}$

&	按位與操作，按二進制位進行”與”運算。運算規則： 0&0=0; 0&1=0; 1&0=0; 1&1=1;	(A & B) 將得到 12，即為 0000 1100
\|	按位或運算符，按二進制位進行”或”運算。運算規則： 0\|0=0; 0\|1=1; 1\|0=1; 1\|1=1;	(A \| B) 將得到 61，即為 0011 1101
^	異或運算符，按二進制位進行”異或”運算。運算規則： 0^0=0; 0^1=1; 1^0=1; 1^1=0;	(A ^ B) 將得到 49，即為 0011 0001
~	取反運算符，按二進制位進行”取反”運算。運算規則： ~1=-2; ~0=-1;	(~A ) 將得到 -61，即為 1100 0011，一個有符號二進制數的補碼形式。
<<	二進制左移運算符。將一個運算對象的各二進制位全部左移若干位（左邊的二進制位丟棄，右邊補0）。	A << 2 將得到 240，即為 1111 0000$x<<y= x\times 2^y$
>>	二進制右移運算符。將一個數的各二進制位全部右移若干位，正數左補0，負數左補1，右邊丟棄。	A >> 2 將得到 15，即為 0000 1111$x>>y=\frac{x}{2^y}$

$∨$:或 -> 只要有一個為真，則表達式為真

$∧$:且 -> 兩個都是真才為真，有一個假為假

$﹃（¬）$：非 -> 假為真，真為假

名稱（按優先級從高到低）	符號	順序
後綴	() [] -> . ++ – –	從左到右
一元	+ – ! ~ ++ – – (type)* & sizeof	從右到左
乘除	* / %	從左到右
加減	+ –	從左到右
移位	<< >>	從左到右
關係	< <= > >=	從左到右
相等	== !=	從左到右
位與 AND	&	從左到右
位異或 XOR	^	從左到右
位或 OR	\|	從左到右
邏輯與 AND	&&	從左到右
邏輯或 OR	\|\|	從左到右
條件	?:	從右到左
賦值	= += -= *= /= %=>>= <<= &= ^= \|=	從右到左
逗號	,	從左到右

數學知識

集合論基礎

集合：若干個互異無序元素。集合有兩種記錄方法，如 $A = \{1,2,3\},T = \{i|i為偶數\}$
空集：沒有函數的集合。計作：$\emptyset$
屬於與不屬於: 表示一個元素是否屬於該集合。如 $1 \in A, 4 \notin A$
子集：如果集合A中包含集合B中的所有元素，則稱B為A的子集。記作 $B \subset A$。若A不是B的子集，記為$A\not\subset B$。
真子集：如果B是A的子集，且B與A並不相等，則稱B是A的真子集。記作 $B \subseteq A$。若A不是B的真子集，記為$A\not\subseteq B$。
並集：字面意思為將兩個集合合併後的結果。即如果元素x在集合A或集合B中，那麼x在集合A與集合B的並集中。A與B的並集可以記作 $X = A \cup B $
交集：字面意思為兩個集合相交的部分。即如果元素x既在集合A中，又在集合B中。那麼元素x在集合A與B的交集中。A與B的交集可以記作 $Y = A \cap B$。

區間：區間是一種特殊的集合，表示一個連續的部分的所有元素。如 $[1,2]、 (4, 5)、 [9, 10)、 (2, +\infty)$
閉區間、開區間與半開半閉區間：
用[]表示的是閉區間，表示區間左右兩端的元素都在集合中，如$[1,2]$，1也是集合的一個元素；
用()表示的是開區間，表示區間左右兩端的元素都不在集合中，如$(4,5)$，4和5都不在集合中；
一邊中括號一邊小括號的是半開半閉區間，中括號那一端的元素在集合中，小括號那一端的不在集合中。
帶有無窮符號的區間：有$+\infty$ 與 $-\infty$ 。無窮符號那一端的必須是小括號，且正無窮的正號不能省略。
幾個重要的集合: 實數集：$\mathbb{R}$ , 自然數集合：$\mathbb{N}$, 整數集合: $\mathbb{Z}$, 正整數集合: $\mathbb{N^+}$
集合與不等式的轉化：如 $1\leq x \leq 10$ 可以寫成 $[1,10]$，$x \gt 3$ 可以寫成 $(3, +\infty)$

概率論基礎

事件：一個不受主觀意念控制的事情。如「天要下雨」，”彩票中一千萬”, “CSP初賽全部靠蒙考滿分”, “明天太陽照常升起”是事件，”我今天吃肯德基”, “CSP憑實力0分”, “我晚上通宵寫代碼”不是事件。在概率論中，我們常用一個字母表示一個事件，如事件A為天要下雨。
概率：事件發生的可能性。一般用P表示，事件A發生的概率記為P(A) 。
頻數與頻率。在計算一個事件發生的概率時，需要進行多次隨機試驗。事件發生的次數就是頻次，事件發生頻次的比例就是頻率。如事件A為扔硬幣扔出正面。我扔了10次硬幣，9次正面，則頻次為9，頻率為90%。
積事件：若事件C為事件A與事件B同時發生，那麼事件C就是事件A與事件B的積事件。記為$C = A \cap B$，$P(C) = P(A\cap B) = P(AB)$
獨立事件：兩個事件的發生沒有相關關係，則這兩個事件為獨立事件。如”今天下雨”與”扔硬幣扔出正面”是獨立事件。”今天下雨”與”今天空氣濕度高於50%”不是獨立事件。
獨立事件的概率：$P(AB) = P(A) \cdot P(B)$ 。注意只有事件A與B獨立該式才成立。
和事件的概率：$P(A+B) = P(A) + P(B) – P(AB)$ 。和事件為兩個事件至少發生一個的概率。
條件概率：$P(A|B)$ 表示在B事件發生的條件下，A事件發生的概率。即「如果今天下雨，門口路上堵車的概率。」、「扔一次骰子扔出的數字是偶數，那麼扔出的數字是2的概率」。
貝葉斯公式：$P(AB) = P(A|B) \cdot P(B) = P(B|A) \cdot P(A)$
互斥事件：不可能同時發生的事件。如「扔一次骰子扔出1」與「扔一次骰子扔出2」，「扔一次硬幣為正面」與「扔一次硬幣為反面」。
對立事件：其中至少一個會發生的互斥事件。如」扔一次骰子扔出1「與「扔一次骰子扔出2」不是對立事件，「扔一次硬幣為正面」與「扔一次硬幣為反面」是對立事件。事件$A$的對立事件記為$\bar{A}$。那麼$P(A)+P(\bar{A}) = 1$。
全概率公式：$P(A) = P(A|B)\cdot P(B) + P(A|\bar{B}) \cdot P(\bar{B})$
數學期望：隨機事件的結果。如果一個隨機試驗會出現多種結果（或事件）$X_1, X_2, …,X_i$，每種事件可以獲得$V_i$的收益。那麼隨機試驗$X$ 的數學期望為 $E(X) = \displaystyle \sum_{i=1}^nP(X_i)\cdot V_i$。

平面直角坐標系

平面直角坐標系由橫軸與縱軸組成。橫軸為x軸，縱軸為y軸，點的坐標由括號組成的二元組表示，如(x, y)。
點A對x軸作垂線到達的位置為A的橫坐標，對y軸作垂線到達的位置為B的縱坐標。

三角函數

勾股定理：在直角三角形中，假設三條邊長度為 $a, b, c(a\leq b\lt c)$。則$a^2 + b ^ 2= c^2$。
“小角對小邊”：在直角三角形中，角度較小的角所對的邊較短
角度制：一種表示角度的方法，一般寫為 $30^\circ, 75^\circ$等。
單位圓：圓心在原點，半徑為1的圓。
弧度制：高中的數學表示方法。角對應的單位圓上弧的長度
$\pi = 180^\circ$
正弦$\sin \theta$ : 角$\theta$對邊與斜邊的比值，餘弦$\cos \theta$: 角 $\theta$ 鄰邊與斜邊的比值，正切$\tan$: 角 $\theta$ 對比與鄰邊的比值
反三角函數: 反正弦函數 $\arcsin x$ : 反餘弦函數 $\arccos x$: 反正切函數 $\arctan x$ 。

組合數學

排列：$A_n^m=\frac{n!}{(n-m)!}$（順序有關）

組合：$C_n^m=\frac{n!}{m!(n-m)!}$（順序無關）

$C_n^m=(C^{m\div p} _{n\div p})(C^{m\mod p}_{n\mod p})$

$ h(n)=h(0) \times h(n-1) + h(1) \times h(n-2)+……+h(n-1)\times h(0)$

$= \sum h(i)\times h(n-i-1)$

$h(n)=C^n_{2n}-C^{n+1}_{2n}$

$h(n)=\frac{C_{2n}^n}{n+1}$

圓排列：$A^m_n=\frac{n!}{(n-m)!}\div m$

錯排序：$D(n)=n!(\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+…+\frac{(-1)^n}{n!})=n!\sum\limits^n_{k=2}\frac{(-1)^k}{k!}=\lbrack\frac{n!}{e}+\frac{1}{2}\rbrack$

樹

存樹

雙親表示法

記錄某個節點的父節點。（根表示為-1）

孩子表示法

用鏈表來表示每個節點的所有子節點。

孩子兄弟表示法

存儲每個節點的子節點和兄弟節點。

二叉排序(查找)樹(binary search tree)

對於二叉樹的任意一個節點，左子樹的所有結點都比他小，右子樹所有節點都比他大。

其中序遍歷是嚴格遞增的。

平衡 bst

深度為 $\log n$ 的二叉樹，查找一個點的時間複雜度為 $O(\log n)$。

歐拉道路

度數為奇數的點為 $0$ 或 $2$。

歐拉迴路

度數為奇數的點為 $0$。

保留小數

#include <iomanip>
cout <<fixed <<setprecision(2) <<a;
printf("%.2f",a);

數組(array)

int/double …… a[1005];      //設置數組a，類型為int/double……（變量類型 數組名[數組長度]）
a[n]=n                   //將數組a的第n個賦值為n
cout <<a[n];             //輸出數組a的第n個
arr[100]={0};            //將數組arr全設為0
arr[100]={n1,n2,n3};     //將數組arr的第0個賦值為n1，第1個賦值為n2,第2個賦值為n3

1.數組長度不要用變量

2.數組長度可以多幾個

3.數組的第一個元素下標為0，即第0個

4.*[n]={n};時，第0個設為n,其他位都為0

排序

#include <algorithm>    //頭文件，導入排序的庫
sort(*+0,*+n+1,……)      //按比較器排序（默認從小到大排序）sort(變量名+開始排序的下標，變量名+結束排序的下標+1，比較器)
greater<int/double ……>()//從大到小排序

格式化數組

#include <cstring>
memset(*,n,sizeof(*))   //把數組的每個值變成同一個值

定義比較器

bool cmp(int x,int,y){  //布爾類型函數，名為cmp
    if(x>y){            
        return true;    //如果x大於y，返回true
    }
    else{               
        return false;   //否則返回false
    }
}

字符串（string）

#include <string>      //頭文件，導入字符串
string *;              //設置變量*，類型為string
cout <<*;              //輸出變量*
getline(cin,*);        //輸入一行忽略空格
*.size()               //求字符串*的長度
*.find(s)               //字符串*中第一個字符串s的位置,如果沒有，返回string::npos
*.insert(index,s)       //在字符串*下標為index的位置插入字符串s
*.replace(index,length,s)  //在字符串*下標為index的位置選取長度為length的部分替換為s
*.substr(index,length) //返回字符串*從下標為index的位置開始，長度為length的部分
substring               //子字符串（必須連續）
subsequence               //子序列（可以不連續）

數學函數

#include <cmath>        //頭文件
pow(a,b)                //a的b次方，參數類型double，返回值類型double
max(a,b)                //a與b的最大值，參數類型相同
min(a,b)                //a與b的最小值，參數類型相同
ceil(x)                 //向上取整，參數類型double
floor(x)                //向下取整，參數類型double
round(x)                //四捨五入，參數類型double
sqrt(x)                 //開根，參數類型double，返回值類型double
__gcd(x,y)              //求x與y的最大公因數
x*y/__gcd(x,y)          //求x與y的最小公倍數

定義函數

int/double …… *(int/double …… *, ……){  //函數類型 函數名稱（參數類型 參數名，……）
    ……                   //函數執行的事
    }

當出現兩個相同的變量時，按就近原則使用

函數內可以調用別的函數，也可以調用自己，即遞歸

struct(結構體)

//定義一種新的類型
struct name{              //定義一個名為name的類型              
    int num;              //一個整數類型num
    double num2;          //一個實數類型num2
    ......                //內含的其他變量（最後不用return）
    void print(){//成員方法
    	cout <<num;
    }
    name(int num,double num2):num(_num),num2(_num2){ }//構造函數初始化
    name(){
    	num1=114514;
        num2=1919.810;//初始化
    }
    name(): ......//用冒號初始化
    name operator+(name num){//重載運算符
    	return node(y+num.x,y+num.y);
    }
};                        
/、結尾有；
name a;                   //定義一個類型為name的變量a
a.num=114514;             //變量a的num值為114514
a.num2=1919.810           //變量a的num2值為1919.810
a.print();//使用成員方法
a=(1,1.1);//初始化
name b;
a=a+b;//重載後的運算符進行運算

class(類)

class a{
	int x,y;//x和y是私有的
   public:
     void print(){
     	cout <<x;//print()是公有的
     }
  
}

鏈表

struct node{
    int val;
    node *nxt;//自引用
};
int main(){
    node *head,*tail,*p;
    int x;
    cin >>x;
    //輸入任意個整數，
    //在鏈表的末尾添加一個值為該整數的節點，
    //輸入-1時結束。
    head=new node;
    tail=head;
    while(x!=-1){
        p=new node;
        //p->val <==> (*p).val;
        p->val=x;
        p->nxt=NULL;
        tail->nxt=p;
        tail=p;
        cin >>x;
    }
    //輸出鏈表
    p=head;
    while(p->nxt!=NULL){
        p=p->nxt;
        cout <<p->val <<" ";
    }
    return 0;
}

STL模板庫

優先隊列

priority_queue<int> q;//優先隊列
priority_queue<int,vector<int>,greater<int>> q;//從小到大
q.push();//推入
q.top();//隊頂

pair

pair<int,int> x;//定義兩個數據在x中
x={1,2};//初始化，形同數組
x.first=1;//第一個
x.second=2;//第二個
    
pair<int,pair<int,int>> x;//套娃
x.first;//第一個
x.second.first;//第二個
x.second.second;//第三個

set

#include <set>
set<int> s;//定義集合
s.insert(1);//插入
if(s.find(2)!=s.end())//查找2是否在s中

map

#include <map>//map是映射的意思
map<int,int> mp;//一個數據對應一個數據
    mp[2]=3;
    mp[-1]=2;
    mp[114514]++;//map默認為0，可以直接使用，而且數據量大，只是慢

最短路

P3366 【模板】最小生成樹

Kruskal

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m,ans=0,x=1;
bool vi[200005];
typedef pair<int,int> node;
priority_queue <node,vector<node>,greater<node> > q;
vector<node> e[200005];
node a[200005];
int main(){
    cin >>n >>m;
    for(int i=1;i<=m;i++){
        int u,v,l;
        cin >>u >>v >>l;
        e[u].push_back({l,v});
        e[v].push_back({l,u});
    }
    for(int i=1;i<=n;i++){
        vi[i]=false;
    }
    vi[1]=true;
    for(int t=1;t<=n-1;t++){
        for(int i=0;i<e[x].size();i++){
            q.push(e[x][i]);
        }
        while(!q.empty() && vi[q.top().second]){
            q.pop();
        }
        if(q.empty()){
            cout <<"orz";
            return 0;
        }
        ans+=q.top().first;
        x=q.top().second;
        vi[x]=true;
    }
    cout <<ans;
    return 0;
}

SPFA

#include <iostream>
#include <queue>
#include <vector>
#include <cstring> 
using namespace std;
struct node{
    int v,l;
};
queue<int> q;
vector<node> e[100005];
int n,m,dis[100005];
int main(){
    memset(dis,0x3f,sizeof(dis));
    int n,m,x;
    cin >>n >>m >>x;
    for(int i=1;i<=n;i++){
        int u,v,l;
        cin >>u >>v >>l;
        node temp;
        temp.v=v,temp.l=l;
        e[u].push_back(temp);
    }
    int INF=dis[1];
    q.push(1);
    dis[1]=0;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=0;i<e[now].size();i++){
            int len=e[now][i].l;
            int nxt=e[now][i].v;
            if(dis[nxt]>dis[now]+len){
                q.push(nxt);
                dis[nxt]=dis[now]+len;
            }
        }    
    }
    if(dis[x]!=INF)cout <<dis[x];
    else cout <<-1;
    return 0;
}

~~關於SPFA,它死了~~

Dijkstra

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
struct node{
    int v, len;
};
ll dis[100005];
vector<node> e[100005];
typedef pair<int,int> PII;
int main(){
    int n, m, x;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        node temp;
        temp.v = v;
        temp.len = len;
        e[u].push_back(temp);        
    }
    priority_queue<PII, vector<PII>, greater<PII> > q;
    q.push({0,1});
    memset(dis, 0x3f, sizeof(dis));
    long long INF = dis[0];
    dis[1] = 0;
    while (!q.empty()) {
        while (!q.empty() && q.top().first > dis[q.top().second]) q.pop();
        if (q.empty()) break;
        int now = q.top().second;
        q.pop();
        for (int i = 0; i < e[now].size(); i++) {
            int nxt = e[now][i].v;
            int len = e[now][i].len;
            if (dis[nxt] > dis[now] + len) {
                q.push({dis[now]+len, nxt});
                dis[nxt] = dis[now] + len;
            }
        } 
    }
    for (int i = 1; i <= n; i++) {
        if (dis[i] != INF) cout << dis[i] << ' ';
        else cout << -1 << ' ';
    }
    return 0;
 }

Floyd

for(int k=1;k<=n;k++){
	for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
      		f[i][j]=min(f[i][k],f[i][j]+f[k][j;
      }
   }
}

傳遞閉包

for(int k=1;k<=n;k++){
	for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
      		f[i][j]|=f[i][j]&f[k][j;
      }
   }
}

質數篩

1.普通篩法

最普通的篩法，也就是將前 $n$ 個正整數一個一個來判斷是否為素數，並且在判斷素數的時候要從 $2$ 枚舉到 $n-1$ 來判斷。

CODE

for(int i=1;i<=n;++i){//枚舉1到n
    bool flag=false;
    for(int j=2;j<i;++j){//枚舉2到i
        if(i%j==0){//如果i%j=0,也就是i已經不為素數了
            flg=1;//打上標記
            break;//跳出循環，不用再枚舉了
        }
    }
    if(!flag)prime[i]=1;//如果沒有被打上標記,標記這個數是素數。
}

這樣的時間複雜度為 $O(n^2)$。

2.普通篩法的優化

學過奧數的朋友們可能會發現，在判斷素數的時候，不一定需要枚舉到 $i-1$ 只需要枚舉到 $\sqrt{n}$ 就可以判斷出來了。

CODE

for(int i=1;i<=n;i++){//枚舉1到n
    bool flag=false;
    for(int j=2;j*j<=i;j++){//枚舉2到i
        if(i%j==0){//如果i%j=0,也就是i已經不為素數了
            flag=true;//打上標記
            break;//跳出循環，不用再枚舉了
        }
    }
    if(!flag)prime[i]=1;//如果沒有被打上標記,標記這個數是為素數。
}

這樣的時間複雜度為 $O(n\sqrt{n})$。

3.埃氏篩

我們發現，上面兩種篩法會篩到許多沒有意義的數，所以我們必須換一種思想方式。

埃氏篩，就是先將 $prime$ 數組全部賦值為 $1$。(記得將 $prime_i$ 賦值為 $0$ )。仍然是要從 $1$ 枚舉到 $n$ 。我們先假設當前枚舉到了 $i$。

如果 $prime_i=1$也就是 $i$ 為質數，則我們可以知道 $i$ 的倍數均為合數，所以我們就將 $prime_{i\times k (2\leq k<n)}$ 賦值為 $0$。

最終篩完之後，如果 $prime_i=1$, $i$ 就是質數。

CODE

memset(prime,1,sizeof(prime));
priem[1]=0;
for(int i=1;i<=n;++i){
    if(prime[i]){
        for(int j=2;j*i<=n;++j){
            prime[i*j]=0;
        }
    }
}

這樣的時間複雜度為 $O(nlogn)$

4.歐拉篩(線性篩)

我們發現，埃氏篩已經很快了，但是還是有所不足。

因為在埃氏篩中，有很多數有可能被篩到很多次（例如 $6$,他就被 $2$ 和 $3$ 分別篩了一次）。所以在歐拉篩中，我們就是在這個問題上面做了優化，使得所有合數只被篩了一次。

首先，我們定義 $st_i$ 數組表示 $i$ 是否為質數，$primes_i$ 儲存已經找到的所有質數，$cnt$ 儲存當前一共找到了多少質數。

如果當前已經枚舉到了 $i$。如果 $st_i=1$ ，也就是 $i$ 為素數。則 $primes_{cnt+1}=i$。

然後我們每一次枚舉都要做這個循環: 枚舉 $j$ 從 $1$ 到 $cnt$。$st_{primesj\times i}=0$（因為 $primes_j$ 為素數，$i$ 就表示這個素數的多少倍，要把他篩掉。

注意，接下來是重點！如果 $i\mod primes_j=0$，跳出第二層循環。(因為歐拉篩默認每一個合數只能由他的最小質因數篩去，而滿足以上條件之後，$primes_j$ 就不是這個數字的最小質因數了，所以我們跳出第二層循環)。因此，有了這一層優化之後，每一個合數就只能被篩掉一次了。

CODE

memset(st,0,sizeof(st));
st[1]=0;
for(i=2;i<=n;i++){
    if(st[i]){
        primes[cnt++]=i;
        for(j=0;primes[j]*i<=n&&j<=cnt;j++){
            st[primes[j]*i]=0;
            if(i%primes[j]==0)break;
        }
    }
}

這樣的時間複雜度為 $O(n)$

DFS

輸入兩個整數$n, m$ ，然後輸入$n$個整數，你可以從中選擇一些數字，問有多少種方案可以讓選擇的數字和為$m$。

若方案A與方案B選擇的數字中，有一個位置上的數字A選擇了，但B沒有選擇，我們就認為兩種方案不同，此時方案數是多少？

#include <iostream>
using namespace std;
int a[105],n,ans,m;
void f(int now,int sum){
	if(now==n+1){
        if(sum==m){
            ans++;
        }
        return ;
    }
    f(now+1,sum+a[now]);
    f(now+1,sum);
}
int main(){
    cin >>n >>m;
    for(int i=1;i<=n;i++){
        cin >>a[i];
    }
    f(1,0);
    cout <<ans;
    return 0;
}

若方案A與方案B選擇的所有數字都相同，我們就認為兩種方案相同。此時方案數是多少？

#include <iostream>
#include <algorithm>
using namespace std;
int a[105],n,ans,m;
bool flag;
void f(int now,int sum,bool flag){
    if(now==n+1){
        if(sum==m){
            ans++;
        }
        return ;
    }
    if(a[now-1]!=a[now] || flag){
        f(now+1,sum+a[now],flag=true);
    }
    f(now+1,sum,flag=false);
}
int main(){
    cin >>n >>m;
    for(int i=1;i<=n;i++){
        cin >>a[i];
    }
    sort(a+1,a+n+1);
    f(1,0,true);
    cout <<ans;
}

給定一個$n * m$的矩陣，輸入兩個整數$n,m (1\leq n,m \leq 10)$ 為矩陣的行數和列數，然後輸入n行，每行m個數字，每個數字$-1000 \leq a_{i,j} \leq 1000$。

求從$(1, 1)$走到$(n, m)$的所有路徑中，路徑上所有數字之和最大可以是多少。

#include <iostream>
using namespace std;
int a[1005][1005],n,m,x1,y1,x2,y2,de_x[2]={1,0},de_y[2]={0,1},ans=-1e9;
bool found=false,flag[1005][1005];
bool c(int x,int y){
    if(x<=0 || x>n || y<=0 ||y >m)return false;//必須在最前面 
    if(flag[x][y])return false;
    return true;
}
void f(int x,int y,int nows){
    if(x==n && y==m){
        ans=max(ans,nows);
        return ;
    }
    flag[x][y]=true;
    for(int i=0;i<4;i++){
        int nx=x+de_x[i];
        int ny=y+de_y[i];
        if(c(nx,ny)){
            f(nx,ny,nows+a[nx][ny]);
        }
    }
    flag[x][y]=false;
}
int main(){
    cin >>n >>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >>a[i][j];
        }
    }
    f(1,1,a[1][1]);
    cout <<ans;
    return 0;
}

給定一個$n * m$的01矩陣，輸入兩個整數$n,m (1\leq n,m \leq 1000)$ 為矩陣的行數和列數，然後輸入n行，每行m個數字，每個數字為0或1.其中0表示通路，1表示牆壁。

輸入四個整數$x1, y1, x2, y2$，問從 $(x1, y1)$ 能否走到 $ (x2, y2)$。可以，則輸出YES；否則輸出NO

#include <iostream>
using namespace std;
int a[1005][1005],n,m,x1,y1,x2,y2,de_x[4]={-1,1,0,0},de_y[4]={0,0,-1,1};
bool found=false,flag[1005][1005];
bool c(int x,int y){
    if(x<=0 || x>n || y<=0 ||y >m)return false;//必須在最前面 
    if(flag[x][y])return false;
    if(a[x][y]==1)return false;
    return true;
}
void f(int x,int y){
    if(x==x2 && y==y2){
        found=true;
        return ;
    }
    flag[x][y]=true;
    for(int i=0;i<4;i++){
        int nx=x+de_x[i];
        int ny=y+de_y[i];
        if(c(nx,ny)){
            f(nx,ny);
        }
    }
}
int main(){
    cin >>n >>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >>a[i][j];
        }	
    }
    cin >>x1 >>y1 >>x2 >>y2;
    f(x1,y1);
    cout <<(found?"yes":"no");
    return 0;
}

BFS

拓撲排序

有$n$課$,m$個前置條件。每個前置條件為兩個數字$u,v$表示上了第$u$個課才能上第$v$個課，請問能不能上完所有的課？輸出任意一個上課方案

      #include <iostream>
      #include <vector>
      #include <queue>
      using namespace std;
      vector<int> e[100005];
      int du[100005];
      vector<int> ans;
      int main(){
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            e[u].push_back(v);
            du[v]++;
        }
        queue<int> q;
        for (int i = 1; i <= n; i++) {
            if (du[i] == 0){
                q.push(i);
            }
        }
        while (!q.empty()){
            // 2. 找隊首
            int now = q.front();
            q.pop();
            ans.push_back(now);
            // 3. 找相鄰點
            for (int i = 0; i < e[now].size(); i++) {
                int nxt = e[now][i];
                du[nxt]--;
                if (du[nxt] == 0) {
                    q.push(nxt);
                }
            }      
        }
        if (ans.size() != n) cout << -1;
        else {
            for (int i = 0; i < ans.size(); i++) {
                cout << ans[i] << ' ';
            }
        }
        return 0;
      }

給定一個$n \times m$的矩陣，$1$表示牆，$0$表示路，你要從$(1,1)$走到$(n,m)$，需要多少步?

    #include <iostream>
    #include <queue>
    using namespace std;
    struct node {
        int x, y; 
    };
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    // dis[x][y]: (1,1)到(x,y)的距離 
    int dis[105][105], a[105][105];
    bool visited[105][105];
    int n, m;
    bool check(int x, int y) {
        if (x <= 0 || y <= 0 || x > n || y > m) return false;
        if (a[x][y] == 1) return false;
        if (visited[x][y]) return false;
        return true;
    }
    
    int main(){
        cin >> n >> m;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++) {
                cin >> a[i][j];
            }
        }
        queue<node> q;
        // 1. 放入起始點 
        node start;
        start.x = 1, start.y = 1;
        q.push(start);
        visited[1][1] = true;
    
        // 只要隊列非空，繼續循環 
        while (!q.empty()) {
            // 2. 彈出隊首 
            node now = q.front();
            q.pop();
            // 3. 找到當前點所有相鄰的點，入隊,把相鄰點設為已訪問過 
            for (int i = 0; i < 4; i++) {
                node nxt;
                nxt.x = now.x + dx[i];
                nxt.y = now.y + dy[i];
                if (check(nxt.x, nxt.y)) {
                    q.push(nxt);
                    // plan2
                    visited[nxt.x][nxt.y] = true;
                    dis[x][y]: (1,1)到(x,y)的最短距離 
                    dis[nxt.x][nxt.y] = dis[now.x][now.y] + 1;
                }
            }
        }
        if (visited[n][m]) cout << dis[n][m];
        else cout << -1;    
    }

層序輸出樹

    #include <iostream>
    #include <queue>
    #include <vector>
    using namespace std;
    vector<int> e[10005];
    bool flag[10005];
    int main(){
        int n;
        cin >>n;
        for(int i=1;i<=n-1;i++){
            int u,v;
            cin >>u >>v;
            e[v].push_back(u);
            e[u].push_back(v);
        }
        queue<int> q;
        q.push(1);
        flag[1]=true;
        while(!q.empty()){
            int now=q.front();
            q.pop();
            cout <<now <<" ";
            for(int i=0;i<e[now].size();i++){
                int nxt=e[now][i];
                if(flag[nxt])continue;
                q.push(nxt);
                flag[nxt]=true;
            }
        }
        return 0;
    }

樹狀數組1

p3374

    #include <iostream>
    using namespace std;
    int n,m,a[500005],b[500005];
    int lowbit(int x){
        return x & -x;
    }
    void init(){
        for(int i=1;i<=n;i++){
            b[i]+=a[i];
            if(i+lowbit(i)<=n)b[i+lowbit(i)]+=b[i];
        }
    }
    void add(int pos,int x){
        while(pos<=n){
            b[pos]+=x;
            pos=pos+lowbit(pos);
        }
    }
    int fi(int pos){
        int ans=0;
        while(pos>=1){
            ans+=b[pos];
            pos-=lowbit(pos);
        }
        return ans;
    }
    int main(){
        cin >>n >>m;
        for(int i=1;i<=n;i++){
            cin >>a[i];
        }
        init();
        while(m--){
            int q,x,y;
            cin >>q >>x >>y;
            if(q==1){
                add(x,y);        
            }
            else{
                cout <<fi(y)-fi(x-1) <<endl;
            }
        }
        return 0;
    }

樹狀數組2

p3368

    #include <iostream>
    using namespace std;
    typedef long long ll;
    ll n,m,a[500005],b[500005],f[500005];
    ll lowbit(int x){
        return x & -x;
    }
    void init(){
        for(int i=1;i<=n;i++){
            f[i]+=a[i];
            if(i+lowbit(i)<=n)f[i+lowbit(i)]+=f[i];
        }
    }
    void add(int pos,int x){
        while(pos<=n){
            f[pos]+=x;
            pos=pos+lowbit(pos);
        }
    }
    ll fi(int pos){
        int ans=0;
        while(pos){
            ans+=f[pos];
            pos-=lowbit(pos);
        }
        return ans;
    }
    int main(){
        cin >>n >>m;
        for(int i=1;i<=n;i++){
            cin >>b[i];
        }
        init();
        while(m--){
            ll q;
            cin >>q;
            if(q==1){
                ll x,y,k;
                cin >>x >>y >>k;
                add(x,k);
                add(y+1,-k);
            }
            else{
                ll x;
                cin >>x;
                cout <<fi(x)+b[x] <<endl;
            }
        }
        return 0;
    }

Tags: 普及組筆記

普及組算法匯總

名詞

小知識

碼

運算符

數學知識

集合論基礎

概率論基礎

平面直角坐標系

三角函數

組合數學

樹

存樹

雙親表示法

孩子表示法

孩子兄弟表示法

二叉排序(查找)樹(binary search tree)

平衡 bst

歐拉道路

歐拉迴路

保留小數

數組(array)

排序

格式化數組

定義比較器

字符串（string）

數學函數

定義函數

struct(結構體)

class(類)

鏈表

STL模板庫

優先隊列

pair

set

map

最短路

Kruskal

SPFA

Dijkstra

Floyd

傳遞閉包

質數篩

1.普通篩法

CODE

2.普通篩法的優化

CODE

3.埃氏篩

CODE

4.歐拉篩(線性篩)

CODE

DFS

輸入兩個整數\(n, m\) ，然後輸入\(n\)個整數 ，你可以從中選擇一些數字，問有多少種方案可以讓選擇的數字和為\(m\)。

給定一個\(n * m\)的矩陣，輸入兩個整數\(n,m (1\leq n,m \leq 10)\) 為矩陣的行數和列數，然後輸入n行，每行m個數字，每個數字\(-1000 \leq a_{i,j} \leq 1000\)。

給定一個\(n * m\)的01矩陣，輸入兩個整數\(n,m (1\leq n,m \leq 1000)\) 為矩陣的行數和列數，然後輸入n行，每行m個數字，每個數字為0或1.其中0表示通路，1表示牆壁。

BFS

拓撲排序

給定一個\(n \times m\)的矩陣，\(1\)表示牆，\(0\)表示路，你要從\((1,1)\)走到\((n,m)\)，需要多少步?

層序輸出樹

樹狀數組1

樹狀數組2

分享此文：

Related Posts

Spring9——通過用Aware接口使用Spring底層組件、環境切換

Qucs初步使用指南（不是multism）

Python入門系列（九）pip、try except、用戶輸入、字符串格式

雷軍傳-懷揣夢想，砥礪前行

VirMach 便宜 VPS

QNews

熱門搜尋

輸入兩個整數\(n, m\) ，然後輸入\(n\)個整數，你可以從中選擇一些數字，問有多少種方案可以讓選擇的數字和為\(m\)。