和LOJ #6004圆桌聚餐很像

建模：

1.从源点向每道试题$x_i$连一条容量为$1$的边

2.从每种类型$y_i$向汇点连一条容量为该类型需求数量的边

3.如果试题$x_i$属于类型$y_i$则从$x_i$向$y_i$连一条容量为$1$的边

然后跑裸的网络最大流，如果最大流$\not=$需求试题总数则无解

方案：

对于每种类型，它连出的所有满流量边即为该类型所对应的试题

建模：

1.从源点向每个单位$x_i$连边，容量是该单位的人数

2.从每张餐桌$y_i$向汇点连边，容量是该餐桌能容纳的人数

3.从每个单位$x_i$向每张餐桌$y_j$连边，容量为$1$

如果最大流量等于所有单位人数之和，则有解，否则无解。

方案：

对于每个单位$x_i$，该单位向$y$集合连出的所有满流量边即为该单位人员的安排情况（证明显然

很简单的网络流

对于每个正飞行员，从源点向它连一条容量为$1$的边

对于每个副飞行员，从它向汇点连一条容量为$1$的边

对于每一对可以配对的正/副飞行员，从正飞行员向副飞行员连一条容量为$1$的边

提交地址: LOJ #143. 质数判定

提交地址: 洛谷P3380 二逼平衡树

Codeforces Round #550 (Div.3) 题解

模拟退火模板题…

题目大意

有一个有着$h$点血量的boss,
你的每一个回合有$n$种攻击

第$i$种攻击可以对boss造成$-d[i]$的伤害($h=h+d[i]$)

求最早在什么时候能击败boss(即boss血量$\leq0$)

可以发现题目可以转化为把从$l$到$r$节点到$1$的路径上的点的点权都加上$1$，然后统计$1$到$z$路径上的点权

然后发现这个东西可以差分。。。

于是我们就把询问拆成$l-1$和$r$,然后按$r$排序

从$1$到$n$把$1$到$i$路径点权全部$+1$

询问时查询$1$到$z$路径点权和

很明显这是一道树剖题

但是，树剖是在点上进行的操作，如何把它转化到边上呢？

不难发现，每一个点与他的父亲节点之间仅有唯一的一条边

于是我们可以把这条边的边权转化为这个儿子节点的点权。