xindoo_社区达人页

2023年10月

• 10.31 23:11:00
  发表了文章 2023-10-31 23:11:00

  hdoj 3732 Ahui Writes Word (多重背包)

  来看题目吧，可能有100000个单词，然后只有1000ms，但看包的大小，有10000，这样只能允许nlog(n)的算法，还有，每个单词的价值和花费都很小（不大于十），如果不考虑单词的不同，只考虑价值和花费只有最多100种东西，但如果把这些按多重背包的方法来计算依旧会超时，很容易想到和之前01背包的时间复杂度是一样的。
• 10.31 23:09:24
  发表了文章 2023-10-31 23:09:24

  poj 2823 Sliding Window

  让你设计一个队列，是其求里面最大值的时间复杂度尽可能的低，但这个队列除了最大值外，就是一个普通的队列，该怎么进出还是怎么进出，并不是优先队列。
• 10.31 23:07:15
  发表了文章 2023-10-31 23:07:15

  POJ 3264 RMQ

  题意就是让你求区间最大和最小值的差值。 这题可以用线段树，也可以用Tarjan 的Sparse Table算法（参考刘汝佳训练指南197），这里我用了ST算法，还有要说明的是题目描述的数据范围是不准确的如果你数组开比50000大一点点的话是会RE的。
• 10.31 23:06:05
  发表了文章 2023-10-31 23:06:05

  Codeforces Round #192 (Div. 2) (329A)C.Purification

  Codeforces Round #192 (Div. 2) (329A)C.Purification
• 10.31 23:04:51
  发表了文章 2023-10-31 23:04:51

  Codeforces Round #192 (Div. 2) (330B) B.Road Construction

  要将N个城市全部相连，刚开始以为是最小生成树的问题，其实就是一道简单的题目。 要求两个城市之间不超过两条道路，那么所有的城市应该是连在一个点上的，至于这个点就很好找了，只要找到一个没有和其他点有道路限制的即可。
• 10.31 23:03:22
  发表了文章 2023-10-31 23:03:22

  Codeforces Round #192 (Div. 2) (330A) A. Cakeminator

  如果某一行没有草莓，就可以吃掉这一行，某一列没有也可以吃点这一列，求最多会被吃掉多少块蛋糕。
• 10.31 23:02:25
  发表了文章 2023-10-31 23:02:25

  poj 1068 模拟

  大概题意就是告诉你有个n个小括号，每一个“）”左边有多少个“（”都告诉你了，然后让你求出每一对括号之间有多少对括号（包含自己本身）。 思路： 我先计算每个“）”左边有多少个“（”要匹配，然后每遇到一个“）”，然后向前寻找第一个可以匹配的“（”，找到后将其数量减一，这样的话在寻找的过程中经过了几个“）”就表示这对括号里面有多少括号。
• 10.31 23:00:34
  发表了文章 2023-10-31 23:00:34

  codeforces 327 B. Hungry Sequence

  题目就是让你输出n个数的序列，要保证该序列是递增的，并且第i个数的前面不能保护它的约数，我直接先对前100000的素数打表，然后输出前n个，so easy。
• 10.31 22:59:42
  发表了文章 2023-10-31 22:59:42

  codeforces 327 A Ciel and Dancing

  给你一串只有0和1的数字，然后对某一区间的数翻转1次（0变1 1变0），只翻转一次而且不能不翻转，然后让你计算最多可能出现多少个1。 这里要注意很多细节 比如全为1，要求必须翻转，这时候我们只要翻转一个1就可以了，对于其他情况，我们只要计算区间里面如果0多于1，将其翻转后计算1的总数，然后取最大值。
• 10.31 22:58:37
  发表了文章 2023-10-31 22:58:37

  codeforces 322 B Ciel and Flowers

  有红绿蓝三种颜色的画，每种拿三朵可以组成一束花，或者各拿一朵组成花束，告诉你每种花的数目，求出可能组成最多的花束。 如果你的代码过不了，考虑一下 8 8 9这种组合。 因为数据量很大，我的思想就是局部和总体采用不同的策略。
