|
|
众数
|
|
|
|
|
|
~~~c
|
|
|
#include <stdio.h>
|
|
|
int num; //全局变量,存放众数
|
|
|
int maxcnt = 0; //全局变量,存放重数
|
|
|
void split(int a[], int low, int high, int& mid, int& left, int& right)
|
|
|
//以a[low..high]中间的元素为界限,确定为等于a[mid]元素的左、右位置left和right
|
|
|
{
|
|
|
mid = (low + high) / 2;
|
|
|
for (left = low; left <= high; left++)
|
|
|
if (a[left] == a[mid])
|
|
|
break;
|
|
|
for (right = left + 1; right <= high; right++)
|
|
|
if (a[right] != a[mid])
|
|
|
break;
|
|
|
right--;
|
|
|
}
|
|
|
void Getmaxcnt(int a[], int low, int high)
|
|
|
{
|
|
|
if (low <= high) //a[low..high]序列至少有1个元素
|
|
|
{
|
|
|
int mid, left, right;
|
|
|
split(a, low, high, mid, left, right);
|
|
|
int cnt = right - left + 1; //求出a[mid]元素的重数
|
|
|
if (cnt > maxcnt) //找到更大的重数
|
|
|
{
|
|
|
num = a[mid];
|
|
|
maxcnt = cnt;
|
|
|
}
|
|
|
Getmaxcnt(a, low, left - 1); //左序列递归处理
|
|
|
Getmaxcnt(a, right + 1, high); //右序列递归处理
|
|
|
}
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int a[] = { 1,2,2,2,3,3,5,6,6,6,6 };
|
|
|
int n = sizeof(a) / sizeof(a[0]);
|
|
|
printf("求解结果\n");
|
|
|
printf(" 递增序列: ");
|
|
|
for (int i = 0; i < n; i++)
|
|
|
printf("%d ", a[i]);
|
|
|
printf("\n");
|
|
|
Getmaxcnt(a, 0, n - 1);
|
|
|
printf(" 众数: %d, 重数: %d\n", num, maxcnt);
|
|
|
}
|
|
|
~~~
|
|
|
|
|
|
钓鱼
|
|
|
|
|
|
```c
|
|
|
#include<stdio.h>
|
|
|
#define MAX 30
|
|
|
int n = 2; //湖的个数
|
|
|
int h = 1; //可用时间
|
|
|
int fi[MAX] = { 0,10,1 }; //最初钓鱼量,数组下标0不用
|
|
|
int di[MAX] = { 0,2,5 }; //单位时间鱼的减少量,数组下标0不用
|
|
|
int ti[MAX] = { 0,2 }; //ti[i]为湖i到湖i+1的时间,数组下标0不用
|
|
|
int cfi[MAX]; //保存fi
|
|
|
//求解结果表示
|
|
|
struct NodeType
|
|
|
{
|
|
|
int num[MAX]; //各个湖的钓鱼时间
|
|
|
int max; //最多的钓鱼量
|
|
|
} Lake[MAX]; //Lake[i]表示经过最后一个湖i的结果
|
|
|
int maxlast; //最多钓鱼量时最后经过湖的编号
|
|
|
int GetMax(int p[], int i, int j) //求p[i..j]中最大元素的下标
|
|
|
{
|
|
|
int maxi = i; //最大元素下标初始化
|
|
|
for (int k = i + 1; k <= j; k++)
|
|
|
if (p[maxi] < p[k]) //比较
|
|
|
maxi = k;
|
|
|
return maxi;
|
|
|
}
|
|
|
|
|
|
void solve() //求解钓鱼问题
|
|
|
{
|
|
|
int i, j, t, restT;
|
|
|
int T = 60 * h; //可用时间总时间
|
|
|
for (i = 1; i <= n; i++) //枚举每一个可能的结束湖位置
|
|
|
{
|
|
|
restT = T; //剩下的时间
|
|
|
for (j = 1; j <= i; j++) //所有走过的湖是1,2,…,i
|
|
|
{
|
|
|
cfi[j] = fi[j]; //初始化cfi
|
|
|
if (j < i)
|
|
|
restT -= 5 * ti[j]; //减去到达湖i路上走路的时间
|
|
|
}
|
|
|
t = 0;
|
|
|
while (t < restT) //考虑所有的钓鱼时间
|
|
|
{
|
|
|
int k = GetMax(cfi, 1, i); //找到钓鱼量最多的湖k
|
|
|
Lake[i].max += cfi[k]; //在湖k中钓一个单位时间的鱼
|
|
|
Lake[i].num[k] += 5; //湖i的钓鱼时间增加一个单位时间
|
|
|
if (cfi[k] >= di[k]) //修改湖k下一个单位时间的钓鱼量
|
|
|
cfi[k] -= di[k];
|
|
|
else
|
|
|
cfi[k] = 0;
|
|
|
t += 5; //增加一个单位时间5
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
int i, j;
|
|
|
for (i = 1; i <= n; i++) //Lake数组初始化
|
|
|
{
|
|
|
Lake[i].max = 0;
|
|
|
for (j = 0; j <= n; j++)
|
|
|
Lake[i].num[j] = 0;
|
|
|
}
|
|
|
solve();
|
|
|
printf("求解结果\n");
|
|
|
maxlast = 1;
|
|
|
for (i = 2; i <= n; i++)
|
|
|
if (Lake[i].max > Lake[maxlast].max)
|
|
|
maxlast = i;
|
|
|
for (i = 1; i <= n; i++)
|
|
|
printf(" 在湖%d钓鱼时间为%d分钟\n", i, Lake[maxlast].num[i]);
|
|
|
printf(" 总的钓鱼量: %d\n", Lake[maxlast].max);
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
填数
|
|
|
|
|
|
```c
|
|
|
#include<iostream>
|
|
|
#include<cmath>
|
|
|
using namespace std;
|
|
|
int a[11] = { 0,1,2,3,4,5,6,7,8,9,10 };
|
|
|
int x[11];
|
|
|
int sum = 0;
|
|
|
bool unprime(int a, int b)
|
|
|
{
|
|
|
int c = a + b, counter = 0;
|
|
|
for (int i = 2; i <= sqrt(c); i++)
|
|
|
{
|
|
|
if (c % i == 0)counter++;
|
|
|
}
|
|
|
if (counter != 0)return true;
|
|
|
else return false;
|
|
|
}
|
|
|
void func(int i)
|
|
|
{
|
|
|
if (i == 11)
|
|
|
{
|
|
|
for (int i = 1; i < 9; i++)
|
|
|
{
|
|
|
if (unprime(x[i], x[i + 1]))return;
|
|
|
}
|
|
|
if (unprime(x[8], x[1]) || unprime(x[9], x[2]) || unprime(x[9], x[4]) || unprime(x[9], x[6]))return;
|
|
|
sum++;
|
|
|
for (int i = 1; i <= 3; i++)cout << x[i] << ' ';
|
|
|
cout << endl;
|
|
|
cout << x[8] << ' ' << x[9] << ' ' << x[4] << endl;
|
|
|
cout << x[7] << ' ' << x[6] << ' ' << x[5] << endl << endl << endl;
|
|
|
}
|
|
|
else
|
|
|
{
|
|
|
for (int j = i; j <= 10; j++)
|
|
|
{
|
|
|
swap(a[i], a[j]);
|
|
|
x[i] = a[i];
|
|
|
func(i + 1);
|
|
|
swap(a[i], a[j]);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
func(1);
|
|
|
cout << "总数：" << sum;
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
求解解救amaze问题
|
|
|
|
|
|
```c
|
|
|
#define _CRT_SECURE_NO_WARNINGS 1
|
|
|
#include <stdio.h>
|
|
|
#include <string.h>
|
|
|
#include <math.h>
|
|
|
#include <queue>
|
|
|
using namespace std;
|
|
|
#define MAX 31
|
|
|
//问题表示
|
|
|
int n;
|
|
|
char b[MAX][MAX];
|
|
|
//求解结果表示
|
|
|
int bite; //被野狗咬的次数
|
|
|
int visited[MAX][MAX];
|
|
|
int px, py, ax, ay; //Magicpig和Amaze的位置
|
|
|
int H[4] = { 0, 1, 0, -1 }; //水平偏移量,下标对应方位号0～3
|
|
|
int V[4] = { -1, 0, 1, 0 }; //垂直偏移量
|
|
|
|
|
|
struct NodeType //队列结点类型
|
|
|
{
|
|
|
int x, y; //当前位置
|
|
|
int length; //走过的路径长度
|
|
|
double lb;
|
|
|
bool operator<(const NodeType& s) const //重载<关系函数
|
|
|
{
|
|
|
return lb > s.lb; //按lb越小越优先出队
|
|
|
}
|
|
|
};
|
|
|
void bound(NodeType& e) //计算分枝结点e的下界
|
|
|
{
|
|
|
double d = sqrt((e.x - ax) * (e.x - ax) + (e.y - ay) * (e.y - ay));
|
|
|
e.lb = e.length + d;
|
|
|
}
|
|
|
bool bfs() //求解解救Amaze问题
|
|
|
{
|
|
|
priority_queue<NodeType> qu;
|
|
|
NodeType e, e1;
|
|
|
e.x = px; e.y = py;
|
|
|
e.length = 0;
|
|
|
bound(e);
|
|
|
visited[px][py] = 1;
|
|
|
qu.push(e);
|
|
|
while (!qu.empty()) //队列不空循环
|
|
|
{
|
|
|
e = qu.top(); qu.pop();
|
|
|
if (e.x == ax && e.y == ay) //找到Amaze
|
|
|
return true;
|
|
|
for (int i = 0; i < 4; i++)
|
|
|
{
|
|
|
e1.x = e.x + H[i];
|
|
|
e1.y = e.y + V[i];
|
|
|
if (e1.x < 0 || e1.x >= n || e1.y < 0 || e1.y >= n)
|
|
|
continue;
|
|
|
if (visited[e1.x][e1.y] == 1) //已经走过，跳出
|
|
|
continue;
|
|
|
if (b[e1.x][e1.y] == 'k') //为金刚，跳出
|
|
|
continue;
|
|
|
if (b[e1.x][e1.y] == 'r' || b[e1.x][e1.y] == 'a')//遇到道路或者Amaze
|
|
|
{
|
|
|
e1.length = e.length + 1; //路径长度增加1
|
|
|
bound(e1);
|
|
|
visited[e1.x][e1.y] = 1;
|
|
|
qu.push(e1);
|
|
|
}
|
|
|
else if (b[e1.x][e1.y] == 'd') //遇到野狗
|
|
|
{
|
|
|
if (bite == 0) //被野狗咬1次的情况
|
|
|
{
|
|
|
e1.length = e.length + 1; //路径长度增加1
|
|
|
bound(e1);
|
|
|
visited[e1.x][e1.y] = 1;
|
|
|
qu.push(e1);
|
|
|
bite++; //被野狗咬次数增加1
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return false;
|
|
|
}
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
int t, i, j, x, y;
|
|
|
scanf("%d", &t); //输入t
|
|
|
while (t--)
|
|
|
{
|
|
|
bite = 0;
|
|
|
memset(visited, 0, sizeof(visited));
|
|
|
scanf("%d", &n); //输入n
|
|
|
for (i = 0; i < n; i++) //输入一个测试用例
|
|
|
scanf("%s", b[i]);
|
|
|
for (i = 0; i < n; i++)
|
|
|
for (j = 0; j < n; j++)
|
|
|
{
|
|
|
if (b[i][j] == 'p') //Magicpig的位置(px,py)
|
|
|
{
|
|
|
px = i;
|
|
|
py = j;
|
|
|
}
|
|
|
if (b[i][j] == 'a') //Amaze的位置(ax,ay)
|
|
|
{
|
|
|
ax = i;
|
|
|
ay = j;
|
|
|
}
|
|
|
}
|
|
|
if (bfs())
|
|
|
printf("Yes\n");
|
|
|
else
|
|
|
printf("No\n");
|
|
|
}
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
仓库设计问题
|
|
|
|
|
|
```c
|
|
|
#include <iostream>
|
|
|
#include <cmath>
|
|
|
using namespace std;//24//53//66
|
|
|
int judge(int x1, int y1, int x2, int y2, int x3, int y3)
|
|
|
{
|
|
|
int minpath;
|
|
|
minpath = x1 + y1 + x2 + y2 + x3 + y3;
|
|
|
for (int i = min(min(x1, x2), x3); i <= max(max(x1, x2), x3); i++)
|
|
|
{
|
|
|
for (int j = min(min(x1, x2), x3); j <= max(max(x1, x2), x3); j++)
|
|
|
{
|
|
|
if (minpath > abs(x1 - i) + abs(y1 - j) + abs(x2 - i) + abs(y2 - j) + abs(x3 - i) + abs(y3 - j))
|
|
|
{
|
|
|
minpath = abs(x1 - i) + abs(y1 - j) + abs(x2 - i) + abs(y2 - j) + abs(x3 - i) + abs(y3 - j);
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
return minpath;
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
cout << judge(2, 4, 5, 3, 6, 6) << endl;
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
买股票
|
|
|
|
|
|
```c
|
|
|
#include <iostream>
|
|
|
#include <algorithm>
|
|
|
using namespace std;
|
|
|
const int maxn = 5050;
|
|
|
int n;
|
|
|
int a[maxn];
|
|
|
int dp[maxn];//dp[i]表示以a[i]结尾的最长下降序列的长度
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 0; i < n; i++) {
|
|
|
cin >> a[i];
|
|
|
dp[i] = 1;
|
|
|
}
|
|
|
//状态转移方程
|
|
|
int res = 0;
|
|
|
for (int i = 1; i < n; i++) {
|
|
|
for (int j = 0; j < i; j++) {
|
|
|
if (a[i] < a[j]) {
|
|
|
dp[i] = max(dp[j] + 1, dp[i]);
|
|
|
}
|
|
|
}
|
|
|
res = max(res, dp[i]);
|
|
|
}
|
|
|
//输出
|
|
|
cout << res;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
自行车
|
|
|
|
|
|
```c
|
|
|
#define _CRT_SECURE_NO_WARNINGS 1
|
|
|
#include <stdio.h>
|
|
|
#define INF 0x3f3f3f3f //定义∞
|
|
|
#define MAXV 101
|
|
|
int A[MAXV][MAXV]; //邻接矩阵
|
|
|
int n, m;
|
|
|
int s, t;
|
|
|
int dist[MAXV];
|
|
|
void BellmanFord(int v) //贝尔曼-福特算法
|
|
|
{
|
|
|
int i, k, u;
|
|
|
for (i = 0; i < n; i++)
|
|
|
dist[i] = A[v][i]; //对dist0[i]初始化
|
|
|
for (k = 1; k < n; k++) //从dist0[u]递推出dist2[u], …,distn-1[u]循环n-2次
|
|
|
{
|
|
|
for (u = 0; u < n; u++) //修改所有非顶点v的dist[]值
|
|
|
{
|
|
|
if (u != v)
|
|
|
{
|
|
|
for (i = 0; i < n; i++)
|
|
|
{
|
|
|
if (A[i][u]<INF && dist[u]>dist[i] + A[i][u])
|
|
|
dist[u] = dist[i] + A[i][u];
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
int main()
|
|
|
{
|
|
|
int i, j;
|
|
|
int a, b, l;
|
|
|
scanf("%d%d", &n, &m); //输入n、m
|
|
|
for (i = 0; i < n; i++) //初始化邻接矩阵
|
|
|
for (j = 0; j < n; j++)
|
|
|
if (i == j)
|
|
|
A[i][j] = 0;
|
|
|
else
|
|
|
A[i][j] = INF;
|
|
|
for (i = 0; i < m; i++) //输入边
|
|
|
{
|
|
|
scanf("%d%d%d", &a, &b, &l);
|
|
|
A[a][b] = -l;
|
|
|
}
|
|
|
scanf("%d%d", &s, &t); //输入s和t
|
|
|
BellmanFord(s); //采用BellmanFord算法求s出发的最短路径
|
|
|
printf("%d\n", -dist[t]); //输出结果
|
|
|
return 1;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
二叉树
|
|
|
|
|
|
```c
|
|
|
#include <vector>
|
|
|
#include <string>
|
|
|
#include<stdlib.h>
|
|
|
using namespace std;
|
|
|
typedef int ElemType;
|
|
|
typedef struct node
|
|
|
{
|
|
|
ElemType data; //数据元素
|
|
|
struct node* lchild; //指向左孩子结点
|
|
|
struct node* rchild; //指向右孩子结点
|
|
|
} BTNode; //二叉链结点类型
|
|
|
BTNode* CreateBTree(ElemType a[], ElemType b[], int n)
|
|
|
//对应例2.8的算法由先序序列a[0..n-1]和中序序列b[0..n-1]建立二叉链
|
|
|
{
|
|
|
int k;
|
|
|
if (n <= 0) return NULL;
|
|
|
ElemType root = a[0]; //根结点值
|
|
|
BTNode* bt = (BTNode*)malloc(sizeof(BTNode));
|
|
|
bt->data = root;
|
|
|
for (k = 0; k < n; k++) //在b中查找b[k]=root的根结点
|
|
|
if (b[k] == root)
|
|
|
break;
|
|
|
bt->lchild = CreateBTree(a + 1, b, k); //递归创建左子树
|
|
|
bt->rchild = CreateBTree(a + k + 1, b + k + 1, n - k - 1); //递归创建右子树
|
|
|
return bt;
|
|
|
}
|
|
|
|
|
|
void DispBTree(BTNode* bt)
|
|
|
//采用括号表示输出二叉链bt
|
|
|
{
|
|
|
if (bt != NULL)
|
|
|
{
|
|
|
printf("%d", bt->data);
|
|
|
if (bt->lchild != NULL || bt->rchild != NULL)
|
|
|
{
|
|
|
printf("("); //有孩子结点时才输出(
|
|
|
DispBTree(bt->lchild); //递归处理左子树
|
|
|
if (bt->rchild != NULL) printf(","); //有右孩子结点时才输出,
|
|
|
DispBTree(bt->rchild); //递归处理右子树
|
|
|
printf(")"); //有孩子结点时才输出)
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
void DestroyBTree(BTNode*& bt)
|
|
|
//释放以bt为根结点的二叉树
|
|
|
{
|
|
|
if (bt != NULL)
|
|
|
{
|
|
|
DestroyBTree(bt->lchild);
|
|
|
DestroyBTree(bt->rchild);
|
|
|
free(bt);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int maxsum = 0; //全局变量:存放最大路径和。
|
|
|
vector<int> maxpath; //全局变量:存放最大路径
|
|
|
void Findmaxpath(BTNode* bt, vector <int > apath, int asum)
|
|
|
//求根结点到叶结点的路径和最大的路径
|
|
|
{
|
|
|
if (bt == NULL) //空树直接返回
|
|
|
return;
|
|
|
apath.push_back(bt->data); asum += bt->data; //bt结点加入apath
|
|
|
asum += bt->data; //累计a路径和。
|
|
|
if (bt->lchild == NULL && bt->rchild == NULL) //bt结点为叶结点
|
|
|
{
|
|
|
if (asum - maxsum)
|
|
|
{
|
|
|
maxsum = asum;
|
|
|
maxpath.clear();
|
|
|
maxpath = apath;
|
|
|
}
|
|
|
}
|
|
|
Findmaxpath(bt->lchild, apath, asum); //在左子树中查找
|
|
|
Findmaxpath(bt->rchild, apath, asum); //在右子树中查找
|
|
|
}
|
|
|
|
|
|
int main()
|
|
|
{
|
|
|
BTNode* bt;
|
|
|
ElemType a[] = { 5,2,3,4,1,6 };
|
|
|
ElemType b[] = { 2,3,5,1,4,6 };
|
|
|
int n = sizeof(a)/sizeof(a[0]);
|
|
|
bt = CreateBTree(a,b,n);
|
|
|
printf("实验结果:\n");
|
|
|
printf("二叉树bt:");
|
|
|
DispBTree(bt);
|
|
|
printf("'in");
|
|
|
printf("最大路径");
|
|
|
vector<int> apath;
|
|
|
int asum = 0;
|
|
|
Findmaxpath(bt,apath,asum);
|
|
|
printf("路径和: % d，路径 : ",maxsum);
|
|
|
for (int i=0;i < maxpath.size();i++)
|
|
|
printf("%d ",maxpath[i]);
|
|
|
printf("\n");
|
|
|
printf("销毁树bt\n");
|
|
|
DestroyBTree(bt);
|
|
|
}
|
|
|
```
|
|
|
|
