pushytao_社区达人页

2022年06月

• 06.09 15:35:58
  发表了文章 2022-06-09 15:35:58

  All in the Family_upc_模拟 or lca + 并查集

  The scientists working at the Family Genetics Institute are tracing the spread of a hereditary disease through family trees. They have started by listing the family members that have the disease,

  
• 06.09 15:13:32
  发表了文章 2022-06-09 15:13:32

  [Nowcoder] 银河 差分约束_spfa+超级源点 | Tarjan缩点

  Description 银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 1。现在对于 N 颗我们关注的恒星，有 M 对亮度之间的相对关系已经判明。你的任务就是求出这 N 颗恒星的亮度值总和至少有多大。

  
• 06.09 15:01:01
  发表了文章 2022-06-09 15:01:01

  杀人游戏_lduoj_Tarjan_强联通

  Description 一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？ Input 第一行有两个整数 N,M。 接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x） 。
• 06.09 14:56:09
  发表了文章 2022-06-09 14:56:09

  Early Orders单调栈

  大体思路： 用pos数组来记录每个数出现的最后的位置 然后遍历每一个数组元素，如果当前元素已经被标记过了（已经被使用），那么就跳过这次循环 设遍历数组元素的时候，将这个数组的下标记为 i ,值的大小为 x 当栈里面有元素，并且栈顶的元素大于x，并且栈顶这个数最后出现的位置大于当前这个数最后出现的位置 i ,那么说明栈里面这一数列就不是最优的，就可以将当前的元素x替换掉栈顶元素，先pop(),然后将这个数标记为 0 ，–>未使用 如果当上述条件一直满足的时候，可以一直进行上面的操作 知道不满足题意，然后讲当前这个数放到栈的顶端

  
• 06.08 21:18:18
  发表了文章 2022-06-08 21:18:18

  树上倍增求LCA

  题目描述 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 输入格式 第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。 接下来 N-1N−1 行每行包含两个正整数 x, yx,y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。 接下来 MM 行每行包含两个正整数 a, ba,b，表示询问 aa 结点和 bb 结点的最近公共祖先。

  
• 06.08 20:57:46
  发表了文章 2022-06-08 20:57:46

  如何优雅的写单词_lduoj_kmp

  在深知单词的重要性之后，PushyTao下定决心要好好背单词。为了防止在考试的时候不会写，PushyTao还决定在背单词的时候还要写几遍，但是他太懒了，所以就“发明”出了一种新的方法： 比如说，对于一个长度为n的单词，PushyTao要写m遍。如果这个单词的后半部分和前面的一部分有相同，他就会省略掉相同的不写。比如说长度为3的一个单词aba，PushyTao要写4遍，那么就可以将单词写成ababababa，因为从s[1] ~ s[3]，从s[3] ~ s[5]，从s[5] ~ s[7]，从s[7]~s[9]都是aba，所以这样PushyTao就非常“巧妙的”写完了4遍单词；
• 06.08 20:47:44
  发表了文章 2022-06-08 20:47:44

  C++使用小细节--持续更新

  文章目录 1. fixed 2. C++中结构体内重载运算符 3. reserve() resize() 4. 优先队列重载运算符的三种方式 方式1 友元函数 方式2 常引用 方式3 结构体之外 5. OJ数据制作（文件读写） 读取文件 写入文件

  
• 06.08 20:34:00
  发表了文章 2022-06-08 20:34:00

  牛客IOI周赛23-普及组全题解

  牛客IOI周赛23-普及组全题解 A 小L的作文 B 小L的多项式 C 小L的编辑器 D 小L的数列
• 06.08 20:25:41
  发表了文章 2022-06-08 20:25:41

  拓扑排序讲解+例题

  比如说给定若干个两个元素之间的大小关系，要转换成所有元素的总体大小关系，就可以用拓扑排序来处理 下面给出的例题就是这个样子 关于拓扑排序还有一种用法->判断给定的有向图中是否存在环 下面来说明一下拓扑排序的相关步骤： （默认已经将图存好）首先统计所有点的入度，然后将所有点入度为0的所有点放进队列（根据题目特殊要求也可以使用优先队列） 然后采取像BFS那样的方式，当队列非空的时候，始终取队列头端的一个元素，并将这个元素记录下来之后pop掉，把这个点（比如说是点P）放进用来存储拓扑序列的不定长数组vector中，然后遍历和这个点相连的所有点，并将与点P相连的所有点的入度减少1
