chengchencheng的博客

1.数字全排列           输出N个数字的所有排列组合情况#include<iostream>using namespace std;void search(int m);void output();int n;int arr[10];int main(){ cin >> n; for(int i = 0; i < n; i+...

1.特殊的二阶魔方描述：魔方大家应该都玩过。现在有一个特殊的二阶魔方，它只有一面是白色，其余五个面全是黑色。玩这个魔方当然也有特殊的规则，玩家只能通过六种方式去改变它，底层向左转一格（称为DL），底层向右转一格（称为DR），右侧向上转一格（称为RU），右侧向下转一格（称为RD），内侧顺时针转一格（称为C），内侧逆时针转一格（称为CC）。现给一魔方的状态，请在最少的步骤内把魔方还原输入：按照...

1.最长公共子序列描述：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1, x2,…, xm>，则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>，使得对于所有j=1,2,…,k有：Xij ＝ Zj如果一个序列S即是A的子序列又是B的子序列，则称S是A...

1.跳马描述：在国际象棋中，马的走法与中车象棋类似，即俗话说的“马走日”，下图所示即国际象棋中马（K）在一步能到达的格子（其中黑色的格子是能到达的位置）。现有一200*200大小的国际象棋棋盘，棋盘中仅有一个马，给定马的当前位置（S）和目标位置（T），求出马最少需要多少跳才能从当前位置到达目标位置。输入：本题包含多个测例。输入数据的第一行有一个整数N（1<=N<=1000），...

1.活动安排描述：Jack是一名nwpu的大一新生，对学校举办的各种活动都十分的好奇，想尽可能多的参加这些活动。Npwu每天共有N项活动，其开始结束时间分别为B[i],E[i],(i = 1,2,……N)请问Jack一天最多能参加几项活动。当然，Jack在同一时间内只能参加一项活动，即jack参加的活动时间上不能重叠，但时间为[t1,t2],[t2,t3]的两个活动是可以同时参加的。输入...

1.加1乘2平方描述：最简单的队列的使用#include <iostream>#include <queue>using namespace std;queue<int> q1;int main(){int temp, x;q1.push(5);//入队q1.push(8);//入队temp = q1.front();//访问队首元素q...

1.最少修建多长的公路能把所有村庄连起来（一）描述：一个地区有n个村庄，有一些村子之间可以修路，已知每条路的长度，问最少修建多长的公路可以把所有的村子连接起来。输入：先输入两个正整数n，m(n小于10000，m小于100000)，表示有n个村庄，m条可以修建的路，接下来的m行每行三个整数，前两个表示村庄的编号（0~n-1），第三个表示这条路的长度。输出：输出路的总长度的最小值。输入...

1.并查集（一）描述：一个城市中有n个人，其中一些人是朋友关系，同时他们都认为：朋友的朋友是朋友，现在任给两个人，问他们是否是朋友关系。输入：先输入两个正整数n和m（均小于1000），表示城市里有n个人，并且将给出m对朋友关系，接下来的m行每行给出两个0~n-1之间的整数，表示这两个人是朋友关系。最后一行再输入两个0~n-1之间的整数，问他们是否是朋友关系。输出：是朋友关系则输出"Ye...

       分治法：将一个规模为n 的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。       大量实践表明，将问题分成大小相等的两个子问题的方法是行之有效的，它几乎总比子问题规模不等的的做法要好。 例1：二分搜索        将n个元素分成大致相同的两半，取a[n/2]与x进行比较。如果x=a[n...

递归算法：直接或间接调用自身的算法。递归函数：用函数自身给出定义的函数。 递归的优点：算法简洁易于分析理解。递归的缺点：分支较多的函数时间、空间复杂度太大。 例1：求n!#include<iostream>using namespace std;int f(int n);int main(){ int m; cin>>m; co...

1.石子合并描述：在一个圆形操场的四周摆放着n堆石子(n<= 100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序，读入石子堆数n及每堆的石子数(<=20)。选择一种合并石子的方案,使得做n－1次合并,得分的总和最小；比如有4堆石子：4 4 5 9 则最佳合并方案如下：4 4 5 9 score: 0...