- 博客(232)
- 收藏
- 关注
RSS订阅原创 PAT - 1065 A+B and C (64bit) (20)
Given three integers A, B and C in [-2^63^, 2^63^], you are supposed to tell whether A+B > C.InputThe first line of the input gives the positive number of test cases, T (<=10). Then T test c...
2018-07-24 23:45:11
309
原创 PAT - 1040 Longest Symmetric String (25)
Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given “Is PAT&TAP symmetric?”, the longest symmetric sub-string is “s PAT&TAP s”, hence ...
2018-07-21 23:34:07
150
原创 PAT - 1033 To Fill or Not to Fill (25)
With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different ga...
2018-07-21 23:02:29
154
原创 PAT - 1003 Emergency (25)
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the l...
2018-07-16 23:50:45
163
原创 PAT - 1002 A+B for Polynomials (25)
This time, you are supposed to find A+B where A and B are two polynomials.InputEach input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polyn...
2018-07-13 23:03:07
139
原创 PAT - 1001 A+B Format (20)
Calculate a + b and output the sum in standard format – that is, the digits must be separated into groups of three by commas (unless there are less than four digits).InputEach input file contains ...
2018-07-13 21:49:56
158
原创 蓝桥杯 算法训练 ALGO-95 2的次幂表示
#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>using namespace std;int n;void dfs(int num) { int cnt = 0; int i = 0, j; int mi[32]; w...
2018-03-05 22:50:10
171
原创 HDU - 1217 Arbitrage（floyd）
题目大意：n 种钱币间进行各种汇率交换，如果能赚就 Yes，否则 No 解题思路：国家为点，汇率为边建图，用 floyd 处理，最终自己到自己的权值大于 1 说明有一个环能赚#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<cmath>#include<string.h>#i
2017-09-22 16:21:45
202
原创 POJ - 1847 Tram（spfa）
题目大意：火车从一点开到另一点，轨道上有很多岔路口，每个路口都有好几个方向，默认是第一个方向，如果要选择别的方向的话要进行一次换向操作 ，给定一个起点一个终点 ，问最少进行几次操作能够到达终点 ， 如果开不到输出 -1 解题思路：转换次数作为权值，第一个路口是 0，别的是 1，求最短路#include<iostream>#include<stdio.h>#include<stdlib.h>#
2017-09-22 16:14:07
230
原创 POJ - 3660 Cow Contest （floyd）
题目大意：给出 n 头牛的强弱关系，问有几头牛能够确定排名 解题思路：为每个关系建立一条边，间接有关的用 floyd 建好，然后统计与剩余 n-1 个点都相连的点的个数#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorithm>#include<cmath>#include<string.h>#incl
2017-09-22 16:04:12
190
原创 POJ - 1502 MPI Maelstrom（dijkstra/spfa）
题目大意：给出一个 n×n 邻接矩阵的下三角，x 表示不可达，A(i, j) = A(j, i)，i == j 时为 0，求 1 到其余点最小花费时间中的最大值 解题思路：裸最短路 dijkstra： Time(ms)：16 Mem(MB)：0.2#include<iostream>#include<stdio.h>#include<stdlib.h>#include<algorith
2017-09-17 10:17:15
230
原创 POJ - 3259 Wormholes（bellman）
题目大意：n 个点 m 条边 w 个虫洞，m 行三个数表示 a 到 b 花费时间 c，w 行表示 a 到 b 时间逆流 c，即花费时间 -c，虫洞是单向的，问能否回到从前 解题思路：就是判断有无负环，权值能够无限减小。道路是双向的，虫洞是单向的，边的数组大小应该是 m×2+w ，贡献了一发 RE#include<iostream>#include<stdio.h>#include<algori
2017-09-17 10:08:40
176
原创 POJ - 1860 currency exchange（bellman）
题目大意：n 个城市 m 条道路，每条路都有一个承载量，求最大承载量。 解题思路：最大生成树，无向图，dijkstra。对于每条路线来说，最大承载量是该条路线所有道路承载量中的最小值#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>
2017-09-17 09:59:12
242
原创 POJ - 3268 Silver Cow Party（dijkstra）
题目大意：n 个点 m 条边，第二行开始每行三个数 表示 a 到 b 要花费 l 时间，所有奶牛要到 x 的位置去开 party，除了 x 外，别的奶牛去 x 都有一个来回的最短时间，求所有奶牛来回最短时间，并输出最大值 解题思路：有向图，所以来回时间是不同的，将临接矩阵行列对换，进行两次dijkstra即可#include<iostream>#include<stdio.h>#include
2017-09-17 09:30:58
257
原创 POJ - 1797 Heavy Transportation（dijkstra）
题目大意：n 个城市 m 条道路，每条路都有一个承载量，求最大承载量。 解题思路：最大生成树，无向图，dijkstra。对于每条路线来说，最大承载量是该条路线所有道路承载量中的最小值#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>
2017-09-17 09:23:28
242
原创 POJ - 2387 Til the Cows Come Home（dijkstra）
题目大意：n 个点，给出若干条边，无向图，求 1 到 n 的最短距离 解题思路：模板题，没啥好说的#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>#include<queue>#define max(a,b) ((a)>(b)?
2017-09-05 17:30:39
213
原创 HDU - 1003 Max Sum（连续子序列最大和）
题目大意：给一组数，求最大连续子序列和。 解题思路：UVA - 507 Jill Rides Again（连续子序列最大和） #include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>#include<queue>#define max(
2017-09-04 11:30:38
286
原创 POJ - 3616 Milking Time（LIS）
题目大意：n时间内产奶，m个时间段，每个段有 l，r，v 表示从 l 时到 r 时共可产奶 v，挤奶工每次挤奶必须挤完完整的时间段，且每次挤完需要休息 r 时，求可获得的牛奶最大值。 解题思路：n 并没有什么卵用……时间段按开始时间从小到大排序，然后套 LIS 多加一个判断条件，点像贪心#include<iostream>#include<stdio.h>#include<algorithm
2017-09-04 11:24:09
201
原创 HDU - 2859 Phalanx
题目大意：给出一个字母矩阵，求最大的对称子矩阵的大小，对称轴左下到右上。 解题思路：枚举每个字母，判断上和右的字母是否相同，while 直到不同跳出。 dp 表示当前字母为子矩阵左下角时，对称矩阵的大小。#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#incl
2017-09-04 11:14:38
170
原创 HDU - 1078 FatMouse and Cheese（记忆化搜索）
题目大意：n*n 棋盘，老鼠从(0，0)出发，可以上下左右移动吃奶酪，每次最多 k 步，且需要保证下一格奶酪比本格多，问最多能吃到多少。 解题思路：dp + 搜索 dp[][] = max(所有可以从当前点走到的点的dfs的结果集) 记得加上当前格子的值#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath
2017-09-04 10:34:52
166
原创 POJ - 3186 Treats for the Cows
题目大意：给一组数，每次能从首或尾取出一个数，然后乘以当前次数，问如何取使得总和最大。 如：a1, a2, a3 第一次取首，第二次取尾，第三次取首，则和为 a1×1+a3×2+a2×3 解题思路：dp 记录每次取完当前数的最大和，i 表示第 i 次取首， j 表示第 j 次取尾，则 i + j 就表示取的次数。处理一下边界即可#include<iostream>#include<stdio
2017-09-04 10:25:24
173
原创 HDU - 1159 Common Subsequence（LCS最长公共子序列）
题目大意：给出字符串 X 和 Y，输出最长公共子序列的长度 解题思路：LCS 水过#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b
2017-09-01 18:58:39
234
原创 UVA - 10131 Is Bigger Smarter?
详见 HDU - 1160 FatMouse’s Speed#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))const int
2017-09-01 18:44:30
195
原创 HDU - 1160 FatMouse's Speed
题目大意：给出若干只老鼠的重量和速度，从数据中找出一组数据满足越重的老鼠速度越慢，数据量越大越好，输出个数和老鼠的序号，有多种答案，只需要输出一种 解题思路：先对这些数据排序（重量递增，重量相同时速度递减）然后递推 dp 记录包含当前老鼠时能够满足条件的数据最多有几个，path 记录满足条件数据的坐标，用于路径输出。感觉这题也是 LIS 的变型#include<iostream>#include
2017-09-01 18:42:43
170
原创 HDU - 1257 最少拦截系统（LIS最长递增子序列）
题目大意：中文题 解题思路：LIS 输出最长上升子序列的长度即可，除该子序列外的数字前均有比自身大的数字，都会被顺便拦截掉。理解这个之后就好做了~#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>#include<queue>#i
2017-09-01 18:33:14
184
原创 HDU - 1260 Tickets
题目大意：给出 N 组测试样例，每组样例第一行表示 k 个人，第二行表示每个人购票所花时间，第三行 k-1 个数表示相邻两人一起购票需要的时间。8 点上班，问几点能下班。 解题思路：对于每个人，都有自己买 s[i] 或者是和前一个人一起买（除第一个人外）d[i] 两种方式。dp 记录当前人购票时花费最少时间，状态转移方程dp[i] = min(dp[i-1]+s[i], dp[i-2]+d[i])
2017-09-01 11:58:23
204
原创 HDU - 1176 免费馅饼
题目大意：中文题 解题思路：列一个矩阵，把每秒的坐标情况都记录下来，然后从矩阵最后一行（即最后一秒）开始往前递推，输出初始位置 5 的馅饼数即可。#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>#include<queue>#i
2017-09-01 11:53:36
190
原创 HDU - 1114 Piggy-Bank（完全背包）
题目大意：有一个小猪存钱罐，给出空和满时候的重量，并给出若干种面额的硬币大小和重量，个数不限，问装满小猪时，硬币最小总额是多少，若无法装满，输出impossible 解题思路：完全背包，dp 数组开小了 TLE 好几发……看了半天不知道哪里有问题 还以为会是越界什么的 居然是 TLE#include<iostream>#include<stdio.h>#include<algorithm>#
2017-08-31 19:17:09
170
原创 HDU - 1087 Super Jumping! Jumping! Jumping!（最长递增子序列）
题目大意：棋子要从 star 跳到 end，每个位置都有一个值，要求每次移动时值都递增，且不能返回，把 star 看作无穷小， end 看作无穷大，输出最大和。 解题思路：LIS 水过 dp 记录到达当前位置时最大和#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>
2017-08-31 16:41:40
199
原创 HDU - 1069 Monkey and Banana
题目大意：给出一系列方块，要求上面的方块长宽都比下面的小，问最高能叠多高。每个方块可以翻转，并且个数不限。 解题思路：可以翻转意味着一组长宽高能有 6 种摆放方式，列出所有方式按照长宽排序，dp记录当前方块之前能够叠的最高高度。#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<stri
2017-08-31 11:10:22
143
原创 HDU - 1029 Ignatius and the Princess IV
题目大意：给出奇数个数，输出这些数中出现 (N+1)/2 次数的数。 解题思路：直接排序取中间的数即可，因为是奇数个数，出现 (N+1)/2 次的数已经超过一半，一定会出现在中位数上。#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>
2017-08-31 11:03:48
137
原创 UVA - 10066 The Twin Towers（LCS最长公共子序列）
题目大意：有两个塔，用类似的石头堆成，现在要求取出一部分石头使得两个塔完全相同，同时要求塔尽可能高，输出剩余石头数量 解题思路：LCS #include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>#include<queue>#includ
2017-08-09 16:47:03
183
原创 UVA - 1600 Patrol Robot（BFS 三维判重）
题目大意：m * n 的地图，机器人要从（0, 0）走到（m, n），上下左右移动，0 可走 1 为障碍，k 表示可以连续通过的障碍数，输出最小步数。 解题思路：vis 多一维判断已经通过的障碍，别的就是套 BFS#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#
2017-08-09 14:41:40
197
原创 HDU - 2612 Find a way（BFS）
题目大意：Y 和 M 约定在一家 KFC 相见，地图上有许多家 KFC 都用 @ 表示，每移动一格耗时 11 分钟，找一条耗费时间最少的路，并输出两人耗时之和。 解题思路：t 数组记录到达当前位置需要几步，两次 BFS 即可求出两个人到达某个位置的步数和，最后遍历地图，找出所有 @ 对应位置次数和最少的地方，输出时间。 有的 @ 是无法达到的，在 t 中仍是初始化的 0，这要比可达的时间少，但显
2017-08-09 14:37:43
191
原创 HDU - 1495 非常可乐（BFS）
题目大意：中文题。一开始以为一定要两个杯子相同，后来发现瓶子也是可以当杯子用的，只要均分就行……天真了 解题思路：六个入口 BFS，没什么难的，复制的时候漏改了调了好久才发现#include<iostream>#include<stdio.h>#include<algorithm>#include<cmath>#include<string.h>#include<string>#inc
2017-08-09 14:31:02
190
原创 POJ - 3984 迷宫问题（BFS、DFS）
题目大意：5×5 的迷宫，左上走到右下，输出最短路线。 解题思路：水题，BFS 和 DFS 都写了，感受了一下区别。 BFS 第一次到达终点就一定是最短路，输出路径的话要保留之前所有的尝试操作并记录上一步，然后从终点找回起点，利用递归输出路径。 DFS 会找出所有的路径，需要对比步数找出最短的那条，同时只需要储存当前最短的那条路径就可以，如果找到更优的路径再更新。#include<iostre
2017-07-24 11:32:01
325
原创 POJ - 3414 Pots（BFS）
题目大意：有编号 1、2 两个水壶，容量分别是 A、B，有 FILL、DROP、POUR 三种操作，现在要通过这些操作得到 C 升水，问最少几步，并输出步骤。 FILL(i) 装满水壶 i DROP(i) 倒空水壶 i POUR(i, j) i 向 j 倒水，若 j 满了，则多余的水留在 i 中 解题思路：因为 i，j 都可以取 1、2，所以仔细拆分一下其实有 6 种操作，所以是 6 个入口
2017-07-24 11:25:05
222
原创 POJ - 3087 Shuffle'm Up（模拟）
题目大意：有S1，S2 两堆牌，每堆牌有 C 张，进行洗牌操作，最终得到 S12 一堆牌（共 2*C 张），从下至上的牌序是：S2的最后一张，S1的最后一张，S2的倒数第二张，S1的倒数第二张……接着把 S12 的上面 C 张当作新的 S2，下面 C 张当作新的 S1，再洗牌，如此循环。问洗几次牌后能够达成目标牌序。 解题思路：不知道为什么归类为搜索，直接用数组模拟了，搜了一下题解好像是数据大的话
2017-07-24 11:13:43
190
原创 POJ - 3126 Prime Path （BFS）
题目大意：给两个四位的素数 A，B，每次只允许变换一个数字，换完后的四位数也要求是素数，问几步能使 A 换成 B，无法换到输出 Impossible 解题思路：4 位数字，每位数字可以换成 0～9，粗糙看一下是40个入口的BFS。 剪枝： 1、千位不能为 0 2、不能换成自己 3、替换后的数字也要是素数 判定素数这边先打一个素数表//素数打表void isprime() { m
2017-07-24 10:59:58
193
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人