杂题乱做2

退役前给自己看的,删了一些东西放出来了,有兴趣可以看看

Conquer the World

题意:树上匹配,权是距离

模拟费用流。

Gem Island

题意:一开始每个人都有1个绿宝石,每天选一个存在的绿宝石并分裂,求拥有前r大的人绿宝石个数期望

考虑任意一种方案被得到的概率:考虑方案数,为分配序列的排列,乘上\prod a_i。这是因为每一组都有很多个,可以任选一个。发现方案数和具体方案无关,那么答案就是总和/总方案数。

考虑DP,考虑分层DP,每次给上一次的子集+1。可以发现这样可以得到想要的答案。

Single Cut of Failure

题意:方框内划线,切割所有线。

可以发现答案的上届是2。双指针可以判断是否可以是1

Triangles

题意:数三角

考虑在三角一个顶点统计答案,可以发现,与另一条边有关。另一条边有一个控制范围,BIT维护。

Black and White

题意:路径贡献为左边的两种颜色差,求贡献为某个数的路径有多少

首先要注意,题意中的左边,指的是所有左边,不是挨着的点。。。。。。。。。。。。。。。。。。。。。。。。。。。那么钦定路径长度是偶数,如果不是,枚举最后一步改为偶数。

考虑两步为一个周期统计。发现只有走出拐形才有贡献。钦定两种一共走了p次,那么可以计算出需要各走多少次。之后排列一下就可以了。

关于走多少次怎么算:钦定各走了i,j次,则贡献为:\frac{i+j+1}{2}-j

Dirichlet k-th root

f^k \equiv g \pmod p,已知g,pf

迪利克雷卷积也可以用费马小定理。

Bags of Candies

题意:[1,n]的整数,如果gcd不为1就可以放在一组,一组最多两个,求最少分成多少组

考虑大于n/2的素数,显然只能一组。1只能一组。结论:除了它们,都能配对。

证明:考虑按每个数的最大质因子划分。最大质因子相同的显然可以匹配。如果有奇数个,匹配则不完全,那么把2x这个数单独留下不匹配,可以发现剩下的都有2,还能匹配。

那么只需求区间素数个数。min25即可。

Contamination

题意:给定不相交圆,钦定y坐标范围,给定两个点,求是否可以不碰圆走到。

因为不交,如果被阻拦,一定是一个圆从下边界顶到了上边界。扫描线即可

Lighthouses

题意:凸包,给定一些对角线,求一条不自交最长路。

倍长凸包,之后发现可以区间DP。

Sum of Palindromes

题意:把一个数分解为若干回文数和,不超过25个

考虑构建一个回文串:只需取原数字一半,减1,再倍长。那么这样会让原数变短一半。

leq or geq

题意:交互,给定10000个大小为10的栈,只知道栈顶,自己选一个数,题目给出一个符号,把和这个符号构成关系的都弹掉。50次弹空。

考虑势能:给每个数选一个势能,找一个数,使得无论是什么符号,势能都减少足够的值。

题解给出的做法是,令权值为3^s,找出一个数使得小于,大于它的都有一定数量,则弹后一定有一半除以3,势能下降到2/3。

Stairways

题意:一堆人走两个楼梯,经典问题

考虑DP,那么发现需要维护:区间+v,区间+i,区间min。分块+凸包维护。

注意斜率不要写错。。。。

The Halfwitters

题意:三种操作,各有代价:交换序列相邻位置,反转序列,随机打乱。求把序列排成顺序的期望次数。

考虑直接求,交换次数就是逆序对(从1,2,3开始换),可以做。

一个排列两种决策:直接换,随机打乱。

考虑求随机的期望,那么把每种排列的代价排序,枚举断点,那么x=\sum pre+sufx,解方程解出来最优的

To argue, or not to argue

题意:一张图,有些位置可以放,一对人不能放在一起,求方案数

考虑容斥,变成至少i对人放在一起,插头Dp即可

无意识的石子堆 加强版

题意:nm的矩阵,放2n个石子,每行每列最多2个,方案数

