题意 求凸包 Sol Andrew算法： 首先按照$x$为第一关键字，$y$为第二关键字从小到大排序，并删除重复的点 用栈维护凸包内的点 1、把$p_1, p_2$放入栈中 2、若$p_{i{(i 3)}}$在直线$p_{i - 1}, p_{i - 2}$的右侧，则不断的弹出栈顶，直到该点在直线左侧 3、此时我们已经...

2018-07-27 06:10:27

声明一个对象，不加括号一般调用默认构造函数 15 T t1; // is obj：Default Constructor 注意：如声明一个对象，加括号，这里一般编译器把这个当成无形参的函数，返回类型为T 18 T t2(); // is function. name is t2, return T 声明一个对象，加括号一般调用用户定义的...

2018-07-27 06:10:26

#includeiostream #include cmath using namespace std; int main(){ int n,sum= 0 ,j,i,k,lpl,a[ 100000 ],b[ 100000 ]; cin n; a[ 1 ]= 1 ,b[ 1 ]= 1 ; for ( int i= 2 ;i=n;i++ ) { a[i] =(a[i- 1 ]+ 1 )%i+ 1 ; if (a[i]==i)b[i]= i; else b[i]= b[a[i]]; } cout b...

2018-07-27 06:10:25

题意 一家餐厅，第$i$天需要$r_i$块餐巾，每天获取餐巾有三种途径 1、以$p$的费用买 2、以$f$的费用送到快洗部，并在$m$天后取出 3、以$s$的费用送到慢洗部，并在$n$天后取出 问满足要求时的最小费用 Sol 一道非常不错的网络流，应该不难看出是费用流。 首先进行拆点，...

2018-07-27 06:10:24

题目描述： Evaluate the value of an arithmetic expression inReverse Polish Notation.Valid operators are+,-,*,/. Each operand may be an integer or another expression. Some examples: 1 [ " 2 " , " 1 " , " + " , " 3 " , " * " ] - (( 2 + 1 ) * 3 ) - 9 2...

2018-07-25 13:00:54

题意 有$m$个实验，$n$中器材，每个实验需要使用一些器材 每个实验有收入，每个器材有花费 最大化收入 - 花费 Sol 最大权闭合图的经典应用 从$S$向每个实验连流量为该实验收入的边 从每个器材箱$T$连流量为花费的边 每个实验向其需要其器材连边权为$INF$的边 答案为：...

2018-07-25 13:00:53

题意 给出一张有向无环图，求出用最少的路径覆盖整张图，要求路径在定点处不相交 输出方案 Sol 定理：路径覆盖 = 定点数 - 二分图最大匹配数 直接上匈牙利 输出方案的话就不断的从一个点跳匹配边 #includecstdio #include queue #include cstring using namespace std;...

2018-07-25 13:00:52

题意 $n$道试题，每道题有多种类别属性 抽取$m$道题组成试卷，要求包含指定的类型 输出方案 Sol 又是一道zz网络流 我的构图长这样，$k_i$表示第$i$道试题需要的数量 #includecstdio #include queue #include cstring using namespace std; const int MAXN = 1e5 + 10 ,...

2018-07-25 13:00:51

题意 $m$个不同单位代表参加会议，第$i$个单位有$r_i$个人 $n$张餐桌，第$i$张可容纳$c_i$个代表就餐 同一个单位的代表需要在不同的餐桌就餐 问是否可行，要求输出方案 Sol 比较zz的最大流 从$S$向$1-m$连流量为$r_i$的边 从$m + 1$向$m + n$连流量为$c_i$的边 从$1-m$...

2018-07-25 13:00:50

题意 $n$个节点的树，每个点有权值，支持三种操作 1、 换根 2、把$x$到$y$路径上节点权值变为$z$ 3、询问路径最小值 Sol 啥？你说这是TopTree的裸题？ 那你写去啊 很显然，如果没有第一个操作就是树剖的裸题 其实有了第一个操作也是树剖的裸题 我们考虑换根之后会对那...

2018-07-25 13:00:47