C++

• 面向对象
• 万能头文件<bits/stdc++.h>
• 常用命名空间using namespace std;
• 输入：cin>>
• 输出：cout<< ;cout<<endl（换行）

1.STL

顺序表的删除(vector, list)

vector

Description
实现一个线性表:参照sq_delete函数，对一个n不超过2^10的线性表进行删除操作。

Input
第一行有一个整数n，表示线性表的大小，第二行有n个整数，分别是list1，list2…listn。
第三行有一个整数q，表示q次删除操作，接下来q行，每行有一个整数k，表示删除线性表中第k个元素。
(输入有多组测试数据，以EOF结束）

Output
对于每次删除操作输出一行，如果k不合法，输出 -1, 否则输出删除的元素。

Sample Input
5
3 2 1 5 4
3
5
5
2

Sample Output
4
-1
2

#include<bits/stdc++.h> 
using namespace std;
int main(){vector<int> ve;int n,i,a,q,k;while(scanf("%d",&n)!=EOF){ //多组测试数据输入ve.clear();for(i=0;i<n;i++){scanf("%d",&a);ve.push_back(a);//在容器的最后添加一个数据 }vector<int>::iterator it;//定义一个迭代器scanf("%d",&q);for(i=0;i<q;i++){scanf("%d",&k);if(k > ve.size()){printf("-1\n");}else{it = ve.begin();for(int j = 0;j < k-1;j++)//指针指向k位置 {it++;}printf("%d\n",*it);ve.erase(it);}}}return 0;	
}

list

#include<bits/stdc++.h> 
using namespace std;
int main(){int n,k,q,a;list<int> li;while(scanf("%d",&n)!=EOF){li.clear();for(int i=0;i<n;i++){scanf("%d",&a);li.push_back(a);}scanf("%d",&q);list<int>::iterator it;for(int i = 0;i < q;i++){scanf("%d",&k);if(k>li.size())printf("-1\n");else{it=li.begin();for(int j = 0 ;j < k-1;j++){it++;}printf("%d\n",*it);li.erase(it);}}}	return 0;
}

---

• 需要高效的随机存取而不再乎中间位置的插入删除->vector
• 需要大量中间位置的插入删除而不关心随机存取->list
• 需要随机存取而且关心两端数据的操作->deque

---

{A} + {B} (set)

set

• set中的元素已经从小到大排好序，采用平衡树来存储，复杂度logn，其中元素可以是任意类型的。
• 基本操作：
  begin() 返回指向第一个元素的迭代器
  empty() 如果集合为空，返回true
  erase() 删除集合中的元素
  find() 返回一个指向或查找到元素的迭代器
  lower_bound() 返回指向大于（或等于）某值的第一个元素的迭代器
• example:

#include<iostream>
#include<set>
using namespace std;
int main(){set<int> s;set<int>::iterator it;  //创建一个对应的迭代器 s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<s.count(1)<<endl;cout<<s.count(4)<<endl;it=s.find(2);if(it!=s.end())cout<<*it<<endl;return 0;
} 

Description
给你两个集合，要求{A} + {B}.
注:同一个集合中不会有两个相同的元素.

Input
每组输入数据分为三行,第一行有两个数字n,m(0 < n,m <=10000),分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.每个元素为不超出int范围的整数,每个元素之间有一个空格隔开.

Output
针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,每个元素之间有一个空格隔开.

Sample Input
1 2
1
2 3
1 2
1
1 2

Sample Output
1 2 3
1 2

#include<iostream>
#include<set>
using namespace std;
int main(){int n,m,value;set<int> res;set<int>::iterator it;while(cin>>n>>m){res.clear();bool flag=false;for(int i=1;i<=n+m;i++){cin>>value;res.insert(value);}for(it=res.begin();it!=res.end();it++){if(flag)cout<<" "; //除了第一个其他都在输出前输出一个空格 flag=true;cout<<*it;}cout<<endl;} return 0;
} 

统计数字（map）

map

记录<key,value>形式元素的容器，元素按key排序
定义map<int ,string>mp;
example:

Description
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

Input
第1行是整数n，表示自然数的个数。
第2~n+1行每行一个自然数。

Output
包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

Sample Input
8
2 4 2 4 5 100 2 100

Sample Output
2 3
4 2
5 1
100 2

#include<iostream>
#include<map> 
#include<string>
using namespace std;
map<int,int> mp;
map<int,int>::iterator it;
int main(){int n,a,t;while(cin>>n){mp.clear();for(int i=0;i<n;i++){cin>>a;mp[a]++;}for(it=mp.begin();it!=mp.end();it++){cout<<it->first<<" "<<it->second<<endl;}}return 0;
} 

ACboy 再次需要你的帮助(stack, queue)

容器适配器

stack<string> s;
stack几个主要函数：
s.empty()堆栈为空则返回真
s.pop()移除栈顶元素（不会返回栈顶元素的值）
s.push(x)在栈顶增加元素
s.size()返回栈中元素数目
s.top()返回栈顶元素

Description
对于每一个样例，第一行是N和一个字符串”FIFO”或者”FILO”(FIFO表示先进先出，即队列；FILO表示先进后出，即栈，)，N表示命令的个数，下面有N行，每一行表示一个命令。命令分为两种，IN a 表示进去一个a，OUT表示出一个对头元素或者栈顶元素。

Input
第一行是一个数字T，表示样例的个数，对于每一个样例，如题目所述。

Output
对于每一个OUT命令，你要根据”FIFO”和”FILO”单独一行输出一个数字，或者输出None如果没有整数了。

Sample Input
4
4 FIFO
IN 1
IN 2
OUT
OUT
4 FILO
IN 1
IN 2
OUT
OUT
5 FIFO
IN 1
IN 2
OUT
OUT
OUT
5
FILO
IN 1
IN 2
OUT
IN 3
OUT

Sample Output
1
2
2
1
1
2
None
2
3

#include<bits/stdc++.h>
using namespace std;
int main(){int T,n,m;char c[5],op[5];cin>>T;while(T--){stack<int> s;queue<int> q;cin>>n>>c;if(c[2]=='L'){  for(int i=0;i<n;i++){cin>>op;if(op[0]=='I'){cin>>m;s.push(m);} else if(op[0]=='O'&&!s.empty()){cout<<s.top()<<endl;s.pop();}else cout<<"None"<<endl;}}if(c[2]=='F'){for(int i=0;i<n;i++){cin>>op;if(op[0]=='I'){cin>>m;q.push(m);} else if(op[0]=='O'&&!q.empty()){cout<<q.front()<<endl;q.pop();}else cout<<"None"<<endl;}}}return 0;
} 

栈的操作(stack)

Description
栈是一种线性数据结构，它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
对输入整数序列1 2 3 …执行一组栈操作，输出操作的出栈序列。

Input
每行是一个测试用例，表示一个操作序列。操作序列由P和Q两个符号组成，P表示入栈，Q表示出栈。每个操作序列长度不超过1000。

Output
对每个操作序列，输出出栈序列，若操作序列有错误，如栈空时执行出栈操作，输出error，且终止程序。 出栈序列之间用一个空格隔开，末尾没有多余的空格！

Sample Input
PQPPQQPPPQPQ
PPPPQQP
PP
PQQPP
PPQQ

Sample Output
1 3 2 6 7
4 3
`
1 error
2 1

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,count;string str;stack<int> st;while(cin>>str){n=1;count=str.find_last_of('Q');for(int i=0;i<str.length();i++){if(str[i]=='P'){st.push(n++);}else{if(st.empty()){cout<<"error";break;}else{cout<<st.top();st.pop();}if(i!=count)cout<<" ";}}//重置 while(!st.empty()){st.pop();  }cout<<endl;}return 0;
}

看病要排队(priority_queue)

priority_queue

默认权值最高者排在最前面

Description
看病要排队这个是地球人都知道的常识。
不过经过细心的0068的观察，他发现了医院里排队还是有讲究的。0068所去的医院有三个医生（汗，这么少）同时看病。而看病的人病情有轻重，所以不能根据简单的先来先服务的原则。所以医院对每种病情规定了10种不同的优先级。级别为10的优先权最高，级别为1的优先权最低。医生在看病时，则会在他的队伍里面选择一个优先权最高的人进行诊治。如果遇到两个优先权一样的病人的话，则选择最早来排队的病人。
现在就请你帮助医院模拟这个看病过程。

Input
输入数据包含多组测试，请处理到文件结束。
每组数据第一行有一个正整数N(0 < N < 2000)表示发生事件的数目。
接下来有N行分别表示发生的事件。
一共有两种事件：
1:“IN A B”,表示有一个拥有优先级B的病人要求医生A诊治。(0 2:“OUT A”,表示医生A进行了一次诊治，诊治完毕后，病人出院。(0

Output
对于每个"OUT A"事件，请在一行里面输出被诊治人的编号ID。如果该事件时无病人需要诊治，则输出"EMPTY"。
诊治人的编号ID的定义为：在一组测试中，"IN A B"事件发生第K次时，进来的病人ID即为K。从1开始编号。

Sample Input
7
IN 1 1
IN 1 2
OUT 1
OUT 2
IN 2 1
OUT 2
OUT 1
2
IN 1 1
OUT 1

Sample Output
2
EMPTY
3
1
1

#include<bits/stdc++.h>
using namespace std;
struct Node{int id;int priority;Node(int i,int p){id=i;priority=p;}//通过自定义operator<操作符来比较元素中的优先级bool operator<(const Node &b) const{if(priority==b.priority)return id>b.id; //如果优先级一致，按照先来后到 else return priority < b.priority;  //不然大的优先 }};int main(){int n;while(scanf("%d",&n)!=EOF){priority_queue<Node> pq[4];int t=1;while(n--){string str;int a,b;cin>>str>>a;if(str=="IN"){cin>>b;pq[a].push(Node(t,b));t++;}else if(str=="OUT"){if(pq[a].size()){Node e=pq[a].top();pq[a].pop();cout<<e.id<<endl;}else cout<<"EMPTY"<<endl;}}}return 0;
} 

快速排序——中级(sort)

Description
输入n个数，对其进行从小到大排序。

Input
有多组测试数据，每组以n（n<=1000000）开始 第二行开始输入n个整数，整数均可用int类型表示。数据以n＝-1结束。

Output
输出每组测试数据组数，排序数据个数以及排序后从小到大的整数序列。最后一个数后没有多于空格。

Sample Input
5
5 4 3 2 1
10
4 6 8 7 5 1 3 9 2 0
-1

Sample Output
Case number:1
Number of elements:5
1 2 3 4 5
Case number:2
Number of elements:10
0 1 2 3 4 5 6 7 8 9

#include<bits/stdc++.h>
using namespace std;
int n,a[1000010];
int t=1; 
int main(){while(cin>>n && n!=-1){cout<<"Case number:"<<t<<endl;t++;cout<<"Number of elements:"<<n<<endl;for(int i=0;i<n;i++)cin>>a[i];sort(a,a+n);for(int i=0;i<n-1;i++)cout<<a[i]<<" ";cout<<a[n-1]<<endl;}return 0;
}

三级排序(sort)

Description
给你三维坐标(x, y, z)，请给三维坐标排序，优先按x值从小到大排序，当x值一样时，按y值从小到大排序，当y值一样时，按z值从小到大排序。

Input
输入数据的第一行是一个数据T，表示有T组数据。
对于每组数据先输入n (1 < n < 50000),表示有n个三维坐标，然后是n行，每行输入三个整数x, y, z。

Output
对于每组输入数据，先输出n，然后输出n行，为排序后的坐标。

Sample Input
2
2
1 2 3
3 2 1
4
2 3 4
2 2 3
2 3 2
3 4 1

Sample Output
2
1 2 3
3 2 1
4
2 2 3
2 3 2
2 3 4
3 4 1

#include <bits/stdc++.h>
using namespace std;
int n,T;
struct three{int x,y,z;}a[50010];
bool cmp(three x,three y){if(x.x==y.x&&x.y==y.y)return x.z<y.z;if(x.x==y.x)return x.y<y.y;return x.x<y.x;
}int main(){cin>>T;while(T--){cin>>n;cout<<n<<endl;for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y>>a[i].z;sort(a,a+n,cmp);for(int i=0;i<n;i++)cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].z<<endl;}return 0;
}

排列(next_permutation)

Description
1,2,3,…n是自然数1到n的最小的排列，易知，第二小的排列是：1,2,3…n，n-1。现在给你2个值n和m，请找到1到n个数的第m小的排列。

Input
输入包括多组样例，对于每组样例包括两个整数n和m（1<=n<=1000,1<=m<=10000000)，分别如题目所述

Output
输出第m小的排列的后各个数字，中间用空格分开，每一个样例占一行

Sample Input
6 4
11 8

Sample Output
1 2 3 5 6 4
1 2 3 4 5 6 7 9 8 11 10

#include <bits/stdc++.h>
using namespace std;
int a[1000010];  //过大的数组要设为全局变量 ，不然栈空间溢出 
int main(){int n,m;while(cin>>n>>m){for(int i=0;i<n;i++)a[i]=i+1;for(int i=1;i<m;i++)next_permutation(a,a+n);for(int i=0;i<n-1;i++)printf("%d ",a[i]);printf("%d\n", a[n-1]);}  return 0;
}

2.递推算法

以已知条件，按照递推关系，依次推出中间结果及最后结果。

确定递推变量
|
v
建立递推关系
|
v
确定初始（边界）条件
|
v
由初始条件依据递推公式计算后续状态

---

菲波那契数列(2)

Description
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数a，要求菲波那契数列中第a个数对1000取模的结果是多少。

Input
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 ≤ a ≤ 1000000)。

Output
n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对1000取模得到的结果。

Sample Input
4
5
2
19
1

Sample Output
5
1
181
1

#include<bits/stdc++.h>
using namespace std;
int main(){int a,b,c,m,n;cin>>n;while(n--){a=1;b=1;cin>>m;if(m<3)cout<<1<<endl;else{for(int i=1;i<m-1;i++){c=a+b;a=b;b=c;}cout<<c%1000<<endl;}	}return 0;
} 

Pell数列

Description
Pell数列a[1],a[2],a[3], …的定义是这样的，a[1] = 1, a[2] = 2, … , a[n] = 2*a[n−1] + a[n-2] (n>2)。
给出一个正整数k，要求Pell数列的第k项模上32767是多少。

Input
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1≤k<1000000)。

Output
n行，每行输出对应一个输入。输出应是一个非负整数。

Sample Input
2
1
8

Sample Output
1
408

#include<bits/stdc++.h>
using namespace std;
int a[1000];
int main(){int n,c,b,res;cin>>n;for(int i=0;i<n;i++){cin>>a[i];if(a[i]==1 || a[i]==2)cout<<a[i]<<endl;else{c=1;b=2;for(int j=2;j<a[i];j++){res=(c+2*b)%32767;c=b;b=res;}cout<<res<<endl;}}	return 0;
}

上台阶

Description
楼梯有n(71>n>0)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶，编程计算共有多少种不同的走法。

Input
输入的每一行包括一组测试数据，即为台阶数n。最后一行为0，表示测试结束。

Output
每一行输出对应一行输入的结果，即为走法的数目。

Sample Input
1
2
3
4
0

Sample Output
1
2
4
7

#include<bits/stdc++.h>
using namespace std;
long long d[80]={0};
int n;
int main(){d[1]=1;d[2]=2;d[3]=4;for(int i=4;i<=71;i++){d[i]=d[i-1]+d[i-2]+d[i-3];}while(scanf("%d",&n)!=EOF){if(n!=0){cout<<d[n]<<endl;}}return 0;
} 

爬楼梯

Description
树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级，也可以第一次走两级，第二次走一级，一共3种方法。

Input
输入包含若干行，每行包含一个正整数N，代表楼梯级数，1≤N≤30。

Output
不同的走法数，每一行输入对应一行输出。

Sample Input
5
8
10

Sample Output
8
34
89

#include<bits/stdc++.h>
using namespace std;
int fun(int n){if(n==1)return 1;else if(n==2)return 2;else return fun(n-1)+fun(n-2);
}
int main(){int n;while(scanf("%d",&n)!=EOF){cout<<fun(n)<<endl;}return 0;
} 

骨牌铺方格——中级

Description
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格，骨牌的铺放方案有三种,如下图：

Input
输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2×n (0<n<=50)。

Output
对于每个测试实例，请输出铺放方案的总数，每个实例的输出占一行。

Sample Input
1
3
2

Sample Output
1
3
2

数学关系式与上题一样

#include<bits/stdc++.h>
using namespace std;
int fun(int n){if(n==1)return 1;else if(n==2)return 2;else return fun(n-1)+fun(n-2);
}
int main(){int n;while(scanf("%d",&n)!=EOF){cout<<fun(n)<<endl;}return 0;
} 

昆虫繁殖

Description
科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0≤X≤20,1≤Y≤20,X≤Z≤50。

Input
x,y,z的数值。

Output
过Z个月以后，共有成虫对数。

Sample Input
1 2 8

Sample Output
37

第n月成虫数是上个月成虫数+两个月前的卵，第n月卵数是x月前的成虫数乘以y对。
注意数组要赋初值，默认数组元素是随机数并不是0。

#include<bits/stdc++.h>
using namespace std;
int main(){int x,y,z,a[100]={0},b[100]={0};while(cin>>x>>y>>z){for(int i=1;i<=x;i++){a[i]=1;b[i]=0;}for(int i=x+1;i<=z+1;i++){a[i]=a[i-1]+b[i-2];b[i]=a[i-x]*y;}cout<<a[z+1]<<endl;}return 0;
} 

放苹果

Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

Input
第一行是测试数据的数目t（0≤t≤20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤10。

Output
对输入的每组数据M和N，用一行输出相应的K。

Sample Input
1
7 3

Sample Output
8

#include<bits/stdc++.h>
using namespace std;
int fun(int m,int n){if(n>m)return fun(m,m);else if(m==0)return 1;else if(n==0)return 0;else return fun(m,n-1)+fun(m-n,n);
}
int main(){int m,n,t;cin>>t;while(t--){cin>>m>>n;cout<<fun(m,n)<<endl;}return 0;
} 

移动路线

Description
X桌子上有一个m行n列的方格矩阵，将每个方格用坐标表示，行坐标从下到上依次递增，列坐标从左至右依次递增，左下角方格的坐标为(1,1)，则右上角方格的坐标为(m,n)。
小明是个调皮的孩子，一天他捉来一只蚂蚁，不小心把蚂蚁的右脚弄伤了，于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中，蚂蚁从
左下角的方格中移动到右上角的方格中，每步移动一个方格。蚂蚁始终在方格矩阵内移动，请计算出不同的移动路线的数目。
对于1行1列的方格矩阵，蚂蚁原地移动，移动路线数为1；对于1行2列（或2行1列）的方格矩阵，蚂蚁只需一次向右（或向上）移动，移动路线数也为1……对于一个2行3列的方格矩阵，如下所示：
(2,1) (2,2) (2,3)
(1,1) (1,2) (1,3)
蚂蚁共有3种移动路线：
路线1：(1,1) → (1,2) → (1,3) → (2,3)
路线2：(1,1) → (1,2) → (2,2) → (2,3)
路线3：(1,1) → (2,1) → (2,2) → (2,3)

Input
输入只有一行，包括两个整数m和n（0 < m+n ≤ 20），代表方格矩阵的行数和列数，m、n之间用空格隔开。

Output
输出只有一行，为不同的移动路线的数目。

Sample Input
2 3

Sample Output
3

#include<bits/stdc++.h>
using namespace std; 
int main(){int m,n;int dp[20][20];cin>>m>>n;dp[0][0]=1;//一行或一列是都只有一种路线 for(int i=1;i<m;i++){dp[i][0]=1;}for(int i=1;i<n;i++){dp[0][i]=1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}cout<<dp[m-1][n-1]<<endl;;return 0;
}

过河卒

如图，A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。

同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为方马的控制点。例如上图C点上的马可以控制9个点（图中的P1，P2…P8和C）。卒不能通过对方的控制点。
棋盘用坐标表示，A点（0，0）、B点（n, m）(n,m为不超过20的整数，并由键盘输入)，同样马 的位置坐标是需要给出的（约定：C≠A，同时C≠B）。现在要求你计算出卒从A点能够到达B点的路径的条数。

Input
B点的坐标（n,m）以及对方马的坐标（X,Y） {不用判错}

Output
一个整数（路径的条数）。

Sample Input
6 6 3 2

Sample Output
17

类似上题，add判断不可走的点就行

#include<bits/stdc++.h>
using namespace std;
long long n,m,x,y,s,dp[20][20];
int main(){cin>>n>>m>>x>>y;dp[0][0]=1;for(int i=1;i<=n;i++){int j=0;//不重合不走马的日 if((i==x&&j==y)||(i==x-1&&j==y-2)||(i==x-1&&j==y+2)||(i==x-2&&j==y-1)||(i==x-2&&j==y+1)||(i==x+1&&j==y-2)||(i==x+1&&j==y+2)||(i==x+2&&j==y-1)||(i==x+2&&j==y+1))continue;dp[i][j]=dp[i-1][j]; } for(int j=1;j<=m;j++){int i=0;if((i==x&&j==y)||(i==x-1&&j==y-2)||(i==x-1&&j==y+2)||(i==x-2&&j==y-1)||(i==x-2&&j==y+1)||(i==x+1&&j==y-2)||(i==x+1&&j==y+2)||(i==x+2&&j==y-1)||(i==x+2&&j==y+1))continue;dp[i][j]=dp[i][j-1];}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if((i==x&&j==y)||(i==x-1&&j==y-2)||(i==x-1&&j==y+2)||(i==x-2&&j==y-1)||(i==x-2&&j==y+1)||(i==x+1&&j==y-2)||(i==x+1&&j==y+2)||(i==x+2&&j==y-1)||(i==x+2&&j==y+1))continue;dp[i][j]=dp[i-1][j]+dp[i][j-1];}}cout<<dp[n][m]<<endl;return 0;
}

踩方格

Description
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a、每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b、走过的格子立即塌陷无法再走第二次；
c、只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。

Input
允许在方格上行走的步数n(n≤20)。

Output
计算出的方案数量。

Sample Input
2

Sample Output
7

对于每个方向，如果向北走则上一步是三个方向的都可以，如果向东（或西）走，则上一步只能是北或东（或西）两个方向来的。

#include<bits/stdc++.h>
using namespace std;
int up[20],le[20],ri[20];
int main(){up[1]=1;le[1]=1;ri[1]=1;int n,res;while(cin>>n){//边界 if(n==1)cout<<3<<endl;else{for(int i=2;i<=n;i++){up[i]=ri[i-1]+le[i-1]+up[i-1];ri[i]=le[i-1]+up[i-1];le[i]=ri[i];}res=up[n]+ri[n]+le[n];cout<<res<<endl; }}return 0;
}

位数问题

Description
在所有的N位数中，有多少个数中有偶数个数字3? 由于结果可能很大，你只需要输出这个答案对12345取余的值。

Input
读入一个数N(N < 1000)。

Output
输出有多少个数中有偶数个数字3。

Sample Input
2

Sample Output
73

#include<bits/stdc++.h>
using namespace std;
const int mod=12345;
int n;
int a[1010][2];
//a[i][0]指i位数中有偶数个3，a[i][1]有奇数个3 
int main(){cin>>n;a[1][1]=1;//1-9,3  a[1][0]=8;//1-9,1、2、4、5、6、7、8、9for(int i=2;i<=2;i++){a[i][1]=(a[i-1][0]+a[i-1][1]*9)%mod;a[i][0]=(a[i-1][1]+a[i-1][0]*9)%mod;}cout<<a[n][0]<<endl;return 0;
}

三角形最佳路径问题

Description
如下所示的由正整数数字构成的三角形:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边（右下方）的数。

Input
第一行为三角形高度100≥h≥1，同时也是最底层边的数字的数目。
从第二行开始，每行为三角形相应行的数字，中间用空格分隔。
1 <= 数 <= 100

Output
最佳路径的长度数值。

Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output
30

a[i][j]存放从i,j出发到n层的最大值

#include<bits/stdc++.h>
using namespace std;
int a[101][101];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}for(int i=n-1;i>0;i--){for(int j=1;j<=i;j++){if(a[i+1][j]>=a[i+1][j+1])a[i][j]+=a[i+1][j];else a[i][j]+=a[i+1][j+1];}}cout<<a[1][1]<<endl;return 0;
}

---

3.递归

直接或间接调用自身，用递归将问题分解成规模更小的子问题来解决。

汉诺塔问题

Description
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18,446,744,073,709,551,615
这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。
假定圆盘从小到大编号为1, 2, …

Input
输入为一个整数(小于20）后面跟三个单字符字符串。
整数为盘子的数目，后三个字符表示三个杆子的编号。

Output
输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如 a->3->b 的形式，即把编号为3的盘子从a杆移至b杆。

Sample Input
2 a b c

Sample Output
a->1->c
a->2->b
c->1->b

总结规律的时候视角放宏观一点

#include<bits/stdc++.h>
#define N 1000010
using namespace std;
void fun(int n,char a,char c,char b)
{if(n==1){printf("%c->%d->%c\n",a,n,b);}else{fun(n-1,a,b,c);  //将n-1个盘子借助b从柱子a移到柱子c上 printf("%c->%d->%c\n",a,n,b);fun(n-1,c,a,b);  //将n-1个盘子借助a从柱子c移到柱子b上} 
}
int main()
{int n;char a,b,c;cin>>n>>a>>b>>c;fun(n,a,c,b);return 0;
}

求最大公约数问题

Description
给定两个正整数，求它们的最大公约数。

Input
输入一行，包含两个正整数(<1,000,000,000)。

Output
输出一个正整数，即这两个正整数的最大公约数。

Sample Input
6 9

Sample Output
3

Source
一本通1207

#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b)//求a与b的最大公约数 
{if(a == b)return a;else if(a > b)return gcd(a-b, b);elsereturn gcd(a, b-a);
}
int main()
{int a, b;while(cin >> a >> b){cout << gcd(a, b) << endl;}return 0;
}

后缀表达式的值

Description
从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。

Input
一个后缀表达式。

Output
一个后缀表达式的值。

Sample Input
16 9 4 3 +*-@

Sample Output
-47

#include<bits/stdc++.h>
using namespace std;
long long num[200];
int main(){string str;getline(cin,str);int len = str.length();int n = 0;for(int i = 0;i < len - 1;i++){if(str[i]=='+'){num[n-2]+=num[n-1];n--;}else if(str[i]=='-'){num[n-2]-=num[n-1];n--;}else if(str[i]=='*'){num[n-2]*=num[n-1];n--;}else if(str[i]=='/'){num[n-2]/=num[n-1];n--;}else{long long x=0;while(str[i]!=' '){x=x*10+str[i]-'0';i++;}num[n++]=x;}}cout<<num[0]<<endl;
}

---

4.数论

素数知多少

Description
在给定区间[1,n]中有多少个素数？

Input
每行一个整数n(1<=n<=1000000)

Output
[1,n]之间素数的个数，独立一行

Sample Input
1013
100

Sample Output
170
25

素数筛的应用
如果2是素数，那么2的所有倍数都是合数，把2所有倍数都标记出来，以此类推

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int prime[N];
bool is_prime[N];
int n;
int fun(){int sum=0;memset(is_prime,true,sizeof(is_prime));is_prime[0]=is_prime[1]=false;for(int i=2;i<=n;i++){if(is_prime[i]){prime[sum++]=i;for(int j=i*2;j<=n;j+=i){is_prime[j]=false;}}}return sum;
} 
int main(){while(scanf("%d",&n)!=EOF){cout<<fun()<<endl;}return 0;
}

[a,b]区间素数的个数

Description
给定区间[a,b]，你知道其中有多少个素数吗？

Input
每行两个正整数a,b (1<a<=b<1000000)

Output
[a,b]之间素数的个数

Sample Input
1 11
11 11111

Sample Output
5
1341

#include <bits/stdc++.h>
using namespace std;
int n;
bool fun(int x);
int main(){int a,b,sum;while(scanf("%d%d",&a,&b)!=EOF){sum=0;for(int i=a;i <= b;i++){if(fun(i)==true)sum++;}cout<<sum<<endl;}	return 0;
} 
bool fun(int x){if(x<2)return false;for(int i = 2;i <= x/i;i++)if(x%i==0)return false;return true;
}

分解质因子

Description
在数论里，某一正整数的质因子指能整除该数的质数整数。比如12的质因子有2和3。给定一个正整数n，你知道它的质因子有哪些吗？

Input
每行一个正整数n (1<n<1000000)

Output
n的质因子，从小到大，任意两个之间用一个空格隔开，独立一行

Sample Input
12
210

Sample Output
2 3
2 3 5 7

#include <bits/stdc++.h>
using namespace std;void divide(int n){for(int i=2;i<=n/i;i++){if(n%i==0){while(n%i==0)n/=i;cout<<i<<' ';}}if(n>1)cout<<n;
}
int main(){int n;while(scanf("%d",&n)!=EOF){divide(n);cout<<endl;}return 0;
}

最大公约数

Description
公约数，亦称“公因数”。它是几个整数同时均能整除的整数。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”；公约数中最大的称为最大公约数。两个数a,b的最大公约数记为gcd(a,b)。给定任意两个正整数a,b，你知道gcd(a,b)是多少吗？

Input
每行两个正整数a,b

Output
gcd(a,b),独立一行

Sample Input
5 6
20 12

Sample Output
1
4

欧几里得算法

#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){if(a%b==0)return b;elsereturn gcd(b,a%b);
}
int main(){int a,b,c;if(a<b){c=a;a=b;b=c;}while(scanf("%d%d",&a,&b)!=EOF){cout<<gcd(a,b)<<endl;}return 0;
}

最小公倍数

Description
最小公倍数（Least Common Multiple，缩写L.C.M.），如果有一个自然数a能被自然数b整除，则称a为b的倍数，b为a的约数，对于两个整数a,b来说，指该两数共有倍数中最小的一个，记为lcm(a,b)。

Input
每行两个正整数a,b

Output
lcm(a,b),独立一行

Sample Input
5 6
1 19

Sample Output
30
19

#include <bits/stdc++.h>
using namespace std;
//两个数的乘积会很大，超过int的表示范围
long long gcd(int a,int b){if(a%b==0)return b;else return gcd(b,a%b);
}
int main(){int a,b;while(cin>>a>>b){cout<<a/gcd(a,b)*b<<endl; }return 0;
}

青蛙的约会

Description
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

Input
输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

Output
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"

Sample Input
1 2 3 4 5

Sample Output
4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y,m,n,l;
void ex_gcd(ll a,ll b,ll &x,ll &y,ll &d){if(!b){d=a;x=1;y=0;return ;}ex_gcd(b,a%b,y,x,d);y-=x*(a/b);
}
int main(){while(cin>>x>>y>>m>>n>>l){ll dx,dy,gcd;ex_gcd(n-m,l,dx,dy,gcd);if((x-y)%gcd)cout<<"Impossible"<<endl;else{ll t=l/gcd;dx=(x-y)/gcd*dx;cout<<(dx%t+t)%t<<endl;}}return 0;
}

中国剩余定理

Sample Input
3
2 3 2
3 5 7

Sample Output
23

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ex_gcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1;y=0;return a;}ll ans = ex_gcd(b,a%b,x,y);ll tmp=x;x=y;y=tmp-a/b*y;return ans;
}
ll crt(ll a[],ll m[],ll n){ll M=1;ll ans=0;for(ll i=0;i<n;i++)M*=m[i];for(int i=0;i<n;i++){ll x,y;ll Mi=M/m[i];ex_gcd(Mi,m[i],x,y);ans=(ans+a[i]*Mi*x)%M;} if(ans<0)ans+=M;return ans;
}
int main(){ll n,b[10],w[10];while(cin>>n){for(int i=0;i<n;i++)cin>>b[i];for(int i=0;i<n;i++)cin>>w[i];cout<<crt(b,w,n)<<endl;}return 0;
}

---

5.分治与二分

查找最接近的元素(二分查找)

Description
在一个非降序列中，查找与给定值最接近的元素。

Input
第一行包含一个整数n，为非降序列长度。1 ≤ n ≤ 100000。
第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。
第三行包含一个整数m，为要询问的给定值个数。1 ≤ m ≤ 10000。
接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000之间。

Output
m行，每行一个整数，为最接近相应给定值的元素值，保持输入顺序。若有多个值满足条件，输出最小的一个。

Sample Input
3
2 5 8
2
10
5

Sample Output
8
5

#include<bits/stdc++.h>
using namespace std;
#define Max 1000000
int a[Max];
int main(){int n,m,x,low,high;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}cin>>m;while(m--){cin>>x;low=1,high=n;//low<high将会死循环 while(low<high-1) {int mid=(low+high)/2;if(a[mid]>x)high=mid;else low=mid;} if(fabs(a[low]-x)>fabs(a[high]-x))cout<<a[high]<<endl;else cout<<a[low]<<endl;}return 0;
} 

取余运算（mod）

Description
输入b，p，k的值，求b^p mod k的值。其中b，p，k为长整型数。

Input
输入b，p，k的值。

Output
求b^p mod k的值。

Sample Input
2 10 9

Sample Output
2^10 mod 9=7

#include<bits/stdc++.h>
using namespace std;
typedef long long int LLI;
LLI fun(LLI b,LLI p,LLI k){LLI res;if(p==0)return 1;res=fun(b,p/2,k)%k;res=res*res%k;if(p%2==1)res=res*b%k;return res;
}
int main(){LLI b,p,k;cin>>b>>p>>k;b%=k;cout<<b<<"^"<<p<<" "<<"mod"<<" "<<k<<"="<<fun(b,p,k)<<endl;return 0;
} 

简单快速幂

Description
杰哥又遇到难题了，大家快来帮他解决。
这次题目很简单。给你一个整数N，求NN的个位数。
当然，事实上作为学霸，杰哥才不会问如此简单的问题呢。注意这里的N非常大：N(1<=N<=1,000,000,000)。

Input
第一行包含一个正整数T，代表有多少组测试样例。
接下T行中每行有一个正整数N

Output
对于每一组测试样例，输出NN的个位数。

Sample Input
2
3
4

Sample Output
7
6

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL fun(LL a,LL b){LL res=1;while(b!=0){if(b%2==1)res=res*a;a=a*a;b/=2;	}return res;
}
int main(){LL N,T,ans;cin>>T;while(T--){cin>>N;ans=fun(N,N)%10;cout<<ans<<endl;}return 0;
}