ww3113306

2018年9月30日

[NOI2017]游戏 2-sat

摘要：～～～题面～～～题解：首先观察到，如果没有x的话，这就是一个2-sat问题。建图方式：对于限制d1 c1 d2 c2,其中d1, d2分别代表比赛编号，c1, c2代表出场的赛车。 1，如果d1不能选c1,那么该限制是不会起到作用的，所以不连边。 2，否则如果d2不能选c2，那么意味这d1-c 阅读全文

posted @ 2018-09-30 18:48 ww3113306 阅读(168) 评论(0) 推荐(0)

ARC076 F Exhausted? Hall定理 + 线段树扫描线

摘要：～～～题面～～～题目大意：有n个人，m个座位，每个人可以匹配的座位是[1, li] || [ri, m],可能有人不需要匹配座位（默认满足），问最少有多少人不能被满足。题解：首先可以看出这是一个二分图匹配，根据hall定理，我们只需要求出max(人的子集大小 - 被选出的人可以选的座位集合大阅读全文

posted @ 2018-09-30 17:13 ww3113306 阅读(411) 评论(0) 推荐(0)

2018年9月25日

CF#366 704D Captain America 上下界网络流

摘要： CF上的题，就不放链接了，打开太慢，直接上题面吧：平面上有n个点, 第 i 个点的坐标为 ($X_i ,Y_i$), 你需要把每个点染成红色或者蓝色, 染成红色的花费为 r , 染成蓝色的花费为 b .有m个限制条件, 有两种类型, 第一种类型为$x = l_i$ 上的红点与蓝点个数差的绝对值不超阅读全文

posted @ 2018-09-25 01:14 ww3113306 阅读(930) 评论(0) 推荐(0)

算法学习——上下界网络流

摘要：顾名思义，带上下限网络流即对于网络流中的每一条边，都带有流量的上界和下界。普通的网络流可以看做下界为0的上下限网络流。 1，无源汇带上下界可行流。定义一个数组d[x]表示图中点x的入度下限和-出度下限和。建图方式为：对于图中每一条边，都连流量为上界-下界的边，并在加边的时候统计d[x]。对阅读全文

posted @ 2018-09-25 01:12 ww3113306 阅读(255) 评论(0) 推荐(0)

2018年9月15日

算法学习——虚树

摘要：虚树听起来是一个很高大上的东西，实际上实现起来是比较简单的。大致的意思是说，对于一棵树而言，也许每次询问我们只需要用到其中的部分节点，因此如果每次询问我们要对全部的节点都做一次处理的话，显然会造成浪费，且很可能会超时。这时就需要虚树了。因为有些节点是完全无用的，但你又不能因此毁了原树——说不定阅读全文

posted @ 2018-09-15 16:50 ww3113306 阅读(465) 评论(0) 推荐(0)

算法学习——st表

摘要： st表是一种基于倍增思想的DP。用于求一个数列中的某个区间的最大/最小值。用st[i][j]表示从第i个开始往后2^j个点，最大的是多少。我们令k[i]表示2^i等于多少那么有转移方程 st[i][j] = max(st[i][j - 1], st[i + k[i - 1]][j - 1]) 阅读全文

posted @ 2018-09-15 16:43 ww3113306 阅读(306) 评论(0) 推荐(0)

2018年9月9日

[USACO07DEC]美食的食草动物Gourmet Grazers

摘要：～～～题面～～～题解：首先观察题面，直觉上对于一头奶牛，肯定要给它配pi和qi符合条件的草中两者尽量低的草，以节省下好草给高要求的牛。实际上这是对的，但观察到两者尽量低这个条件并不明确，无法用于判断，因此要考虑一些其他的方法。首先我们把牛和草都放在一个数组里，然后按照口感给它们排序。这样对于阅读全文

posted @ 2018-09-09 22:28 ww3113306 阅读(248) 评论(0) 推荐(0)

[ZJOI2005]沼泽鳄鱼矩阵乘法

摘要：～～～题面～～～题解：乍一看还是挺懵逼的。和HH去散步很像，思路也是类似的。复制一段我在HH去散步的题解里面写的一段话吧：考虑f[i][j]表示i和j是否右边相连，有为1，否则为0，那么f同时可以表示从每个点出发走一步到其他点的方案数。于是用一个和f长得一模一样的矩阵g来表示从每个点出发到阅读全文

posted @ 2018-09-09 22:01 ww3113306 阅读(183) 评论(0) 推荐(0)

[SCOI2010]序列操作线段树

摘要：～～～题面～～～题解：在考场上打的这道题，出人意料的很快就打完了？！直接用线段树，维护几个东西： 1，lazy标记：表示区间赋值 2，mark标记：表示区间翻转 3，l1：前缀最长连续的1的子段长度 4，l0：前缀最长连续的0的子段长度 5，m0：区间内最长的全为0的子段的长度 6，r0：阅读全文

posted @ 2018-09-09 19:24 ww3113306 阅读(207) 评论(0) 推荐(0)

[LNOI2014]LCA

摘要：～～～题面～～～题解：首先我们要转化一下，因为直接求不好求。首先考虑一个点对z的贡献，观察这么一个图：显然点x对点z的贡献为2，因为LCA的深度为2。LCA可以看做点x和点z分别走向root的两条路径中第一个重合的点，因此，如果我们给x到root的路径上的点都赋1的点权，那么再从z往上走，因阅读全文

posted @ 2018-09-09 19:15 ww3113306 阅读(279) 评论(0) 推荐(0)

鸽王了属于是

公告