• 06.08 19:59:39
  发表了文章 2022-06-08 19:59:39

  Optimization for UltraNet二分最小生成树

  二分边，要把边最小值尽可能最大化，可以对这个值进行二分判断是否可以，在判断的过程中，如果是要连接的次数等于n-1，n为点的数量，点之间如果要构成生成树最少连接的数量为n-1，所以说判断的时候可以通过连接的次数来判断是否可以构成生成树 将最小生成树的那条边进行最小值的最大化之后，就可以再往后遍历的过程中，把要用到的n-1条边进行记录下来，然后进行下一步操作->计算边权 将要用到的边记录下来之后，按照边权的大小对他进行从大到小进行排序，用并查集来维护两个联通块的大小，这个联通块对答案的贡献就是两个联通块的大小size_a * size_b * w

  
• 06.08 19:44:36
  发表了文章 2022-06-08 19:44:36

  Optimal Coin Change（完全背包计数）

  题目描述 In a 10-dollar shop, everything is worthy 10 dollars or less. In order to serve customers more effectively at the cashier, change needs to be provided in the minimum number of coins. In this problem, you are going to provide a given value of the change in different coins.
• 06.08 19:40:37
  发表了文章 2022-06-08 19:40:37

  宵暗的妖怪

  题目描述 露米娅作为宵暗的妖怪，非常喜欢吞噬黑暗。 这天，她来到了一条路上，准备吞噬这条路上的黑暗。 这条道路一共被分为部分，每个部分上的黑暗数量为。 露米娅每次可以任取 连续的 未被吞噬过的 三部分，将其中的黑暗全部吞噬，并获得中间部分的饱食度。 露米娅想知道，自己能获得的饱食度最大值是多少？ 输入描述: 第一行一个正整数，代表道路被分的份数。 第二行有个正整数，代表每一部分黑暗数量。 数据范围： 输出描述: 一个正整数，代表最终饱食度的最大值。
• 06.08 19:25:15
  发表了文章 2022-06-08 19:25:15

  Java课堂笔记（下）

  10.30java课堂笔记 instanceof新特性 抽象类 如何实现多态 重要概念：接口 接口和抽象类的区别 继承与组合 面型对象的程序设计原则 11.13课堂笔记 java中的异常问题: java异常处理机制 Final语句的问题 链式异常 更加精确的抛出异常 反射与注解 11.19 java课堂笔记 OCP原则 内部类 局部内部类 匿名内部类 函数式编程 lambda表达式

  
• 06.08 17:29:49
  发表了文章 2022-06-08 17:29:49

  Java课堂笔记（中）

  10.22java课堂笔记 substr截取字符串左闭右开 API format方法，可以创建一个格式化的字符串 字符串转换为整型 字符串转换为浮点型 数值转换为字符串 字符串与字符、字符数组 字符串与字节数组 StringBuffer类 基本类型数据的类包装器 正则表达式与模式匹配 模式匹配： 限定字符模式; 模式的逻辑或 模式匹配
• 06.08 17:11:33
  发表了文章 2022-06-08 17:11:33

  Java课堂笔记（上）

  10.13Java课堂笔记 数组 二维数组 匿名数组 增强for循环 字符串 字符串中常用的API
• 06.08 16:43:03
  发表了文章 2022-06-08 16:43:03

  养猪_lduoj_dp

  Description 你有一个猪圈，有N头猪，每天你最多可以杀一头猪卖钱，获益就是猪的体重。但是每过一天每头猪的体重都会下降P[i]（当然，如果猪体重≤0了，自然获利为0），问K天内你的最大获利。 Input 第一行两个数N,K； 第二行N个数，表示猪的初始重量A[i]； 第三行N个数表示P[i]。 Output 一行一个数表示最大获利。
• 06.08 16:37:39
  发表了文章 2022-06-08 16:37:39

  邮递员送信_lduoj_最短路

  邮递员送信 Description 有一个邮递员要送东西，邮局在结点1。他总共要送N−1样东西，其目的地分别是2−N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N−1样东西并且最终回到邮局最少需要多少时间。 Input 输入文件第一行包括一个正整数N和M； 接下来M行，每行三个正整数U,V,W，表示该条道路为从U到V的，且通过这条道路需要W的时间。满足1 <= U,V、N <= 1000 , 1≤W≤10000，输入保证任意两点都能互相到达。 Output 输出仅一行，包含一个整数，为最少需要的时间。
