- 博客(1165)
- 收藏
- 关注
RSS订阅
原创 康复计划
几天前还在想 这辈子都不要再碰这个东西了可是既然已经入了计算机的坑 哪有不写代码的道理到了大学之后 之前的oi基础还是在很多方面给了我很大程度的帮助几个小时之前无意间翻到之前的游记 cf和bc和bz上的记录 还有某些能让人笑出腹肌的日常还是很怀念以前的日子但是现在真的是老了啊 退役了之后就再也不可能再变回之前的那个我了吧以前烂熟于心的东西全部都离我远去 那种崩溃谁又能理解的了呢选择不...
2018-09-27 21:17:30
2241
18
原创 [NOI2002]银河英雄传说（并查集）
题目描述传送门解题思路before表示i前面还有几个元素，count[i]表示i所在的有几个元素并查集代码#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;int father[30005],before[3...
2020-03-10 11:24:28
333
原创 写给NOIp2018前的你们
不知不觉中已经退役一年多了，现在的高二认不得几个，低三届的学弟学妹就更别说了，可能连照面都没打过。所幸圈子里还有各种因为博客认识的我也弄不清是高一还是高二的孩子们，还能让我得到一点点关于OI的消息。我不知道NOI P对于大家来说到底意味着什么。可能对于有些人来说，拿到一等之后就已经完成任务可以回教室学文化课了。对于有些人来说，它是WC的敲门砖，也是来年省选中说小也小说大也大的一部分，或者说，这更...
2018-10-14 11:13:56
1735
1
原创 [BZOJ1266][AHOI2006]上学路线route（spfa+最小割）
题目描述传送门题目大意：给出一个n个点m条边的无向图，每一条边有长度和代价，先求1-n的长度最短路，在求去掉最小代价的边，使1-n的长度最短路变大题解首先建出来最短路径图，然后连边容量为代价，跑最小割就行了最短路径图也就是图上的每一条边都在至少一条最短路中，判断的时候只需要判断边(u,v,c)是否满足dis(u)+c=dis(v)就行了 让这些最短路都不能1和n连通所以跑一下最小割就行了代码#in
2017-05-11 22:23:42
1122
原创 [BZOJ4128]Matrix（BSGS+矩乘）
题目描述传送门题目大意：给出矩阵AB和模数p，求最小的正整数x，满足Ax≡B(modp)A^x\equiv B\pmod p题解裸的BSGS，直接换成矩阵乘法就好了 注意map里放结构体的话要重载一下<和==代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#inc
2017-05-11 22:19:58
959
原创 [BZOJ3613][Heoi2014]南园满地堆轻絮（贪心）
题目描述传送门题目大意：给出序列a，构造一个严格上升的序列b，使得max(|ai-bi|)最小题解考虑两个数，如果是上升的就不用管了，如果是下降的需要把这两个数都变成中间值才能保证答案最小 所以答案就是最大的(逆序对差值+1)/2代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<
2017-05-11 22:16:31
1093
原创 [BZOJ1570][JSOI2008]Blue Mary的旅行（最大流）
题目描述传送门题目大意：有n个点m条边的图，每一条边一天只能通过一定数量的人，每个人一天只能走一条边，问T个人全部从1走到n所用的最短天数。题解首先二分答案k，然后判定k天能不能过去 每个点拆k+1个点，分别表示k+1个时刻，然后对于从第i个时刻到第i+1个时刻连边，连对应的m条边，然后对于每一个时刻的1号点和n号点s->1,n->t，然后判断最大流是否>=T就行了 但是我并没有写二分，而是枚举
2017-05-09 21:33:31
1118
原创 [BZOJ4336][BJOI2015]骑士的旅行（树链剖分+线段树+multiset+归并）
题目描述传送门题目大意：n个点的一棵树，有m个骑士，每个骑士居住在n个点中的一个，有一个武力值fi，有三种操作： 1 x y 询问居住在树链x-y上前k大的骑士的武力值 2 x y 编号为x的骑士居住地改为y 3 x y 编号为x的骑士武力值改为y题解k比较小 树链剖分，对线段树中的底层节点维护一个multiset，维护所有居住在这个点的骑士的武力值，然后线段树中的每一个点开一个结构体
2017-05-06 22:04:36
1295
原创 [BZOJ4152][AMPPZ2014]The Captain（堆优化dijkstra）
题目描述传送门题目大意：给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。题解分别按照xy排序，然后相邻点连边，跑最短路就行了 写了一发堆优化dijkstra，竟然把大小记反了！代码#include<algorithm>#include<iostream>#include<cstring>#include<
2017-05-05 23:11:47
1024
1
原创 [BZOJ1237][SCOI2008]配对（dp）
题目描述传送门题目大意：你有n 个整数Ai和n 个整数Bi。你需要把它们配对，即每个Ai恰好对应一 个Bp[i]。要求所有配对的整数差的绝对值之和尽量小，但不允许两个相同的数配 对。题解这题并没有想出来。。。 首先排序，一个结论是一个数配对的数与其距离不会超过2，也就是最多一个3的置换 这个证明的话，直观的理解是如果没有冲突的，直接对应位置配对就好了，然后有冲突的话应该尽量减少置换的大小，所以3
2017-05-05 17:40:33
928
3
原创 [BZOJ3209]花神的数论题（数位dp）
题目描述传送门题目大意：sum(i)表示i的二进制中1的个数，求∏i=1nsum(i)\prod\limits_{i=1}^n sum(i)题解f(i,0/1,j)表示二进制为i位数，是否卡上界，有j个1的数的个数 dp完了之后快速幂一下就行了代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#i
2017-05-05 14:08:46
731
原创 [BZOJ3566][SHOI2014]概率充电器（概率期望+树形dp）
题目描述传送门题目大意：一棵树，每一个点初始有一个概率为1，然后每个点可以沿着边向四周扩展，每条边有一个概率可以经过，问最终为1的点的个数的期望。题解f(i)表示点i从父亲扩展不到的概率，g(i)表示点i从儿子扩展不到的概率 最终的答案是 sigma 1 - f(i) * g(i) * (1-p(i)) 转移的时候，先计算出来某一个点扩展不到的概率，应该为f(i) or g(i) * 点不为1的
2017-05-05 11:12:24
959
原创 [BZOJ4545]DQS的trie（广义后缀自动机+lct）
题目描述传送门题目大意： 先给出一棵trie，然后支持几种操作 若opt=1，则是一组询问，询问当前trie的本质不同的子串数目是多少。 若opt=2，则后面跟两个整数rt,si，表示以点rt为根向下长出一个子树，大小为si。即加入一个子trie 若opt=3，则是一组询问，后面输入一个字符串S，询问字符串S在当前trie中的出现次数。 题解这题其实是substring和生成魔咒的结合版
2017-05-04 21:08:23
1118
原创 [BZOJ4319]cerc2008 Suffix reconstruction（贪心+构造+后缀数组）
题目描述传送门题目大意：给出一个sa，求一个合法的字符串的方案，或无解-1。题解无解就是a..z都填完了但是还不够 所以肯定是按照rank填，填的过程中相邻两个rank的地方尽量是一样的，实在不行再不一样 按照rank从小到大填数，对于相邻两个rank，比较两个的后面那个位置，如果后面的那个位置前面的rank小于后面的rank，说明这两个位置是可以填一样的，否则不行代码#include<algo
2017-05-04 17:24:23
676
原创 [BZOJ3513][MUTC2013]idiots（FFT+组合数学）
题目描述传送门题目大意：给定n个长度分别为ai的木棒，问随机选择3个木棒能够拼成三角形的概率。题解这道题要根据三角形的两边之和大于第三边来做，其实判定的条件就是随机选出来的三条边中较小的两条之和大于第三条边 首先容斥一下，用总的方案数减去不合法的方案数 令F(i)表示两条边和为i的方案数，a(i)表示长为i的木棒有多少个，那么可以写成一个卷积的形式F(i)=∑a(i−j)a(j)F(i)=\su
2017-05-04 15:35:10
1027
4
原创 [BZOJ4445][Scoi2015]小凸想跑步（半平面交）
题目描述传送门题目大意：一个凸n边形，N个顶点按照逆时针从0～n-l编号。现在小凸随机选择多边形中的某个位置，标记为P点。将P点与n个顶点各连一条边，形成N个三角形。如果这时P点，0号点，1号点形成的三角形的面 积是N个三角形中最小的一个，小凸则认为这是一次正确站位。现在小凸想知道他一次站位正确的概率是多少。题解设选的位置坐标为(x,y)，用叉积化一下式子 (x1−x)(y2−y)−(y1−y)
2017-05-04 14:02:10
954
原创 [BZOJ2756][JLOI2010]铁人双项比赛（半平面交+三分法）
题目描述传送门题目大意：n个人参加比赛，先跑步和自行车的总路程为s，其中跑步为k，走路为r，每个人跑步和自行车都有一个速度。求出对第n个人最有利的k和r，使其获得冠军，并且领先第二名的时间最多。题解首先将每个人的k-时间方程写出来 y=x/v1+(s-x)/v2=(1/v1-1/v2)x+s/v2 这样得到了n个方程，用半平面交求凸壳（其它比半平面交高明到不知道哪里去了的办法都资瓷 求出凸壳之后
2017-05-04 09:03:36
788
原创 [BZOJ4864][BeiJing 2017 Wc]神秘物质（splay）
题目描述传送门题目大意： 有一列数列，支持以下操作 对于一列数，相邻一段中最大和最小的两个数的差值称为区间极差。 merge x e 当前第 x 个数和第 x+1 个数合并，得到值为 e 的新数； insert x e 在当前第 x 个数和第 x+1 个数之间插入一个能量为 e 的新数。 max x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最大值； min x y 当
2017-05-04 08:55:52
924
原创 [BZOJ1088][SCOI2005]扫雷Mine（dp）
题目描述传送门题目大意：第一行有雷，第二行没有雷，但是有数字。问满足这个数字的第一行的方案数。题解f(i,s)表示满足前i个格子的限制，并且第一行最后三个格子的状态是s的方案数 直接dp就可以了代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using names
2017-05-03 18:51:55
832
原创 [BZOJ1029][JSOI2007]建筑抢修（贪心+堆）
题目描述传送门题目大意：修复每一个建筑都需要一定的时间，如果某一个建筑不能在某一个时刻前被修复就永不能被修复了，问最多能修复多少个建筑题解按照最晚的时刻排序，然后对于一个建筑，如果能修就修，否则让其替换前面一个耗时最长的建筑 和工作安排那道题有点像代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>
2017-05-03 18:49:47
1054
原创 [BZOJ1192][HNOI2006]鬼谷子的钱袋（数学相关）
题目描述传送门题目大意：问最少用多少个不同的数，能组合出来1~m中所有的数。题解显然是所有<=m的2的幂次代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;int n,p;int main(){ scanf("%d
2017-05-03 17:48:32
999
原创 [BZOJ1049][HAOI2006]数字序列（dp）
题目描述传送门题目大意：给出一个数列，要将其改变成单调上升序列，求最少需要改变多少个数，和在改变的数最少的情况下，每个数改变的绝对值之和的最小值。题解第一问，把所有的数减去标号然后求最长不下降子序列就行了 第二问，g(i)表示改好前i个的最小代价，若f(j)+1=f(i)则可以转移，求[j,i]区间内的修改代价可以暴力，枚举一个端点然后将左边的都修改成j，右边的都修改成i，这一步具体的证明可以参考
2017-05-03 17:30:56
898
原创 [BZOJ1048][HAOI2007]分割矩阵（数学相关+记搜）
题目描述传送门题目大意：给出一个n*m的棋盘，每一个格子有一个权，切n-1刀，变成n个子矩形，每一个子矩形的权为所有格子的权值和，求一种方案使这些子矩形的均方差最小。题解均方差的化简方法同棋盘分割：http://blog.csdn.net/clove_unique/article/details/52936610 f(i,a,b,c,d)表示还有i刀可切，当前的矩形为(a,b,c,d)的最小值
2017-05-03 17:24:33
604
原创 [BZOJ1034][ZJOI2008]泡泡堂BNB（贪心）
题目描述传送门题目大意：给出浙江队n个人的权值，和对手n个人的权值，两人战平各得1分，胜2分，败0分，问最好和最坏情况下浙江队得多少分。题解一个田忌赛马问题 首先排序，若当前最弱的>对方当前最弱的，那么打；若当前最强的>对方当前最强的，那么也打；否则用最弱的去打对方最强的 由于两个人得分和一定是2n，第二问就将两个队反一下然后再用2n减去就可以了代码#include<algorithm>#in
2017-05-03 17:20:33
749
原创 [BZOJ1044][HAOI2008]木棍分割（二分+贪心+dp）
题目描述传送门题目大意：有n根木棍, 第i根木棍的长度为Li,n根木棍依次连结了一起, 总共有n-1个连接处. 现在允许你最多砍断m个连接处, 砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小, 并且输出有多少种砍的方法使得总长度最大的一段长度最小. 并将结果mod 10007。题解第一问贪心+二分判定 判定出了答案之后dp一下，f(i,j)表示砍了i刀，砍到第j个的方案数，单调地扫
2017-05-02 21:48:02
675
原创 [BZOJ1083][SCOI2005]繁忙的都市（二分+并查集）
题目描述传送门题目大意：给出n个点m条边的无向图，每一条边有一个边权，要求选出一些边，将n个点连通，并且边的数量最少，并且边权的最大值最小。题解首先二分答案，然后并查集判定这些边是否能将n个点连通 边数最少必然是一棵树啊代码#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath
2017-05-02 21:01:30
784
原创 [BZOJ2338][HNOI2011]数矩形（计算几何）
题目描述传送门题目大意：给出二维平面上的n个点，求一个最大的矩形，它的顶点都在给出的点上。题解首先预处理出所有的线段，中点相同、长度相同的两条线段可以组成一个合法的矩形 将所有的线段按照一维中点、一维长度、一维斜率排序，对于中点相同、长度相同的线段必定在一段区间里，并且对于一条线段，取到最大值的另一条线段单峰，用两个指针扫一下就行了代码#include<algorithm>#include<io
2017-05-02 19:06:36
599
原创 [BZOJ1132][POI2008]Tro（计算几何）
题目描述传送门题目大意：平面上有N个点. 求出所有以这N个点为顶点的三角形的面积和。题解枚举每一个点，以它为原点建立平面直角坐标系，然后其他的点按照极角排序。 向量的叉积满足分配律，所以可以two pointer一下，每一次右指针移动到最后一个与左指针夹角小于180°的地方，然后每加入一个向量，计算一下这个向量与两个指针之间所有向量的叉积，利用分配律。 看了PoPoQQQ的题解才发现，其实不用这
2017-05-02 15:42:27
745
原创 [BZOJ1045][HAOI2008] 糖果传递（数学相关）
题目描述传送门题目大意：有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。求使所有人获得均等糖果的最小代价。题解设第i个人会给第i+1个人xix_i个糖果（带符号），那么ai−xi+xi−1=avea_i-x_i+x_{i-1}=ave，将所有的式子列出来然后每一个做一个前缀和，那么xn−xi=∑ai−avex_n-x_i=\sum a_i-ave，要
2017-05-02 10:33:19
940
原创 [BZOJ2303][Apio2011]方格染色（数学相关+加权并查集）
题目描述传送门题目大意：一个n*m的网格染成红蓝两种颜色，要求每个田字格有1个或3个红色的。现在有一些格子已经染了颜色，问有多少合法的染色方案。题解和这题gang了一天。。。这题的关键在于，将每一个限制点的关系，转化成和第一行第一列的关系 若把颜色标记为0/1，那么每个田字格的异或值为1。首先枚举(1,1)的取值。考虑一个限制点(x,y)(x>1,y>1)，如果x,y都为偶数，那么(1,1)..(
2017-04-28 20:12:48
832
原创 [BZOJ2304][Apio2011]寻路（模拟+spfa）
题目描述传送门题目大意：在二维平面上有起点和终点，若干不相交、边界平行或竖直的矩形。不能进入矩形内部，只能在矩形的边界上改变方向，求起点到终点的最短距离或者No Path。题解这题和之前写过的冰原探险那道题挺像的，都是将这种图连边然后跑最短路 因为最优情况下只会在矩形的顶点处改变方向，所以可以先将坐标离散化，然后对于矩形的每一个顶点向第一个能到达的地方连边 这样的话除了矩形的顶点图上还会多出来一
2017-04-28 08:05:56
1198
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人