• 10.31 22:57:34
  发表了文章 2023-10-31 22:57:34

  codeforces 322 A Ciel and Dancing

  有n个男孩和m个女孩，他们要结对跳舞，每对要有一个女孩和一个男孩，而且其中一个要求之前没有和其他人结对，求出最大可以结多少对。
• 10.31 22:56:12
  发表了文章 2023-10-31 22:56:12

  hdoj 3555 BOMB(数位dp)

  hdoj 3555 BOMB(数位dp)
• 10.31 22:55:22
  发表了文章 2023-10-31 22:55:22

  hdoj 2089 不要62

  这题数据量相对比较小，可以暴力打表解决。不过我这里用数位dp 刚开始学数位dp，参考了别人的代码。
• 10.31 22:54:26
  发表了文章 2023-10-31 22:54:26

  poj 1164 放苹果

  这题可以用递归的方式做，想给第一个盘子里放上苹果从（0到m），然后给第二个放上，为了保证每次产生的放法是不同的，第二个里面放置的苹果不能从0开始，否则就会产生相同的放法，然后同理第三第四个盘子。。。。 还有一个问题，可能放到最后一个盘子了，还有很多苹果没有放，怎么办？
• 10.31 22:53:24
  发表了文章 2023-10-31 22:53:24

  poj 1050 To the Max(最大子矩阵之和)

  poj 1050 To the Max(最大子矩阵之和)
• 10.31 22:52:21
  发表了文章 2023-10-31 22:52:21

  light oj 1011 - Marriage Ceremonies (状态压缩+记忆化搜索)

  light oj 1011 - Marriage Ceremonies (状态压缩+记忆化搜索)
• 10.31 22:50:48
  发表了文章 2023-10-31 22:50:48

  codeforces 317 A Perfect Pair

  我先排除了输出-1的，然后再考虑如何计算最小的步数。我们主要在每一步中最小一个加上另一个就可以了，这是朴素的求法，但可能出现这样的情况 比如 -100000000 1 10000000 这样的话会循环100000000多次，肯定超时，所以我们要加快速度。
• 10.31 22:49:08
  发表了文章 2023-10-31 22:49:08

  codeforces 318 A.Even Odds B.Sereja and Array

  codeforces 318 A.Even Odds B.Sereja and Array
• 10.31 22:47:35
  发表了文章 2023-10-31 22:47:35

  codeforces 315 B.Sereja and Array

  codeforces 315 B.Sereja and Array
• 10.31 22:46:04
  发表了文章 2023-10-31 22:46:04

  codeforces 285C - Building Permutation

  题目大意是有一个含n个数的数组，你可以通过+1或者-1的操作使得其中的数是1--n中的数，且没有重复的数。 既然是这样的题意，那么我就应该把原数组中的数尽量往他最接近1--n中的位置放，然后求差绝对值之和，但有多个数，怎么使他们和最小，这样就要对其进行排序了，直接按大小给它们安排好位置，然后计算。
• 10.31 22:45:08
  发表了文章 2023-10-31 22:45:08

  codeforces 299 A. Ksusha and Array

  题目就是让你找出一个数组中可以将这个数组中所有数整除的数，很明显，如果存在，这个数肯定是最小的一个。
• 10.31 22:44:07
  发表了文章 2023-10-31 22:44:07

  codeforces 304 B. Calendar

  就是给你两个日期，让你求两个日期之间差多少天。 我先算出两个日期分别是公元多少天，然后相减得到结果。
• 10.31 22:43:16
  发表了文章 2023-10-31 22:43:16

  codeforces 304A. Pythagorean Theorem II

  给你一个n，计算出1 ≤ a ≤ b ≤ c ≤ n.使得由abc构成的三角形满足勾股定理，c为斜边。 没有简单的方法，直接爆力，但是要注意，有些abc满足勾股定理的表达式，但不一定是三角形，所以要判断一下，根据三角形三边的性质，两边之和大于第三边，两边之差小于第三边。
