- 博客(41)
- 收藏
- 关注
RSS订阅原创 阅读笔记DAPG：Learning Complex Dexterous Manipulation with Deep Reinforcement Learning and Demonstrations
DAPG
2022-07-03 01:07:14
386
原创 阅读笔记：PlasticineLab A Soft-Body Manipulation Benchmark with Differentiable Physics
阅读笔记
2022-06-28 03:03:11
340
原创 BZOJ 1004 Card（Burnside）+BZOJ 1815 有色图（Polya）
先来写一写什么是置换群和Burside、Polya。关于置换群、Burnside和Polya一、一些概念1、群：对于一个集合G={a,b,c,…}和G上的二元运算*，满足①封闭性②结合律③单位元④逆元，则称：集合G在运算’*’之下是一个群 2、置换群：置换群的元素是置换，运算是置换的连接3、ZkZkZ_k （K不动置换类）：设G是1~n的置换群，若K是1~n中的某个元素...
2018-06-29 21:42:19
328
原创 洛谷 P3577 [POI2014]Tourism（状压DP）
题目链接：洛谷 P3577题目大意：n个点，m条边的无向图（2<=n<=20000,0<=m<=25000），图中任意两点间不存在节点数超过10的简单路径。给出在每个点建立旅游站点的花费，问最小花费，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。题解：任意两点间不存在节点数超过10的简单路径，说明对图进行dfs得到的dfs树的深...
2018-06-17 10:15:15
330
原创 SDOJ #2013 随机数生成器（笛卡尔树）
题目链接：SDOJ #2013题目大意：给出一个n*m（n,m<=5000）的网格，每个网格有互不相同的权值，定义两个格子联通当且仅当从其中的某个格子只向下或向右走能到达另一个格子，求网格中字典序最大的反链。题解：反链即不存在一个被选中的格子位于另一个被选中的格子的右下方，要求字典序最大即每次选可选的格子中权值最大的一个。关键在于如何快速找到可选的权值最大的格子。 由于每次被标记不...
2018-06-13 20:29:15
459
原创 BZOJ 4338 糖果（扩展Lucas定理+CRT）
题目链接：BZOJ 4338题目大意：用数字1~k填一个n*m的表格，每种数字可用任意次，要求每行数字1~m列单调不减，任意两行不完全相同，求方案数对P取模的值。题解：扩展Lucas+CRT模板题，板子还不是太熟悉，贴到这里方便复习，有空回来加点注释。最后答案的式子比较容易得到，是 AnCmm+k−1&nbsp;&nbsp;mod&nbsp;PACm+k−1mn&nbsp;&nbsp;mo...
2018-05-20 11:04:15
385
原创 洛谷 P3479 [POI2009]GAS-Fire Extinguishers（树形DP）
题目链接：洛谷 P3479题目大意：在一棵n个节点的树上放置灭火器，每个灭火器可以覆盖与其所在节点距离不超过k的节点，每个灭火器最多能覆盖s个节点，求至少需要多少灭火器可以使得所有节点都被覆盖。（n<=100000，s<=n，k<=20）题解：树形DP，设f[i][j]表示以i为根的子树里已经放置的与i的距离为j的灭火器还可以覆盖的点数，g[i][j]表示以i为根的子树里与i距离为j的未被覆盖的点数
2018-04-25 21:02:54
460
原创 HDU 3565 Bi-peak Number（数位DP）
题目链接：HDU 3565题目大意：定义“双峰数”为满足可以分割成两个 /\ /\ 的形式的数，求区间[L,R]内双峰数位数和的最大值。题解：第一次写数位DP，开篇BLOG记录一下 ○(>_<)○ 用记忆化搜索实现，dfs(int wei,int cur,int sta,bool fdn,bool fup)表示当前填到第wei位，上一位数字是cur，双峰数的状态为sta，这一位的取值是(true)
2018-04-23 12:33:46
218
原创 某场模拟赛 博弈（树形DP+二分+贪心）
题目大意： 一棵n个节点的树，初始时s节点有一个棋子，两个人A、B轮流进行操作，规则如下： ①A先手，A可以选择不进行操作，或选择操作，即选择删除一条边或清除一条边上的标记。 ②B后手，每次B会选择与棋子所在节点相邻的一条没有标记的边，将棋子移动到边的另一端，并在边上做标记。如果与棋子所在节点相邻的边都有标记则B不操作（如果存在与棋子所在节点相邻的未标记的边，则B必须移动棋子）。 ③棋子移动
2018-04-22 17:29:18
358
原创 BZOJ 3197 assassin（树形DP+费用流）
题目链接：BZOJ 3197题目大意：给出两棵节点被染成黑白两色的无根树，问第一棵树经过重标号后至少要反转多少个节点的颜色使之与第二棵树完全相同。题解：类似BZOJ3162独钓寒江雪 的解法，可以将树的重心作为根DP，设f[i][j]表示若使第一棵树中以i为根的子树和第而棵树中以j为根的子树完全相同需要反转至少多少个节点的颜色。转移的时候对于同构的子树用费用流转移（还是比较好理解的，详见代码）。co
2018-04-16 11:52:16
323
2
原创 BZOJ 3162 独钓寒江雪（树形DP）
题目链接：BZOJ 3162题目大意：求一棵无根树上本质不同的独立集个数题解：经典的求树的独立集个数可以DP来做，f[x][0/1]分别表示以x为根的子树中不选点x和选点x的独立集个数，初始f[x][0]=f[x][1]=1，转移的时候f[x][0]*=f[v][0]+f[v][1],f[x][1]*=f[v][0] /*v是x的子节点*/。 这个题只需要考虑一下同构就可以了。判断树是否同构可以哈
2018-04-16 09:57:46
348
原创 BZOJ 3743 Kamp（树形DP）
题目链接：BZOJ 3743题目大意：给出n个点n-1条边的一棵树，边有边权，有K个关键点，对于i=1~n，计算从第i个点起遍历K个关键点（不要求最后回到点i）经过的路径总长度的最小值。题解：如果起点是K个关键点之一，答案会是2倍的K个关键点组成的虚树的边权和，再减去起点到剩下K-1个关键点的路径长度的最大值。如果起点不是K个关键点之一，答案会是起点到某个关键点的路经长度，加上以这个关键点为起点、遍
2018-04-15 16:29:23
378
原创 BZOJ 3277 串（后缀数组+线段树）
题目大意： 给出n个字符串，询问每个字符串中有多少子串（不包括空串）是所有n个字符串中至少k个字符串的子串。（n,k<=100000，n个串总长<=100000）题解： 子串是后缀的前缀。某一个字符串id的答案就是id所有后缀的 最长的 出现在k个串中的 前缀 长度的和。 把n个串拼在一起，中间用不同的、没有出现过的字符隔开，求一遍SA[]和height[]。考虑到出现k次的最长前缀长度就是一
2018-04-11 11:56:42
287
原创 BZOJ5249 [2018多省省队联测]IIIDX（神奇的贪心）
题目链接：BZOJ 5249题目大意：n(n<=500000)首曲子，n个难度值d[i] (d[i]<=1000000000)。给定一个实数k (k<=1000000000)，完成第⌊ik⌋ \lfloor \frac ik \rfloor 首曲子后才能解锁第i首曲子，若⌊ik⌋=0 \lfloor \frac ik \rfloor =0，说明第i首曲子无需解锁。确定一种字典序最大的难度顺序，保证每
2018-04-11 11:24:44
743
1
原创 BZOJ5248 [2018多省省队联测]一双木棋（状压+记忆化搜索）
题目链接：BZOJ 5248题目描述： 菲菲和牛牛在一块n行m列的棋盘上下棋(n,m<=10)，菲菲执黑棋先手，牛牛执白棋后手。棋局开始时，棋盘上没有任何棋子，两人轮流在格子上落子，直到填满棋盘时结束。落子的规则是：一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。 棋盘的每个格子上，都写有两个非负整数，从上到下第i行中从左到右第j列的格子上的两个整数记作Ai
2018-04-09 10:43:54
429
原创 BZOJ 3504 危桥（网络流）
题目链接：BZOJ 3504题目大意：n(n<=50)座岛，互相之间有或者没有双向边相连，有的边可以走两次，有的可以走无限次，问是否可以从a1~a2往返an次、从b1~b2往返bn次。题解：最大流，建图比较显然，用流量限制边走的次数。因为是双向边，往返就是走两次。所以，S向a1、b1连边，a2、b2向T连边，边权为2an、2bn，判断S是否满流。只是需要注意一下，还要重新建图，S改向a1、b2连边，
2018-04-02 19:45:11
241
原创 随手写
1、博弈论 ①搜索模板+打表找规律 ②Nim相似，关注“模仿操作”2、概率期望 ①对概率，设一堆未知数疯狂列式子，相信可解3、重要思想 ①补集思想，正难则反 ②每个二进制位单独考虑，二进制特别神奇4、一些优化 ①写出DP方程，构造卷积 ②能枚举的，尝试验证二分性 ③列式子，不断改变表达方式5、一些经验 ①先推好...
2018-03-31 07:26:18
291
原创 BZOJ 1176 Mokia（CDQ分治）
题目链接：BZOJ 1176题目大意：维护一个W*W的矩阵，初始值均为S。每次操作可以增加某格子的权值或询问某子矩阵的总权值（修改操作数M<=160000，询问数Q<=10000,W<=2000000）。题解：CDQ分治。查询操作可以分成4个(1,1)到(x,y)的子矩形的权值和查询，再加加减减。先把操作按x坐标为第一关键字，y为第二关键字排序，然后按操作的先后分治。分治的每一层里，计算左边的修改对
2018-03-30 17:09:42
244
原创 BZOJ 4919 大根堆（LIS）
题目链接：BZOJ 4919题目大意：一棵n个节点的数，从中选择尽可能多的节点，满足：对于任意两个点i,j，如果i在树上是j的祖先，那么v_i>v_j。求可选的最多的点数。题解：先考虑一条链的情况，就是求一个LIS。再考虑一棵树。再次回想LIS经典求法，维护一个序列，即每次新加一个元素时，在维护的序列中找到比它大的第一个元素，替换，最后维护序列的长度就是LIS的长度。所以可以在每个节点开一个mult
2018-03-29 16:59:34
324
原创 在这里堆一些DP题
这里放一些做不出来的DP题，方便复习总结1、题意： 一个序列，nnn个数 (n≤400)(n≤400)(n\le400) w[i]w[i]w[i]，可以删除其中任意段，每次删除获得一定价值。删除的序列满足相邻两数的差为1且数值单增、单减或先增后减（不能先减后增）。已知删除每种长度的序列可获得的价值v[len]v[len]v[len]，求最大价值。题解： 区间DP。感觉设的状态比...
2018-03-22 19:30:40
234
原创 BZOJ1558 等差数列（线段树）
题目大意：给出长为n（n<=100000）的序列v[]，q（q<=100000）次操作，每次对当前序列的[s,t]加上以a为首项b为公差的等差数列，或询问当前序列[s,t]最少能划分成多少段等差数列。题目链接：BZOJ 1558题解：神奇的线段树！ 等差数列差分之后值是相同的，便于统计最少划分数，所以我们可以维护差分数组。 这样修改操作就变成s-1和t+1两个位置的单点加和s~t-1的区间加了。
2018-03-04 21:32:03
450
原创 BZOJ 3938 Robot（超哥线段树）
题目大意：一条数轴上有n个机器人,对其进行m次操作。操作t_i commond k_i x_i （1≤k_i≤n）表示ti时刻将第ki个机器人的速度变为正方向上xi格每秒；操作t_i query则是询问ti时刻离原点最远的机器人到原点的距离（t1≤t2≤t3≤…≤tm，若同一时间发生多次操作，则按读入顺序依次执行）题目链接：BZOJ3938题解：以时间为x轴，位置坐标为y轴，commond...
2018-03-01 17:18:01
389
1
原创 一些模板（后缀数组+虚树+辛普森积分+凸包+博弈论搜索+矩阵求逆+高斯消元+半平面交+LCT基本操作+状态压缩+序列自动机+后缀自动机+三模数NTT+FWT+分治FFT+Pollard Rho质因数）
后缀数组+虚树+辛普森积分+凸包+博弈论搜索+矩阵求逆+高斯消元+半平面交+LCT基本操作+状态压缩+序列自动机+后缀自动机+三模数NTT+FWT+分治FFT
2018-02-24 09:37:02
503
4
原创 洛谷P1290 欧几里德游戏(博弈论)
题目链接：洛谷P1290 题目大意：给出两个正整数n和m，Stan先手，Ollie后手，轮流操作，每次取较大的数减去较小的数的正整数倍（得到的数不能小于0），得到0的人胜利，问最后胜者是谁。这是一道比较简单的题，但是感觉分析的思路蛮有意思，所以放到这里。分析如下： 1、最后的胜负能由n和m唯一确定，所以设 result(n,m) result(n,m) 表示先手是否必胜 (n≥m) (n\g
2018-02-23 22:04:55
464
原创 HDU4903 The only survival（计数神题）
题目链接：HDU 4903 题目大意：给出n个点的无向完全图，确定每一条边的长度（1~L之间的任意数），使得1到n的最短路是k。输出方案数对1000000007取模，多组数据(组数题解：听过一遍没有懂，自己又琢磨了很长时间稍微懂了一些。 大概是先枚举1到每个点的最短路dis（优化之后变成枚举最短路为某个值的点有多少个），按dis排序后，从dis大的点向dis小的点连边，满足：对于任意dis[
2018-01-16 23:02:47
622
3
原创 BZOJ 4006 管道连接（最小斯坦纳树+状压DP）
题目链接：BZOJ 4006题目大意：n个点，其中p (p<=10) 个重要的点，m条无向边。p个重要点分成几类，求同类重要点互相联通的最小花费。题解：说说我的理解，不一定对。只需要某些点联通，想到最小斯坦纳树；看到 p<=10，想到状压。令dp[i][status]表示i点为(某棵)最小斯坦纳树的根，status表示的点都依照题意同颜色建立起通道的最小花费，最终答案 max { dp[i][2
2017-12-21 20:22:05
434
原创 codeforces 757F Team Rocket Rises Again（最短路+支配树）
今天刚刚看了支配树，然而恕我太弱并没有看明白Lengauer-Tarjan算法，比较懵QAQ……不过我倒是学会了在DAG上构建支配树，就贴一道简单题过来吧O(∩_∩)O。如何在DAG上求支配树？ 有向无环图（DAG）里我们可以按照拓扑序构建支配树。 假设当前我们构造到拓扑序中第x个节点编号为v，那么此时支配树中已经有拓扑序第1~x-1个节点了。考虑所有能够直接到达v的节点，对于这些节
2017-12-13 14:44:52
521
原创 洛谷P2422 良好的感觉（简单数据结构复习）
这道题不是很难，只是太久没有敲过ST表和单调栈，就当贴个板子咯。而且，这道题的做法有很多，也比较常用，所以写一写这个题的题解吧 (*^__^*) 嘻嘻~题目链接：洛谷 P2422 题目大意：找出一段区间，使得“区间最小值×区间和”最大。 题解：单调栈 这种题有一个常见的思路是用枚举最小值是谁，然后就能确定区间长度。所以可以用正反两遍单调栈，处理出某个点作为最小值时左右两边各能扩展到哪里。最后
2017-10-15 09:56:02
381
原创 BZOJ3312 不找零（状压DP）
题目链接：BZOJ 3312 题目大意： 按顺序买 N个物品(1 <= N <= 100,000)，第i个物品花费c(i)，(1<=c(i)<=10,000)，用K（1<=K<=16）个面值的范围是 1..100,000,000 硬币支付。购买过程中，可随时停下来付款，每次付款只用一个硬币，支付从上一次支付后到现在的这些所有物品的价格（如果钱够）。如果硬币面值大于所需的费用，不找零。计算买完N个
2017-10-11 21:08:34
270
原创 BZOJ1079 着色方案（高维DP+神奇的状态）
题目链接：BZOJ 1079 题目大意：n个木块，排成一行，染成k种颜色，相邻两块颜色不同，求方案数。（各颜色有c1，c2，……，ck个，1<=k<=15,1<=ci<=5，颜料正好可以染完所有木块）题解：这道题是个DP。 - 有一个比较好想的思路是写15维的DP，每一维记录某种颜色还剩几个，但5^15的复杂度是肯定过不了这个题的。所以就有一种巧妙的状态设计：按ci将颜色分类，因为c在1到5之
2017-10-11 11:30:47
386
原创 BZOJ1087 互不侵犯king（状压DP）
题目链接：BZOJ 1087 题目大意：在N×N (1<=N<=9)的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。（国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子） 题解：看N的范围1<=N<=9，大概就是状压DP了。把行的放法压起来，状态还是比较好想的。 f[i][j][now]表示前i行一共放了j个king，并且第i行的放法为now时的方案总
2017-10-11 09:44:31
371
原创 vijos1264 神秘的咒语（DP）
题目链接：vijos 1264 题意：求两个序列的最长上升公共子序列 题解：f[i,j] 表示以a序列的前i个为结尾、以b序列的第j个为结尾的最长上升公共序列长度,转移见代码（还是比较好理解的吧(⊙v⊙)）。 code#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>
2017-09-12 20:40:08
503
原创 BZOJ 4010 菜肴制作（拓扑排序）
题目链接：BZOJ 4010 题解： 拓扑排序是比较明显的，两种思路：正着，每次找字典序最小的倒着，每次找字典序最大的如果有限制条件<4,1>，那么最优解是（4,1,2,3），但正着找字典序最小找到的却是 （2,3,4,1），因此正着行不通。反着的正确性想想似乎有道理，反向建边，每次字典序最大的放到最后，就能让字典序小的尽量靠前了吧。（我不会证明QwQ……） code(代码还是比较简单的
2017-09-10 21:32:53
335
原创 Usaco 奶牛抗议（树状数组+DP+离散化）
题目链接：奶牛抗议 题解：用 dp[i] 表示前 i 头奶牛的分组方案，s[i] 表示前 i 头奶牛的理智度的和，那么就有转移 dp[i]=sum{ dp[j] } ( s[i]-s[j]>=0 且 i>j )。所以，把前缀和hash成树状数组下标，树状数组里存dp的值。时间复杂度 O(n*log n)。 code#include<iostream>#include<cstdio>#incl
2017-09-10 20:40:34
378
原创 BZOJ1123 BLO（tarjan割点）
题目链接：BZOJ 1123 题目大意：一张无向图中，对于每一个点，求删去这个点后有多少对点不能相互到达。 题解：tarjan求割点。求出删除一个点后形成的几个联通块，任意不同联通块里的点不能互相到达。代码(有参考hzwer大神(*^__^*) )#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#incl
2017-09-08 08:40:19
353
原创 BZOJ2038 小z的袜子（分块版莫队）
题目链接：BZOJ2038 第一次看莫队算法，写写感受。 看的第一篇博客是用平面哈夫曼距离最小生成树写的，看懂了原理，但不会写代码。后来看到了一个更简单的替代品分块，时间复杂度相近，为 n*sqrt(n) 。原理不难理解，基本思路就是通过改变处理询问顺序，降低复杂度。分块版的是按询问的左端点所在块的编号为第一关键字，右端点为第二关键字，排序之后直接暴力就好了。复杂度分析（每次修改复杂度为 O(1
2017-08-27 08:41:38
318
原创 树链剖分+线段树
之前就学过树链剖分的原理，只会树链剖分LCA，今天做了一道“树链剖分+数据结构”的题，虽然很简单，但可以当模板用一用，粘到这里。树链剖分简单描述（可能不大对）：第一步就是划分轻重边，按每一棵子树的大小，与形成子树最大的一个子节点是重边，其余为轻边，然后就得到了轻重链。 之后就可以用数据结构维护一些东西了，可以是点也可以是边。对节点 x 到 y 间的路径进行操作时，分别找到 x 和 y 所在链（
2017-08-26 19:48:04
584
原创 BZOJ3631 松鼠的新家（差分）
题目链接：BZOJ 3631 题解：从节点x走到节点y经过的所有节点都要放一块糖果，树上两个点之间的路径是唯一的，经过lca(x,y)，所以可以差分来做。x 和 y 处 +1，lca(x,y) 和 fa[lca(x,y)] 处 -1，从下到上累加答案即可。又因为一条路径的终点是下一条路径的起点，除了a1和an，其他节点处的糖果数都多算了一次，减掉1；an处不用放糖果，也减掉1；PS：倍增lca好久
2017-08-25 15:31:23
424
原创 BZOJ2152 聪聪可可（树形DP/点分治）
题目链接：BZOJ2152 题意大致是找树中多少点对之间的距离%3为0 题解：可以树形DP，也可以点分治，两个代码都粘过来咯 (上面是树形DP，下面是点分治)//树形DP#include<iostream>#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using name
2017-08-24 18:14:50
429
原创 BZOJ4016 最短路径树问题（点分治）
题目链接：BZOJ4016题解：先跑一个最短路图，然后按照结点编号从小到大dfs一遍，dfs树即为题目所要求。然后就是点分治的经典做法，路径分为经过根节点的和不经过根节点的，不经过根节点的路径一定属于其某个子树中，分治来做。#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>
2017-08-24 16:09:54
414
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人