xindoo_社区达人页

2023年10月

• 10.31 17:35:20
  发表了文章 2023-10-31 17:35:20

  hdoj 1028/poj 2704 Pascal's Travels(记忆化搜索||dp)

  有个小球，只能向右边或下边滚动，而且它下一步滚动的步数是它在当前点上的数字，如果是0表示进入一个死胡同。求它从左上角到右下角到路径数目。 注意， 题目给了提示了，要用64位的整数。
• 10.31 17:33:56
  发表了文章 2023-10-31 17:33:56

  hdoj 1078 FatMouse and Cheese（记忆化搜索）

  简单的记忆化搜索，和其他不一样的地方就是这个一次可以走K步，其他没啥！！
• 10.31 17:32:29
  发表了文章 2023-10-31 17:32:29

  hdoj 1907

  这是一道博弈的题，准确说是尼姆博弈，只要判断各项的异或值即可。
• 10.31 17:31:22
  发表了文章 2023-10-31 17:31:22

  hdoj 1520 Anniversary party(树形dp)

  我们可以把一个节点当做一个人，每个节点都有一个权重。按照题目意思，如果我们取了某个节点，那么他的父节点和子节点都是不能取的。按要求选取节点，使得选取节点的权重和最大。
• 10.31 17:29:35
  发表了文章 2023-10-31 17:29:35

  poj 2299 Ultra-QuickSort 求逆序数 树状数组解法

  所谓离散化，我们的了解就是对原数组排序，然后用所在位置的下标代替原数，这样我们就可以把数据范围缩小到1-500000，这个数组是开的下的。
• 10.31 17:28:16
  发表了文章 2023-10-31 17:28:16

  hdoj 3466 Proud Merchants(01背包)

  想想我们为什么要排序， 举个简单的例子，如果数据中出现这样到情况 5 9 3、 6 6 5、5 6 3…… 对5 9 3 处理的时候他只能求出dp[9]然后6 6 5只能在dp[9]的基础上继续处理，它要用到dp[6]、dp[7]……，而这些全是零，但这些一直会是0吗？不是在处理5 6 3的时候可以得到这些值，但6 6 5已经被处理了，它再也不会用的这些了，所以怎么得到正确的结果？ 如果我们对5 6 3优先处理就不会出现这样到情况了。
• 10.31 17:26:22
  发表了文章 2023-10-31 17:26:22

  hdoj 2191 背包

  虽然每件物品的数目并不是1，可能有多个，但我们完全可以把这个题目转化成01背包来解决。 可以把多件相同的物品合并成一件，马上就变01背包了。
• 10.31 17:25:10
  发表了文章 2023-10-31 17:25:10

  light oj 1231-1232 - 1233- Coin Change 背包

  暂时到半懂不懂也没办法讲明白，就不误人子弟了，直接贴代码了。
• 10.31 17:23:09
  发表了文章 2023-10-31 17:23:09

  light oj 1047 - Neighbor House 动态规划

  动态规划，这个和刘汝佳算法竞赛入门经典P158的数字三角形有些相似，不过是求最小的值，而且有些限制，每次走到点和上次走的点不在同一列。
• 10.31 17:22:05
  发表了文章 2023-10-31 17:22:05

  loj 1224 - DNA Prefix

  还有最后一点，虽然我们在竞赛中很少使用指针，但涉及到指针，在用完后一定要释放，否则会MLE，我就MLE两次。
• 10.31 17:20:25
  发表了文章 2023-10-31 17:20:25

  动态规划详解

  前段时间一直在做关于数据结构的题，也算是对数据结构有了一定的了解，知道了有些数据结构的基本算法。现在刚刚开始接触动态规划，其实写这篇文章的初衷是一来锻炼一下自己的总结能力，二来也是希望通过这篇文章，来指引和我一样的初学者，废话不多说了，开始吧。