• 10.31 22:42:21
  发表了文章 2023-10-31 22:42:21

  codeforces 305 C. Ivan and Powers of Two

  我的思路是这样的，由2^a+2^a = 2^(a+1)可知，如果有两个连续的数a，我们可以把他们合并为a+1放入集合中，使集合中没有重复的数，我可以用stl里的set。如果想要满足题目中的要求，集合中必须有最大那个数个元素，缺多少就可以计算出来了。
• 10.31 22:41:03
  发表了文章 2023-10-31 22:41:03

  codeforces 289 B. Polo the Penguin and Matrix

  题目意思是在n*m的矩阵中，你可以对矩阵中的每个数加或者减d，求最少的操作次数，使得矩阵中所有的元素相同。 虽然在condeforces中被分到了dp一类，但完全可以通过排序，暴力的方法解决。
• 10.31 22:39:55
  发表了文章 2023-10-31 22:39:55

  hdoj 4572 Bottles Arrangement

  虽然不知道怎么做，但是AC还是没有问题的。 大概就是循环n次，从m加到m-n/2 除了最后一个数，每个都加两次。
• 10.31 22:38:53
  发表了文章 2023-10-31 22:38:53

  100个经典的动态规划方程

  设g’表示从起点到第i个旅店住宿一天的最少天数；f’表示从起点到第i个旅店住宿一天，在满足最小天数前提下所需要的最少费用。那么：
• 10.31 22:37:37
  发表了文章 2023-10-31 22:37:37

  Codeforces Round #186 (Div. 2)A、B、C、D、E

  Ilya得到了一个礼物，可以在删掉银行账户最后和倒数第二位的数字（账户有可能是负的），也可以不做任何处理。
• 10.31 22:35:35
  发表了文章 2023-10-31 22:35:35

  poj 1159 Palindrome(最长公共子串)

  关于求最长公共子串， 用到的是动态规划
• 10.31 22:34:09
  发表了文章 2023-10-31 22:34:09

  poj 2105 IP Address

  题目链接
• 10.31 22:33:10
  发表了文章 2023-10-31 22:33:10

  uva 10891 game of sum

  题目链接 详细请参考刘汝佳《算法竞赛入门经典训练指南》 p67
• 10.31 22:31:56
  发表了文章 2023-10-31 22:31:56

  codeforces 312

  A. Whose sentence is it?
• 10.31 22:30:36
  发表了文章 2023-10-31 22:30:36

  hdoj 4551 生日猜猜猜

  题目链接
• 10.31 22:29:35
  发表了文章 2023-10-31 22:29:35

  hdoj 4554 叛逆的小明

  printf("%d %d\n", a+b, a-b); }
• 10.31 17:53:19
  发表了文章 2023-10-31 17:53:19

  codeforces 302 B. Eugeny and Play List

  题目链接 有n首歌，编号从1到n，每首歌播放时间为t，播放次数为c，n首歌按次序播放，有m个询问，输出第v分钟正在播放的歌曲编号。 很简单的二分查找，直接贴代码。
• 10.31 17:52:18
  发表了文章 2023-10-31 17:52:18

  uva 10340 all in all

  输入两个字符串s和t，判断是否可以从t中删除0个或多个字符（其他字符顺序不变），得到字符串是。
• 10.31 17:51:10
  发表了文章 2023-10-31 17:51:10

  UVA live 2678 - Subsequence

  关于这个题目，有多种的解法，如果枚举起点和终点，时间复杂度为O(n^3)，但如果我们用一个数组B把一段数的和存起来，B[i] = sum(a[1].....a[i])。这样就可以把时间复杂度降到O(n^2)。
• 10.31 17:50:06
  发表了文章 2023-10-31 17:50:06

  uva 11549 CALCULATOR CONUNDRUM

  题目链接 刘汝佳算法竞赛经典入门训练指南p42
• 10.31 17:47:05
  发表了文章 2023-10-31 17:47:05

  hdoj 4288coder & cf 85d Sum of Medians

  这两个题目是一样的，大概题意是有3个操作 add x， 在集合中加入x， del x 是删除x， sum 是求出由小到大排序后所有下标mod5等于3的数的和。
