HWizard_wph-CSDN博客

原创高斯消元

高斯消元。。。自己以前写的思路：具体的做法就是枚举当前行，然后找出当前列未知数没消掉的一行，替换一下。然后，把当前行下方的所有行消掉当前列的未知数。最后，回代求出所有值。这个写法比较普遍。今天在做一道题的时候，遇到一点小阻碍。具体的小问题出在替换那个地方，这题好像并不能换。于是，翻了陈老师的代码，学了一种新的姿势。枚举当前行，然后找出没有消去未知数的一列，用它把其他这列存在未

2017-04-05 16:37:20 470

原创 bzoj 3729

题意：在一棵树上博弈，每次能将不超L个的石头移到父亲。支持三种操作： 1.询问u为子树的博弈情况 2.修改某个点的值权 3.插入一个新点题解：博弈部分如果直接将u为第0层，就是奇数层的数值才是有用的。因为不超过L个，后手可以保证每次两人取得(L+1)，所以sg值为模(L+1)。那每次询问就是对整棵树奇偶分层，和当前点奇偶性不同的sg值XOR和。用splay维护dfs序，

2017-03-23 16:01:19 394

原创 bzoj 4527

题意：给出一个数列a。需要求出一个最长的子串加入不超过k个数，能够形成公差为d的等差数列。题解：形成公差为d的等差数列的条件： 1.不存在相同的数 2.所有的数应该在模d下同余 3.若设max为区间最大值，min为区间最小值，应该满足： (max−min)/d−(i−j)<=k(max-min)/d-(i-j)<=k如何实现？设b=a%d,c=a/d 先将b相同的一段段区间

2017-03-23 15:41:42 451

原创 bzoj 3958

题意：在一个无限的坐标系中，有若干个僵尸还有一个人。每一秒钟，人先运动，然后僵尸们运动。每一秒钟，可以向相邻的格子运动一步。询问，人到最多第几秒会死。题解：考虑第t秒的状态，若人已经死了，那t+1秒他也不可能活着。。。然后就可以二分这个时间了。再考虑，在t秒内，对应物体能走到的位置就是一个长和宽均为2*t的正方形。如果人所在的正方形没有被完全覆盖，他就能活下来。然后，就可

2017-03-23 15:16:58 395

原创 bzoj 3443

题意：有若干种装备，每种装备有若干种属性。两个装备之间可以合成，具有方向性。 a并到b上，则a中所有小于b的属性全部换成b的值。有三种操作: 1.将两个装备合并 2.更改某个装备的某个属性的初始值。（合并后仍有影响） 3.询问当前的某个装备的某个属性的值。题解：发现属性数量少，考虑对每个属性分别维护。然后，就开始了我的无脑想法：打算把合并状态先建出树，然后什么树链剖分。。

2017-03-23 15:04:18 440

原创 bzoj 4662

题意：有若干个工人，每个人要在一个区间中扫地。每天需要一个区间范围最短的工人扫地(扫过的地方就不用扫了)。要求输出这个工人。题解：将这个坐标系离散化。若一个一段位置被扫掉，那影响的人应该是连续的一段。。。->这个可以二分来找吧。嗯，对于每个要扫地的工人，可以”暴力”枚举清理的部分，然后二分影响到的人。然后在线段树上区间修改一下。其实上面说到的”暴力”，需要用一个并查集来维

2017-03-23 14:50:59 476

原创 bzoj 3133

题意：给出一棵树，一个人在树的顶端放球，球会优先进入子树内最小值更小的那一部分。有两种操作： 1.在根节点放入若干个球。要求输出最后一个球落到了哪里。 2.拿走某个球，要求输出有几个球会落下来。题解：球落下的顺序是一定的，而且可以求出来。。。 ->先在树上做出dfs序。 ->然后在树上记录一下子树内最小值，然后按照这个顺序将dfs序存下来。这个序列就是球从先到后落下的dfs序

2017-03-23 14:35:50 421

原创 bzoj 2006

题意：从n个数中，选出不同的k段，长度在[l,r]中间，使得权值和最大。位置不同则为不同。题解：一段权值考虑差分，表示成两段前缀和的差。对于每一个位置为结尾，在限制范围中，先选出最大的放进一个堆里面。每次从堆中选出一个最优的，然后从堆删除掉，累计答案。然后在限制范围中选一个小一点的值，再放进堆。如何在限制范围中找值？搞笑的我，用主席树去搞，就被嘲笑了。可以在每次存当前

2017-03-23 13:30:46 324

原创 bzoj 3809