• 10.31 17:16:55
  发表了文章 2023-10-31 17:16:55

  poj 1088 记忆化搜索||动态规划

  记忆化搜索也也是采用递归深搜的对数据进行搜索，但不同于直接深搜的方式，记忆化搜索是在每次搜索时将得到的结果保存下来，避免了重复计算，这就是所谓的记忆化。记忆化应该是属于动态规划。
• 10.31 17:15:23
  发表了文章 2023-10-31 17:15:23

  归并树&划分树详解

  对4 5 2 8 7 6 1 3 分别建划分树和归并树
• 10.31 17:11:55
  发表了文章 2023-10-31 17:11:55

  Light oj 1112 - Curious Robin Hood(树状数组)

  有n个数，有m组操作，1 i表示将第i个数先输出，然后置0， 2 i v 表示给第i个数加上v， 3 i j 表示求i 到 j 的和，注意，这里数组是从0开始的，而我们构造的树状数组是从1 开始的，使用在程序中要进行一定的处理。
• 10.31 17:10:25
  发表了文章 2023-10-31 17:10:25

  Light oj 1080 - Binary Simulation(树状数组区间更新点查询)

  有一字符串只包含0和1，然后又m组操作，I L R是将从L到R的字符进行翻转操作0变为1、1变为0，Q x表示询问第x的字符。
• 10.31 17:08:57
  发表了文章 2023-10-31 17:08:57

  poj 3624 Charm Bracelet（简单01背包）

  Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
• 10.31 17:07:53
  发表了文章 2023-10-31 17:07:53

  poj 1976 A Mini Locomotive(01背包)

  题目的大概意思就是说给你n个数，然后就是有三辆货车头可以拉连续k辆车厢，问你这三个火车头最终可以拉的最大的乘客数是多少。
• 10.31 17:06:32
  发表了文章 2023-10-31 17:06:32

  Light oj 1082 - Array Queries（区间最小值）

  这里只要知道这种算法即可，因为数据量过大，都编译不通过，不过思想算法没有任何问题。
• 10.31 17:04:43
  发表了文章 2023-10-31 17:04:43

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

  我们每次加进来的点相当于k，首先需要进行一个双重循环找到k点和所有点之间的最短路径；然后就以k点位判断节点更新之前的k-1个点，时间复杂度降到O(n^3),而暴力解法每次都要进行floyd，时间复杂度为O(n^4)；相比之下前述解法考虑到了floyd算法的性质，更好了运用了算法的内质。
• 10.31 17:00:23
  发表了文章 2023-10-31 17:00:23

  hackerrank challenges median

  只能说这题我想多了，使用普通的插入排序完全可以解决这道题，在查找的时候用二分加快查找速度。 正确解题报告 这道题的关键在于，不能用int，因为两个int相加可能会越界！因为这个WA了好多遍。所以改用long long。 对double，使用math.h中的函数ceil(double)可以取整，根据ceil(v) == v的结果可以判断v是否是整数。
• 10.31 16:57:49
  发表了文章 2023-10-31 16:57:49

  Codeforces Round #178 (Div. 2)

  在n条电线上有不同数量的鸟， Shaass开了m枪，每一枪打的是第xi条电线上的第yi只鸟，然后被打中的这只鸟左边的飞到第i-1条电线上，右边的飞到i+1条电线上，没有落脚点的鸟会飞走。
• 10.31 16:55:49
  发表了文章 2023-10-31 16:55:49

  poj 1961 Period(kmp最短循环节)

  给定一个长度为n的字符串s，求他每个前缀的最短循环节。换句话说，对于每个i（2<=i<=n），求一个最大的整数k（如果k存在），使得s的前i个字符可以组成的前缀是某个字符串重复k次得到的。输出所有存在K的i和对应的k。
• 10.31 16:54:05
  发表了文章 2023-10-31 16:54:05

  poj 2352 Stars 树状数组

  树状数组，简单题，我刚刚开始学的时候就a了，不多说什么了，直接贴代码。
