ural专题
ural 1297. Palindrome dp
1297. Palindrome Time limit: 1.0 second Memory limit: 64 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unli
ural 1149. Sinus Dances dfs
1149. Sinus Dances Time limit: 1.0 second Memory limit: 64 MB Let An = sin(1–sin(2+sin(3–sin(4+…sin( n))…) Let Sn = (…( A 1+ n) A 2+ n–1) A 3+…+2) An+1 For given N print SN Input One
ural 1820. Ural Steaks 贪心
1820. Ural Steaks Time limit: 0.5 second Memory limit: 64 MB After the personal contest, happy but hungry programmers dropped into the restaurant “Ural Steaks” and ordered n specialty steaks
ural 1017. Staircases DP
1017. Staircases Time limit: 1.0 second Memory limit: 64 MB One curious child has a set of N little bricks (5 ≤ N ≤ 500). From these bricks he builds different staircases. Staircase consist
ural 1026. Questions and Answers 查询
1026. Questions and Answers Time limit: 2.0 second Memory limit: 64 MB Background The database of the Pentagon contains a top-secret information. We don’t know what the information is — you
ural 1014. Product of Digits贪心
1014. Product of Digits Time limit: 1.0 second Memory limit: 64 MB Your task is to find the minimal positive integer number Q so that the product of digits of Q is exactly equal to N. Inpu
后缀数组 - 求最长回文子串 + 模板题 --- ural 1297
1297. Palindrome Time Limit: 1.0 second Memory Limit: 16 MB The “U.S. Robots” HQ has just received a rather alarming anonymous letter. It states that the agent from the competing «Robots Unlim
【URAL】1057 Amount of Degrees 数位DP
传送门：【URAL】1057 Amount of Degrees 题目分析：将数转化成能达到的最大的01串，串上从右往左第i位为1表示该数包括B^i。 代码如下： #include <cstdio>#include <cstring>#include <algorithm>using namespace std ;typedef long long LL ;#de
ural Minimal Coverage (区间覆盖)
http://acm.timus.ru/problem.aspx?space=1&num=1303 给出一些区间，选择尽量少的区间能覆盖到[0,m]。 小白p154，典型的区间覆盖问题。一直在想怎么dp。。 首先预处理，先按左端点从小到大排序，若左端点相同右端点从大到小排序，若区间x完全包含y，按照贪心的思想，y是没有意义的，有大区间可以选何必选择小区间。处理完事之后各个区间满足a1
ural Binary Lexicographic Sequence (dp + dfs)
http://acm.timus.ru/problem.aspx?space=1&num=1081 有一个二进制序列，定义为不能有两个连续的1出现，才是合法的。给出序列的长度n，求合法的二进制序列中按字典序排序后第k个序列是什么。 设dp[i][0]和dp[i][1]分别表示第i位上是0和1的个数。 那么dp[i][0] = dp[i-1][0] + dp[i-1][1]；dp[
ural Mnemonics and Palindromes （dp）
http://acm.timus.ru/problem.aspx?space=1&num=1635 给出一个字符串，将这个字符串分成尽量少的回文串。 起初没有思路，想着应该先预处理出所有的回文串，然后进行dp。但是字符串的长度是4000，O(n^3)肯定不行，其实可以转化为O(n^2)，就是枚举中点而不是枚举起点和终点，又NC了吧。 然后就是线性的dp了。dp[i]表示到第i位为
ural Brackets Sequence (dp)
http://acm.timus.ru/problem.aspx?space=1&num=1183 很经典的问题吧，看的黑书上的讲解。 设dp[i][j]表示i到j括号合法需要的最少括号数。 共有四种情况： s[i]s[j]配对，dp[i][j] = min( dp[i][j] , dp[i-1][j+1] )； s[i] = '('或'[' dp[i][j] = min( dp
ural False Mirrors (状态压缩+记忆化搜索)
http://acm.timus.ru/problem.aspx?space=1&num=1152 有n个阳台围城一圈，每个阳台都有若干个怪兽，一次可以打三个相邻的阳台上的怪兽，它们就会全部死去，但攻击者会受到没有死去怪兽的攻击，每个怪兽的攻击是1unit，问最后攻击者受到的最小伤害。 n <= 20，可以直接dfs过去。 1次WA，1次TLE。 WA是没看透题意，我判断的递归
ural Threeprime Numbers(dp)
http://acm.timus.ru/problem.aspx?space=1&num=1586 题意没看懂，看了别人的翻译。threeprime number的意思是任意三个连续的数组成的一个三位数是素数，注意必须是三位数。给出n，问满足条件的n位数有多少个。 先把三位数的素数筛选出来并标记，设dp[i][j][k]表示到i位为止，最后两位是j和k的满足条件的数的个数。 那么
ural Bicolored Horses（二维dp）
http://acm.timus.ru/problem.aspx?space=1&num=1167 有n个马，黑白两种，依次放入k个马厩，将x匹马放在一个马厩的不快乐值为黑马数目*白马数目。问最后的不快乐值最小是多少？ 设dp[i][j]表示前i个马厩放了j匹马的最小不快乐值，那么dp[i][j] = min(dp[i-1][g]+tmp[g+1][j])。 其中tmp是预处理的
Ural 1017 Staircases（DP）
题目地址：Ural 1017 简单的背包。 代码如下： #include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#in
Ural 1073 Square Country （DP）
题目地址：Ural 1073 DP水题。也可以说是背包。 #include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#in
Ural 1353 Milliard Vasya's Function（DP）
题目地址:Ural 1353 定义dp[i][j]，表示当前位数为i位时，各位数和为j的个数。 对于第i位数来说，总可以看成在前i-1位后面加上一个0~9，所以状态转移方程就很容易出来了: dp[i][j]=dp[i][j]+dp[i][j-1]+dp[i][j-2]+.......+dp[i][j-9]； 最后统计即可。 代码如下： #include <iostream>#in
Ural 1146 Maximum Sum（DP）
题目地址：Ural 1146 这题是求最大子矩阵和。方法是将二维转化一维。 首先用n*n的方法来确定矩阵的列。需要先进行预处理，只对每行来说，转化成一维的前缀和，这样对列的确定只需要前后两个指针来确定，只需要用前缀和相减即可得到。前后两个指针用n*n的枚举。 确定好了哪几列，那么再确定行的时候就转化成了一维的最大连续子序列的和。再来一次O(n)的枚举就可以。 这样，总复杂就变成了O(n^3
Ural 1119 Metro（DP）
题目地址：Ural 1119 因为还有一个可不可以穿的问题，所以需要再加一维。0代表可穿不可穿，可穿设置成0，不可穿就设置成无穷大。1代表当前这格的最短距离。 代码如下： #include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math
Ural 1009 K-based Numbers（DP）
题目地址：Ural 1009 DP水题。。二维DP，第一维只用0和1来表示0和非零就可以。 代码如下： #include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <q
Ural 1225 Flags（DP）
题目地址：Ural 1225 感觉刷DP的时候到了。。 这个题还是很简单的，用个二维数组，第一维表示当前位是什么颜色，只有1,2,3。第二维表示当前是第几维。由于蓝色只能在中间，所以统计只能统计当前位是白和红的时候。 代码如下： #include <iostream>#include <cstdio>#include <string>#include <cstring>#inc
URAL 1002. Phone Numbers
题意就是，已知一串数字，按照题目给的对应表，转换成字母之后，能否由给定的单词组成。要求 输出单词数最小的任意一组答案，或输出无解。 用的DP。 dp[ i ]表示以前i个字母可以组成的最少单词数量。 最后dp [ 总字符数量 ] 就是最少单词个数。 再根据path[ i ] 记录的路径，返回去输出每个单词。 具体见代码: #define K2(a,b,t) case a:c
URAL 1022. Genealogical Tree
本来是写的DFS求最长路的，结果WA at test #2 ,后来发现是因为 图不一定要是连通图。然后就好麻烦了……写了个多次的DFS，没过。 写了个先连成连通图 ，再一次DFS，结果连接成连通图的过程中有错误，WA at test #5 。 最后发现这题是求 拓扑排序，从头写起，终于过了。 每次删除入度最小的顶点，并输出这个顶点的编号。我写的有点复杂……
URAL 1005 Stone Pile
这种题型： Balanced Partition 刚开始用的方法： 从最大的开始放，每次放到数量较小的那一堆上，最后看相差为多少。 这样很容易想，可惜是错的，反例如下。 5 10 9 8 7 2 如果这么算，分的是 (10，7) 和 (9，8，2) 相差2 而最小的答案是（10，8）和（9，7，2） 相差0 看了这
URAL 1017. Staircases
这题，写出递推式就过了。用数组zrt[x][n]表示 x个方块在宽度为n的情况下的种类数。 递推式：枚举第一列的高度，然后每一列减去第一列的高度，问题就转化成了若干个zrt [ 剩下的方块数 ] [ n-1 ]. n=2时，有公式 zrt[x][2]=(x-1)/2; 然后再加上记忆化搜索就行了。 代码如下： long long zrt[501][32];long