题意：给出一个序列，每次询问一个区间内权值在[a,b]内的数有几种题解：想一下，大概可以想到O(n∗sqrtn∗logn)O(n*sqrtn*logn)的做法。就是莫队然后维护个树状数组。但是，复杂度要求是O(n∗sqrtn)O(n*sqrtn)的。那相应的每次修改的都要O(1)O(1)完成，然后需要用一个东西来代替树状数组来完成统计。可以考虑对数的权值分块，这样就该就可以O(1)实现，

2017-03-18 21:42:37 304

原创 bzoj 3451

题目：求随机点分治的期望复杂度。题解：思路一开始就没对，应该往贡献的方向去思考的。考虑一个点对(u,v)，若u会对v产生影响，当且仅当u->v的路径上不存在被选中的点。而一条路径上所有的点被选中的概率是均等的，u被首选的概率为1/(dis(u,v)+1)1/(dis(u,v) + 1)。那么对v的期望贡献就是那么多。那问题成功转化成 ∑i,j<=n1/(dis(u,v)+1)\su

2017-03-11 11:16:47 536

原创 bzoj 3566

题意：给出一棵树，每个节点和边都有一个通电的概率，问发光的节点的期望个数。吐槽一下： naive。。。先按照感觉，列了能发光概率的式子，后来发现自己分析的漏洞太多了。题解：考虑树形动态规划。很容易知道电流不会跨过当前节点u后再转移到u。所以，不妨分开子树和子树外来考虑。然后，很难考虑能发光的概率，就去考虑不能发光的概率。设计状态f(u)表示子树内不能使u发光的概率，g(u)表示

2017-03-09 10:15:57 340

原创 bzoj 2337

题意：给出一个联通图，存在自环和重边，边上带权。要求：求出从1点到n点的期望路径XOR和。题解： XOR嘛……容易想到拆位，对于0和1的边权肯定好处理。然后，设计状态是f(u)表示从u到n的期望XOR和。因为f(u) = P(期望为1) * 1 + P(期望为0) * 0 即f(u)也为到n点期望为1的概率。然后，枚举边：若权在此位为1，f(u) += (1 - f[v])

2017-03-08 13:21:45 392

原创 bzoj3270

题意：两个人在A和B两个点，然后自由游走在位置i时有pi的概率留在原定，到周围每个点的概率相同，求两人在每个点相遇的概率。题解：先不考虑对概率列方程，而是对期望去列。 F（x，y）表示一人在x，另一人在y的状态，列方程的时候表示的是这种状态出现的期望。枚举两个nx，ny，然后通过F（nx，ny）可以转移到F（x，y），当然nx != ny，因为相遇后就不会再游走了。然后对于一个F（i，i）

2017-02-25 08:25:13 353

原创 bzoj1415

感觉此题题意不清啊题意：两个人A、B左右游戏。每轮游戏A先手，A会走向靠近B的点，若走一步到不了会再走一步。然后B会随机向周围的某个点走一步。问A与B相遇的期望游戏轮数。 n<=1000题解：千万不要忽略一个条件，A先手走，因为这个差点去打了check。先n次的宽搜找出每对点（u，v），当A在u而B到v时，下一次A会到的点。然后，设计状态g（u，v）表示A在u，B在v的

2017-02-23 17:20:07 314

原创 bzoj1122

题意：一个长度为n的记账单，+表示存￥1，-表示取￥1。现在发现记账单有问题。一开始本来已经存了￥p，并且知道最后账户上还有￥q。你要把记账单修改正确，使得 1：账户永远不会出现负数； 2：最后账户上还有￥q。你有2种操作： 1：对某一位取反，耗时x； 2：把最后一位移到第一位，耗时y。题解：很容易知道1操作数量是一定的，设+的数量为np，-的数量为nm，可以计算出需要将(p - q + n

2017-02-12 10:01:50 460

原创 bzoj1115

题意：有N堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。题解：后手会模仿先手的行为，所以不难想到差分。然后可以发现，相当于若干堆石头，每次可从第i堆放到第i+1堆。就是那个阶梯的模型，然后偶数层阶梯的石头后手也可以利用以上方法处理，所以相当于

2017-02-11 10:08:18 325

原创 codeforces泛做

364B: Connecting Universities Problem: 一颗无根树上给出2*k个点带有标记，现在要将2*k个点两两配对，会一种方案使总距离最大，求最大的距离。 Keyword: 搜索 Analyse: 边是没有长度的。而长度最多，则每条边应该覆盖尽量多的次数。 Solution: 每条边可以把整棵树分成两个点集。对于小的部分是某个点的子树，维护该子树的黑点个数siz

2016-08-29 09:20:42 1393

HWizard