• 06.08 16:32:38
  发表了文章 2022-06-08 16:32:38

  求和_数学

  求和 Description Input 输入两个整数n,m。 Output 输出占两行，第一行一个整数X，第二行整数Y，表示S＝X/Y，且X,Y互质。 Samples Input Copy 1 2 Output 1 2 Hint m>1，n>0； 50%的数据满足n≤50； 100%的数据满足n+m≤500。 Source 信息学模拟-2 可以看出数据范围并不是很大 但是如果是求阶乘的话，肯定是要用C++大数来模拟的 对式子进行通分可以得到：

  
• 06.08 16:15:24
  发表了文章 2022-06-08 16:15:24

  黑白棋_lduoj_dfs深搜

  Description Lagno是一种二人智力游戏。游戏设有一个黑方和一个白方。游戏桌面是正方形的，包含8行8列。 如果黑方玩家走出这样一步棋：将一枚黑子放在任一空格上，而在这个空格的八个方向（上、下、左、右和4个对角线方向）的至少一个方向上有一排白子被夹在这枚新下的黑子和其他黑子之间，任何方向，在新黑子和原来黑子之间的所有白子都要变成黑子。为这个游戏设计一个程序，计算一步棋中黑方能转变的白子数量的最大值。 Input 输入文件lango.in共8行，每行8个字符；“.”代表一个空格；“B”代表黑子，“W”代表白子
• 06.07 19:22:55
  发表了文章 2022-06-07 19:22:55

  lduoj_2021年初寒假训练第42场（下）

  目录 2021年初寒假训练第41场 A. 复制-粘贴 B. 足球联赛 C. 捕食关系 D. 幻方 E. 求和 F. 猜歌名

  
• 06.07 19:15:47
  发表了文章 2022-06-07 19:15:47

  lduoj_2021年初寒假训练第41场（上）

  2021年初寒假训练第41场 A. 复制-粘贴 B. 足球联赛 C. 捕食关系 D. 幻方 E. 求和 F. 猜歌名
• 06.07 19:06:05
  发表了文章 2022-06-07 19:06:05

  境界的彼方_lduoj_bfs宽搜

  Description wyy是一个著名动画《境界的彼方》的男主，此时他非常的慌张，因为女主栗山未来进入了境界的彼方内部，并且花费了大量的血量去拯救wyy，wyy此时也进入了境界的彼方，他妈给了他一张地图去寻找境界的彼方的核心去拯救女主，现给你一张n×n的地图，以及男主的位置，问男主要拐弯几次才会到达境界的彼方内部（境界的彼方的位置为(n,n)） 不过你以为这就是道搜索题？还得加条件：此时女主血条狂掉，你必须判断此时wyy是否可以走到终点且女主的血条不会掉光，如果掉光了那么输出"Die",如果地图无法到达境界的彼方就输出"No",如果到得了终点且女主血条活着输出res代表男主此时要拐弯几次
• 06.07 18:30:33
  发表了文章 2022-06-07 18:30:33

  3045 Lcm与Gcd构造

  已知： gcd(a,b) = n lcm(a,b) = m 求min(a,b)是多少 通过gcd的了解我们可以知道，两个数a == k1 * n以及b == k2 * n并且gcd(k1,k2) == 1 ab == n * m m == a * b/n ab == k1 * k2 * n * n 于是可以得到 m == k1 * k2 * n 将n除到左边，可以得出m/n == k1 * k2 于是k1 和 k2 都是 m / n的因子 这样就可以以根号的复杂度找出这两个因子，并判断k1 和 k2 是否是互质的 a + b == (k1 + k2 ) * n 所以说代码：
• 06.07 18:23:04
  发表了文章 2022-06-07 18:23:04

  对拍程序

  其中data.cpp是用来生成数据的，数据保存在data.txt ac.cpp是ac的源代码 wrong.cpp是错误的代码，提前要进行编译 ac的代码结果放在ac.txt wrong的代码放在wrong.txt 如果比较有差异就会停止运行 以下是对拍的源代码

  
• 06.07 18:17:10
  发表了文章 2022-06-07 18:17:10

  【LDUOJ】寒假专题训练——贪心EG题解

  题意： 给出若干个零件，每个零件都有两个属性，长度L和重量W，要对零件进行分组，每组中每个零件的长度 L 和重量 W 都能排成一个长度和重量都不下降（若i<j，则Li≤Lj，Wi ≤ Wj）的序列,求解最少的分组 长度和重量均不超过10000 给n个物品进行分组，对于同一组中 这一组里的零件可以排序成单调不减的情况下 比如： 重量 1 2 3 4 对应的长度是 123 123 456 678

  
