留下的足迹-CSDN博客

原创深搜练习题——蜘蛛纸牌

蜘蛛牌是windows xp操作系统自带的一款纸牌游戏，游戏规则是这样的：只能将牌拖到比她大一的牌上面（A最小，K最大），如果拖动的牌上有按顺序排好的牌时，那么这些牌也跟着一起移动，游戏的目的是将所有的牌按同一花色从小到大排好，为了简单起见，我们的游戏只有同一花色的10张牌，从A到10，且随机的在一行上展开，编号从1到10，把第i号上的牌移到第j号牌上，移动距离为abs(i-j)，现在你要做的是求出完成游戏的最小移动距离。Input第一个输入数据是T，表示数据的组数。每组数据有一行，10个输入数据，数

2021-03-23 20:48:52 529

原创迷宫问题——bfs（输出最短路径）

定义一个二维数组：int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。Input一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。Output左上角到右下角的最短路径，格式如样例所示。Sample Input0 1 0 0

2021-03-13 09:58:03 5689 2

原创越狱——快速幂

题目描述：监狱有连续编号为1…N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。输入格式：输入两个整数M，N。输出格式：可能越狱的状态数，对100003取余。思路：利用快速幂，因为相邻房间犯人的宗教相同，就有可能发生越狱，而m是宗教数，n是房间数，所以先求相邻房间的所有匹配情况(mn),再求出不会越狱的情况，不会越狱的条件是相邻房间的宗教不同，所以不会越狱的情况有m*(m-1)^(n-1),由此得出

2021-02-23 20:46:52 1325 1

原创线段——贪心思想

题目描述数轴上有条线段，选取其中条线段使得这条线段两两没有重合部分，问最大为多少。输入格式第一行为一个正整数；在接下来的行中，每行有个数，描述每条线段。输出格式输出一个整数，为的最大值。样例输入：30 22 41 3样例输出：2思路：贪心思想，线段的起始点和终止点放入结构体中，按起始点从小到大排序，每次用当前线段的起始点和上一个找到的不重合的线段的终止点进行比较，如果当前线段和上一个找到的线段重合，（因为线段起始点从小到大排序，所以起始点肯定比

2021-02-20 17:00:53 269 1

原创广搜优化

Fat brother and Maze are playing a kind of special (hentai) game on an N*M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids wh

2021-02-06 20:30:27 139 1

原创贪心算法——最小区间覆盖问题

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first bein

2021-01-28 16:22:39 2238 1

原创 Wormholes——Floyd（判断是否存在负权环）

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms co

2021-01-23 17:29:16 634

原创表达式转换——中缀表达式转换为后缀表达式

表达式转换算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换为后缀表达式。输入格式:输入在一行中给出不含空格的中缀表达式，可包含+、-、*、\以及左右括号()，表达式不超过20个字符。输出格式:在一行中输出转换后的后缀表达式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。输入样例:...

2020-12-26 10:53:09 3933

原创新的开始——最小生成树

发展采矿业当然首先得有矿井，小FF花了上次探险获得的千分之一的财富请人在岛上挖了n口矿井，但他似乎忘记考虑的矿井供电问题…… 为了保证电力的供应，小FF想到了两种办法：在这一口矿井上建立一个发电站，费用为v（发电站的输出功率可以供给任意多个矿井）。将这口矿井与另外的已经有电力供应的矿井之间建立电网，费用为p。小FF希望身为”NewBe_One" 计划首席工程师的你帮他想出一个保证所有矿井电力供应的最小花费。输入格式:第一行一个整数n，表示矿井总数。第2～n+1行，每行一个整数，第i个数

2020-12-05 09:50:29 362

原创北极通讯网络——最小生成树kruskal

北极的某区域共有 n 座村庄，每座村庄的坐标用一对整数 (x,y) 表示。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机，也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机，且所有的无线电收发机型号相同。但卫星设备数量有限，只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数 d，两座村庄之间的距离如果不超过 d 就可以用该型号的无线电收发机直接通讯，d 值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。现在有 k 台卫星设备，请你编一个

2020-12-05 08:37:04 332

原创 2020-11-14

给定若干个长度 ≤10^6的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3个 ab 连接而成。输入格式输入若干行，每行有一个字符串。特别的，字符串可能为 . 即一个半角句号，此时输入结束。样例样例输入abcdaaaaababab.样例输出143数据范围与提示字符串长度 ≤10^6。题意：给出字符串，求解字符串由几个子串重复而成利用kmp求出next数组，然后通过(l%nex[l]==0&&nex[l]!=0)

2020-11-14 11:30:15 661

原创字典树——例题

给定 n个长度不超过10的数字串，问其中是否存在两个数字串 S、T，使得 S是 T的前缀，多组数据。输入格式第一行一个整数 T，表示数据组数。对于每组数据，第一行一个数n，接下来 n行输入 n个数字串。输出格式对于每组数据，若存在两个数字串 S、T，使得 S是 T的前缀，则输出 NO ，否则输出 YES 。请注意此处结果与输出的对应关系！样例样例输入2391197625999911254265113123401234401234598346样例输出NOYES数据

2020-11-14 11:11:48 733

原创喷水装置——贪心

题目描述：长 L米，宽 W 米的草坪里装有 n个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？Picture1输入格式输入包含若干组测试数据。第一行一个整数 T表示数据组数；每组数据的第一行是整数n、L和W；接下来的 n行，每行包含两个整数，给出一个喷头的位置和浇灌半径（上面的示意图是样例输入第一组数据所描述的情况）。输出格式对每组测试数据输出

2020-10-29 19:57:31 296

原创深搜剪枝——小木棍

题目描述：乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50 。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。输入格式第一行为一个单独的整数 N表示砍过以后的小木棍的总数。第二行为 N个用空格隔开的正整数，表示 N 根小木棍的长度。输出格式输出仅一行，表示要求的原始木棍的最小可能长度。样例样例输入95 2 1 5 2 1 5 2 1样例输出6数据范围与提示1

2020-10-29 19:21:23 279

原创完全二叉树的权值

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示:现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点权值之和最大?如果有多个深度的权值和同为最大，请你输出其中最小的深度。注:根的深度是 1。输入第一行包含一个整数 N。第二行包含N个整数A1,A2,··· AN。输出输出一个整数代表答案。样例输入71 6 5 4 3 2 1样例输出2#include<cstdio&

2020-10-16 15:59:23 3952 2

原创 KMP模板

KMP模板分析：next数组：存储字符串的最大公共前后缀对于公共前后缀，不能从第一位开始找，也就是本身相同不属于公共前后缀。伪代码——求next数组：void getnext()///找子串的next数组{ int i=0,j=-1; ///i,j不同，目的：防止从第一位开始找自身 nex[0]=-1; ///j回溯到0时j=-1 while(i<l2) ///l2为子串的长度，i相当于子串的右端 { if(j==-1||b[i]==b[

2020-08-08 22:10:04 194

原创最长回文长度——manacher（马拉车）

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.回文就是正反读都是一样的字符串,如aba, abba等Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c…y,z组成的字符串S两组case之间由空行隔开(该空行不用处理)字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.Sample InputaaaaababSample Output

2020-08-07 19:24:37 340

原创单源最短路-求最大承重

BackgroundHugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where

2020-05-12 22:12:30 164

原创拓扑排序例题——判断有环和无环

ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many “holy cows” like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions,

2020-05-10 20:03:25 332

mashizuren的博客