标签 - LOJ

? 解题记录 ? ? LOJ ? ? FFT|NTT ? ? 动态规划 ?    2019-03-16 07:59:01    629    0    0
传送门 题解: 考虑怎么做这道题。 首先发现性质: 改变次数=2×总操作数−答案中′1′的个数" role="presentation">改变次数=2×总操作数−答案中′1′的个数改变次数
? 解题记录 ? ? LOJ ? ? 字典树 ?    2019-03-14 15:26:58    547    0    0
题目链接 题解:发现只需要分两段维护就可以了。 上一次排过序的前缀部分用字典树维护,并且对每一位记录nowxor" role="presentation">nowxornowxornow_xor表示按照当前的顺序,第i" role="presentation">iii位是否被翻转。后面的部分用一个前缀和维护。 这样的话,异或的时候维护偏移值,每一次排序我们就把后面的部分全部插入字典树,并且更新now&#x005F;xor" role="presentation">now_xornow_xornow\_xor。 #include<cstdio&g
? 解题记录 ? ? LOJ ? ? 树链剖分 ? ? FFT|NTT ? ? 动态规划 ?    2019-03-14 11:31:06    735    0    0
题目链接:传送门 题解:不难发现,我们有一个优秀的N2N^2的dpdp做法,记录f(i,j,0/1)f(i,j,0/1)表示ii子树内选jj个,当前根选没选。 我们要知道分治NTTNTT的复杂度:对于kk个总度数∑deg=k\sum deg=k的多项式来说,计算它们乘积的复杂度可以做到:O((∑deg)log(∑deg)logk)O((\sum deg)log(\sum deg)logk)。 因此,我们采用重链剖分,先转移所有轻链。 不难发现, g(u,0)=∏v∈son(g(v,0)+g(v,1))g(u,0)=\prod_{v\in son} (g(v,0)+g(v,1))
? 解题记录 ? ? LOJ ? ? 动态规划 ? ? 状态压缩 ?    2018-12-13 08:35:48    748    0    0
传送魔法:biu~~~~~~~ 算是一道较有趣的dp" role="presentation" style="position: relative;">dpdpdp了。 首先有一个简单的做法,状压3" role="presentation" style="position: relative;">333进制。 第i" role="presentation" style="position: relative;">iii位是0" role="presentation" style="position: relative;">000表示ai" role="pres
? 解题记录 ? ? LOJ ? ? FMT|FWT ? ? 动态规划 ? ? 状态压缩 ?    2018-12-10 09:19:13    395    0    0
题目地址:嘤嘤嘤 听说是FMT" role="presentation" style="position: relative;">FMTFMTFMT裸题然而学了FMT" role="presentation" style="position: relative;">FMTFMTFMT还是不会啊QAQ" role="presentation" style="position: relative;">QAQQAQQAQ。 首先有一个比较显然的dp" role="presentation" style="position: relative;">dpdpdp。
? 解题记录 ? ? LOJ ? ? 带权二分 ? ? 动态规划 ?    2018-12-10 09:18:19    331    0    0
题目描述 小 L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做 “LCT” 的挑战,它的规则是这样子的:现在有一个 NN 个点的树(Tree),每条边有一个整数边权 vi" role="presentation">viviv_i,若 vi&#x2265;0" role="presentation">vi≥0vi≥0v_i \ge 0,表示走这条边会获得 vi" role="presentation">viviv_i的收益;若 vi&
? 解题记录 ? ? LOJ ? ? Treap ? ? 可持久化数据结构 ?    2018-12-09 17:13:20    454    0    0
原题地址 感觉还是很妙一个题,自己想了一会,看标签后茅塞顿开。发现这个题的操作一直在用数列已经有的部分去覆盖一部分。因为一直在用原来的,有点可持久化的意思。发现其实我只要维护一个数据结构,可以把原来的一段提取出来插入到一个位置,并且可以维护区间加区间和以及可以可持久化即可,这里的可持久化是为了不影响原来已有的部分,对于所有的修改都在新点上操作。这样的数据结构就只有可持久化平衡树了。非旋Treap的可持久化和线段树差不多,只要有修改的地方拉一个新点起来就行了。时间复杂度O(n log n),空间常数很大,注意不要爆空间。#include<cstdio> #include<alg
? 解题记录 ? ? LOJ ? ? 生成函数 ? ? 期望概率 ? ? FFT|NTT ?    2018-12-09 16:21:41    430    0    0
题目地址:"噔" 题目给定的条件不太好求。 发现原题死了人之后概率的分母会变,十分不可做。 然后就有一步神转化了,我们将原题改为打死人之后这个人并不出局,而是被打上标记。如果开枪射中打标记的人,那么这一枪无效,重新射击。 这样我们发现,分母一定了,容易了许多。 整理一下,发现我们没有办法确切算出1" role="presentation" style="position: relative;">111在最后一个死的概率,但是我们可以确切算出至少有k" role="presentation" style="position: relative;">kkk个人死在1"
? 解题记录 ? ? LOJ ? ? 动态规划 ? ? 期望概率 ? ? 状态压缩 ? ? FMT|FWT ?    2018-12-05 21:25:10    864    0    0
链接:戳轻点 >_< 神仙题啊! 还不自量力的想了半天。 看完题解发现自己更本没资格做这道题…… 首先貌似有个没分的高斯消元? 嗯……全部都至少走一遍的期望根本不会算啊。 我们先来看一个很好理解的结论: 最值反演:   考虑任意集合S" role="presentation" style="position: relative;">SSS,元素i" role="presentation" style="position: relative;">iii有点权wi" role="presentation" style="position: r
? 解题记录 ? ? LOJ ? ? 动态规划 ? ? 状态压缩 ? ? 组合数 ?    2018-12-05 20:33:53    862    0    0
题目地址:呀,戳轻点qwq 一开始自己就想错了,本来以为只要选择的点集定了,那么覆盖状态也就定了。 但是发现并不对,和点选择的顺序还有关。 …… 我们去Orz" role="presentation" style="position: relative;">OrzOrzOrz题解吧。 发现自己仍然是没有完全理解增量的构造方式。 考虑到选择点的顺序其实是和答案有关的,我们考虑对整个操作序列增量的过程进行dp" role="presentation" style="position: relative;">dpdpdp。 设f(i,S)" role="presenta