XJTU-Diamond-Sea昆明站前集训-第七周
The 2021 ICPC Asia Nanjing Regional Contest
E. Paimon Segment Tree
tyy很快意识到额外维护一个前缀和即可求解,则现在只需要处理一个平方和即可。
但是看到需要维护平方和,naive的我以为线段树无法解决,再加上看到5e4的数据量,所以训练的时候想了个分块的做法。
可惜需要维护的变量太多,导致一直没有调出来,下来补题却最后一直在第23个点TLE
无奈查看题解,居然真的是线段树…其实使用矩阵乘法来维护,继而就可利用懒标记来优化了…
注意矩阵乘法的常数极大,又观察得知,矩阵中仅有6个参数是变量,所以可以极大的优化乘法运算的复杂度。
最后在cf上面使用64位测评机,刚好卡过去…
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293 ...
XJTU#Diamond_Sea昆明站前集训_第五周
Diamond_Sea#Day5
E. Company
容易想到使用st表来维护区间的lca(注意实现的过程中,位运算的优先级)
我们发现如果是改变一个点就能使得lca的深度变大的话,那这个点去掉之后,剩余点的lca必须是原lca的后代节点废话
相当于,剩下的点在原lca的最多两个不同子节点的子树中,且其中有一个子树只含有一个在当前区间中的点,我们要删除的就是这个点。
这里采用了分治的方法,具体可参见实现过程
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132#in ...
XJTU#Diamond_Sea昆明站前集训_第四周
D. Chemical table
最开始想了一个比较复杂的解法,调整了很久依然WA5。下来看题解才发现这个题目其实十分简单,把行和列看为点,然后输出联通块的数量减一即可。
证明如下:
首先,每一个二维平面上的点(r,c)(r,c)(r,c)都可以看成是点r和点c之间连的一条边。显然这是一个二分图。题意要求我们覆盖满所有的二维平面上的点,就相当于要让每一行和每一列之间都要互相连通。由于是二分图,所以我们要连接的点之间的边一定是奇数条。易知,对于任意一个连通块,其内部的行点和列点一定连通。
这里还是贴一下我的wa代码吧
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768// WA#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int>pii;ty ...
XJTU#Diamond_Sea昆明站前集训_第三周
D. Sonya and Matrix
超级恶心的一个构造题…在训练的时候被折磨了两个小时,完全想偏了
首先要明确的是,只要知道了数字零的位置和矩形的长宽后,可以O(n)O(n)O(n)判断是否合法。显然我们可以暴力在sqrt(n)sqrt(n)sqrt(n)的时间内枚举长和宽,然后可以发现,如果有一个数字出现的次数不是4∗i4*i4∗i,那么该数字一定是数字零的行或列坐标。再通过序列中最大数的值,即可求出行加宽的值(简单画个图就能看出来了,当然最直接的方法还是像题解那样老老实实列方程算)
剩下的难点就是计算每个数字的合法出现次数了,这里把矩形按照边分成了四段和四个顶点。每段单独考虑,这样会简单一点。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include<bits/stdc++.h>using name ...
网络流24题
餐巾计划问题
将每天的早晚分开,分成两个点,然后建图
如果要让最大流等于每天用到的餐巾数量之和,那么一定要满足每天都要向汇点连一条容量为当天餐巾数量的边。
如何体现餐巾的重复利用呢?答案是从源点向每天晚上连容量为当天餐巾数量的边。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103#include<bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN=4e3+5;const int MAXM=2e4+5;const int INF=1e9;int N;int cp,dm,cf,dn,cs,lim[MAXN];int head[MAXN], c ...
LCT小记
Intro
首先要明确一点,LCT的应用场合是什么?
回想以前的树上操作,树的拓扑结构都是不发生变化的,然后一般利用树链剖分结合线段树实现logn或logn^2的单次操作。
而LCT其实也是一个广义的“树链剖分”,它在树的拓扑结构发生变化时(例如要求能满足断开边,再连接新边的操作),仍然能满足logn或logn^2的单次操作复杂度
实链剖分
对于一个点连向它所有儿子的边 , 我们自己选择一条边进行剖分,我们称被选择的边为实边,其他边则为虚边(当然,有可能所有儿子都是虚边)。
对于实边,我们称它所连接的儿子为实儿子。
对于一条由实边组成的链,我们同样称之为实链。
辅助树
在一条实链中的所有点,使用同一个splay维护。这个splay被称为辅助树。每棵辅助树维护的是一棵树,一些辅助树构成了LCT,其维护的是整个森林。
辅助树由多棵 Splay 组成,每棵 Splay 维护原树中的一条路径,且中序遍历这棵 Splay 得到的点序列,从前到后对应原树“从上到下”的一条路径。
原树每个节点与辅助树的 Splay 节点一一对应。
每棵 Splay 的根节点的父亲节点本应是空,但在 LC ...
线段树的进阶操作
区间最值
区间最值操作指,将区间[l,r][l,r][l,r]的数全部对x取max或min,例如ai=max(ai,x)a_i=max(a_i,x)ai=max(ai,x)
HDU5306 Gorgeous Sequence
这里比较玄学的是,维护一个最大值和次大值即可,这样的复杂度就能降为logn。这里可以用势能分析法得到证明。
这里使用到的势能分析法在splay的复杂度证明中也用到了,但是没有系统学习,过段时间来填坑。
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107#include <algorithm>#include <cctype>#include <cstdio& ...
Splay
intro
Splay 是一种二叉查找树,它通过不断将某个节点旋转到根节点,使得整棵树仍然满足二叉查找树的性质,并且保持平衡而不至于退化为链
实现过程
主要过程参照传送门即可,讲得十分详细,这里就不再赘述
说一下删除操作吧,这部分当时看了比较长的时间才看明白
1234567891011121314151617181920212223242526272829303132void del(int k) { rk(k); if (cnt[rt] > 1) { cnt[rt]--; maintain(rt); return; } if (!ch[rt][0] && !ch[rt][1]) { clear(rt); rt = 0; return; } if (!ch[rt][0]) { int cur = rt; rt = ch[rt][1]; fa[rt] = 0; clear(cur); return; } if ( ...
一点点回顾和随想——2021.12.14随笔
现在
现在是12.14凌晨1点40,晚上八点的时候睡了一觉,刚才醒了就一直睡不着,想想还是写点东西吧。
一
这里聊一聊我目前人生中最喜欢的一部电影吧:《少年时代》。
这部电影花了12年拍摄,讲述了一个男孩从6岁到18岁的成长的故事。
我记得是在高二一个周六的晚上,一个人躺在沙发上看电视,无意间刷到了这部电影,然后就一口气看到了结束。
虽然很多剧情都记不太清了,但是我现在依然能清晰地回想起,在电影结束后泪流满面的我。
其实我的人生和男主的故事并没有太多相似之处,所以这份感动并没有来自所谓的“共情”,而是来自于目睹了一个男孩的成长经历后,感到无比的怅然。这里的伤感是因为我忽然意识到,其实我也目睹过了另一个男孩的成长——即我自己。
小时候,总觉得自己的人生有无限的可能性,总觉得只要自己肯努力,就一定会做成任何事情。可随着年龄的增长,我发现这种可能性在逐渐的消磨,对自己的怀疑与否定也越来越深。
当我回顾我的前几年,这种感觉愈发的强烈。
可能这里还有一个比较特殊的因素吧,那就是我现在的观念以及处事态度,是基于对更早的岁月的激烈否定以及兼并中形成的。而在那段更早的岁月里,却是我人生中对未来最为 ...
2021.11.1-2021.11.7_training
XXII Open Cup. Grand Prix of Korea
C.Equivalent Pipelines
首先可以看到,树的数量很多,所以只能给每个树一个hash值,从而通过hash是否相同判断是否同类
这里可以首先意识到,对于两棵树而言,先把所有边断开,从大到小开始依次加边,一次操作只加相同长度的边,如果能保证每次连起来的若干个新的连通分量内部的点都是一样的,那么就符合要求。
通过归纳法可以容易得出:对于所有长度为w的边,我们记录这个长度w,还有连接发生前每个连通分量中编号最小的点,以及通过这条边连成的新连通分量中编号最小的点,形成一个三元组;如果对于两棵树而言,它们的三元组的集合完全一样,则一定满足上述条件。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include<bits/stdc ...