• 06.07 18:03:09
  发表了文章 2022-06-07 18:03:09

  edu99 div.2 Sequence and Swaps优雅的暴力

  首先找到不满足非递减的位置的元素，然后考虑将这个数换掉，但是问题是换掉这个数要满足a[i] > x;这样一来，就需要找到找到这样一个满足条件的位置，并记录在pos中，然后从满足条件的 pos往后到 i - 1的部分进行交换，每交换一次就讲记录答案的ans加一，然后判断是不是满足非递减的情况，如果满足的时候，输出ans,不满足的时候直接输出 -1 在中途的时候可以优化一下下，如果说交换了一波时候还没有满足a[i] >= a[i-1];就直接记录下，最后输出 -1

  
• 06.07 17:56:23
  发表了文章 2022-06-07 17:56:23

  求逆序对

  给出若干个数，每次可以交换相邻的两个，如果要将这些数变成非递减的数，需要操作多少次？ 很容易就可以想到暴力的解决方式 如果是数据范围比较小的时候，可以直接进行暴力求解 如果是数据范围比较大的时候，这时候需要用树状数组求解一下 附上暴力的代码
• 06.07 17:53:51
  发表了文章 2022-06-07 17:53:51

  Nearest Opposite Parity最短路径+超级源点

  time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a consisting of n integers. In one move, you can jump from the position i to the position i−ai (if 1≤i−ai) or to the position i+ai (if i+ai≤n).

  
• 06.07 17:48:32
  发表了文章 2022-06-07 17:48:32

  Queen on Grid_dp

  思想很单纯-> dp Code: 代码解释： dp加上之后，注意进行取模 然后再更新这一个节点的计数（ans）

  
• 06.07 17:40:15
  发表了文章 2022-06-07 17:40:15

  Educational Codeforces Round 98 (Rated for Div. 2)B-Toy Blocks

  You are asked to watch your nephew who likes to play with toy blocks in a strange way. He has n boxes and the i-th box has ai blocks. His game consists of two steps: he chooses an arbitrary box i; he tries to move all blocks from the i-th box to other boxes.
• 06.07 17:21:50
  发表了文章 2022-06-07 17:21:50

  线段树水题

  Problem Description 很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
• 06.07 17:12:39
  发表了文章 2022-06-07 17:12:39

  Dropping Balls—满二叉树

  题意： 给出一棵满二叉树，编号从上往下、从左向右进行编号，然后每次询问给出一个树的深度，以及当前查询的是第几个球，问这个球的编号是多少 一个球来的时候能来左边就先来左边，不能的话才去右面 对于满二叉树还有一个性质，一个节点的左子节点的编号是 2 * x,右节点是 2 * x + 1 然后就是进行模拟就行了 如果说一个节点被访问了 t 次，如果t % 2 == 1的话，那么，会有（t + 1） / 2的在左面， t / 2的在右面

  
• 06.07 15:40:45
  发表了文章 2022-06-07 15:40:45

  UPC组队训练-补题记录（下）

  Eggfruit Cake 时间限制: 1 Sec 内存限制: 128 MB 题目描述 Today is Jaime’s birthday and, to celebrate, his friends ordered a cake decorated with eggfruits and persimmons. When the cake arrived, to their surprise, they noticed that the bakery didn’t use equal amounts of eggfruits and persimmons,
• 06.07 15:31:45
  发表了文章 2022-06-07 15:31:45

  UPC组队训练-补题记录（上）

  Game on a Tree 时间限制: 1 Sec 内存限制: 1024 MB 题目描述 Alice and Bob play a game on a tree. Initially, all nodes are white. Alice is the first to move. She chooses any node and put a chip on it. The node becomes black. After that players take turns.

  
• 06.07 15:07:21
  发表了文章 2022-06-07 15:07:21

  并查集计数——总结与例题

  比较基础的知识可以看这位大佬的博客 or 这篇博客 并查集主要有初始化、union、计数等
• 06.07 15:01:01
  发表了文章 2022-06-07 15:01:01

  数学题-零点式转换为一般式Know your Aliens

  题目描述 Our world has been invaded by shapeshifting aliens that kidnap people and steal their identities.You are an inspector from a task force dedicated to detect and capture them. As such, you were given special tools to detect aliens and differentiate them from real humans.

  

2022年05月

