UVA 465 (13.08.02)
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/62.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
哈夫曼树 编码-【UVA No. 12676】转换哈夫曼编码 Inverting Huffman
【UVA No. 12676】转换哈夫曼编码 洛谷题目地址 【题意】 静态哈夫曼编码是一种主要用于文本压缩的编码算法。给定一个由N 个不同字符组成的特定长度的文本，算法选择N 个编码哈夫曼树 编码，每个不同的字符都对应一个编码。使用这些编码压缩文本，当选择编码算法构建一个具有N 个叶子的二叉树时，对于N ≥2，树的构建流程如下。 ① 对文本中的每个不同字符，都构建一个仅包含单个节点
日期 2023-06-12 10:48:40
UVAoj 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:40Uvaoj 11624 - Fire!
/************************************************************************* File Name: test.cpp Author: HJZ Mail: 2570230521@qq.com Created Time: 2014年08月03日 星期日 07时26分58秒 ******************
日期 2023-06-12 10:48:40Java实现偶数矩阵（Even Parity, UVa 11464）
偶数矩阵（Even Parity
日期 2023-06-12 10:48:40Java实现UVA10131越大越聪明（蓝桥杯每周一题）
10131越大越聪明（蓝桥杯每周一题） [问题描述] 一些人认为，大象的体型越大，脑子越聪明。为了反驳这一错误观点，你想要分析一组大
日期 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:40
UVA 10066 The Twin Towers（LCS）
Problem B The Twin Towers Input: standard input Output: standard output Once upon a time, in an ancient Empire, there were two towers of dissimilar shapes in two different cities. T
日期 2023-06-12 10:48:40UVa 401 Palindromes
LeetCode 409. Longest Palindrome 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。 在构造过程中，请注意区分大小写。比如 Aa 不能当做一个回文字符串。 Uva - 12050 Palindrome Numbers【数论】 题目链接：uva 12050 - Palindrome Numbers 题意：求第n个回
日期 2023-06-12 10:48:40【习题 4-7 UVA - 509】RAID!
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 如果一行里面某位有>1个x 那么是invalid的。 没有x的话。 可以分析以下(设输入的标准Even为0,然后Odd为1) (列出所有情况分析后会发现.) 那么必须满足标准^这一列该位的亦或和==0 x只有1个的情况的话。也应该满足这个,所以就能根据上面这个求出x是啥啦。 末尾添加0 是添加(4-len%
日期 2023-06-12 10:48:40【习题4-1 Uva1589】Xiangqi
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 车是可以被吃掉的。。。 注意这个情况。 其他的模拟即可。 【代码】 #include <bits/stdc++.h> using namespace std; const int dx[4] = {0,0,1,-1}; const int dy[4] = {1,-1,0,0}; const in
日期 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-17 UVA - 11536】Smallest Sub-Array
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 尺取法。 考虑一个1..i的窗口。 里面在到达了i位置的时候恰好有1..k这些数字了。 为了更接近答案。 显然可以试着让左端点变成2.(如果还能有1..k这些数字的话。 所以有1..k这些数字之后。就让左端点尽可能往右。 然后尝试更新答案。 然后让右端点右移。 重复上述过程。 【代码】 #include &l
日期 2023-06-12 10:48:40【习题 8-13 UVA - 10570】Meeting with Aliens
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 枚举1的位置在i 往右摆成一排。 a[i+1]..a[n]..a[1]..a[i-1]变为有序的 ->寻找循环节,每个循环节的长度-1是必要的步骤数 ->获取必要的步骤数,取最小值。 ->O(n^2) 往左排成一排
日期 2023-06-12 10:48:40【习题 8-10 UVA - 1614】Hell on the Markets
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 证明:前i个数一定能凑够1..sum[i]中的所有数字 i=1时显然成立。 现在假设i>=2时结论成立 即前i个数字能凑出1..sum[i] 令k=i+1; 现在证明前i+1个数字能凑出1..sum[i+1] 即用前i个数字和数字a[i+1]凑出1..sum[i+1] 现在我们把i+1个数字全都用上。 得到
日期 2023-06-12 10:48:40【习题 8-7 UVA - 11925】Generating Permutations
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 让你把排列1..n变换成对应的输入序列。 每次可以交换前两个数字,或者把第一个数字放到末尾去。 可以逆向考虑。 即把无序的序列变换成有序的. 则第二种操作就变为"把末尾的数字放到最前面去" 则可以这样。 如果a[0]>a[1] 且a[0]不为n那么就swap(a[0],a[1]) 否则把最后面的那个数字放到
日期 2023-06-12 10:48:40
【习题 8-6 UVA - 1611】 Crane
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 想把数字i从位置j移动到位置i 可以这样。 假设mov(x,y)表示将(x..x+len/2-1)和(x+len/2..y)交换。 则可以先进行mov(j,i-1)操作。 (如果(j,i-1)的长度为奇数,终点就变为i-2) 令len = (i-1)-j+1 //当然长度为奇数的时候就是(i-2)-j+1了 x
日期 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-1 UVA - 1149】Bin Packing
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 每个背包只能装两个东西。 而且每个东西都要被装进去。 那么我们随意考虑某个物品。(不必要求顺序 这个物品肯定要放进某个背包里面的。 那么背包数递增。 那么剩余的空间。 只能装一个了。 要装谁呢? 肯定是尽可能装较大的.所以用upper_bound-1找一个最大的能装的装就可以了。 这样就能尽量减少体积较大的物品了
日期 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-12 UVA-12627】Erratic Expansion
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 规律+递归题 f[k][i] k时刻前i行的红气球个数 i<=2^(k-1) f[k][i] = 2*f[k-1][i]; i>2^(k-1) f[k][i] = 2*c[k-1] + f[k-1][i-2^(k-1)]; c[
日期 2023-06-12 10:48:40【习题 7-9 UVA-1604】Cubic Eight-Puzzle
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 IDA* 保证这次移动的方格不和前一次重复。 然后加一个8数码的剪枝就行了。 ->看看当前状态和目标状态有多少个地方是不一样的。 如果当前的步数加上它仍然比答案大。 显然可以剪枝。 因为不同的数目肯定小于等于要移动的数目； (每次移动最多只能让一个方格还原) (然后只要记录上面和前面的颜色就好了 剩下一个面
日期 2023-06-12 10:48:40【习题 7-8 UVA-12107】Digit Puzzle
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 迭代加深搜索。 枚举最大层数。(也即改变的数字个数 然后枚举第一个改哪个数字,第二个改哪个数字。。 一定要注意字典序问题。 每次优先改成较小的字典序(也即顺序枚举 然后注意这个字符不改的情况。 不要算改变数。 最后改完之后。 只需要枚举a和b的情况。 看看a*b是不是等于c就好 ->查看这样的a*b数量是不
日期 2023-06-12 10:48:40【习题 7-4 UVA-818】Cutting Chains
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 二进制枚举要解开哪些环。 把所有和它相关的边都删掉。 对于剩下的联通分量。 看看是不是每一个联通分量都是一条链 ->每个点的度数都不大于2 ->不是环。 同时剩余的联通分量的个数x 解开的环的个数y y>=x-1才行 满足以上条件即可 【代码】 #include <b
日期 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-1 UVA-208】Firetruck
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 预处理一下终点能到达哪些点。 暴力就好。 输出结果的时候,数字之间一个空格。。 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(at least therr) yourself? 3.Can you
日期 2023-06-12 10:48:40【例题 7-1 UVA - 725】Division
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 枚举分母从0到99999. 得到分子,判断合法 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(at least therr) yourself? 3.Can you promise that th
日期 2023-06-12 10:48:40【习题 6-10 UVA - 246】10-20-30
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 发牌的那个牌堆用一个deque,7个牌堆用vector来模拟。 然后按照题意模拟就好。 不难。 【代码】 /* 1.Shoud it use long long ? 2.Have you ever test several sample(at least therr) yourself? 3.Can you
日期 2023-06-12 10:48:40【例题 6-19 UVA - 1572】Self-Assembly
【链接】 我是链接,点我呀:) 【题意】 在这里输入题意 【题解】 旋转和翻转,会发现。 如果可以顺着某个方向一直放的话。 总是能转换成往下或者往右连的。 则只要能够出现一个连接顺序的循环,则总是有解的。 ->转化成图论模型 如果一个正方形有A+ 另外一个正方形有A-B+C+D- 那么从A+连3条边分别到B+,C+,D- 按照这样的方式连,如果能出现一个环的话,肯定是有解的
日期 2023-06-12 10:48:40