Dispwnl

Crazy Up

[BZOJ4311]向量

题目 Description 你要维护一个向量集合，支持以下操作： 1.插入一个向量(x,y) 2.删除插入的第i个向量 3.查询当前集合与(x,y)点积的最大值是多少。如果当前是空集输出0 Input 第一行输入一个整数n，表示操作个数接下来n行，每行先是一个整数t表示类型，如果t=1，输入向量 (x,y)；如果t=2，输入id表示删除第id个向量；否则输入(x,y)，查询与向量(x,...

Posted by Dispwnl on December 9, 2018

[CF938G]Shortest Path Queries

题目题目大意给定一个$n$个点$m$条边无向图，有$q$个询问 $1\;x\;y\;d$ 新加入一条连接$x,y$长度为$d$的无向边 $2\;x\;y$删除$x,y$之间的边 $3\;x\;y$查询$x,y$之间的最小$XOR$路径 Example input 5 5 1 2 3 2 3 4 3 4 5 4 5 6 1 5 1 5 3 1 5 1 1 3 1 3 1...

Posted by Dispwnl on December 8, 2018

[HNOI2016]网络

没有什么是四百万个堆不能搞定的，如果有，那就八百万的堆题目题目描述一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据的交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。由于这条路径是唯一的，当路径上的某个服务器出现故障，无法正常运行时，数据便无法交互。此外，每个数据交互...

Posted by Dispwnl on December 5, 2018

[CF1088X]Codeforces Round #525 (Div. 2)

感觉这场CF有点不够$Div2$难度啊……没打真是可惜了恭喜$XG$大爷一场上紫！ A　　Ehab and another construction problem 题目大意找两个数$a,b$，使得 $1\le a,b\le x$ $b$能整除$a$ $a·b>x$ $\frac{a}{b}<x$ 题解枚举即可代码 ...

Posted by Dispwnl on December 5, 2018

[TJOI2015]旅游

题目题目描述为了提高智商,ZJY准备去往一个新世界去旅游。这个世界的城市布局像一棵树。每两座城市之间只有一条路径可以互达。每座城市都有一种宝石,有一定的价格。ZJY为了赚取最高利益,她会选择从A城市买入再转手卖到B城市。由于ZJY买宝石时经常卖萌,因而凡是ZJY路过的城市,这座城市的宝石价格会上涨。让我们来算算ZJY旅游完之后能够赚取的最大利润。(如a城市宝石价格为v,则ZJY出售价格也...

Posted by Dispwnl on December 4, 2018

[LUOGU3401]洛谷树

题目题目背景萌哒的Created equal小仓鼠种了一棵洛谷树！（题目背景是辣鸡小仓鼠乱写的QAQ）。题目描述树是一个无环、联通的无向图，由n个点和n-1条边构成。树上两个点之间的路径被定义为他们之间的唯一一条简单路径——显然这是一条最短路径。现在引入一个概念——子路径。假设树上两个点p1和pn之间的路径是P=<p1,p2,p3,…,pn>，那么它的子路径被定...

Posted by Dispwnl on December 4, 2018

网络流整理

关于模型傻逼型看一眼解决问题拆点模型要限制某个点的流量或者一个点在多个条件下往往需要用到，其他模型多与混合限流型限制点$i$只能选/经过$k$次 $(i,i+n,k)$ 满足多个条件型满足条件$a$流量为$A$，满足条件$b$流量为$B$，…… $(S,i,A),(S,i+n,B),……$ ...

Posted by Dispwnl on December 3, 2018

[LUOGU2418]yyy loves OI IV

题目题目背景某校2015届有两位OI神牛，yyy和c01。题目描述全校除他们以外的N名学生，每人都会膜拜他们中的某一个人。现在老师要给他们分宿舍了。但是，问题来了：同一间宿舍里的人要么膜拜同一位大牛，要么膜拜yyy和c01的人数的差的绝对值不超过M。否则他们就会打起来。为了方便，老师让N名学生站成一排，只有连续地站在一起的人才能分进同一个宿舍。假设每间宿舍能容纳任意多的...

Posted by Dispwnl on December 3, 2018

[HAOI2012]高速公路

题目题目描述 Y901高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。 Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为1~N，从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。政府部门根据实际情况，会...

Posted by Dispwnl on December 3, 2018

[SDOI2013]费用流

题目题目描述 Alice和Bob在图论课程上学习了最大流和最小费用最大流的相关知识。最大流问题：给定一张有向图表示运输网络，一个源点S和一个汇点T，每条边都有最大流量。一个合法的网络流方案必须满足： (1)每条边的实际流量都不超过其最大流量且非负； (2)除了源点S和汇点T之外，对于其余所有点，都满足该点总流入流量等于该点总流出流量；而S点的净流出流量等于T点的净流入流量，这个值...

Posted by Dispwnl on November 28, 2018