发现每一行都要放恰好2个。那么考虑枚举放了2个的列有多少。之后考虑方案数:

二分图,左边度数是2,右边一些是1一些是2

首先考虑瞎连边,发现有可能两个点之间连了两条边,是错误的。所以容斥。连边的时候假设两条边有序,之后除掉,就可以做了。

小 Q 的序列

题意:序列权值为\prod (a_i+i),对于输入序列所有子序列求权值和。

考虑一个DP:f_{i,j}=f_{i-1,j-1}(A_i+j)+f_{i-1,j}

考虑优化:这个DP有些复杂,用i-j代替jf_{i,j}=f_{i-1,j}(A_i+i-j)+f_{i-1,j-1}

那么直接考虑组合含义:对于一个元素有三种选择:不选,贡献为A_i+i。放进原来的盒子里,或放进新的盒子里,不选的可以分治NTT,剩下的部分考虑DP:g_{i,j}=-g_{i-1,j}j+g_{i-1,j-1}把转移乘-1,组合意义变成了贡献是(-1)^m

那么考虑生成函数:固定j,生成函数是有标号随便放,除以盒子排列。答案要对所有g求和,推一下发现是e^{1-e^x}

Lucky Tickets

题意略

重新注意一下比较系数求幂的方法。

其实有一个更简单的推倒方法:

g=f^k

g'=kf'f^{k-1}

g'f=kf'g

比较系数即可

Many Easy Problems

题意:一个点集会被能包含它的,最小的联通块覆盖。求每个大小的点集,覆盖所有这个大小的点集的联通块大小和。

考虑算一个点的贡献:如果贡献,那么在不同子树中出现。就可以做了

一道数学题 加强版

考虑f的递推式:f_{i}=2f_{i-1}+i^k-(i-1)^k,令g_{i}=2g_{i-1}-i^k+(i-1)^k,则f_i+g_i=2(f_{i-1}+g_{i-1})

