JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj1978][BeiJing2010]取数游戏 game_动态规划_质因数分解

取数游戏 game bzoj-1978 BeiJing-2010 题目大意：给定一个$n$个数的$a$序列，要求取出$k$个数。假设目前取出的数是$a_j$，那么下次取出的$a_k$必须保证：$j<k$且$gcd(a_j,a_k)/reL$。问最多能取出多少个数。注释：$1\le n\l...

2019-01-08

0 605

[bzoj1112][POI2008]砖块Klo_非旋转Treap

砖块Klo bzoj-1112 POI-2008 题目大意：$N$柱砖,希望有连续$K$柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务. 注释：$1\le k\le n\...

2019-01-07

0 351

[bzoj5379]Tree_dfs序_线段树_倍增lca

Tree bzoj-5379 题目大意：给定一棵$n$节点的树。支持：换根、把节点$u$和$v$的$lca$的子树加、询问$u$的子树和。注释：$1\le n,q\le 3\times 10^5$。想法：和bzoj3306比较像。发现麻烦的就是第二个操作，其实就是一个大特判而已...

2018-12-30

0 596

[bzoj1207][HNOI2004]打鼹鼠_动态规划

打鼹鼠 bzoj-1207 HNOI-2004 题目大意：题目链接。注释：略。想法： $dp_i$表示打到了第$i$个鼹鼠时最多打了多少个鼹鼠。 $O(n)$转移即可。总时间复杂度$O(n^2)$。 Code： #include <iostream> #i...

2018-12-30

0 401

[bzo1211][HNOI2004]树的计数_prufer序列

树的计数 bzoj-1211 HNOI-2004 题目大意：题目链接。注释：略。想法： prufer序列有一个性质就是一个数在prufer序列中出现的次数等于这个prufer序列生成的树中它的度数-1。故此我们就是要求$C_{n-2}^{d_1-1}\times C_{n-2-d...

2018-12-30

0 405

[bzoj1430]小猴打架_prufer序列

小猴打架 bzoj-1430 题目大意：题目链接。注释：略。想法：我们发现打架的情况就是一棵树。我们只需要把确定树的形态然后乘以$(n-1)!$表示生成这棵树时边的顺序。一共$n$个节点我们发现数的形态一共有$n^{n-2}$种。所以答案就是$n^{n-2}\cdot ...

2018-12-30

0 460

[bzoj3306]树_dfs序_线段树_倍增lca

树 bzoj-3306 题目大意：给定一颗n个节点的树，支持换根、修改点权、查询子树最小值。注释：$1\le n,q\le 10^5$。想法：如果没有换根操作，就是$dfs$序+线段树维护区间最小值即可。加入有换根操作，我们发现对修改操作没影响。我们只需要判断一下询问的点和...

2018-12-30

0 381

[bzoj4300]绝世好题_二进制拆分

绝世好题 bzoj-4300 题目大意：题目链接。注释：略。想法：二进制拆分然后用一个数组单独存一下当前答案即可。 Code： #include <iostream> #include <cstdio> #include <cstring&g...

2018-12-23

0 450

[bzoj2463][中山市选2009]谁能赢呢？_博弈论

博弈论 bzoj-2463 中山市选-2009 题目大意：题目链接。注释：略。想法：如果$n$是偶数的话就可以被多米诺骨牌恰好覆盖，这样的话只需要先手先走向(1,1)对应的第二段，后者必定会将棋子移动到多米诺骨牌的第一段。故先手必胜。反之同理。 Code： #incl...

2018-12-23

0 393

[bzoj3991][SDOI2015]寻宝游戏_树链的并_倍增lca_平衡树set

寻宝游戏 bzoj-3991 SDOI-2015 题目大意：题目链接。注释：略。想法：我们发现如果给定了一些点有宝物的话那么答案就是树链的并。树链的并的求法就是把所有点按照$dfs$序排序然后相加再减去相邻之间的$lca$。故此我们按照$dfs$序维护一个平衡树。每次往里插...

2018-12-23

0 394