Rewinner

分类

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 图论(24) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

全部文章（共136篇）

P2756 飞行员配对方案问题【网络流24题最大流】

传送门废话：最大流模板题思路：二分匹配也可以写，最简单的网络流，只需要增加超级源点和超级汇点即可超级源点->外籍飞行员（流上限为1）外籍飞行员->英国飞行员（流上限为1）英国飞行员->超级汇点（流上限为1）最大流就是最多匹配数，我们可以通过每条边的反向边来判断是...

2019-05-21

0 440

P4014 分配问题【网络流24题最小/大费用最大流】

传送门废话：应该是一道最大流最小费用流的模板题解题思路：在保证每个人都有工作的条件下获得的收益最大和最小。收益最小：费用流模板。收益最大：将收益取反，跑一遍板子，答案就等于最小费用取反。一个超级源点 - > 每一个人 (流上限均为1,费用为0) 人->工作 (流上限为1，费用（最小...

2019-05-21

0 620

Power OJ 2478: 最短路问题

传送门题意：求最短路，多了一个约束条件，可以将一条边的花费变为0或者两条相连的边的花费都变为0。废话：很早在OJ上看到的题，当时不会做，现在终于可以把这道题干掉了(结果自己疯狂WA，居然是多组输入！！！！！)解题思路：表示三种状态表示还没有使用过免费边表示还可以接着上一条边再使用一次免费边...

2019-05-12

0 559

西北大学：西湖奇遇记Ⅰ【最短路】

传送门看代码更容易理解 ///#include<bits/stdc++.h> ///#include<unordered_map> ///#include<unordered_set> #include<iostream> #include&l...

2019-05-12

0 477

[CQOI2011]动态逆序对【主席树+树状数组】

传送门废话：这道题和当初队长他们去电子科技大学的校赛A题几乎是一样，这道题没有挂在他们的OJ上，无意之间发现了这道题，赶紧补一下。这道题的做法也太多了吧。。。。。分块会板子(这道题不会)，CDQ分治不会，只会大佬说的动态主席树板子题，然后拿来改一下就能过了。。。解题思路：求解逆序数，我们常常用到...

2019-05-09

0 490

P2617 Dynamic Rankings【动态第K大树状数组+主席树】

传送门中文题目，题意不再叙述！实现方法：静态第K大，我们利用就是前缀和的思想来建立的线段树，[L,R]的状态由R状态的线段树减去L-1状态的线段树得到的。既然就是前缀和而且存在修改操作，我们可以利用树状数组来解决这个问题。原本处于下标 i 的线段树代表[1 - i ]所有元素的线段树，那么在...

2019-05-09

0 501

Power OJ 2840 伯陵防线【可持久化线段树】

传送门废话一波：这道题是几个月前比赛的题，当时就我一个人开了这道题，我当时写的可持久化线段树，但是思维出错了，一直WA。这道题还可以用树状数组或者线段树来写，但是我想不到。。。。出题人博客：https://blog.csdn.net/swust5120166213/article/deta...

2019-05-08

0 480

[SDOI2013] 森林【可持久化线段树+启发式合并+LCA】

传送门吐槽：题目上给的 testcase 太迷惑人了。。。题目描述：小Z有一片森林，含有N个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有M条边。小Z希望执行T个操作，操作有两类： Q x y k查询点x到点y路径上所有的权值中，第k小的权值是多少...

2019-05-07

0 489

The Stream of Corning 2【可持久化线段树】

2018 ICPC Asia Nakhon Pathom Regional Contest K 题意上的重点：In the given inputs, the CURRENT_TIMESTAMPS will be strictly increasing between consecutive ev...

2019-05-06

0 481

[SCOI2016] 美味【可持久化线段树+位运算】

传送门题目描述：一家餐厅有 n 道菜，编号 1...n ，大家对第 i 道菜的评价值为 ai(1<=i<=n)。有 m 位顾客，第 i 位顾客的期望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异...

2019-04-30

0 492