g是一个K-1次多项式(原因待填

现在的问题是不知道g_0是多少。那么看作未知数,直接递推出g_1,...,g_n,再插值插出g_0即可。

原因Update:

看来需要补习数学知识啊。。

实际上,f_i=2f_{i-1}+i^k-(i-1)^k,是一个k-1次多项式。只不过问题是,因为它有f_1=1的限制,推出来的式子不满足这个限制,所以不可以直接求解。

那么下面来证明这样的式子是k-1次多项式:

实际上非常的简单。

考虑x^k - (x-1)^k。容易知道,这个式子是一个k-1次多项式。

考虑f的形状。它一定形如若干k-1次多项式之和,其中i0,n之间的整数。

那么它就是k-1次多项式了。

至于怎么知道上面的式子因为f_1=1不满足了?这就又是一个坑了。目前并不会数学证明,只能考虑用等同于g的方法验证。

不过虽然不知道如何证明,却可以记一个技巧:看到这个式子很简单,那么大概率有天坑

Beautiful Bracket Sequence (hard version)

题意:括号序列,一些位置可以自己填,定义贡献为删掉一些后最长匹配,求所有方案之和

题目要求的是删掉一些后的括号匹配,那么直接从左到右,从右到左扫就好了。枚举中点,令两边恰好有某个个数的括号即可。

记一个Trick:\binom nm m=\binom{n-1}{m-1}n

LCC

题意:一个点可以往两边走。定义答案为最小的相遇时间,求期望

之前做过。考虑枚举答案在哪里产生,求概率。那么它的概率就是,在某时刻后碰撞减去当前碰撞。

考虑如何求某时刻后碰撞的概率:把某时刻前可能碰撞的方案都删掉,之后DP一下。可以用线段树维护DP。

Game Relics

题意:抽卡有代价,保底有代价,如果抽到已经有的,返钱。保底价格一定高于抽卡。求期望

可以发现因为抽卡更便宜,先抽一会比较优秀。我们无法控制抽卡的走向,于是计算每一种情况的贡献。

注意到抽卡越来越贵。那么求出每种状态(数量,和)的概率后,求它转移到多一个数量的期望。要么抽卡,要么把后面的全买上。全买不好表示,可以加一个平均数。因为后面都是买,就对了

Mergesort Strikes Back

题意:归并排序,钦定了只能递归几层。求逆序对期望

考虑先把每一块求出来,之后算两块之间的贡献。

一块内的好算,只需要算两块。注意到两块的本质是划分成下降子段后,对段头排序。考虑随机状况下的期望:1/2。在新的排序方法下,还是随机的,只不过有特殊情况:一个点是max时,不可能有贡献。于是期望就是\frac{1}{2}-\frac{1}{i+j}

注意到叶子只有两种,枚举就可以了

Mr. Kitayuta's Gift

题意:给一个串,长度是200。添加1e9个字符使得它是回文的,求方案,要求回文串本质不同

跪了。。注意到本质不同,那么考虑尽量把串往外匹配确保唯一

f_{l,r,i}表示l,r没匹配,一共用了i个字符的方案数。

那么对两端是否相同分类讨论。可以DP。

考虑构造自动机,并DP。复杂度没变。

考虑压缩自动机:对两端是否相等的路径分类讨论。发现类型相同的点转移相同,于是顺序无关。那么本质不同的路径只有n条。压成n条路径。

发现复杂度还是很高,继续压缩:构造两排点,之间连边即可。把路径数放在两种点之间的边。矩乘。

注意到当幂是奇数时,最后一步如果要消去两个点,则不可能。所以奇数时再算一下减去即可。

龙与地下城

题意:正态分布,求期望。

考虑一种多项式做法:构造一个正态分布的函数,求幂即可。但是复杂度很高,考虑优化:

注意到正态分布两边的值很小,只需要每次把边界的数直接删掉即可。

无意识之外的捉迷藏

题意:DAG上博弈,一个人抓另一个人。两人操作是同时的。求抓住的期望时间

考虑DP:f_{x,y,t}。但是问题是,不一定存在最优解。因为操作同时,只能把策略变成更倾向于某一种操作。这个问题可以用线性规划解决,但是不会。

国际象棋

考虑主元法:把上方2行,左边1行看作未知数,就可以表示每个格子了。

RNG and XOR

题意:初始为0,每次有概率变成其它数,求变成每个数的期望次数。

列出高斯消元的式子,之后移项,发现求逆就可以。但是问题是有0,那么待定系数求解。

Good Contest

题意:APIO那个DP题同款

根据套路,左闭右开离散化,之后DP就好了

Isolation

题意:初始坐标在1500内,走1500步,不能走到距离原点曼哈顿距离是4的地方,求方案数。

考虑求出t步,第一次碰到边界的方案数:考虑到合法的点只有16个,直接暴力设状态暴力转移即可。要解决的唯一问题就是,走若干步,从一个点走到另一个点的方案数。

考虑旋转坐标系,之后就转化为了两维独立,且每一维都要走。就可以算了

Count Modulo 2

题意:200种元素,选1e18个,使得和等于s。求方案数模2

考虑记录每种元素选了多少。考虑模2:每种元素选的个数都要是n的子集,且不交。

那么枚举n的每一位,选一个数上来。

注意到,此时选的数\geq 2^i,那么说明比这一位低的位,必须在模意义下与s相同。也就是说,上一次DP出的结果,只有一部分可以转移到这一位。

那么在DP后,把符合条件的移一位就可以了。

ColoringBalls

题意:给定操作序列,对空白序列染色。染色时,可以在之前的基础上染。但是特别的,蓝色不能在空白的上染。求最终序列数。

考虑合法序列条件:把相同颜色缩起来之后,用白色分割序列。每一段独立。

考虑一段有若干蓝色,那么一定形如RBRBRBRB...。要想染出这样的形状,需要一次红色一次蓝色,后面就可以任意了。

那么考虑DP这个蓝色数量。把70划分一下,发现方案数是不多的。贪心匹配即可。

考虑计算方案:首先多重排列,之后计算给定蓝色,对应多少合法序列:

考虑最简序列,之后在最简序列中插一些点进去。首先,有一些球已经钦定了,不能用。考虑去重后最长序列样式唯一。那么用剩下的球插出这个序列即可。

Everything on It

题意:求子集族方案数,满足每个元素至少出现2次。

考虑容斥,钦定i个出现了1次。那么问题就变成了怎么求有多少出现了1次。

首先钦定一共分入了j个子集族。那么考虑加一个垃圾堆,就可以求出方案数。

剩下的n-i个数,瞎选有2^{2^{n-i}}种方案。考虑前面的j个子集族,子集可以随便往里面加,那么再乘({2^{n-i}})^j

某个套路求和题

题意:n的约数的mu之积,求前缀和

考虑上面式子的含义:没有平方因子的才有值,并且值是1,特别的,质数是-1。那么求一下没有平方因子的,和质数有多少就可以了

[LOJ某比赛] 求和

题意:求\sum_{i=1}^n \sum_{j=1}^m \mu^2(gcd(i,j)),数据范围10^{13}

考虑枚举gcd,反演,就变成了\sum_{i=1}^n \sum_{d|i} \mu^2(d)\mu(i/d)

考虑后面的式子:首先i的约数最多幂是2,否则就只能是0

考虑幂是2的,一定是平均分配,对乘对贡献是1

考虑幂是1的。把它拿出来,剩下的式子写出来,再考虑把它插回去。发现插在两边抵消了。

于是只有是完全平方数的时候才有值,就可以化简

二分图染色

题意:完全二分图,可以空着或者染两种颜色,要求同色不共用点

考虑转化为网格图,之后就是一行一列只能放一种颜色。考虑两种方案分别算,乘一下,减去共用格子的。枚举共用格子容斥。

问题是如何求方案数:考虑f_n,新加入一行一列。只考虑行,向之前连边,如果已经有边就断开连列。那么方案唯一。对列也做一次。

问题是可能有重复,前面的每对点都有贡献,减去。

f_{n}=2nf_{n-1}-(n-1)^2f_{n-2}

Misaka Network 与求和

\sum_{i=1}^n\sum_{j=1}^n f(gcd(i,j))^k,其中f表示次大因子。

考虑一波反演,问题转化为了求\sum_{d|n}f(d)^k\mu(n/d)

考虑杜教筛:卷一个I\mu就没了。问题转化为求f(i)^k前缀和。

考虑min25筛:S(n,j)表示因子不小于j。那么分类讨论贡献在哪里产生。

min25筛的时候,分类讨论:在状态S(n,j),钦定第二大因子在这里产生的方案,就是比p_j大的质数乘p_j。剩下的直接加就好了。

以及,看freopen的博客冷静了一下,其实化简到一半的时候有个\varphi,直接筛也行...

蒜头的奖杯

题意:\sum_{i,j,k}A_iB_jC_kD_{(i,j)}E_{(j,k)}F_{(i,k)}

丧心病狂题。考虑先枚举k,顺便枚举(j,k),(i,k)。因为k的范围与lcm有关,就缩小到了能看的范围。

枚举两个gcd的gcd,后面可以算。经过大力推倒,可以得到一个复杂度与xy有关的式子。那么钦定x \leq y,就可以大力枚举。

注意高维前缀和的技巧:枚举质数

Ribbons on Tree

题意:树上点对配对,把路径染色。求整个树都有颜色方案

考虑容斥,枚举联通块,求方案数。方案数就是块内点两两配对,即n!!

但是不能枚举,考虑优化过程:直接DP,并动态记录。注意到数据范围不大,可以考虑DP时记录当前联通块有多大。

Two Histograms

题意:行列可以贴着两个边界+1,求本质不同方案数。

之前做过,写了个**。

考虑什么时候会重复:两条顶住了。那么考虑钦定其中一种顶法有i条,剩下的随便,目标是把它容斥没。

考虑i条方案:f_i=(m+1)^{n-i}(n+1)^{m-i}\binom{n}{i} \binom{m}{i}i!

「CodePlus 2018 4 月赛」Tommy 的结合

题意:树上斜率优化。

做法:写的倍增飞了。。发现二分其实也挺好写的。。。

核心思想如下:考虑二分出弹栈弹到哪里。具体来说,二分最靠前的,不能用的位置,把它替换成新的。注意到这事实等价于两个操作:修改栈的一个位置,移动右端点。于是可以维护。询问也二分,二分最靠前的满足条件的位置即可。

Hyperrectangle

题意:超立方体,求和到原点\leq s的单纯性的体积

首先考虑没有每一维的限制的答案:考虑积分,首先二维可以求出。之后迭代的对每一维积分,可以发现答案是\frac{1}{d!}s^d

那么每一维有限制,就考虑容斥。钦定一组超过限制,那么把s减去它们的和,求一下。这样的原因是我们需要减去多余的面积,那么钦定一些维超过,求得的面积就是多余的。

具体来说,令f_i表示,之后f_i = f_i - f_{i-A},求容斥系数就可以了。

Rigid Frameworks

题意:给一个网格,可以在每个格子加斜对角线,要求网格稳定。求方案数

考虑什么时候稳定:事实上和方向无关,只需每行每列都有就行了。于是转化为二分图,要求联通,方案数。根据套路枚举第一个点联通块即可

World of Tank

题意:2 \times n的矩形,坦克从一端走到另一端,可以绕路可以开炮,炮有冷却,求方案

考虑到达一个点后有关的是当前冷却了多久,越久越好。注意到冷却完毕后,如果不绕路,应该立即开炮。那么在一行走哦的时候,可以把时间累加起来,高于冷却上限,但是转弯的时候必须求min。又注意到有用的点不多,离散DP就行了

The Tree

题意:三种操作,从白点染色,如果没染,递归子树。子树染白。单点询问

考虑操作分块:之后在虚树上暴力。或者树剖,一个点被染色,那么祖先存在一个点,权值到它比距离大。考虑子树推平:首先清零,之后如果祖先的max还会染到,把x点减少一些权值。

Iron Man

题意:树,给若干路径,有时间,速度,起点终点。求最小相遇时间

考虑链怎么做:枚举,求交点。这个太慢,优化:如果两个线段相交,那么必然有它们的起点是相邻的。扫描线。树上树剖就行了

Holy Diver

题意:每次序列后push一个值,再给定l,r,求区间的子区间mex和。

维护右端点的mex:加入点后,受影响的是mex=a的区间。把它丢掉,之后更新。对于答案,用线段树维护。具体来说,l,r的答案=r版本线段树的答案。因为当前只有一段有效,一次修改,首先把上次的删掉,贡献为持续时间。之后更新当前区间,两种贡献:区间长度,区间长度乘起始时间。永久化标记解决。

描述一下怎么更新mex:考虑加入数字a,那么找出一个数满足大于a,且上一次出现位置在r之前。那么[p,r]mex就是它。多次重复即可。

Network

题意:给定A点B点,定义路径权值为路径max-min,定义A点权值为它到B点的权值max。定义答案为A点权值min。现在可以反转一个A变成B,求最大答案

首先求出不反转的答案。考虑点分,之后拼接答案。因为只关心极值,所以直接记录子树的权值区间[L,R],以及次优值。之后可以拼接。

考虑反转一个点,之后点分树上跑一下,更新答案。二分答案,判断反转后是否还存在小于答案的点。这个可以通过分类讨论得到。

代码没写,咕咕咕

A Sequence of Permutations

题意:给两个排列,定义递推,下一个是f(p,q),表示第p_i个元素为q_i

a_{p_i}=q_i,a_{i}=q_ip^{-1}_i。后面是找规律,这个我也没办法了

Synchronized Subsequence

题意:序列,只有a,b,数量相等,一对可以一起删,最大字典序。

考虑从两种相等的位置断开,考虑每一段:如果a开头,贪心选ab。如果b开头,考虑多选b肯定优秀,但是不一定每个b都要选:比如bbbabbbbb,那么不选第一个b比较好。假设知道了第一个b是谁,后面的b都要选,枚举判断。

[APIO2017]斑斓之地

题意:网格图联通块

老套路:一个点-两个点+四个点。

Distance Sums

题意:给定每个点到其它点的最短路,复原这个树

首先最大值对应的是叶子,考虑求它连着的边。事实上是可以从一个点推出另一个点答案的。所以就推一下连着的点是多少,连上就行了。

注意最后要check一下答案。

CF1336D Yui and Mahjong Set

题意:交互,可以求\sum \binom{a_i}{3}, \sum a_{i-1}a_ia_{i+1},可以单次+1,可以操作n次,求每个位置

考虑先把3,n-1操作一下,之后求出1,2,3,4,就知道答案了。进行121这样的操作即可。

[WC2018] 战略游戏

题意:交互,可以询问(x,y),返回从x出发往y走第一个碰到的点。nlogn次确定答案

考虑如果走过,就跳到目标点。但是可能跳过,考虑一层一层的跳,点分树优化。动态点分即可,注意动态点分重构时,父亲会改变。

势函数和鞅的停时定理

我也不知道是啥,记个做法:

期望步数的题,对于状态记录势函数\varphi(A_t)=\sum_i f(A_{t,i})。考虑推出A_{t+1}。发现可以列一个等式。

势函数需要满足走一步值-1,通过这个,可以求出f的形式。

数树

题意:给定一个树,另一个不确定,求\sum y^k,其中k是交集大小。再求两个树都不确定的。

首先考虑钦定一个相同集合,再求方案。那么可能会有更多边相同。但是考虑钦定一个集合s,会被算多少:会被子集合t算到。考虑贡献:\sum y^i \binom ni,所以把y-1之后直接算就行了。

之后考虑DP:f_{x,0/1}表示集合内是否选了点。

两个的:钦定相同集合,大小一样的一起算。可以写成EXP的形式。\sum_{\sum a_i=n} \prod a_i这样的式子。

随机立方体

题意:立方体,一个点是优秀的,则和它相交的三个平面上的值都小于他。求有恰好k个优秀点方案

考虑转化为至少,那么钦定k个点,并钦定一些数分给它的并集,再乘一下分配方案数

考虑分配方案数:把关键点从小到大放,发现放大关键点的时候,小关键点用到的值,都满足新的限制。于是可以转化为一个树,树的拓扑序方案就是全排列,除以每个子树大小的逆元

氪金手游

题意:一个人有三种值,是随机的。选一个点概率是w_i / w_{sum}给一个树,边有方向,要求指向的比起点选中更晚,求方案

首先变成外向树并DP,对于其它方向,容斥掉

考虑一条链,则一个点在它后面之前被选概率,等于w_i / w_{son},之后树形DP。

重复

题意:给定串S,求有多少T,满足T复制无限份后,存在一个子串字典序比S小。

首先转化一下求不存在。考虑把S的KMP自动机搞出来,在上面跑。一个点的出边有一些是不能用的,具体来说,是fail树上的max。

有一个这样的性质:在跑无穷多次后,会循环,且循环节是m的约数。

证明:冷静了一下有一种简单的理解:考虑匹配到的是S的前缀,T的后缀。当长度为无穷的时候,加一个还是无穷,没有变化,所以循环长度不可能是倍数。

那么考虑不同的T串,走出的循环路一定不同,那么只需对循环计数。具体来说,令f_{i,j},表示走i步,走到j的方案即可。

但是复杂度不太对劲,考虑优化:考虑每个点的出边,可以发现一定是前缀的max。那么也就是说,一个点最多有一个不跑回起点的出边,且一定存在。

考虑一个满足题目要求的T:它的路径是\rho形的。如果不经过根,考虑环:如果环的大小是m的约数,则贡献为环的大小。(考虑环的每种拆分,因为环是递增的,路径形如在根绕一会再出去,所以可行)

如果经过根,考虑一个环,是从x点走回根,再走回来,其中走回去的路不能碰到根。那么拆开DP即可。

「JOISC 2017 Day 1」烟花棒

题意:每个人可以左右跑,两个人在一起的时候可以选择点燃另一个人,一开始一个人有火,T时间后熄灭,要把所有的都点着,求最小速度

二分速度后求解。考虑两个人相遇后,最优方案:应该是一个人熄灭的时候再点另一个人。那么发现原问题等价于碰到每个人时间+T,要碰每个人。那么考虑把人合并为若干对(x,y),表示需要代价x才能进,出来后加y的时间。

合并后贪心,如果消完就没了,否则把序列剩下的全加上,把对看作需要退若干代价进去,出来后加一些,再贪心一次。

[APIO2018] 选圆圈

题意:若干圆,每次操作选最大圆把相交的都删掉,求被谁删

正解的姿势:考虑可能消除一个圆的圆:最多有四个,且与这个圆四边界的直线相交。那么扫描线就行了。或者KD树?

[APIO2018] 新家

题意:每个东西有属性:类型,出现时间段,位置。询问某时间某位置,每种类型距离min的max

排序一下,上个二分答案:只需区间询问出现次数

考虑一种值在[l,r]如果没有出现,那么它在r后第一次出现的pre就。于是维护min pre即可

[APIO2019]奇怪装置

题意:给若干不相交区间,一个位置的值定义为((t+\lfloor \frac{t}{B} \rfloor) \mod A, t \mod B),求有多少对

既然取模,那么循环了:手玩一下可以发现要满足(B+1)k \equiv 0 \pmod A,于是应该是gcd(B+1,A)

[APIO2019]桥梁

题意:修改边权,求一个点带权出发能到多少点。能到要满足权不大于边权

根号重构暴力DFS即可

[APIO2019]路灯

题意:序列[l,r]可行仅当区间都是1。操作反转或询问一开始到现在有多少时刻联通

直接维护点对答案,发现差分一下后矩形加即可。注意询问时如果还联通着,要减去当前时刻

Easy win

首先有个套路:把边的位置设为1,独立集就是无环图

动态插入的最大线性基的姿势:考虑插入一个新元素。如果能插进去就直接插。考虑维护一个集合,表示当前线性基是由哪些元素搞出来的。对于每个位置维护一下它是这个集合怎么组合出来的。

如果插不进去,考虑把最小的元素换掉。扫过一次之后,得到了当前元素能由哪些组合出来,枚举找一个最小的替换。那么我们可以理解我们用一个集合代替了之前的一个元素,于是枚举集合中的所有元素,xor上当前元素的集合。

const int N = 130;
std::bitset<N> A[N], B[N];
long long ans, w[N];
int cnt;
bool ins[N];
inline void insert(std::bitset<N> a, int v) {
  std::bitset<N> b;
  for (int i = 128; ~i; --i) {
    if (!a[i]) continue;
    if (!ins[i]) {
      ins[i] = 1;
      ans += v;
      w[++cnt] = v;
      b[cnt] = 1;
      A[i] = a;
      B[i] = b;
      return;
    } else {
      a ^= A[i];
      b ^= B[i];
    }
  }
  int pos = -1;
  for (int i = 1; i <= cnt; ++i)
    if (b[i] && (pos == -1 || (w[i] < w[pos])))
       pos = i;
  if (~pos && v > w[pos]) {
    ans += v - w[pos];
    w[pos] = v;
    b[pos] = 0;
    for (int i = 128; ~i; --i)
      if (ins[i] && B[i][pos])
        B[i] ^= b;
  }
}

[WC2019]I君的商店

考虑权值相等的时候随便返回一个东西,其实就是把小于变成小于等于。

考虑如果已知序列形如11111...110000...000怎么做:直接二分分界点即可。

考虑不是这样怎么做:维护三个指针a,b,c,先比较一下令a<=b,再比较a+b和c的大小:要么a=0,要么b>=c。于是可以得到若干0和一条偏序链。二分即可

[NOI2019]I君的探险

考虑树,且父亲比自己小:二分mid,把之前的都改一下,查自己的值。整体二分即可

考虑一般图:随机排列做上面的操作即可。复杂度不太会证,反正能过

发表评论

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