• 10.31 17:46:00
  发表了文章 2023-10-31 17:46:00

  hdoj 1176免费馅饼（dp）

  tmax = max(dp[t+1][i], dp[t+1][i-1]); else {
• 10.31 17:45:00
  发表了文章 2023-10-31 17:45:00

  codeforces 272C. Dima and Staircase（线段树）

  题目很长，看加猜加谷歌翻译才看懂了题目。每级台阶的宽都是1，但高不同，并且告诉你了，然后给你m个箱子，长和宽都告诉你，把箱子靠左放，求箱子的底部有多高。
• 10.31 17:43:48
  发表了文章 2023-10-31 17:43:48

  light oj 1258 - Making Huge Palindromes(KMP)

  ight oj里这个题目是属于KMP分类的，但乍看好像不是kmp，因为只有一个字符串。要想的到一个回文串，把该字符串翻转接到原串后面必然是一个回文串，但并不一定是最短的。我们必须考虑怎么把两个串尽量融合在一起，这就要看翻转串的前段与原串的后段有多少是匹配的了，这里就用到了KMP算法。
• 10.31 17:42:41
  发表了文章 2023-10-31 17:42:41

  light oj 1255 - Substring Frequency (KMP)

  输入两个字符串，计算二串在一串中出现的次数。 裸裸的KMP，参考刘汝佳《算法竞赛入门经典训练指南》 P212 或数据结构。
• 10.31 17:41:37
  发表了文章 2023-10-31 17:41:37

  poj 1185 炮兵阵地 （状态压缩dp）

  如果你是刚刚开始做状态压缩dp，我建议你先看看 poj 3254 Corn Fields 这是一道比这一题更简单，更容易入门的题目。 还有在代码中我用了一个很巧妙的方法求一个数二进制数中1的个数 具体请看我博客中 x& (x - 1)==0 这篇文章 链接 。
• 10.31 17:40:38
  发表了文章 2023-10-31 17:40:38

  poj 3254 Corn Fields （状态压缩dp）

  状态压缩dp其实就是用二进制来表示所有的状态，比如这题， 我们在某一行可以这样取0 1 0 1 1 0 1，用1代表取了，0代表没取，因为这点，它的数据量也限制在20以内，所有看到这样数据量的题目可以先考虑一下状态压缩dp。对于有多行的数据，所有状态的总数必然很庞大，而且不用特殊的方法想要存储这些状态是不太现实的。既然每个点只有这两种情况，我们可以用二进制的一位来表示，0 1 0 1 1 0 1就可以表示为二进制0101101也就是十进制的45，如果我们想要枚举6个点的所有状态，我们只需要从0到2^6取其二进制就可以了，并不会重复或是多余。
• 10.31 17:39:33
  发表了文章 2023-10-31 17:39:33

  light oj 1005 - Rooks(组合数学)

  组合数学解法 现在n行中选出m行，C(n,m)，再在n列中选出m列随便放A(n,m)，答案为C(n,m)*A(n,m)。
• 10.31 17:38:27
  发表了文章 2023-10-31 17:38:27

  poj 2479 Maximum sum（求最大子段和的延伸）

  看完最大连续子段和 的 dp算法 这个很容易理解，我用dplift[i]保存第1到第i个之间的最大子段和，dpright[i]保存第i到第n个之间的最大子段和，最终结果就是dplift[i]+dpright[i+1]中最大的一个。
• 10.31 17:37:24
  发表了文章 2023-10-31 17:37:24

  求最大连续子段和 的 dp算法

  对于这样的问题，我们可以直接用暴力，一个双重循环，虽说可以，但也没有更高明的方法？ 我们再分析这个问题，如果我们知道了某个数前面一段数的和，我们就该考虑把这个数加入到前一段，还是重新开始一段。这个地方很重要，如果前一段的和小于0，我们重新建一段，反之加到前一段。这样我们就可以把n个数分成几段了，且每一段都求出了他们的和，然后再循环一次求出最大的一个和，我们就得到想要的结果了，也可以在分段的时候直接求结果。