• 05.31 18:30:54
  发表了文章 2022-05-31 18:30:54

  数据结构知识整理

  标题2020 - 1024 == 996 你品，你细品 堆、栈、队列 大根堆小根堆 大根堆 堆顶的元素是最大的，越往下越小 小根堆 堆顶的元素是最小的，越往下越大

  
• 05.31 18:23:30
  发表了文章 2022-05-31 18:23:30

  杜教筛BM（找规律）

  杜教筛BM（找规律）
• 05.31 18:14:48
  发表了文章 2022-05-31 18:14:48

  Just Arrange the Icons——优雅的暴力

  BerPhone X is almost ready for release with n applications being preinstalled on the phone. A category of an application characterizes a genre or a theme of this application (like “game”, “business”, or “education”). The categories are given as integers between 1 and n, inclusive;
• 05.31 18:08:11
  发表了文章 2022-05-31 18:08:11

  Tree with Maximum Cost---CF1092F 树上DP

  You are given a tree consisting exactly of n vertices. Tree is a connected undirected graph with n−1 edges. Each vertex v of this tree has a value av assigned to it. Let dist(x,y) be the distance between the vertices x and y.

  
• 05.31 17:58:28
  发表了文章 2022-05-31 17:58:28

  Lexicography——CF1267L构造题

  Lucy likes letters. She studied the definition of the lexicographical order at school and plays with it. At first, she tried to construct the lexicographically smallest word out of given letters. It was so easy! Then she tried to build multiple words and minimize one of them. This was much harder!
• 05.31 17:51:05
  发表了文章 2022-05-31 17:51:05

  离散化处理

  什么是离散化呢？比如有这么一道题： 题目描述 小鱼有 n 名优秀的粉丝。 粉丝们得知小鱼将会在一条直线上出现，打算去膜他。为了方便，粉丝们在这条直线上建立数轴。 第 i 名粉丝有一个侦查区间[li,ri] 。如果小鱼在 j(li≤j≤ri) 处出现，这名粉丝将立刻发现并膜他。 小鱼希望膜他的人越多越好，但是他不能分身，因此只能选择一个位置出现。 小鱼想知道自己最多能被多少个人膜。

  
• 05.31 17:35:47
  发表了文章 2022-05-31 17:35:47

  卡常优化

  为卡常而生的三个函数 封装的快读
• 05.31 17:02:32
  发表了文章 2022-05-31 17:02:32

  小思维题-蚂蚁感冒——蓝桥杯

  Description 长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。 当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。 这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。 请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。
• 05.31 16:53:25
  发表了文章 2022-05-31 16:53:25

  Elven Postman 二叉树遍历问题

  Description Elves are very peculiar creatures. As we all know, they can live for a very long time and their magical prowess are not something to be taken lightly. Also, they live on trees. However, there is something about them you may not know. Although delivering stuffs through magical

  
• 05.31 16:49:00
  发表了文章 2022-05-31 16:49:00

  拓扑排序-Kitchen Plates

  J. Kitchen Plates time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output

  
• 05.31 16:37:02
  发表了文章 2022-05-31 16:37:02

  2021中石油组队训练第八场记录（下）

  题目描述 Alice and Bob decide to share a chocolate bar, which is an n by m rectangular grid of chocolate cells. They decide that Alice should get a < n·m pieces and that Bob should get b = n·m − a pieces. To split the chocolate bar, they repeatedly take a single piece of chocolate and break it either

  
• 05.31 16:25:29
  发表了文章 2022-05-31 16:25:29

  2020中石油组队训练第八场记录（上）

  问题 D: Eeny Meeny 时间限制: 2 Sec 内存限制: 128 MB 题目描述 “Eeny meeny miny moe” is a well-known nursery rhyme in English, used (among other things) by kids to “randomly” select members of a team. It exists in many variations, one of which goes like this: Eeny, meeny, miny, moe, Catch a tiger by the toe.

  
• 05.31 16:09:10
  发表了文章 2022-05-31 16:09:10

  The Famous ICPC Team Again

  题目描述 When Mr. B, Mr. G and Mr. M were preparing for the 2012 ACM-ICPC World Final Contest, Mr. B had collected a large set of contest problems for their daily training. When they decided to take training, Mr. B would choose one of them from the problem set.
• 05.31 16:06:04
  发表了文章 2022-05-31 16:06:04

  Contest Print Server组队第四场J

  问题 J:Contest Print Server 时间限制: 1 Sec 内存限制: 128 MB 题目描述 In ACM/ICPC on-site contests ,3 students share 1 computer,so you can print your source code any time. Here you need to write a contest print server to handle all the requests.