- 博客(39)
- 收藏
- 关注
RSS订阅原创 错误集
5.27 ZJ W11 T4#include<iostream>#include<cstdio>#include<cstring>#include<set>using namespace std;struct Node{ int pos,val; bool operator < (const Node &A) const{...
2018-05-28 19:05:54
195
原创 UVA11181条件概率
题意：n<=20个人,给出每个人买东西的概率,知道有r个人买了东西，问每个人买东西的概率是多少求P（i买|共r人买）=P（共r人买且i买）/Ｐ（共r人买）枚举每种r个人买了的情况，算出这种情况的概率，然后累加到Ｐ（共r人买）。再统计出这种情况下每个人，累加到这个人买且共r人买的概率#include<iostream>#include<cstdio>#include...
2018-05-23 21:57:55
178
原创 UVA12716 GCD XOR
题意：给出n(3e7),求出有多少对1<=b<=a<=n满足gcd(a,b)=a^b(5s)nlog^2n:设c为a^b,则根据异或性质a^c=b。且c=GCD（a,b），所以c为a的因数，这样如果枚举a,c可以求出b，同时因为c是a的因数复杂度也会降低。外层枚举c内层a的话复杂度应该是n/1+n/2+...n/3,大约是logn，加上判gcd的logn应该是nlog^2nnlo...
2018-05-22 16:01:29
216
原创 UVA1633 禁止回文子串
给出n<=400,k<=10，问长度为n且不含长度>=k的回文子串的01串有多少个dp的过程有点像模拟构造的过程，可以发现一个长度>=k的回文子串一定包含一个长度为k或k+1的回文子串，所以构造的时候我们就防患于未然，禁止构造出长度为k或k+1的回文子串，那么更长的就不会出现了#include<iostream>#include<cstdio>#...
2018-05-11 20:46:07
347
原创 【树形dp】5.6 Week8 移动棋子
题目大意：你有一棵 n 个点的有根树，每条边都是带权的，其中 1 号点是这棵树的根。你开始你把一个棋子放在 1 号点位置。接下来你可以做如下的事情：• 将这个棋子移向它的某个儿子。代价为这条边的权值。• 将这个棋子跳回 1 号节点。这个操作不需要任何代价。• 在这个棋子所在的位置设立存档点。注意你只能在整棵树上设立一个存档点，如果之前在某个节点上设立过存档点，那么原来的存档点会消失。这个操作不需要...
2018-05-08 16:53:22
217
原创 2018浙江省赛 括号序列
题意你有 n 个元素排成一行，每个元素都由一个括号 (左括号或右括号) 和一个权值构成，我们将第 i 个元素记作(si; vi)，其中 si 为 “(” 或者 “)”，vi 为一个整数 (可能为负数)。你每次可以选择一对相邻的元素，对应的括号为 “()”，即找到一个 k(1 k < n)，满足 sk 为 “(” 且 sk+1 为“)”。你可以交换第 k 和 k + 1 个元素 (包括括号和...
2018-05-07 20:30:12
415
原创 【dp&贪心】UVA1228 整数传输
贪心1：首先可以规定，k（待接收数）中的所有0和1均按原顺序接收，即每个数不会比k中它前面的同类数早被接收，因为每一个这样的情况，都可以调整成按原顺序接收，所以这种情况得到的数删去对答案没有影响例如上图，调整两个0的接收顺序，会发现两个数的最大时间延迟会变小，更容易符合条件贪心2：每当需要接收一个0或1时，一定接收k中还未被接收的最靠左的，因为这个数早晚都要接收，留到后面接收容易超出时间限制。所以...
2018-05-04 17:06:58
302
原创 方块消除 UVA10559
题意：给一排方块，每个方块有一个颜色，每次可以选几个连续颜色相同方块消除，得分为方块数平方，求最大总得分。按照一般的序列dp思路，dp[i][j]应当从dp[i][k]和dp[k][j]中转移(i<=k<=j)，但本题中可能两边都剩下方块一起消，无法转移，状态也不好表示。我预处理时先用分块的思想，把颜色相同的小块分为一个大块。所以这个题以[i,j]这个区间中最后一个方块j怎样消除为决策...
2018-04-28 19:27:55
474
原创 【dp&减少状态】轻松爬山 UVA12170
题意，给定n（<=70）座山的高度和d（<=1e9)，每座山可以花x的代价使高度增加x或减少x，使得两座相邻的山高度差<=d,求最小代价，无解输出impossible首先大致想到，可以用f(i,k)表示已经调整完了第i座山，第i座山调整成了高度k，花费的最小代价但是很明显，k的范围是1e9，显然不通，所以就要想办法简化这一维当n=3，只能调整第二座山，第二座山调整后的范围应为(h...
2018-04-26 19:21:22
222
原创 【dp&技巧】书架 UVA12099
题意，n(<=70)本书,每本书有一个高度(<=150),宽度(<=30)，把他们分到书架里的三层，每层的高度就是这层里所有书的最大高度，宽度就是所有书的宽度和。ans=三层高度和*三层宽度最大值，求ans最小值又是一道ACM毒瘤好dp,最近做dp感觉出来了点规律，很多时候可以制定一些规则，使无论怎样都有最优答案都能满足这些规则，这样减少了最优答案的数量dp自然就简化了。所以在这...
2018-04-24 21:48:04
266
原创 【状压dp&预处理难】Fun Game UVA1204
题意:一群小孩(至少两个)围成一圈做游戏。每一轮从某个小孩开始往他左边或者右边传手帕。一个小孩拿到手帕后在手帕上写上自己的性别，男孩写B,女孩写G，然后按照相同的方向传递给下一个小孩，每一轮都可能在任何一个小孩写完后停止，现在游戏已经进行了n轮，已知n轮中每轮手帕上留下的字,问最少可能有几个小孩。ACM的题果真好题。书上说的已经非常好了，首先把能被包含的串去掉，这些串对答案没有贡献。剩下的工作就是...
2018-04-23 23:13:38
162
原创 【状压dp】UVA1252二十个问题
题目大意：有n件物品，每件物品有m个特征，可以对特征进行询问，询问的结果是得知某个物体是否含有该特征，要把所有的物品区分出来（n个物品的特征都互不相同）至少需要多少次询问？考虑状态的表示，可以用一个集合s1表示已经询问过的特征集合，s2表示已经确定物体有的特征集合。在每个状态下，考虑询问哪个特征。首先明确一个问题，在一个状态下，问哪个特征是由你决定，但得到什么回答就不一定了。比如询问一个所有物体中...
2018-04-15 19:17:14
149
原创 【状压dp】校长的烦恼UVA10817
又是一道看题就懵逼抄题解的题每个状态可以用三个集合表示，没有人教科目集，只有一个人教科目集，至少两人教科目集，可以发现任意两个集合可以推出来第三个，为了方便我选了前两个然后另一维是当前已经对前i个老师做完决策了，对每个老师有选和不选两种决策，但是前M个必须选。所以当没人教科目集和只有一人教科目集为空集时和所有老师都考虑完时为边界怒交一发，不出意外又WA。然后看了一眼debug不过的数据发现，有一种...
2018-04-15 17:09:45
245
原创 【背包dp】团队分组UVA1627
今天上午很神奇地被两个dp用小错误卡了一上午。。。题意：给出每个人是否认识另外的人（可能单向认识），分两组让每组中的人互相认识，使两组人数差最小并输出方案把每对不是互相认识的人连边，代表他们不能分到一个组，这样的话连通分量可能有很多个，然而各个连通分量之间是互不影响的，所以分别二分图染色就可以，然后统计两种颜色在这个连通分量里分别有多少人。这样就把人分成了k个组，每个组中可以让染黑色的人去Team...
2018-04-15 14:08:10
349
原创 【树形dp】完美的服务UVA1218
一道树形dp卡了这么久。。。题意：一个书中，每个点都可以安服务器，问最少多少服务器可以使每个不是服务器的点恰好只与一个服务器相邻把每个点分情况讨论1.自己安服务器 2.自己不安，父节点安，这样所有子节点不能安 3自己不安，父节点不安，这样有且只有一个子节点安设dp[i][0]为i及其子树，当i安服务器时最少服务器。dp[i][2]表示i的父亲安儿子不安，dp[i][1]表示i的一个儿子安父亲不安d...
2018-04-15 10:53:04
201
原创 UVA4847排序二叉树
题意：给出n，给出一种排列， 问有多少个排列，依次插入二叉查找树后和它形态一样（最普通的不旋转，别想多）首先明确，在一个排列中，一个数后面的数，比它小的一定在它左子树，比它大的一定在右子树。所以在这棵排序二叉树中，如果一个节点的左子树中每个节点确定了插入顺序，右子树中每个节点规定了插入顺序，那么对于这个节点来说，只要它后面每个小于它的数，在小于它的中排名不变，比它大的数同理，那么无论怎样排列都不会...
2018-04-05 17:35:04
142
原创 王国LA4730
题意简化一下平面上有n个点（n<=100000,坐标<=一百万），两种操作，一种是选两点连边，二是问在某一y坐标上有几个联通块，以及这些联通块连接了多少个点总体思路是并查集+线段树，在并查集合并时维护线段树。开两棵线段树，一颗维护每个y坐标上的联通块上的点数目，一颗维护每个y坐标上的联通块数目注意这个题每个点的x坐标对答案没有影响，所以只记录一下高度就可以了并查集维护四个量，父亲，以此...
2018-04-03 19:41:11
146
原创 UVA11019 矩阵匹配器
题意简化，给你一个大矩阵和一个小矩阵，求小矩阵在大矩阵中出现了多少次，矩阵都不得旋转这个题就是字符串匹配的二维版，然而不像数据结构，它的二维版并不复杂只是一行行拆开处理，但复杂度十分优越，几乎等于读入时间（vjudge上跑了0ms）首先将小矩阵的每一行分开看，这样小矩阵就成了多个模板串，建个AC自动机。再用大矩阵的每一行去AC自动机里找匹配，例如大矩阵第i行的第j位与第k个模板串（小矩阵第k行）匹...
2018-04-02 21:23:47
223
原创 NOI2011阿狸的打字机
刚学完字符串算法做一做题，这道题的质量的确很高，做完以后感觉对AC自动机有长进一下的神仙思路来自yyb dalao%%%，蒟蒻开始只想到了40分暴力，全程靠题解STEP1首先直接处理出所有的串再裸KMP好写，但是觉得得分应该不高，也没有人说能拿多少分这个题正解的第一步是要想到AC自动机，准确地说和Fail指针关系密切首先明确一个定理，如果当前沿着目标串A在trie树下向下走，走到了一个节点，发现这...
2018-04-02 19:18:25
170
原创 愚人节两轮
day1,三个板子题，t3数据出锅暂且不表，t1虽然对规律似懂非懂，但是还是靠打表找出了规律。然而也不知道脑子是不是抽了，内存充裕到要死手欠把后缀数组求Sa的桶从MAXN改成了200（当时我好像想的是ASCII码最多到122？exm?后来一想排名会越来越大最后也会到MAXN啊，还调了一节多晚自习无解了）day2就更加的无解了，t1KMP没看出来怎么转化也就还则罢了，送的十分也没拿上？还zz地调了一...
2018-04-02 15:07:56
211
原创 UVA11468子串 AC自动机+概率DP
最近在学习字符串算法，学到KMP和AC自动机总有种似懂非懂的感觉，这个题的思路也是看的STDKMP个人感觉KMP的精髓就是失配函数，在当前匹配失败的情况下不必重头推倒再来，而是从特定的位置。i位置的失配函数为f[i],可表示i位置失配后去f[i]位置找，是因为f[i]位置之前的模板串与i位置前的模板串的等长后缀是相等的，这样做下去当发现整个模板串都遍历完成，就是找到了模板串作为目标串子串的结束位置...
2018-03-30 16:09:15
204
原创 最大流+Tarjan舞动的夜晚
舞动的夜晚 CH Round #17描述L公司和H公司举办了一次联谊晚会。晚会上，L公司的N位员工和H公司的M位员工打算进行一场交际舞。在这些领导中，一些L公司的员工和H公司的员工之间是互相认识的，这样的认识关系一共有T对。舞会上，每位员工会尝试选择一名Ta认识的对方公司的员工作为舞伴，并且每位员工至多跳一支舞。完成的交际舞的数量越多，晚会的气氛就越热烈。顾及到晚会的气氛，员工们希望知道，哪...
2018-03-26 17:06:15
406
原创 [SDOI2009]虔诚的墓主人
这个题是今天上午模拟赛做的，考场上代码最后时间紧写得巨丑，所以改完以后还是巨丑80分做法这是考场上写的，然而数学实在太渣，不知道在模数下不能做除法，组合数部分写ci了组合数预处理首先都知道组合数是必须要处理的，然而这个题直接处理阶乘做组合数公式是不行的，因为模数下不能做除法。然后既然都要处理出来，又不需要O(1)，可以用杨辉三角，如果普通的杨辉三角，可以做到3000*3000（其实组合数的处理决定...
2018-03-25 18:30:01
278
1
原创 ZJOI2006书架Treap做法
作为一个刚学Treap只会打板子的菜鸡，这个做法还参悟题解了一节课才参悟出来的，感觉这个方法很巧妙变量解释A[i]表示编号为i的书的优先级，优先级第k小就是从上向下数第k本书树的节点Node.val表示优先级，也是平衡树排序的关键字Node.num表示该节点对应书的编号因为没有两个书的优先级是一样的，所以元素不重复，getrank函数好写些五个操作Top：删去原来该书的代表元素，把该书优先级改为当...
2018-03-22 16:14:50
243
原创 [SDOI2010]星际竞速
这道题和最小路径覆盖比较像，都是把点拆成x部和y部，最小路径覆盖直观地看可以说是在y部中给x部的点找后继，这个题直观地看可以说是在x部中给y部的点找前驱。以下建模方法摘自学长题解思路和最小路径覆盖类似，先进行拆点，把每个点u拆成u和u‘。对于跳跃模式【忘了叫什么模式了】就从源点往u'连一条流量为1，费用为边权的边。对于星球间的航道(u,v)【假设u<v】就从u往v'连一条流量为1，费用为边权...
2018-03-08 09:10:38
288
原创 20180305T3【bzoj1513】TET
给定一个矩阵，初始每个位置上的元素都是0，每次选择一个子矩形，将这个子矩形内的值修改为这个子矩形内的最大值+h，求最终所有位置上的最大值第一行输入D,S,N,就是长宽和操作数后面每行读入5个数，d,s,h,x,y，表示把(x,y),(x+d-1,y),(x,y+s-1),(x+d-1,y+s-1)为四顶点的子矩阵进行操作h就是题目描述里的h注意行列是从0开始数的这个题很明显可以看出是一个二维线段树...
2018-03-07 19:16:29
135
原创 20180305T1 【STARAS】poj2482
假定天空是一个平面，每个星星都有一个坐标(x,y)，每颗星星都有一个亮度C，代表它的亮度。窗户是长方形的，有固定的长和宽，边平行于x轴和y轴。你的任务是告诉我如何摆放窗户，才能获得在窗口内所有星星的亮度总和最大值。注意，边框的星星不算。窗口可以被平移，但不允许旋转。输入在输入中有几个测试用例。每一行的第一行包含3个整数：n，w，h，表示星形的数目，矩形窗口的水平长度和垂直高度。然后N行如下，有3个...
2018-03-06 22:00:02
166
原创 【模板】可持久化线段树 1（主席树）
模板没什么好说的，这个离散化方法比较好用#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<map>#define LL long long#define fr(i,s,t) for (i=s;i<=t;i++)#...
2018-03-05 20:49:52
127
原创 20180305T2[USACO5.5]矩形周长Picture
[USACO5.5]矩形周长Picture横线和竖线分两遍分别求用扫描线扫一遍，扫到一个地方先加边，再删边，这样每次操作对答案的贡献就是整个线段树覆盖区域长度前后的差值（绝对值），这样可以省去query函数这样题目就转化成了一个维护线段树，支持区间加，维护区间不为0的数的数量tree[root].len表示区间覆盖的长度，tree[root].col表示区间被完全覆盖的次数#include<...
2018-03-05 20:45:54
247
原创 [SDOI2009]HH的项链
dalao们都告诉我这是莫队板子题然而像我这种菜鸡肯定不会莫队啊题意简化一下就是静态求一个区间内数的种数我们记录pre[x]，为数列中第x个数上次出现的位置，如果之前未出现过则为0所以显然区间【l,r】内pre[i](l<=i<=r)如果>=l的话就是重复的，这样对答案有贡献的就是pre[i]<=l-1的这样就转化为了一个二维数点，x轴为数列位置，y轴为pre值，原来数列中...
2018-03-04 17:23:45
175
原创 SDOI2008校门外的区间
这道题作为前天的模拟赛题，考场上我在还剩一个半小时的情况下居然选择求稳打暴力，水过了40分，然后就坐看cansult和refun这俩dalaoAK...一开始我的想法是，把区间看成两点之间不包含端点的小区间和端点构成的集合，然后分开处理，这个做法可能暴力还是可以的，然而如果要用线段树的话，就要开两颗线段树正确做法应该是把每个点拆成三个点，）就是标记第一个点，】和【就是标记第二个点，（就是标记第三个...
2018-03-03 16:01:27
193
原创 NOI2009植物大战僵尸
因为昨天做了一道最大获利，所以感觉思路差不多对于每个植物，首先思考如果它们score都是整数的时候，贪心就好了，可以到达的就攻击然而植物的score有负数，所以植物就可以分为获得收益的和付出代价的这样大体思路就是分为两部分，代价连源点，收益连汇点，中间有保护关系的连不可删边，再跑个最小割然而这个题的细节还是让我这个菜鸡一遍爆0首先，显而易见的保护关系是攻击型的植物对攻击位置的保护关系但是还有一些保...
2018-02-28 10:12:22
286
原创 NOI2006最大获利
这个题的题意简化一下就是选每个点有个代价，然后俩点凑一对产生点化学反应能获得一个收益，让你求采取最优方案能获得多大收益（好像最优方案好多都是跑网络流）简化一下，想获得一个收益，需要满足它的两个前提，如果这两个前提有一个不满足，那就是放弃了这个收益这样建模方式就出来了x部为每个用户，y部为每个中转站，源点向每个用户连边，边权为收益x部的每个用户向y部自己需要的中转站连边，边权为INF然后y部每个中转...
2018-02-26 20:02:49
205
原创 UVA 11082
这个题的建模方法非常妙首先处理出每一行和每一列所有元素值的和先开一个源点和一个汇点，源点连所有的行，所有的列连汇源点到行的容量为该行元素和，列到汇点同理，每一行到每一列的容量为最大值20，这样跑一个最大流，行i到列j的流量即为答案i,j的值，最后如果有解源点和汇点相邻的边都应该是满流例如这一行的元素和是16，源点流过来16，再把16分配到每一列去但这样有个问题就是中间可能有0流所以就预先先把每个位...
2018-02-25 10:45:08
170
原创 LA3415 保守的老师
如果四个条件都满足的话，就把两个学生连边，代表这两个学生不能共存最后肯定是一个二分图，因为一个学生不是男生就是女生，然而男生和女生两部内部是没有连边的所以问题变成了删去最小的点，使所有边最多只有一个点还是二分图最小覆盖（和最大独立集互补），不需要求方案，跑一遍就可以了#include<cstdio>#include<cstring>#include<vector&...
2018-02-25 07:30:23
200
原创 UVA 11419 SAM I AM
考虑每个点，因为必须被打掉，所以就是要不被所在行的子弹打掉，要不被所在列子弹打掉所以就建一个二分图，行和列为x部和y部，若i行j列有目标，就把x部i和y部j连边如果把在某一行或某一列发射子弹表示为把对应点涂色，那么问题转化为了把最少的点涂色，使得每一条边至少有一个点被涂色这就变成了一个二分图最小覆盖如果只是求需要的点数只需要求出最大匹配就好了，但是还要求方案所以在跑完匈牙利最大匹配以后，从x部所有...
2018-02-24 20:20:02
198
原创 Luogu食物链做法2
这个题的做法2比做法1好想以下距离都在 mod 3意义下到最后所有动物的关系可以用树表示，d[i]表示节点i到当前fa[i]的距离，我们规定若d[x]+1=d[y](规定成-1也可以)，代表x吃y那么如果x、y同族，那么如果规定x当前祖先到y当前距离为的d[y]-d[x],这样x到y祖先距离为d[x](到自己当前祖先距离)+d[y]-d[x]=d[y]=y到y祖先距离，所以x\y同族如果x吃y，那...
2018-02-24 20:10:41
197
原创 Luogu2024食物链做法1
第一次看见这个做法就觉得很妙这个做法把所有点复制成三份分成三个阵营其中第i个阵营吃第（i+1) mod 3个阵营所以第i个阵营的动物x和第(i+1) mod 3个阵营的动物y如果联通的话，代表x吃y如果相同阵营的两个动物联通代表他们是同类这样的话把两种动物联通就是确立了一种关系，这种联通代表确立关系很像很多二分图的题，把符合条件的两个对象联通，在二分图上跑求解然后你看代码就会发现判断联通关系自始至...
2018-02-24 18:36:31
298
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人