08.03
1、《王道机试》—— 动态规划
搬宿舍
步骤：
（1）将所有物品重量递增排序
（2）用二维数组dp[i][j]记录在前j件物品中选择i件的最小疲劳度。
j和之前的是否为一组。
（3）初始dp[0][j] = 0.说明这时还没有开始选择。
- n的最大值为2000，k的最大值为1000，
- 输入可以用普通的
scanf("%d,%d",&n,&k)，也可
while(scanf("%d,%d",&n,&k)!=EOF){
...
}
- 下标从1开始了
- 对于数组list排序，只用包含头文件
#include <algorithm>，并且使用语句sort(list+1,list+1+n)即可排好序了。 - 将dp序列进行初始化
- 根据逻辑关系递推 求状态
外层循环：k次循环，i从1到k，表示选取2k件物品。
内层循环是j从2k开始，但是j要小于n。
08.04
1、接上题
要搬的是2k件，i就从1开始，遍历k之前的所有情况
j是从2i到n.
如果j>2*i，那么就说明前面的物体已经可以配成对了。为了使得疲劳度最小，还是搬轻的物品吧。
设定初始值，再更新。
2、放橘子
找出能够得到的两边橘子的最大量
首先输入t，是输入的数据有t种情况。
对每种测试数据，先输入n,是橘子的数量，再输入每个橘子的重量
输出每种测试用例的一边橘子的最大数量
dp[i][j]表示 前i个柑橘被选择后，第一堆比第二堆重j时，两堆的最大重量总和。
这是在三种情况中取最大值，表示当前状态可以由哪一种转移而来。三种现有的情况分别是：差值为[j - list]，差值为[j+list] ，或原本的差值是j，即不放入。 看这三种哪种情况下dp重量最大。
判断时的限制条件为：
- j(现有差值)+list[i] < 2000
- dp[i - 1][j + list[i] + OFFSET] !=-INF)
计算三种情况各自的值，保存下来最大的那个在dp[i][j]中。
我们最后要的结果就是 dp[n][0] / 2的值。
3、背包问题（ 0-1 、完全和多重背包 问题）
- 0-1背包
08.05
1、接上，0-1背包
目的：使得总价值最大
最优解中：每个物体只有两种情况，在背包中和不在背包中。
dp[i][j]表示：总体积不超过j的情况下，前i件物品所能达到的最大值。
每个状态有两个来源：与前一个值相等，或前一个状态新放入一个。
数组结构体赋值：&list[i].w
外层循环对的是每个物体，内层循环从时间T开始往下减。
每行都只与上一行有关，与本行的次序无关。因此可以将原来的二维数组优化为一维数组。可以把i省略掉，每次保存本行的值为最后的结果。
状态转移更新时倒序进行，是为了使得在定 dp[j]的值时，dp[j - list[i].w]的值未修改。
2、0-1背包变形
要求最后恰好能够装满背包
dp[i][j]的概念改变即可，表示前i件物品恰好总体积为j时的最大价值。初试值改变一下，其他内容不改变。
3、完全背包
每个物品的数量是可以无限增加的。
把无限的情况归结为有限的情况。
但是使用单纯的0-1背包问题的复杂度比较高。
遍历时j是顺序从小到大遍历的。
0-1背包逆序是因为每个物品最多被选择一次，这里顺序是因为物品可以多次选择。
例题：给出储蓄罐中💰的总重量和每种钱的重量，求出最少的钱数。
每次输入E和F，求出钱重量
给出所用的硬币的种类N
下面N行，分别给出每种硬币的价值和重量。
先算出来钱的重量。s是当前储蓄罐的重量，计算之后s为钱的数量。
如果dp[s]不为无穷，说明这种情况存在。如果为无穷，说明这种情况不存在。
4、多重背包
物品的数量为k
把k进行二进制拆分
08.06
1、dp例题---买大米
钱可以不正好用完。多重背包。
将数量k按照二进制拆分。同时重量k和价格p也会按照本组的数量进行更改。
2、PAT-TOP-Business
需要保证：
（1）规定时间之前完成 （2）获利最大
dp[i][j]表示：以i工程结尾，并且在j时间之前完成了，这样即可往前递推。
首先将工程按照截止时间升序排列
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 100005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,dp[MAX];
struct node{
int val;
int cost;
int ddl;
bool operator < (const node &a) const{
return ddl<a.ddl;
}
}t[MAX]; //定义每个工程的时间、ddl、时长等。
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d%d",&t[i].val,&t[i].cost,&t[i].ddl);
}
sort(t,t+n); //没懂这里按照什么排序的。实验结果是按照ddl从小到大排序了。
int sum=t[n-1].ddl;//sum为最大的截止时间
for(int i=0;i<n;i++){
int tot=t[i].ddl;
for(int j=tot;j>=t[i].cost;j--){
dp[j]=max(dp[j],dp[j-t[i].cost]+t[i].val);
}
}
int maxl=0;
for(int i=0;i<=sum;i++){
maxl=max(maxl,dp[i]);
}
printf("%d",maxl);
return 0;
}
3、Universal Travel Sites
猜测是考察图的知识。
《王道》图论
用邻接矩阵和邻接表来表示。
邻接链表
08.08
1、《王道——图论》
08.09
1、邻接链表的实现
使用STL中的std::vector
#include <vector>
using namespace std;
struct Edge{
int nextNode;
int cost;
}
vector<Edge> edge[N];
为每个节点建立单链表，即存储每个节点相邻的边信息。
相应操作：
for( i = 0; i < N; i ++){
edge[i].clear(); //清空
//添加信息
Edge tmp;
tmp.nextNode = 3;
tmp.cost = 38;
edge[i].pushback(tmp);
}
查询
//查询
for(int i = 0; i < edge[2].size(); i++ ){
int nextNode = edge[2][i].nextNode;
int cost = edge[2][i].cost;
}
当不用clear，即不全部清除，需要部分清除时：
edge[1].erase（edge[1].begin+i, dge[1].begin+i + 1）;
这会删除第i个
2、并查集
表示树：双亲节点表示法，即每个节点需要记录其父节点。可用数组表示。
合并：修改根节点。有可能会使得树退化，树高较长。解决方法：路径压缩。
代码编写,数组表示，记录双亲
int Tree[N];
int fintRoot(int x){
if(Tree[x] == -1)
return x;
else
return findRoot[Tree[x]];
}
如果查找的过程需要路径优化
else中后面加一句
else{
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
例题：畅通道路
即所有的节点都能连接起来，根节点是相同的。即查找连通分量。
操作是：合并集合，看最后还剩多少集合。
如果多个用例输入，需要while(scanf("%d",&n)!= EOF)
初始时,Tree[i] = -1;
3、例题3: 朋友关系，求人数最大的集合
令开一个数组，在树的根节点记录该集合包含的元素的个数。
4、最小生成树
08.10
1、MST
概念：子图连通且不存在回路。若带权：权重最小。
Kruskal 算法
思想：选择权重最小的边，看他所连接的节点是否在一个集合中。如果顶点不在同一个集合中，就加入这条边，即包含这条边。
在结构体中重载符号的方法：
struct{
...
bool operator < (const Edge & A) const{
return cost < A.cost;
}
}
练习：freckles
double型的输入需要 scarf("%lf",&n)；
08.11
1、例题
给出坐标，求最小生成树
头文件
#include <stdio.h>
#include <algorithm> //sort用
#include <math.h> //sqrt用
using namespace std;
定义一些初始值
#define N 101
int Tree[N];
函数findRoot
int findRoot(int x){
if(Tree[x] == -1)
return x;
else{
int tmp = findRoot(x);
Tree[x] = tmp;
return tmp;
}
}
需要自己定义边的结构体
struct Edge{
int a,b; //包含两个节点的编号
double cost; //cost花费/代价
bool operator < (const Edge & A) const{ //定义排序的操作，背住
return cost < A.cost;
}
}edge[6000];
由于题目给出的是点的信息，定义点的结构体
struct Point{
double x,y; //需要表示点的两个坐标
double getDistance(Point A){ //根据这个点，定义一个计算与另一个点距离的函数。
double tmp;
tmp = (x - A.x)*(x - A.x) + (y-A.y)*(y-A.y);
return sqrt(tmp); //需要用到math.h
}
}list[N]; //最多有N个点
main函数如下
首先输入n,double类型的用lf，共有n个点，把它输入到Point结构体中去
for(int i = 1;i<=n;i++){
scanf("%lf,%lf",&list[i].x,&list[i].y);
}
size保存边数。
for(i=1;i<=n;i++){
for(j=i+1;j<=n;j++){
edge[size].a = i;
edge[size].b = j;
edge[size].cost = list[i].getDistance(list[j]);
size++;
}
}
sort(edge,edge+size);
先给每个可能存在的点都设定一个边，再填入具体的数值。保存在结构体edge中。两个顶点分别是i,j，边的cost是用i中的getDistance函数计算。算完之后sort排序，Tree初始化。
ans用来记录最终结果，遍历每条边，看结果是否应该包含这条边。
for (i=0;i<size;i++){
int a = findRoot(edge[i].a);
int b = findRoot(edge[i].b);
if(a!=b){
Tree[a] = b;
ans+=edge[i].cost;
}
}
2、最短路径问题
算法1:弗洛伊德算法
（1）邻接矩阵保存原图
（2）考虑从节点i到节点j只能经过节点1（或什么节点都不经过）。
如果由于加入节点1出现了最短路径，则更新我们的记录矩阵ans[k][i][j]。
（3）依次加入其他节点。
代码实现：k,i,j循环
- 先判断在k-1的情况下i,j分别能否与k连通。若不能连通，就不改变
- 如果（原来的路径没有连通）或者（加入k节点，可以更新最短路径），则更新。否则，保持原来的值。
这样就可以求的所有节点间的最短路径。
由于我们最后只要最终的数组，也可以将原来的三位数组转化为2维，直接表示[i][j]之间的距离。
3、弗洛伊德算法例题：最短路
由于是无向图，矩阵初始值赋值操作要执行两次。
3次循环
(1)加上k能否连通，不能连通则不改变，continue （2）如果可以连通，那么<1>原来不能连通 <2>值更新， 这两种情况都会更新值
4、狄杰斯特拉算法
只能求的某个节点到其他所有节点的距离，1对n，不是n到n。
步骤如下：
（1）初始化1到所有节点的最短路径长度都是无穷，1到1的距离为0
（2）K表示求出最短路径的。
（3）求出下一个最短距离以及将相应的节点加入K
（4）重复上述操作，直到所有节点都加入了
代码实现
头文件
#include <stdio.h>
#include <vector>
using namespace std;
定义一个结构体，代表链表中的结构体
包含邻接的节点以及相应的边的权值。
08.12
1、
定义结构体,以及需要预先用来存储的变量
struct E{
int next;
int c;
};
vector<E> edge[101];
bool mark[101];
int Dis[101];
main函数中，每条边都输入相关信息，存到edge中，用push_back
while (m--) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
E tmp;
tmp.c = c;
tmp.next = b;
edge[a].push_back(tmp);
tmp.next = a;
edge[b].push_back(tmp);
}
加入节点前的初始化操作
for(i=1;i<=n;i++){
Dis[i] = -1;
mark[i] = false;
}
Dis[1]=0;
mark[1]=true;
int newP = 1;
开始循环进行更新操作
外层循环表示还需要加入n-1个节点（已经加入了1）
内层表示的是要遍历新加入节点相邻的所有的边（下一个节点）
先找到要比较的下一个节点t和所对应的边c
这时候表示下一个节点可达了。如果之前没距离，就加入距离，如果之前距离较大，就对距离进行更新。
全部的都更新完之后，来进行一次比较。找出所有重新可达的节点中距离最小的值。
for(i=1;i<n;i++){
for(j=0;j<edge[newP].size();j++){
int t = edge[newP][j].next;
int c = edge[newP][j].c;
if(mark[t] == true) continue;
if(Dis[t] == -1 || Dis[t] > Dis[newP] + c)
Dis[t] = Dis[newP] + c;
}
int min = 123123123;
for(j=1;j<=n;j++){
if(mark[j] == true) continue;
if (Dis[j] == -1) continue;
if(Dis[j]<min){
min = Dis[j];
newP = j;
}
}
mark[newP] = true;
}
printf("%d",Dis[n]);
2、最短路径例题
但是每条边有长度d，求最短距离，顺带记录其花费。
最后输出的是自己随便定义的两个节点的最小距离.但是和原来的是一样的，只不过加入节点时S 是第一个加入的，不是1第一个加入了。
3、拓扑排序
针对有向无环图DAG。
判断是否为有向无环图，可以用拓扑排序
算法
首先选择入度为0的节点，并将其从图中删去
再选择下一个入度为0的节点
例题：判断是否为有向无环图。使用队列
当出现入度为0的节点时，将其放入队列之中。
头文件
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
保存图的信息都是用临界链表，所以还需要用到vector。
vector<int> edge[501];
queue<int> Q;
main函数结构如下：
int inDegree[501];
n=0,m=0判断是否成立；
初始化inDegree, edge.clear(),队列Q也清空[while(Q.empty()==false )Q.pop()]
输入边的信息。edge[a].push_back(b) , inDegree[b]++
初始统计，将所有起始节点入队列
for(i=0;i<n;i++){
if(inDegree[i]==0) Q.push(i);
}
将队列中现有的分别取出来，进行寻找下一个节点。
去除节点时，需要把入度减少
while(Q.empty()==false){
int nowP = Q.front;
Q.pop();
cnt++;
for(i=0;i<edge[nowP].size();i++){
inDegree[edge[nowP][i]]--;
if(inDegree[edge[nowP][i] ==0]){
Q.push(edge[nowP][i]);
}
}
}
节点入队列的时机为：（1）最开始（2）去除边更新信息之后
4、PAT——Universal Travel Sites
考察的知识点是：搜索中的最大流问题
是第六章的内容，继承第二章，故先看第二章内容
08.13
1、排序
- 冒泡排序
代码实现
头文件 stdio.h
main函数
用n保存数字个数，buf[i]分别存储各个数字
排序主体，i = 0~n-1 , j = 0~n-1-i
比较j 和 j+1的大小，每次把较大的数放在后面
如果i = 1~n , j = i+1~n
比较i和j的大小，每次把小的放在i的位置
排序完成，输出
- 冒泡排序
输入n个数，进行排序（2006华科）
#include <iostream>
using namespace std;
int main(){
int n = 0,i = 0,j = 0, temp = 0;
int sorting[100] = {0};
cin >> n;
for(i = 0;i<n;i++){
cin >> sorting[i]; //输入
}
for(i = 0;i < n; i++){
for(j = i+1 ;j< n; j++){
if(sorting[i] > sorting[j]){
temp = sorting[i];
sorting[i] = sorting[j];
sorting[j] = temp;
}
}
}
for(i = 0;i<n;i++){
cout << sorting[i] <<" ";
}
return 0;
}
上面这种方法想当于每次都把最小的放在前面。真正的应该是把相邻的比较，然后每次都把现有的最大的放到最后面。如下所示。可以把n理解为已经拍好序的个数。
for(i = 0;i < n; i++){
for(j = 0 ;j< n-1-i; j++){
if(sorting[j] > sorting[j+1]){
temp = sorting[j];
sorting[j] = sorting[j+1];
sorting[j+1] = temp;
}
}
}
补充：scanf返回成功赋值的变量的个数。
如果n较大，需要使用快速排序、归并排序等
- 快速排序
若n较大，超过了时间复杂度，使用快速排序，C++中有直接的sort()函数，默认的是快速排序升序形式
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n,i;
int buf[10000];
while(scanf("%d",&n)!= EOF){
//这句，需要保证输入了n，如果没输入，则重新输入
for(i = 0;i<n;i++){
cin >> buf[i];//输入数据
}
sort(buf,buf+n); //排序函数。对于数组buf，输入的是buf,buf+n
for(i = 0;i<n;i++){
cout << buf[i] << " ";
}
}
return 0;
}
- 降序排序
1）按照上面升序排好后，倒着输出
2）
头文件
#include <stdio.h>
#include <algorithm>
using namespace std;
定义函数cmp
bool cmp (int x,int y) { //定义排序规则
return x > y;
}
int main () {
int n;
int buf[100];
while (scanf ("%d",&n) != EOF) {
for (int i = 0;i < n;i ++) {
scanf ("%d",&buf[i]);
}
sort (buf,buf + n,cmp); //使用该重载形式,我们表明将要使用自己定义的排列规则
for (int i = 0;i < n;i ++) {
printf("%d ",buf[i]);
}
printf("\n");
}
return 0;
}
cmp函数自己定义排序规则 return的是x>y，所以最后降序排列了
- 补充一个比较杂的内容(6.30)
如果图形显示，在界面中会有光标，C语言中可以隐藏光标，代码如下：
void HideCursor()//隐藏光标
{
CONSOLE_CURSOR_INFO cursor_info = {1, 0};
SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE), &cursor_info);
}
int main(){
HideCursor();
return 0;
}
制作图形界面，使用Visual studio + easyX
整体的结构
#include <stdio.h>
#include <algorithm>
using namespace std;
bool cmp() //自己定义排序规则
int main(){
while //输入
sort(but,buf + n,cmp)
for //输出；
}
2、第二章的五——查找
最简单的找数：数组中查找特定数字
代码实现
头文件
#include <stdio.h>
main函数如下
定义n和buf[]，输入相关数据
一次遍历数组，看x与buf[i]是否相等
对于线性数组，可以用二分法查找
移动的时候新的查找集变为中中间节点前一个或后一个
查找失败的标记是：起始点大于结束点。
代码实现
头文件
#include <stdio.h>
#include <algorithm> //sort排序
#include <string.h> //需要输入字符串
using namespace std;
根据题目信息，定义结构体
struct Student{
char no[100]; //学号
char name[100];
char sex[5];
int age;
bool operator < (const Student & A) const{
return strcmp(no,A.no) < 0; //sort排序，按照no从小到大
}
} buf[1000];
main函数如下
输入学生的信息
scanf("%s%s%s%d",buf[i].no,buf[i].name,buf[i].sex,&buf[i].age);
注意这里只有age用了&符号
按照学号升序排序
sort(but,buf+n);
输入要查询的t组信息，进行t次循环，用while
用x来表示待查找序号
定义top和base，分别用来标示数组起始位置和结束位置的下标
循环的条件是top >= base
计算mid
tmp = strcmp(buf[mid].no, x);
tmp > = < 0,分3种情况，分别处理
若查找失败，输出失败
若查找成功，printf("%s %s %s %d\n", buf[ans].no, buf[ans].name, buf[ans].sex, buf[ans].age );
时间复杂度： O(n*logn排序 + m*logn查找)
二分查找还可以用于定界
根据目标数字把数组的数值分为两部分
最后，buf[top]就是这个目标数字本身
其实本质上还是二分查找
看完之后，看第六章
3、第六章——搜索
搜索方式：枚举（需考虑时间复杂度）
代码实现
#include <stdio.h>
x: 0-100
y:0-100-x
z: 100 - x - y
如果计算的时候有小数，最好都乘一个数☝️，变为整数
根据题目要求进行判断
输出
广度优先搜索BFS
远远不止图的遍历应用
例题
三维空间
要首先把问题转化一下，如这里需要考虑到时间，于是定义了四元组(x,y,z,t)
构造解答树🌲：包含所有状态。BFS表现为：层次遍历。过程中需要剪枝
本题中是去掉了不是最短时间t的分枝。
在树中每个坐标状态出现一次即可，多了也没用。
为了实现先进先出，需要用到队列。/ 节点用结构体表示
用mark[x][y][z]记录已经到达了的点的坐标。
代码实现
头文件
#include <stdio.h>
#include <queue>
using namespace std;
初始化信息
mark
maze
结构体N
queue<N> Q; //其实模拟的是解答树
变换数组坐标go
int go[][3] = {
..... //共六行，表示变换的六种情况
}
函数存储结构如下
定义BFS函数
有的数据是a,b,c
当队列Q中还有数据时，进行循环
N now = Q.front(); Q.pop();
依次扩展其6个相邻节点
i=0~6
3种情况会丢次此坐标（continue）
<1>坐标在立方体之外，超过了范围。
<2>maze = 1，即为墙
<3>mark = true,即此点已经出现过
得到的新的状态tmp入队列Q, Q.push(tmp);
标记坐标已经出现过，mark[nx][ny][nz] = true;
判断新的到的状态是否已经得到了最终结果，入股得到了，返回tmp.t
如果搜索完所有的空间还是没有最终的结果，说明不存在这种方案，返回-1
main函数如下
输入测试次数T，对于每次测试进行while循环
输入a.b.c.t，即时间最多不超过t
maze, mark 进行初始化
如果Q不空，将Q清空
while(Q.empty() == false) Q.pop();
标记起点：mark[0][0][0]
N tmp; 初始化
将tmp放入队列 Q.push(tmp);
进行广度优先搜索rec = BFS(a,b,c)
根据rec的结果进行分类输出。
4、例题：非常可乐
S = N + M，考虑能否平分呢？
如果能平分，输出倒可乐的最少次数
还是用四元组来表示。
（x,y,z,t）分别 表示三个杯子中的重量 和 需要倾倒的次数
与上题不同的是：需要自己根据题意定义一个变换函数。
上题是mark和go()
void AtoB(int &a,int sa,int &b,int sb){ //如果需要全局改变值的，定义的是&a, &b,即可以理解为会把更新的值传回去。只用来计数，不需要变值的，用sa,sb.
分为能完全倒完和不能完全倒完两种情况
如果可以完全倒完
if(sb - b >= a)
b +=a;
a= 0;
else
倒sb-b
a -= sb-b;
b= sb;
}
再定义BFS
有的数据是s,m,n,即3个杯子的大小
用a,b,c临时保存杯子中可乐的体积
AtoB(a,s,b,n),由A倾倒向B，出现了新的组合
如果该组合之前没出现过，就标记MARK，并将其保存为N型的tmp
如果已经出现平分了（a == s/2 && b == s/2 及其他可能的情况 ），直接返回
如果还没有平分，将这个新的节点入队列 Q.push(tmp)
重复刚才的过程，由b倒向a,
再重复，由a倒向c
c倒向a
b倒向c
c倒向b
main函数逻辑如下
输入s\n\m
必须要求s为偶数
对mark进行初始化，为false
当Q不空时，Q.pop();
构造一个N型的tmp,并初始化,并存入Q中，Q.push(tmp);
修改mark[s][0][0] = true
int rec = BFS(s,n,m);
根据rec的值进行不同结果的输出，
程序代码很长，但是中间有很多重复的部分。
5、 递归调用
今天看太多啦，明天再看
08.14
1、递归的例子，汉诺塔3
对题目进行分析，不同的题目要求可能不同。这里分析出F(x) = 3*F(x-1) + 2,并且F(1) = 2
函数实现过程如下：
头文件
#include <stdio.h>
#include <string.h>
定义递归函数
long long F(int num){
if(num == 1) return 2;
else
return 3*F(num-1) + 2;
}
代码十分简单，但是计算机做的工作较多，所以N不能太大
递归的另一个例子
素数环：环中任意两个相邻数字的和为素数。
解决方法：可以采用回溯法去枚举每一个值。如果放了之后发现后面的都不能再成立了，就改变上一个的值。
代码实现
头文件
#inclde <stdio.h>
#include <string.h>
定义一些元素ans , hash, n, prime数组
判断一个数是否为素数，需要定义一个函数judge
bool judge(int x){
for(i = 0; i < 13; i++){
if(prime[i] == x) return true;
}
return false
}
check是进行最后的检查
重点在DFS函数，这道题中有一点清奇，按照常理应该是先检查是否正确再放入ans中，但是这个是先放入，下一次再检查是否正确。
void DFS(int num){ num是刚刚放入的，但是不确定是否正确
if(num > 1) //
if(judge(ans[num] + ans[num - 1]) == false) return; 说明这个情况是不正确的，直接return，就不会到check输出了
if(num == n){ //n
check(); //
return; //,
}
for(int i = 2;i <= n;i ++){ 从小到大依次放入
if(hash[i] == false){ //i 如果之前没有被放入过，就可以放入
hash[i] = true; //i
ans[num + 1] = i; // 尝试把i放入num+1的位置
DFS(num + 1); // 检测是否成立
hash[i] = false; // 只有刚才的不成立，或者成立并且已经输出结束 的时候才会返回这里，再进行下一个。
}
} }
递归的应用2：图的遍历
题目条件：把一矩形的区域创建为许多方形结构。
有油的区域叫做pocket, 相邻的区域可以连起来。程序需要检测出来有多少不相邻的区域。
输入m和n,表示每个grid的行和列，1-100之间，*表示没有石油，而@表示此处有石油。对每个grid，输出分离的油区共有多少。
解决思路：对每个@都要设置标记位
代码实现：
头文件
#include <stdio.h>
一些元素用于保存信息
char maze[101][101]; 存储输入的信息
bool mark[101][101]; 标记状态
int n,m; 长宽
int go[][2] = {1,0,-1,0,0,1,0,-1,1,1,-1,1,-1,-1,-1,1}; 定义八个方向
main函数如下：
判断是否结束
if (m == 0 && n == 0) break;
输入地图信息（二维数组,字符串）
for(i=1;i<=n;i++){
scanf("%s",maze[i]+1);
}
初始化所有mark为false
遍历的思想为：按照行和列分别进行遍历。
如果mark已经被标记过，continue
如果是*，也跳过
否则，DFS遍历，并且ans++
DFS的过程如下：遍历与(x,y)相邻的所有的点，标记为false
for(i=0;i>8;i++){
int nx = x + go[i][0];
int ny = y + go[i][1];
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(maze[nx][ny] == '*') continue;
if(mark[nx][ny] == true) continue;
mark[nx][ny] = true;
DFS(nx,ny); // 最重要的是这一步：还要遍历新找到的这个节点相邻的点。
}
2、深度优先搜索DFS
不再具有最优特性了，只求解🈶️或🈚️问题。
把一枝上的遍历完之后，才会到上一个节点，再遍历其他的分枝。
应该可以使用栈结构 也可以使用递归操作来完成。
此处用递归。
例题
一个迷宫问题，每个门🚪会在特定的一秒内开一下
08.17
1、上面的例题
每个位置被走过之后，就不能再通过了。（题目上说会掉下去）
定义一个三元组(x,y,t)，x,y表示坐标，t表示走到这个位置的时间t
过程中需要剪枝
每次移动都会让坐标的奇偶性发生变化，首先可以判断一个根据起始位置和终点位置和时间，减去的枝（起点和终点的奇偶性不同，说明需要奇数个时间，但是题目给的需要偶数个时间）
代码实现过程如下
头文件
#include <stdio.h>
定义需要用到的变量
char maze[8][8]; 给出的矩阵的大小都不大于7
int n,m,t;
bool success; 用来标记是否成功了
int go[][2] = {
1,0,
-1,0,
0,1,
0,-1
}; 定义要行走的四个方向
main函数如下
大的循环输入
while(scanf("%d%d%d",&n,&m,&t)!=EOF){
...
}
while内部的东西如下
if(n==0 && m==0 && t==0) break;
输入
for(int i = 1;i<=n,i++){
scanf("%s",maze[i]+1);
}
数组输入时，不需要&符号，并且二维数组每次输入一行
原来定义的大小是8，所以如果n = 7,下标是从1-8，并没有占用0的位置，所以有maze[i]+1
初始化success, 终点sx和sy，起点,并判断是否一定无解
success = false;
for...(maze[i][j] = 'D') sx = i,sy = j;
t时间会让位置的奇偶性变化t次
if(maze[i][j] == 'S' && (i+j)%2 == ( (sx + sy)%2 + t%2 )%2 ){
maze[i][j] = 'X'; 起点标记为强，即走过的地方都标记为墙
DFS(i,j,0);
}
每个测试用例都输出结果
puts(success == true? "YES" : "NO");
DFS函数如下,有x,y,time
for(i=0;i<4;i++){ 每个位置可走的情况有四种，分别进行遍历。并且需要用到的是go[][]，所以下标从0开始
....
}
int nx = x + go[i][0];
int ny = y + go[i][1];
需要保证坐标在地图内
if(nx < 1 || nx > n || ny < 1 || ny > m) continue;
if(maze[nx][ny] == 'X') continue;
对成功的情况进行处理,（如果时间恰好对，就是结果，如果时间不对，这条枝上的结果不可能再对了）
if(maze[nx][ny] == 'D'){
if(time +1 == t){
success = true;
return;
}
else
continue;
}
如果这个点没有成功，就先标记不可再达，再遍历这个点的下一个点。
maze[nx][ny] = 'X' ;
DFS(nx,ny,time+1);
----->如果调用的后续的节点都是不答案，那么就会返回这里，那么再把它改为普通位置，再次搜索时可以遍历。
maze[nx][ny] = '.' ;
if(success) return;
深度优先搜索类似于先序遍历
看完之后，看编程题。
2、Universal Travel Sites
题目要求：
第一行输入 源地址、目的地址、整数N
再输入N行，格式为：源 目的 capacity
自己还是不会做。参考答案，考察最大流问题。用基于BFS的Edmonds-Karp算法求解。
最大流基础参考 https://blog.csdn.net/u014679804/article/details/47016513
代码实现如下
头文件
#include <cstdio> 输入输出
#include <cstdlib> C语言中对应stdlib.h,包含了一些常见的函数，如malloc\free等
#include <cstring> 字符串
#include <vector> 类似栈
#include <queue> 队列
#include <algorithm> 一些算法如排序等
#include <climits> 用来定义各种数据类型的最值常量
using namespace std;
定义结构体
此处定义的是边的结构体,以及一些操作函数
struct edge {
char source[4], dest[4];
int capacity, s, d;
int dindex(void) {
int index = 0;
index = ((dest[0] - 'A') * 26 + dest[1] - 'A') * 26 + dest[2] - 'A';
return index;
}
int sindex(void) {
int index = 0;
index = ((source[0] - 'A') * 26 + source[1] - 'A') * 26 + source[2] - 'A';
return index;
}
void read(void) {
scanf("%s %s %d", source, dest, capacity);
return;
}
};
看不懂
08.18
1、Universal Travel Sites
定义的边的结构体
分别包含 变量，以及index
index是分别按照地址的三个字母顺序排列的。
index = ((dest[0] - 'A')*26 + dest[1] - 'A' )*26 + dest[2] - 'A';
还定义了一个read函数，用于输出
准备工作
静态变量 const int MAX = 26*26*26;
BFS
Edmonds_Karp
main函数如下
初始变量
用到了setbuf函数
setvbuf(stdin, new char[1 << 20], _IOFBF, 1 << 20);
int setvbuf(FILE *stream, char *buffer, int mode, size_t size); setbuf函数声明
mode是 `IOFBF`,指定文件缓冲模式的
tmp内容输入
定义arr，用来输入信息
arr = new vector<edge>[MAX];
for(i = 0; i < n; i++){
scanf("%s %s %d", tmp.source, tmp.dest, &tmp.capacity);
tmp.s = s.index;
tmp.d = d.index;
arr[tmp.s].push_back(tmp);
}
调用 Edmonds_Karp 函数
这里返回的结果就是最大流，输出
setbuf用来定义stream流应该如何缓冲
setvbuf(stdin, new char[1 << 20], _IOFBF, 1 << 20);
int setvbuf(FILE *stream, char *buffer, int mode, size_t size); setbuf函数声明
new char[1<<20] 是分配给用户的缓冲，1<<20是左移20位，是用来规定大小的。
mode是_IOFBF
如果成功返回0，否则返回非0
Edmonds_Karp函数，EK算法
思想就是：找增广路。从源点开始做BFS。
代码实现如下
vector<edge>::iterator vit;
::表示成员函数所属的类
route[i] = -1,首先把route[i]初始化都置为-1
每次循环都进行BFS，返回从源地址到目的地址是否还能找到增广路
while (BFS(arr, route, source, dest)) {
f = INT_MAX;
for (i = dest; i != source;) {
j = route[i];
for (vit = arr[j].begin(); vit != arr[j].end(); vit++) {
if (vit->d == i) {
f = min(f, vit->capacity);
break;
}
}
i = j;
} 这里结束之后，找到的f为最小值，即增广路的最大值。
for (i = dest; i != source;) {
j = route[i];
for (vit = arr[j].begin(); vit != arr[j].end(); vit++) {
if (vit->d == i) {
vit->capacity -= f; 把所有的容量减去f，相当于把现有的流量增加了f
break;
}
}
i = j;
}
max += f; 最大值再加上f
for (i = 0; i < MAX; i++) {
route[i] = -1; 清除操作
}
}
delete[] route; 清除操作
return max; 返回
BFS代码如下
bool *visit = (bool *)calloc(MAX, sizeof(bool)); calloc一个 visit
int i, j;
queue<int> q;
q.push(source);
visit[source] = true;
while (!q.empty()) {
i = q.front();
q.pop();
if (i == dest) {
break;
}
for (auto vit : arr[i]) { C++ 里面的一种新的遍历方式
j = vit.d;
if (!visit[j] && vit.capacity > 0) { 需要使得visit[j] == 0
q.push(j);
route[j] = i;
visit[j] = true; 已经访问过j
}
}
}
free(visit);
return i == dest ? true : false;
void *calloc(size_t nitems, size_t size)
参考https://www.runoob.com/cprogramming/c-function-calloc.html
感悟：目前见过的最难的一道题，理解一下最大流的思想即可，自己也写不出来。
2、To Buy or Not to Buy - Hard Version
题目大意：Eva想用最喜欢的颜色做一串珠子，商店只整片地卖。
给出想做的和商店有的，输出能否做成，以及额外的/缺少的珠子个数。
不知道考察什么算法
先看简单版本To Buy or Not to Buy
题目大意差不多，但是每个测试用例只有两行，参考结果，人家用的暴力搜索
#include <iostream> 头文件
using namespace std;
int main(){
string s1,s2;
cin>>s1>>s2; 由于输入的只有两行，直接输入s1,s2即可。
int a[123]={0},less=0,more=0;
a[123]中的123代表的是：0-9 + a-z + A - Z , 的最大的ASCII码，z的码为122.
for(int i=0;i<s1.size();i++)
a[s1[i]]++; 将s1的字母在数组a中表示出来
for(int i=0;i<s2.size();i++)
a[s2[i]]--; 把s2的减去
for(int i=1;i<123;i++)
if(a[i]<0) less+=a[i]; 如果有<0的，说明有不满足情况的，少的，计数
else more+=a[i]; 如果>的话，就记下来多的（每次都会记）
if(less<0) cout<<"No "<<-less<<endl; 如果较小，输出less的相反数。
else cout<<"Yes "<<more<<endl;否则，输出more
return 0;
}
暴力搜索，思想简单
08.19
补充数据结构知识
1、To Buy or Not to Buy - Hard Version
与原来的区别是，项链种类的数目增多了，并且可以选择多条。
不能简单地用暴力搜索了，需要DFS+剪枝
参考别人代码如下：一个想法：我还是不会做
08.20
数据结构知识
1、栈
头文件 #include <stack>
stack<int> S
S.push(i)
例题：括号匹配
要求：分别找到不能匹配的左括号和右括号，并输出。
知识点：栈应用
思想：左括号入栈，检测到右括号时，栈顶的出栈。
代码实现：
头文件
#include <stdio.h>
#include <iostream> 这句可以不要
#include <stack>
#include <string.h>
using namespace std;
主函数
int main(){
char s[101];
int flag[101]; 用flag做标记也行，也可以用char ans[110]直接来保存输出的结果，待会儿直接输出
stack<int> S; 一般放在main函数外面
int i = 0;
输入
scanf("%s",s); 因为有多组数据，最好直接写成while(scanf("%s",s) != EOF){
XXX
}
循环检测
for(i=0; s[i]!= 0;i++){
if(s[i] == '(')
S.push(i);
如果使用ans的话，ans[i] = ' '; 先默认一个空格
else if ( s[i] == ')'){
if(S.empty() == true)
flag[i] == -1; ---> ?
else
S.pop();
加入ans[i] = ' ' ;
}
else ans[i] = ' '; 普通的字符
左括号不匹配的做标记
while( !S.empty()){
flag[S.top()] = 1;
加ans[S.top()] == '$';
S.pop();
}
输出
puts(s);
for(i = 0; s[i] != 0; i++){
if(flag[i] == 1)
printf("?");
else if(flag[i] == -1)
printf("$");
else
printf(" ");
}
return 0;
}
收获：
- 判断字符串数组中是否到了结尾，是用str[i] == 0是否成立来判断的
- 字符串ans赋值之后，为了使得能够正确输出，加一句ans[i] = 0;
栈的例题2：表达式求值
知识点：堆栈
思想：
需要设立两个堆栈，一个保存数字，一个保存运算符
数学运算有优先级的，自己定义一个优先级矩阵，5*5，代表加减乘除，并且自己在表达式首位默认加入一个最低优先级。
收获：
- 运算优先级用一个矩阵来表示，并且还自己加了运算符0号。
- 栈和队列在使用前，都先自己清空一下
08.21
1、哈夫曼树
中间节点的权值的和即为哈夫曼树的带权路径和
求最小值：用堆，用优先队列 priority_queue<int> Q来实现，默认堆顶是最大值。
小顶堆：priority_queue<int, vector<int>, greater<int> > Q
需要头文件： #include <queue>
例题：构造哈夫曼树，输出所有节点的值与权值的乘积之和
限制：2=<n<=1000
代码实现：
头文件
#include <queue>
#include <stdio.h>
using namespace std;
小堆顶
priority_queue<int, vector<int>, greater<int>> Q;
main函数如下，对于每次输入
while(Q.empty() == false) Q.pop();
for(i = 1;i<=n;i++){
int x;
scanf("%d",&x);
Q.push(x);
}
int ans = 0;
下面是精华
while(Q.size()>1){
int a = Q.top();
Q.pop();
int b = Q.top();
Q.pop();
ans += a+b; //非叶子节点的权值和
Q.push(a+b);
}
printf("%d", ans);
2、二叉树
遍历：前序、中序、后序，可以使用递归来实现
节点的结构体
struct Node{
Node *lchild;
Node *rchild;
XXX...
}
中序遍历
void inOrder(Node *Tree){
遍历左子树
if(Tree -> lchild != NULL)
inOrder(Tree -> lchild);
}
遍历当前节点
if(Tree -> rchild != NULL){
inOrder(Tree -> rchild);
return;
}
例题：给定前序和中序遍历，求其后序遍历
限制：节点数n<=26
知识点：根据前序中序还原二叉树，并保存在内存中。
08.22
1、二叉树构建
代码实现：
#include <stdio.h>
#include <string.h>
struct Node{
Node *lchild;
Node *rchild;
char c;
}Tree[50];
char str1[30], str2[30];
main函数如下
int main(){
while(scanf("%s",str1)!= EOF){
scanf("%s",str2);
loc = 0; 表示静态数组中已经分配的节点个数
int L1 = strlen(str1);
int L2 = strlen(str2);
Node *T = build(0,L1-1,0,L2-1);
postOrder(T);
}
return 0;
}
build函数如下
Node *build(int s1, int e1, int s2, int e2){
Node *ret = creat();
ret -> c = str1[s1];
int rootIdx;
查找根节点在中序中的位置
for(int 1 = s2; i<= e2; i++){
if(str2[i] == str1[s1]){
rootIdx = i;
break;
}
}
如果左子树不空，重建左子树
if(rootIdx != s2){
ret -> lchild = build(s1+1,s1+ (rootIdx - s2), s2, rootIdx - 1 )
如果右子树不空，重建右子树
类似左
}
收获：
- 结构体中的内容，用 ->输出，比如 T -> c;
- loc表示的是：每组数据中，已经处理完的节点，所以在main中每次循环先初始化为0
- 每次创建节点 ，定义的是create函数。
2、二叉排序树
插入顺序不同，结果可能不同
中序遍历，是一个递增序列
例题：建立二叉排序树
要求：节点数n <= 100，重复节点忽略，不用输出
插入函数
Node *Insert(Node *T, int x){
情况一：T是空树
if(T == NULL){
T = creat();
T ->c = x;
return T;
}
插入左子树
else if( x < T ->c ){
T -> lchild = Insert( T->lchild, x );
}
else if (x > T->c){
T -> rchild = Insert( T->rchild, x );
}
return T;
}
收获：
- postOrder 后序遍历 / inOrder 中序遍历 / preOrder 先序遍历
- 只要掌握了调用的逻辑，递归循环即可完成操作，我们所做的工作是很小的。
3、一个结论
中序遍历再加上任何一个遍历，就可以完全确定一个二叉树。
例题：二叉搜索树，判断两个序列是否为同一个树的序列
限制：n<= 20,表示有n个需要判断/ 序列的长度小于10
思路：给出的只是插入顺序，其实还没开始构建树，我们的目的就是要构建树。
对输入序列构建二叉树，构建两颗，分别进行前序遍历和中序遍历，如果结果相同，说明树相同。否则不同。
代码实现
输入tmp并转为数字的方法
scanf("%s",tmp);
for(int i = 0; tmp[i] != 0; i++) {
T = Insert(T,tmp[i] - '0');
}
在先序和中序遍历的时候，已经把节点中的字符放入字符串str中了
str[*(size) ++ ] = T ->c + '0';
T中存放的纯数字，放入字符串中需要加上数字0的ASCII
处理其他需要判别的输入字符串
由于程序比较复杂，有多个字符串，多个标记变量。
char *str；用来指示当前正在保存的字符串
size的操作
int size1, size2;
int *size;
size1 = 0;
size = &size1;
遍历保存时：str[*(size) ++ ] = T ->c + '0';，即size1 ++
str1[size1] = 0;
收获：
- 要根据题目进行变通。这里把前序遍历和中序遍历都保存在一个字符串中，字符串的长度设置为25,实际应用应该不超过20
- tmp暂时用来存储,可以存储自己的基字符串，也可以存储要比较的字符串。虽然它单个是数字，但是由于一串输入了，仍然看作是字符串的形式。所以需要进行处理。
- 比较两个字符串是否相同，使用
puts(strcmp(str1,str2)==0 ? "YES" : "NO" );
08.23
1、二叉树的删除操作
非特殊情况：将右子树的最小的节点代替这个节点。
原理：中序遍历不变。
08.24
1、上题 —— 买珠子
代码不容易理解，参考另一个答案
main函数如下
str是输入的，j单个遍历每个字符，
如果这个字符在需要的字符串中出现过，
使用到了str.find()函数
str.find(ss) 返回字符串ss在str中的位置，需要的头文件是iostream。
string::npos是个特殊值，说明查找没有匹配
头文件
用到的 cstdio, cstdlib, cstring,
和 algorithm, climits, cctype, set, map, vector
定义const N = 150
还是不会做，确实难了，先放弃。
继续看《王道机试》
2、成绩排序
要求：按照三个条件排序
限制：学生个数N <= 1000, 姓名的长度不超过100
需要自己根据题意来定义排序规则函数
bool cmp(E a, E b){ 定义成bool型，如果a < b， 返回真
if (a.score != b.score) return a.score < b.score;
int tmp = strcmp(a.name, b,name);
if tmp != 0, return tmp < 0;
else return a.age < b.age;
}
main函数中，排序用 sort(buf, buf + n, cmp)
如果不定义cmp函数，我们可以定义<运算
bool operator < (const E &b ) const {
if(score != b.score) return score < b.score;
int tmp = strcmp(name, b.name);
if(tmp != 0) return tmp < 0;
else return age < b.age;
}
这样在main函数中写的时候，就不用再写cmp了，只写sort(buf,buf+n)即可。
有两种，记重载运算符这种形式。
3、日期类问题
例如：两个日期之间的天数
思想：预先写好一个程序，可以处理所有日期与一个特定日期之间的差值，再将这两个值相减即可。
2月需要做特殊处理，考虑平年闰年
#define ISYEAP(x) x % 100 != 0 && x % 4 == 0 || x % 400 == 0 ? 1 : 0 //
定义一个数组，预存每个月的天数
int dayOfMonth[13][2]{
0,0,
31,31,
28,29,
31,31,
30,30,
31,31,
30,30,
31,31,
31,31,
30,30,
31,31,
30,30
31,31
};
为日期定义一个类，方便时间的推移
struct Data{
int Day;
int Month;
int Year;
void nextDay(){
Day ++;
if(Day > dayOfMonth[Month][ISYEAP(Year)]){ 若成立，需要换月
Day = 1;
Month++;
if(Month > 12){ 如果成立，需要换年
Month = 1;
Year++;
}
}
}
};
main函数将相差的日期结果都保存在数组buf中。
当要计算题目给的数据时，输入为：
while(scanf("%4d%2d%2d",&y1,&m1,&d1) != EOF){
XXX
}
收获：
- 这种思想很好，可以解决很多问题
- 开辟大空间，如果在main函数中，可能会由于栈空间不足无法开辟这么大的空间，所以定义成全局变量。
联想：之前一个老师问的问题：全局变量和局部变量各自的优缺点：可以加一个点：如果要开辟的内存太大，局部变量无法满足要求空间不够，就需要开辟为全局变量（或者malloc动态分配）
日期类例题2: 给出一个日期 三个数，年月日，算出它星期几
限制：年为1000-3000之间
思想：与上题相同，知道基数日期是星期几，求出基数日期和给出日期之间的差的天数，将天数%7，计算出结果。
与上题的差别在输出格式上。month的英文输出，星期的英文输出。
char monthName[13][20] = {
"",
"January",
"February",
"March",
"April",
"May",
"June",
"July",
"August",
"September",
"October",
"November",
"December"
}
char weekName[7][20]{
"Sunday",
"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saterday"
};
main函数中对于每次输入，通过strcmp函数，找到对应的月份，保存在m中。
日期差保存在days中。
(day % 7 + 7 ) % 7
第一个%7是为了运算方便，+7 是为了解决负数的情况（但是按理说没有负数了）%7是为了最后的运算。
4、Hash的应用
hash：将存储位置与数据本身对应起来。
08.25
1、Hash的应用
例题1: 统计同成绩的学生人数
要求：输出某个分数的学生的人数
限制：N <= 1000
思想：用hash来解决。
因为输入的分数在0-100之间，共有101种情况，是有限的。在输入时，就对这些情况分别计数。
代码实现如下：
头文件
#include <stdio.h>
main函数如下
int main(){
int n;
while(scanf("%d",&n) != EOF && n != 0){
int Hash[101] = {0};
输入
int i;
for(i = 1;i<n;i++){
int x;
scanf("%d",&x);
Hash[x]++;
}
输出
int x;
scanf("%d",&x);
printf("%d\n",Hash[x]);
}
return 0;
}
2、例题2:排序
输入格式，输入n\m,共有n个数，找出其中前m大的数。
如果n和m较大，算法的复杂度较高，不能简单的排序。
考察：哈希实现排序
代码实现如下
#include <stdio.h>
#define OFFSET 500000
int Hash[1000001];
int main(){
int n,m;
while (scanf("%d%d",&n,&m)!= EOF) {
for(int i= -500000; i<= 500000; i++){
Hash[i + OFFSET] = 0;
}
for(int i = 1; i<= n; i++){
int x;
scanf("%d",&x);
Hash[x + OFFSET] = 1;
}
for(int i = 500000; i>= -500000; i--){
if(Hash[i+OFFSET] == 1){
printf("%d",i);
m--;
if(m!=0) printf(" ");
else{
printf("\n");
break;
}
}
}
}
return 0;
}
收获：
- 由于Hash的位置相当于一境排序过的，我们只需要判断出现过没有即可。
- 对于输出结束，是每次都让m --，当m到0的时候表示输出结束了。这时候break就会跳出循环。
- 有负数，所以使用OFFSET偏移。
- 观察输出格式，何时有空格
3、数学问题
a%b的值的正负与a相同，与b无关。
当有可能出现负数时，对于原来求得的r, (r + b) %b
大数求模时，为了防止溢出，可以在内部进行%c
例题：位数拆解
特殊乘法
限制：两个数小于1000000000
知识点：位数拆解
#include <stdio.h>
int main(){
int a,b; 要输入的两个数保存在a和b中
while(scanf("%d%d",&a,&b)!= EOF){
int buf1[20], buf2[20], size1 = 0, size2 = 0;
while(a != 0){
buf1[size1++] = a%10; 先求模，再/10，把位数保存在buf1中。
a = a/10;
}
while( b != 0){
buf2[size2++] = b%10; 把位数保存在buf2中。低位在左边，是靠0开始的。
b/= 10;
}
int ans = 0;
int i,j;
for(i = 0; i<size1 ; i++){
for(j = 0; j<size2; j++){
ans+= buf1[i] * buf2[j]; 题目给出的运算方法
}
}
printf("%d\n",ans);
}
return 0;
}
08.26
1、进制转换
都以10进制为过渡，所以每次都需要转换两次
例题：把输入的十进制转为m进制，m是输入的。
#include <stdio.h>
int main(){
long long a,b;
int m;
while(scanf("%d",&m)!= EOF){
if (m == 0) break;
scanf("%lld%lld",&a,&b);
a = a+b;
int ans[50], size = 0;
do{
ans[size++] = a%m;
a/= m;
} while(a != 0); 数值转换为m进制，保存在ans[]中。
for(int i = size - 1; i>= 0; i--){
printf("%d",ans[i]); 将其输出
}
printf("\n");
}
return 0;
}
收获：
- 题目给出的整数是不超过整形定义，所以定义的为long long型，scanf输入时，为lld
例题2:进制转换
要求：输入为 a,n,b，表示输入的n是a进制，但是我们想把其转换为b进制。
限制：a,b均 <= 16
#include <stdio.h>
#include <string.h>
int main(){
int a,b;
char str[40]; 保存输入的字符串
while(scanf("%d%s%s",&a,str,&b) != EOF){
int tmp, length = strlen(str), c = 1;
int i;
for(i=length-1; i>= 0; i--){
int x;
if(str[i] >= '0' && str[i] <= '9'){
x = str[i] - '0';
}
else if (str[i] >= 'a' && str[i] <= 'z'){
x = str[i] - 'a' + 10;
}
else{
x = str[i] - 'A' + 10;
}
tmp += x*c;
c*= a;
}
tmp是得到的数的十进制
char ans[40], size = 0;
do{
int x = tmp % b;
ans[size++] = (x<10)? x+'0':'x'- 10 + 'A';
tmp /= b;
}while(tmp); 将b进制的结果保存在ans[]中
for(int i = size - 1; i>= 0; i--){
printf("%c",ans[i]);
} 输出结果
printf("\n");
}
return 0;
}
2、STL标准模版库
string : 保存和处理字符串
一般来说，XXX.h 头文件是C文件，XXX是C++ 。但是string比较特殊，
string.h : C标准库，包含一些常见的字符串处理函数，如strcmp
<string>: 是c++ 的头文件，其内包含了一个string类，string s1就是建立一个string类的对象
string对象中已经重载了 + 、+=、<=、等运算符。
输出
使用C++风格：
string c = "cout";
cout << c << endl;
使用C语言风格：
string c = "cout";
printf("%s\b",c.c_str());
记住c.c_str()
并且\b是退格的意思
对每一个字符进行遍历：
for(int i = 0; i<s.size(); i++){
char c = s[i];
}
其中 erase函数，s.erase(10,8)会从10开始，
int pos = a.find(b,startPos);
会在a中从startPos开始找b字符串，如果能找到，就返回第一次出现的位置。如果没找到，返回一个常数string::nops
例题：字符串的查找删除
要求：在字符串中进行删除，删除短字符串。并且还要删除空格。
08.27
1、上个例题
记录一下自己的情绪，发泄一下。
在医院两天我是没有任何怨言的。真正让我崩溃的是：公交车上看到的消息/打电话时的冷嘲热讽/楼梯间吸烟的老人/被气到肚子发抖。
人们的悲喜并不相通。
虽然说过很多遍了，但是还是真正去做到：认真地感受生活，不要对任何人有太多期待，自己强大起来才是最可靠的。
加油刷题！小马最棒！在我心里，我自己就是最棒的！
给字符串赋值如下：
char str[101];
gets(str);
string a = str;
将str中的大写转为小写。
for(int i = 0; i < a.size();i++){
a[i] = tolower(a[i]);
}
下面这个循环用来进行删除操作
while(gets(str)){
string b = str, c = b; b用来删除小写的，但是c中保存的才是我们真正需要输出的。
for(int i = 0; i<b.size(); i++){
b[i] = tolower(b[i]);
}
int t = b.find(a,0);
while( t != string::npos){
c.erase(t,a.size());
b.erase(t,a.size());
t = b.find(a.t);
}
t = c.find(' ',0); 空格就要从真正的c中去删除了。
while( t!= string::npos){
c.erase(t,1);
t = c.find(' ',0);
}
cout << c << endl;
}
收获：
scanf 在读入内容之后，不会清除后面的换行符。如果后面用一个gets，见到换行之后就会停止。就会导致输入错误。解决方法是：使用getchar() 消除空格符。所以尽可能不使用gets()
-
如果题目说了是不区分大小写输出的，那么我们可以都先把字符串转为小写。对于判断大小写，需要使用一些函数。那么需要包含的头文件是：
#include <ctype.h>
image.png
2、最大公约数GCD
a和0的最大公约数是a
方法：遍历（数字较大时复杂度较高）；扩展的欧几里得
- 需要注意：非零数与零的最大公因数是这个非零数。
例题：
#include <stdio.h>
int gcd(int a, int b){
if(b == 0) return a;
else return gcd(b, a%b);
}
int main(){
int a, b;
while(scanf("%d%d",&a,&b) != EOF){
printf("%d\n",gcd(a,b));
}
return 0;
}
