八皇后问题（链接） 努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1 − 99 1-99 1−99 的数字。他又准备了 8 8 8 个皇后棋子。 8 8 8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 8 8 8 个皇后所在的位置的数字的和是最大的。 输入格式 输入一个数字 k ( k ≤ 20 ) k(k\leq 20) k(k≤20)，代表棋盘的数量。 接下来有 k k k 个棋盘，每个棋盘有 64 64 6...

问题描述及要求 产生一个菜单驱动的演示程序，用以说明二叉树的使用。元素由单个键组成，键为单个字符。用户能演示的二叉树基本操作至少包括：构造二叉树，按先序、中序、后序、层序遍历这棵二叉树，求二叉树的深度、宽度，统计度为0，1，2的结点数等。二叉树采用链式存储结构。对二叉查找树做上述工作，且增加以下操作：插入、删除给定键的元素、查找目标键。 由于没使用类模板，请使用二叉树演示时此处为char 而使用二叉排序树时将char 改为int。 Code #include<iostream> #include<string> #include<map> #inclu...

查找算法的实现及性能测试与比较 问题描述 在顺序线性表中存放n个整数，n的值由用户输入确定，线性表可以是有序表或无序表。比较各查找算法在不同情况下的时间性能。 各查找算法的实测时间性能包括两个指标：算法执行的绝对时间和关键字的平均比较次数。 各查找算法要求评测查找成功与不成功的两种情形。 为了能比较出各种查找算法执行的绝对时间，需要对表中的数据进行较大量的查找，设为m次，m的值也由用户输入确定。当输入m为1000000时，则对线性表作1000000次查找。 （1）比较在有序表和无序表中进行顺序查找时，查找成功和查找失败时的算法执行的绝对时间和关键字的平均比较次数。 （2）比较在同一有序表中...

题目：图在社交网络上的应用 [问题描述] 设计并实现一个社交网络模型图，并实现相关图的算法。 要求： （1）每个人的信息是一个顶点，A关注了B，则构成A到B的边。请随机生成不少于50个点，和不少于500条边，边有方向，带权重（0-1之间），权重可以认为是两个人的亲密度，可随机生成。 （2）根据输入的任意两个人的信息，可以查询打印他们之间的所有可能的路径。 （3）实现图的深度优先遍历和广度优先遍历算法，打印图中所有点。 （4）求图的所有强连通分量。 （5）在最大的强连通分量上用prim和chruscal算法求最小生成树。 （6）在最大的强连通分量上，实现dijstra和floyd算法求节点之间最...

引子 子问题–1 给出n个数，m次问询，每次问询给出一个范围l、r，求区间l–r的总和 很容易想到用前缀和可以解决 O(n) 子问题–2 给出n个数，m次修改，每次给出一个范围l、r和一个值k，将区间l—r的数全部+k，m次修改后，再问询1次求区间l–r的总和 也可以想到这用差分就能解决 O(n) 最后将这两个问题结合起来，给出n个数，m次操作，操作有两种一个是将区间l–r的值+k,一个是询问区间l–r的总和。 这个问题与之前不同的地方是，之前想要求一个范围只需处理一次数据算前缀和，然后数据不变，可以一劳永逸算出多次查询，但现在用原本的方法的话，每当数据更新一次，就必须再算一次前缀和 ...

声明：该项目是牛客网的一个开源项目 飞翔小鸟游戏 文章目录 一 效果图 二 思维导图 1.类的属性关系 2.类的相关方法 三 设计步骤 1.素材准备 2.预备知识及其运用 3.大体流程 四 源码 1.游戏类 2.地面类 3.小鸟类 4.柱子类 文章目录 一 效果图 二 思维导图 1.类的属性关系 2.类的相关方法 三 设计步骤 1.素材准备 相关项目/...

目录 1.链表篇 反转链表 判断链表中是否有环 合并有序链表 2.动态规划篇 跳台阶 子数组的最大累加和 求路径 最长公共子串 3.树篇 两个节点最近公共祖先 实现二叉树先中后序排列 二叉树之字形遍历 4.二分篇 求平方根 5.其他 岛屿数量 最长无重复子串 括号生成 有重复数字的所有排列 1.链表篇 反转链表 难...

昨天笔试开始，6道题目，感觉挺简单的。大家是不是基本都AK了...

其实对于数组的顺序打乱并不会影响，因为都是要求对所有i,j分别匹配求出能满足条件的解的个数，所以排序加二分即可。 include include include include include<memory.h> include include define pii pair<int,int> define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std;typedef long long ll;const int Max = 2e5 + 5;int lst[Max]...

题解：此题有两个问题，第一求这套系统最多能拦截多少导弹，第二个求如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。 第一个问题即为求最长下降子序列，不多阐述。 对于第二个问题我是用贪心求解的。对于每一个处在i位置的导弹，它可以和（从1到i-1位置且还没有被击落的）任一大于等于其高度的导弹共在一套装置（意思即为无需添置新的装置），在此想既然是选一个符合要求的导弹共处一套装置，则选对于之后的更有利的导弹（即为选比位置i导弹高度高的所有导弹中高度最小的那个，可以好好思考一下为何如此选）。 AC代码： #include<iostream> using namespace std; con...

01背包的变式题 思路：对于经典的01背包本题的不同之处在于多了只有当主件购买时才可以购买附件，并且每个主件最多只有2个附件。思考一下不难发现，将原本的01背包的决策（选或不选）变为现在的决策（不选主件|选主件|选主件+附件1|选主件+附件2|选主件+附件1+附件2）。dp[i][j]表示在前i件物品当金钱为j时的最大价值，如果第i件物品为附件则dp[i][j]=dp[i-1][j](略过该判断附件的情况在主件时一并判断了)。接下来是判断针对dp[i][j]判断5个决策。 int c[Max],v[Max],f[Max];//分别存储价格、重要程度、所对应主件vector<int>...

最长上升子序列的变式。先从左往右求一遍最长上升子序列(dpl)，再从右往左求一遍(dpr)。结果遍历一遍从左和从右的dp值和(dpr[i]+dpl[i])，找出和为最大的-1即为最大正常先递增再递减的子序列长度，-》n-长度即为需要出列的最少同学数。 AC代码如下 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int Max = 1e5 + 5; int lst[Max]; int dpl[Max],dpr[Max]; int main() { int n; cin...