Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

2018JLWC(?)难题选讲

2018JLWC不得了

怎么不得了呢
我也不知道
各位爷都呢么强
大概是我没有给你们拉低平均分吧(跑

Day 5——树专题

这个专题由于我也没有系统学过
你们学的时候我在成都
成都还没有讲
所以我那天就GG了
这个专题有两道题我讲的

首先是B题
题目链接

传送门

一句话题意

一棵自认为萌萌哒其实很傻逼的树
支持换根操作(这个操作尽显傻逼本性 和询问子树大小操作

想法


直接告诉你?不存在的 接着想

继续想

好了不闹了
这个题可以简单说成子树问题
当然楼下的爷有高级算法
我大概就是个讨论的方法
怎么讨论呢
大概思路就是一开始它的根是1
那么我们就预处理出来以1为根的时候
每个节点子树大小是多少
然后接下来如果涉及换根
我们就分析一下对于换根之后的操作是什么样子的
然后正常处理就行了
大概思路是这样的
预处理每个点以 1 为根子树大小。
设当前的根为 x 点,询问 y 点子树大小。
如果 x 点在 y 点以 1 为根的子树之外,那么以 x 为根 y 的子树与 以 1 为根 y 的子树相同。
否则,如果 y 是此时的根,即 x 与 y 重合,那么子树即为整棵树。
否则 x 在 y 的子树内且不为 y,此时 y 是 x 的祖先。
设 x 到 y 路径上除去 y 的最后一个点为 z,z 是 y 的一个儿子。 那么以 x 为根 y 的子树为整棵树去掉以 1 为根 z 的子树。
可以通过一次 dfs 预处理出每个点以 1 为根子树大小。 判断 x 是否在 y 的以 1 为根的子树内部,可以判断 x 是否在 y 子 树对应的 dfs 序区间中。
z 点可以通过倍增求出。 时间复杂度 O(nlogn + Qlogn)
接下来听我分析 以sample为例
我太懒了 懒得做图放上来
分析时间

相信大家大概经过讲解理解的差不多了
想听思路的你们都太强了
而且你们主要是想听代码23333
接下来代码送上
我会先把每个步骤拆解开讲解
之后给出完整代码
下面所有题都是这样
代码这么丑 你们要是ctrl+c马上就会暴露

代码+讲解

Step1.建图
大家这么强不用前向星也要用vector嘛

Step2.dfs
在这个之前
讲一下倍增LCA
(也不是讲 就是放个代码 毕竟用到倍增了

接下来我们可以开始dfs了
这个dfs的目的就是我们要get到每个节点的深度 直接父节点
以及我们上文提到的dfs序
正常是两次dfs的 不过为了满足倍增这个一贯的规律
就一次好了

相对来讲 这个dfs的过程是比较粗略的
详细的我刚才提到的dfs两次 看我博客树链剖分
在这里时间不够不讲解
树链剖分传送门
Step3.找到我们刚才说的那个z节点
这个没什么好讲得了
大家思考一下怎么求

当然是非常简单了

Step4.query
这个严格按照我刚才的来就行了
不过多进行赘述

odk

完整代码之前


容我抱怨一下数组开小的锅!!!

下面是完整代码

好的这是B题

然后是C题
题目链接

传送门

想说的话

这个题fzoj上面的排版真的没法看
于是乎我找了一切的办法
get到了pdf的原图

这样看起来就好多了
然后看一下传说中的Solution

这个只好和大家讨论一下了
因为我现在也没有题解
看了Solution觉得特别有道理
但是我不会写啊qwq

Day6——图论专题

这里面我有一道题需要讲

C题
题目链接

传送门

一句话题意

最多一条双向边 一堆有向边 问你最多经过多少个点

题解

首先将图中的强联通分量用 tarjan 算法缩点。
缩点后的图是一张拓扑图。
定义缩点后一条路径的权值是这条路径上所有强联通分量的点数之和。
最终的路径在缩点后的图中一定可以表示成如下形式:
path(bel[1],i)− > path(j,bel[1])
其中 path(x,y) 表示在缩点后的图中从 x 到 y 的权值最大的路径, 且缩点后的图中存在一条从 j 到 i 的边。
bel[1] 表示 1 所在的强联通分量。
用拓扑图上的 dp 求出 f[i] 表示缩点后的图中从 i 到 bel[1] 的权值 最大的路径。
将缩点后图中所有边反转,dp 求出 g[i] 表示从 i 到 bel[1] 的权值 最大的路径。
g[i] 即为反转边之前,从 bel[1] 到 i 的权值最大的路径。
枚举缩点后图中所有边 u− > v。
用 g[v] + f[u]−size[1] 更新答案。 size[1] 为 1 点所在强联通分量大小。


场面一定是十分尴尬的
毕竟我觉得各位爷听不太懂
那就让我带你们分析一下吧

分析完事之后 我们来看代码
这个代码我实在太懒了
懒得写注释了
直接讲解吧

代码+讲解

这个题我还是把它拆分成为很多步
Step1.建边
没有代码 懒
值得注意的一点是这个题我们需要建两个图
Step2.tarjan缩点
我们把所有的强连通分量看成一个点
我记得当时咱们学tarjan的时候没讲过
所以我讲一下下

这个坎过去了后面就简单了
Step3.直接跑
我们正向跑一遍 反向跑一遍
拿到最大的权值
之后枚举

代码

Day7——叫不上来什么专题 数据结构(雾

这个专题我有一道题需要讲

C题 异或区间
题目链接

传送门

想说的话(吐槽

这个题一开始看到50秒的时间限制
我以为是有50个测试点把我吓一跳
结果后来说单个测试点50秒?!
你是在搞笑么
早说这个我当时就5分钟敲一个前缀和然后睡觉不好么!!!
这个题我的目标是1s
这才是正解
那个都特么是哄你玩的

题解

前缀和傻逼做法我不讲了
我讲正解
TRIE树
有没有不会的?!
有的话就简单说说

好了接下来讲正解
Step1.考虑到异或运算建立在二进制基础上面 所以我们进制转换

Step2.TRIE树



两步解题法2333
结束

完整代码

值得注意的是
由于涉及到多组数据
要加上一个初始化的操作
我加在了结构体里面
当然这个添加的位置是任意的了

Day8——动态规划专题

这个专题跟USACO很像
可以有煞笔题
也可以到国家集训队里面出 一样干人

这个专题我讲三道题

第一题——混合背包

与其说这是一道题 不如说这是一个知识点
混合背包跟普通背包一样
只不过这个麻烦一点
这个只有一个技巧——拆包
拆包是什么呢 我们把一个物品的不同数量拆成多个物品
这样每个作为一个背包 就可以进行背包操作了
正常挨个拆开就行了
但是这道题卡空间 怎么办呢
鬼谷子的钱袋大家做过么
没做过啊 那就没做过吧
我们考虑二进制拆包
1,2,4,8,16.。。
这样确保我们可以随机选取k个背包
使得能够选到任意数量的该物品

代码

第二题——回文串
题目链接

传送门
这个题给我们送来了两种操作:插入 删除
这个弯我们绕一下
就是当我们发现不对的时候 这两种做法任选其一都能完成矫正
这就是说对于每个不匹配的位置 我们有两种选择让它匹配
这个题是不是就变得弱爆了?
利用回文串的特性 把这个串反过来
这样的话我们的任务变成了面对着两个可爱的字符串 让他们变成一毛一样的
这可真是容易啊

代码

第三题——最长公共子序列

这个题要求我们用nlogn算法求出来
我们都会n^2算法
这个算法其实思维量蛮大的
两个思路——树状数组和转化
转化思路
首先看到这道题很容易一下就想到dp(n^2),但是看看数据范围,放弃dp,再看一看它题目给出的,这两串数都是1到n的全排列,说白了就上下两个串中的元素都是相同的,只有顺序不同而已,那么知道这个,我们又怎么来解决这道题呢?
我们可以以第一个串为标准,用第二个串来匹配第一个串,看能匹配多少,所以,其实第一个串的每个数字其实影响不大,只有知道它对应了第二串的哪个数字就好了,那么我们为什么不把他给的串重新定义一下?
比如他的样例:3 2 1 4 5 我们把他变成 1 2 3 4 5 用一个数组记录一下每个数字变成了什么,相当于离散化了一下3-1;2-2;1-3;4-4;5-5;
现在我们的第二串1 2 3 4 5 按我们离散化的表示:3 2 1 4 5
可能有些人已经懂了,我们把第一个串离散化后的数组是满足上升,反过来,满足上升的也就是满足原串的排列顺序的
好了 ,现在的问题就变成了求一个最长不下降序列!好了!解决完成!
树状数组做法我也不太明白 就是胡乱地写了一发

2 Comments

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