• 10.31 16:52:56
  发表了文章 2023-10-31 16:52:56

  poj 2182 Lost Cows（树状数组）

  FJ有n头牛，现在它们排成一排，每一头牛都有一个不同的编号（1-n），现在知道从第二头牛开始每头牛左边比自己编号小的牛的数目，让你确定每头牛的编号。
• 10.31 16:51:34
  发表了文章 2023-10-31 16:51:34

  ZOJ1117 POJ1521 HDU1053 Huffman编码

  Huffman编码的思想就是贪心，我们这里使用stl里的优先队列，priority_queue使用堆进行优化，虽然自己也可以写一个堆，但我感觉对于这道题有点主次不分了，再次感觉到stl确实是一个很强大的东西。
• 10.31 16:50:13
  发表了文章 2023-10-31 16:50:13

  POJ 1195 Mobile phones (二维树状树组)

  题意：这道题目只是题意自己就去理解了半天，大概题意如下：给出i一个n*n的矩阵，初始化为均为0，还有关于这个矩阵的几种操作，操作如下：命令1：(X Y A)对位于坐标（X Y）的值加A；命令2：（L B R T）求出位于L<=x<=R，B<=y<=T的值的和；命令3：退出不做任何操作。
• 10.31 16:48:09
  发表了文章 2023-10-31 16:48:09

  计算机科学中的树

  二叉树 ▪ 二叉查找树 ▪ 笛卡尔树 ▪ Top tree ▪ T树 自平衡二叉查找树
• 10.31 16:46:57
  发表了文章 2023-10-31 16:46:57

  ACM竞赛常用STL（二）之STL--algorithm

  内部实现: 数组 // 就是没有固定大小的数组，vector 直接翻译是向量vector // T 就是数据类型，Alloc 是关于内存的一个什么东西，一般是使用默认参数。
• 10.31 16:41:40
  发表了文章 2023-10-31 16:41:40

  ACM竞赛常用STL（一）2

  ACM/ICPC 竞赛之STL--iterator 简介 iterator(迭代器)是用于访问容器中元素的指示器，从这个意义上说，iterator(迭代器)相当于数据结构中所说的“遍历指针”，也可以把iterator(迭代器)看作是一种泛化的指针。STL 中关于iterator(迭代器)的实现是相当复杂的，这里我们暂时不去详细讨论关于iterator(迭代器)的实现和使用，而只对iterator(迭代器)做一点简单的介绍。
• 10.31 16:37:54
  发表了文章 2023-10-31 16:37:54

  ACM竞赛常用STL（一）1

  s.resize(n, val)改变序列的长度，超出的元素将会被删除，如果序列需要扩展（原空间小于n），将用val 填满扩展出的空间。
• 10.31 16:36:02
  发表了文章 2023-10-31 16:36:02

  第K小数 uva 10041 - Vito's Family poj 2388 Who's in the Middle

  了解快排的人对int (int l, int r) 这个函数很熟悉，因为这是在快排中用到的，它的作用是对数组的某一段选一个分界点，使得该点左边的数都不大于该点的数，右边的点不小于该点的数，也就是说我们通过一次调用这个函数确定一个数的位置，快排是将该点两边分别进行递归操作，时间复杂度为O(nlogn)，而select只是对一边进行递归操作（有点像二分的递归形式），所以时间复杂度仅为O(n)。
• 10.31 16:34:22
  发表了文章 2023-10-31 16:34:22

  hdoj 1166 敌兵布阵

  暴力超时，这道题可以用线段树做，因为更新的是单个节点，我们也可以用数组数组来做，我将两种方法的代码都给出 数组数组最适宜的用途就是区间求和和点的更新，但树状数组并不适用于区间的更新问题，也不是做不到，比较麻烦且难理解，有兴趣的可以看看这个
• 10.31 16:31:54
  发表了文章 2023-10-31 16:31:54

  poj 3468 A Simple Problem with Integers线段树区间修改

  题目意思很简单，有N个数，Q个操作， Q l r 表示查询从l到r 的和，C l r v 表示将从l到r 的值加上v，明显的线段树，不知道线段树的人肯定暴力，肯定超时，哈哈！！
