UVA 839 (13.08.20)
UVa 414 – Machined Surfaces
大家好，又见面了，我是你们的朋友全栈君。题目：n个由X和空格组成的串，两边有至少一个X，将n个串压缩，每次每行消除一个空格，问到不能消除时剩余的空格。分析：简单题。统计全体空格数sum_b和最少空格数min_b，则结果就是sum_b – n*min_b。注意：利用gets或者getline读入串。#include <iostream> #include <cstdlib>
日期 2023-06-12 10:48:40![uva 11151 Longest Palindrome （最长公共子序列）[通俗易懂]](/scriptcss/images/61.png)
uva 11151 Longest Palindrome （最长公共子序列）[通俗易懂]
大家好，又见面了，我是你们的朋友全栈君。 uva 11151 Longest PalindromeA palindrome is a string that reads the same from the left as it does from the right. For example, I, GAG and MADAM are palindromes, but ADAM is not.
日期 2023-06-12 10:48:40
Easy Climb UVA - 12170 滚动dp +离散化+ 单调队列优化
E.Easy Climb Somewhere in the neighborhood we have a very nice mountain that gives a splendid view over the surrounding area. There is one problem though: climbing this mountain is very difficult, be
日期 2023-06-12 10:48:40UVAoj 348 - Optimal Array Multiplication Sequence
题意：矩阵相乘的最少的步数 dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j]); 表示的是第i个矩阵到第j个矩阵相乘的最少步数 sign[i][j]表示的是第i个矩阵到第j个矩阵相乘的最少步数是由第i个矩阵到第sign[i][j]个矩阵相乘最少步数 和第sign[i][j]+1个矩阵到第j个矩阵相乘
日期 2023-06-12 10:48:40
uva 10801 - Lift Hopping(最短路Dijkstra)
题目大意： 就是一幢大厦中有0～99的楼层, 然后有1～5个电梯！每个电梯有一定的上升或下降速度和楼层的停止的位置！ 问从第0层楼到第k层最少经过多长时间到达！ 思路：明显的Dijkstra ，在建图的时候u- v可能有多个电梯到达，取时间最少的当作路径的权值！ 如果我们发现 d[i] d[j] + map[j][i] + 60, 那么说明从第0层到达第 i 层的时间大于从第j
日期 2023-06-12 10:48:40
UvaOJ10369 - Arctic Network
/* The first line of each test case contains 1 = S = 100, the number of satellite channels! 注意：S表示一共有多少个卫星，那么就是有 最多有S-1个通道！ 然后将最小生成树中的后边的 S-1通道去掉就行了！ 思路：最小生成树中的第 k 个最小边！ //克鲁斯克尔算法..... #incl
日期 2023-06-12 10:48:40UVAoj 11324 - The Largest Clique(tarjan + dp)
题意：给定一个有向图，寻找一个点数最大集合，使得这个集合中的任意两个点u,v, 都有u- v 或者 v- u 或者u == v思路：首先将强连通分量通过tarjan算法求出来，然后进行缩点，也就是每一个缩点所组成的图就是一个DAG图！令每一个点的权值就是这个缩点所包含节点（也就是对应的强连通分量的节点数目），因为强连通分量的任意的两个节点都是相互可达的，那么这个缩点要么选要么不选，问题就转换成了D
日期 2023-06-12 10:48:40Java实现偶数矩阵（Even Parity, UVa 11464）
偶数矩阵（Even Parity
日期 2023-06-12 10:48:40UVA 10739 String to Palindrome（动态规划 回文）
String to Palindrome 题目大意：给出一个字符串s，现在可以进行3种操作（添加字母，删除字母，替换字母），将其变成回文串，求出最少的操作次数。比如abccda，可以用删除操作，删除b，d两步可变成回文；但如果用替换操作，把b换成d则只需要1步。 分析：刚开始我一直考虑它是否具有最优子结构性质，直到现在，还是不明白为什么可以用动态规划来做，大神若是看见，还望指教。 由于添加字
日期 2023-06-12 10:48:40UVA 12097 LA 3635 Pie（二分法）
Pie My birthday is coming up and traditionally I'm serving pie. Not just one pie, no, I have a number N of them, of various tastes and of various sizes. F of my friends are coming
日期 2023-06-12 10:48:40UVA 11464 Even Parity（部分枚举 递推）
Even Parity We have a grid of size N x N. Each cell of the grid initially contains a zero(0) or a one(1). The parity of a cell is the number of 1s surrounding that cell.
日期 2023-06-12 10:48:40UVA 10881 Piotr's Ants（等效变换 sort结构体排序）
Piotr's AntsTime Limit: 2 seconds Piotr likes playing with ants. He has n of them on a horizontal pole L cm long. Each ant is facing either left or right and walks at a con
日期 2023-06-12 10:48:40UVa 10082 WERTYU
点击打开链接 题意：给定一个n*m的矩阵，问有多少种方法放置两个相互攻击的皇后？规定在同一行同一列和同对角线的能够相互攻击 1 先考虑同一行的情况，n行就有n种情况，每一行有m*（m-1）种，总的是n*m*(m-1); 2 考虑同... 1 对于一个无向图来说如果这个图是一个欧拉图，那么必须满足该图是连通的并且每个点的度数都是偶数 2 题目给定n条边的无向图问我们是否是一个欧拉图，是的话
日期 2023-06-12 10:48:40【习题 4-3 UVA - 220】Othello
【链接】 我是链接,点我呀:) 【题意】 【题解】 legal被我打成leagal... 然后注意输出坐标的时候,格式是%2d.. 然后就没啥难的了。。 【代码】 #include <bits/stdc++.h> using namespace std; const int dx[8]={0,-1,-1,-1,0,1,1,1}; const int dy[8]=
日期 2023-06-12 10:48:40【例题 4-4 uva 213】Message Decoding
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 输入的二进制长度最长为7 所以得开个sta[7][2^7]的样子才存的下所有的字符的。。 定义这么一个数组当字典。 然后一个字符一个字符地读。。组合成题目中的参数。 然后根据读入的每个长度为len的二进制,在字典中找到相应的字符就ok啦。 【代码】 #include <bits/stdc++.h>
日期 2023-06-12 10:48:40【习题 8-18 UVA - 1619】Feel Good
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 用单调队列求出l[i]和r[i] 分别表示i的左边最近的大于a[i]的数的位置以及i右边最近的大于a[i]的数的位置。 则l[i]+1..r[i]-1就是a[i]这个数作为最小数的最大管辖区间了。 写个前缀和就好。 然后取a[i]*区间l[i]+1..r[i]-1的和 中的最大值。 并不是special judg
日期 2023-06-12 10:48:40【习题 8-15 UVA - 1617】Laptop
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 贪心。 把所有的区间按照右端点为第一关键字,左端点为第二关键字升序排。 然后令now = a[i].second. (now即当前的连续区间的最右端点 即第一个区间的右端点。 第一个点就应该放在这个地方。 然后对于第i+1个区间。 如果now==a[i+1].second 则把第i+1个点放在之前一连串的点的最左
日期 2023-06-12 10:48:40
【习题 8-12 UVA - 1153】Keep the Customer Satisfied
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 结束时间比较早的,就早点开始做。 所以,将n件事情,按照结束时间升序排。 然后对于第i件事情。 尽量把它往左排。 即t+1..t+a[i].q 然后如果发现t+a[i].q<=a[i].d了 那么前i件事情就不能全都做了。 那么我们尝试
日期 2023-06-12 10:48:40【习题 8-4 UVA - 11491】Erasing and Winning
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 考虑删掉第i位。 则第i+1位就会取代第i位。 则肯定第i+1位比第i位大的话,才比较好。 则从小到大贪心删,找到第一个a[i+1]>a[i]的i. 然后每次删掉这样的i就可以了。 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test
日期 2023-06-12 10:48:40【例题 8-13 UVA - 11093】Just Finish it up
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 尺取法。 假设现在取[l..r]这一段。 然后发现累加的和小于0了。 那么方法只能是不走l..l+1这一段了 即delta递减(p[l]-q[l]); 直到delta>=0为止。 某个时刻如果发现r+1==l 或者l==1且r==n 则合法。 如果发现l大于n了.则返回无解 【代码】 #include
日期 2023-06-12 10:48:40【例题 8-11 UVA-10954】Add All
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 就是合并果子。。 每次都合并最小的就可以啦。 别忘了初始化 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(at least therr) yourself? 3.Can you promise t
日期 2023-06-12 10:48:40【例题 8-10 UVA - 714】 Copying Books
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 二分最后的最大值的最小值。 得到ans 然后从后往前尽量划分。 如果发现不够分成k个。 那么就从第一个开始接着分restk个(每隔1个分1块 中间遇到之前分了的就直接跳过 【代码】 /* 1.Shoud it use long long ? 2.Ha
日期 2023-06-12 10:48:40【例题 8-7 UVA - 11572】Unique Snowflakes
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 类似尺取法。 用set判断这段区间有没有重复的数字。 有的话,就把头节点的那个数字删掉,直到没有为止。 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(at least therr) yourself?
日期 2023-06-12 10:48:40【例题 8-1 UVA 120 】Stacks of Flapjacks
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 从大到小安排。 显然想让第i大的数字归位 只要让他翻到最上面,然后再翻回来就ok了 即operate(pos[i]) -> operate(i) 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(at
日期 2023-06-12 10:48:40【习题 7-10 Uva11214】Guarding the Chessboard
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 迭代加深搜索。 可以想见最后深度不会很深吧。。 然后皇后之间互相攻击到是允许的。。 就这样 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(at least therr) yourself? 3.C
日期 2023-06-12 10:48:40【习题 7-9 UVA-1604】Cubic Eight-Puzzle
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 IDA* 保证这次移动的方格不和前一次重复。 然后加一个8数码的剪枝就行了。 ->看看当前状态和目标状态有多少个地方是不一样的。 如果当前的步数加上它仍然比答案大。 显然可以剪枝。 因为不同的数目肯定小于等于要移动的数目； (每次移动最多只能让一个方格还原) (然后只要记录上面和前面的颜色就好了 剩下一个面
日期 2023-06-12 10:48:40【习题 7-6 UVA - 12113】Overlapping Squares
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 先预处理出来一个正方形。 然后每次枚举新加的正方形左上角的坐标就可以。 注意覆盖的规则,控制一下就可以。 然后暴力判断是否相同。 暴力回溯即可(只用回溯一个正方形区域) 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several
日期 2023-06-12 10:48:40【习题 7-3 UVA - 211】The Domino Effect
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 每次搜素要往下还是要往右摆。 然后维护一下让每个下标只出现一次就可以了。 =>作为剪枝条件 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(at least therr) yourself?
日期 2023-06-12 10:48:40【习题 7-2 UVA-225】Golygons
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 暴力枚举每次走哪里就好。 用一个二维数组来判重。(数据里,要求不能经过一个点两次->但路径可以相交 然后再用一个flag数组,来判断这个点能不能走。 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(
日期 2023-06-12 10:48:40【例题 7-11 UVA - 12325】Zombie's Treasure Chest
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 1.N/s1 < 1e6 枚举1的个数 2.N/s2<1e6 枚举2的个数 3.s1和s2的值较小 假设买了s2个1和s1个2 那么这两种物品占的体积就一样大了。 即都为s1s2 而第一种物品价值为s2v1第二种物品价值为s1v2 那么 如果s2v1>s1v2的话。 可以想见,如果第二种物品的数
日期 2023-06-12 10:48:40【例题 7-9 UVA-1601】The Morning after Halloween
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 对于没有出现的,当成0节点就好。 所以总是认为有3个人需要走到各自的终点。 将平面图转成点边图。这样比较好枚举。 (二维变成一维，模拟的时候变量都少了一半啦) 然后每次按照要求模拟走一下就好。 (三重循环,枚举每一个人下一步走到了哪个位置即可 (注意两个0节点可以走到相同的位置->因为实际上他们都不存在);
日期 2023-06-12 10:48:40