• 10.31 16:29:16
  发表了文章 2023-10-31 16:29:16

  interviewstreet pair

  今天突然想起interviewstreet这个网站，这个网站和其他oj有些不同，每题只要通过一组测试样例就会获得一定的分数，然后按分数的高低进行排名，刚刚看到一题。
• 10.31 16:23:38
  发表了文章 2023-10-31 16:23:38

  uva 11991 - Easy Problem from Rujia Liu?

  这个题目的意思是输入n个数，m组询问，每组询问包含两个整数k，v，意思是询问整数v第k次出现的位置。
• 10.31 16:18:03
  发表了文章 2023-10-31 16:18:03

  hdoj 1230 火星A＋Ｂ

  if(i == 1 && j == 1 && !a[0] && !b[0])
• 10.31 16:16:35
  发表了文章 2023-10-31 16:16:35

  hdoj 1202 水水更健康

  double fun(double x)
• 10.31 16:13:31
  发表了文章 2023-10-31 16:13:31

  poj 3298 数状数组

  题目大意是一条大街上住着n个乒乓球爱好者，他们的水平高低用一个数值表示，他们经常举办比赛，比赛要三个人，一人当裁判。对裁判是有一定要求的，裁判的水平必须介于两选手之间且必须住他们中间，计算可以举办多少场比赛
• 10.31 16:12:11
  发表了文章 2023-10-31 16:12:11

  线段树区间修改和点修改 hdoj 1698（区间修改）、hdoj 1754（点修改）

  这两题我都在之前做过，但并未通过，那次做的时候是刚开始接触线段树，现在有了一点点的了解，翻出以前的代码稍作修改就AC了。之前1698错误的原因是没有注意到位运算的优先级。

2023年08月

• 08.12 20:48:40
  发表了文章 2023-08-12 20:48:40

  IO密集型服务提升性能的三种方法

  本文介绍了优化IO密集型系统性能的三种主要策略——批处理、缓存和多线程，其工作原理和适用场景。

2023年03月

• 03.19 17:40:20
  发表了文章 2023-03-19 17:40:20

  深入理解Spring的事件通知机制

  Spring作为一个优秀的企业级应用开发框架，不仅提供了众多的功能模块和工具，还提供了一种灵活高效的事件通知机制，用于处理组件之间的松耦合通讯。本文将详细介绍Spring的事件通知机制的原理、使用方法以及示例，希望对大家深入理解Spring框架有所帮助。
• 03.13 20:14:29
  发表了文章 2023-03-13 20:14:29

  聊一聊过度设计！

  新手程序员在做设计时，因为缺乏经验，很容易写出欠设计的代码，但有一些经验的程序员，尤其是在刚学习过设计模式之后，很容易写出过度设计的代码，而这种代码比新手程序员的代码更可怕，过度设计的代码不仅写出来时的成本很高，后续维护的成本也高。因为相对于毫无设计的代码，过度设计的代码有比较高的理解成本。说这么多，到底什么是过度设计？

  
• 03.13 20:11:49
  发表了文章 2023-03-13 20:11:49

  Java高并发之CyclicBarrier简介

  CyclicBarrier 是 Java 中的一种同步工具，它可以让多个线程在一个屏障点处等待，直到所有线程都到达该点后，才能继续执行。CyclicBarrier 可以用于协调多个线程的执行，以便它们可以在某个点上同步执行。

2023年02月

• 02.11 20:13:14
  发表了文章 2023-02-11 20:13:14

  详解Redisson分布式限流的实现原理

  多图详解Redisson中RRateLimiter分布式限流的实现原理。

  

2022年12月

• 12.16 23:13:50
  发表了文章 2022-12-16 23:13:50

  LinkedHashMap源码解析

  LinkedHashMap源码解析