NIRVANA

Problem

【NOI2009】植物大战僵尸

Time Limit: $10 Sec$
Memory Limit: $64 MB$

Description

Input

Output

仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为$0$。

Problem

【SDOI2009】晨跑

$\mathrm{Time\;Limit:\;4\;Sec}$
$\mathrm{Memory\;Limit:\;64\;MB}$

Description

$Elaxia$最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等 等，不过到目前为止，他坚持下来的只有晨跑。 现在给出一张学校附近的地图，这张地图中包含$N$个十字路口和$M$条街道，$Elaxia$只能从 一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。$Elaxia$每天从寝室出发 跑到学校，保证寝室编号为$1$，学校编号为$N$。 $Elaxia$的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路 口。$Elaxia$耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。 除了练空手道，$Elaxia$其他时间都花在了学习和找$MM$上面，所有他想请你帮忙为他设计 一套满足他要求的晨跑计划。

Input

第一行：两个数$N,M$。表示十字路口数和街道数。
接下来$M$行，每行$3$个数$a,b,c$，表示路口$a$和路口$b$之间有条长度为$c$的街道（单向）。

Output

两个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长度。

Problem

【BJ2011集训】星器

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

$\mathrm{Magic\;Land}$上的时间又过了若干世纪……
现在，人们谈论着一个传说：从前，他们的祖先来到了一个位于东方的岛屿，那里简直就是另外一个世界。善于分析与构造的$\mathrm{Magic\;Land}$上的人们总是不明白那里的人们是如何不借助精确的实验与计算驱动和操纵魔法。
偶然地，一个魔法使（$\mathrm{Magician}$）来到了$\mathrm{Magic\;Land}$，在临走的时候留下了一个神奇的盒子，叫做星器（$\mathrm{casket\;of\;star}$）。
虽然不知道这个盒子是做什么的，但是经过了大量的实验和计算后，人们已经清楚它的一些事实：

• 星器之中有$N\times M$个区域，可看作分成$N$行和$M$列的格子，每个区域之中有若干单位的称为“星”的对象，这个对象的最小单位已经被确定，所以，这个数量总是整数。
• 魔法使可以驱动星器中位于同一行或同一列的不相邻（有公共边的区域称为相邻的）两个区域中各1单位的“星”，使得它们分别向中心移动1格。
• 每一次使用2中的方法驱动“星”，将会产生魔力，魔法使会得到这一部分魔力。魔力的量等于这个两个区域之间所间隔的区域数。
  这样，我们可以用一个$N\times M$的数表来表示星器的状态，比如$N=2$，$M=3$时：

当星器为左图的状态时，通过操纵第一行的第$1$和$3$个区域中的“星”（加粗的数字对应的区域），变为右图所示的状态，同时，将产生$1$单位的魔力（因为这两个区域之间恰好隔了$1$个区域）。
在经过了进一步的研究之后，人们知道了这个星器最初的状态（$\mathrm{Ini}$）以及最终被他们得到时的状态（$\mathrm{Fin}$）。
你希望知道，星器最多帮助它的拥有者提供了多少的魔力。即：经过一系列上述操作由初态（$\mathrm{Ini}$）变为终态（$\mathrm{Fin}$），至多产生多少魔力。
需要注意的是，显然操作过程中每个区域内“星”的数量不能是负的，即：如果那个区域已经没有“星”了，当然就不能继续操作了。

Input

第一行包含两个正整数$N$、$M$表示星器的大小。
接下来的$N$行，每行包含$M$个自然数：$Ini_{i,j}$，描绘了初态（$Ini$）。
在一个空行后的$N$行，每行包含$M$个自然数：$Fin_{i,j}$，描绘了终态（$Fin$）。

Output

输出一个正整数，表示至多产生的魔力。

Problem

【FJ2015集训】卡牌配对

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

现在有一种卡牌游戏，每张卡牌上有三个属性值：$A,B,C$。把卡牌分为$X,Y$两类，分别有$n_1,n_2$张。
两张卡牌能够配对，当且仅当，存在至多一项属性值使得两张卡牌该项属性值互质，且两张卡牌类别不同。
比如一张$X$类卡牌属性值分别是$225,233,101$，一张$Y$类卡牌属性值分别为$115,466,99$。那么这两张牌是可以配对的，因为只有$101$和$99$一组属性互质。
游戏的目的是最大化匹配上的卡牌组数，当然每张卡牌只能用一次。

Input

数据第一行两个数$n_1$，$n_2$，空格分割。
接下来$n_1$行，每行$3$个数，依次表示每张$X$类卡牌的$3$项属性值。
接下来$n_2$行，每行$3$个数，依次表示每张$Y$类卡牌的$3$项属性值。

Output

输出一个整数：最多能够匹配的数目。

Problem

【SDOI2016】数字配对

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

有 $n$ 种数字，第 $i$ 种数字是 $a_i$、有 $b_i$ 个，权值是 $c_i$。
若两个数字 $a_i,\ a_j$ 满足，$a_i$ 是 $a_j$ 的倍数，且 $\frac{a_i}{a_j}$ 是一个质数，那么这两个数字可以配对，并获得 $c_i\times c_j$ 的价值。
一个数字只能参与一次配对，可以不参与配对。
在获得的价值总和不小于 $0$ 的前提下，求最多进行多少次配对。

Input

第一行一个整数 $n$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
第三行 $n$ 个整数$b_1,b_2,\cdots,b_n$。
第四行 $n$ 个整数 $c_1,c_2,\cdots,c_n$。

Output

一行一个数，最多进行多少次配对

Problem

【JSOI2010】Frozen Nova 冷冻波

Time Limit: $10 Sec$
Memory Limit: $64 MB$

Description

$WJJ$喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能$Frozen\ Nova$每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过$R$，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。 在森林里有$N$个巫妖，每个巫妖释放$Frozen\ Nova$之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道，若从$0$时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？

Input

输入文件第一行包含三个整数$N,M,K(N,M,K\le 200)$，分别代表巫妖的数量、小精灵的数量和树木的数量。 接下来$N$行，每行包含四个整数$x, y, r, t$，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。 再接下来$M$行，每行两个整数$x, y$，分别代表了每个小精灵的坐标。 再接下来K行，每行三个整数$x, y, r$，分别代表了每个树木的坐标。 输入数据中所有坐标范围绝对值不超过$10000$，半径和施法间隔不超过$20000$。

Output

输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出$-1$。

Problem

Choosing Capital for Treeland

$\mathrm{Time\;limit:\;3000\;ms}$
$\mathrm{Memory\;limit:\;262144\;kB}$

Description

The country Treeland consists of n cities, some pairs of them are connected with unidirectional roads. Overall there are $n-1$ roads in the country. We know that if we don’t take the direction of the roads into consideration, we can get from any city to any other one.
The council of the elders has recently decided to choose the capital of Treeland. Of course it should be a city of this country. The council is supposed to meet in the capital and regularly move from the capital to other cities (at this stage nobody is thinking about getting back to the capital from these cities). For that reason if city a is chosen a capital, then all roads must be oriented so that if we move along them, we can get from city a to any other city. For that some roads may have to be inversed.
Help the elders to choose the capital so that they have to inverse the minimum number of roads in the country.

Input

The first input line contains integer $n (2\le n\le 2\times 10^5)$ — the number of cities in Treeland. Next $n-1$ lines contain the descriptions of the roads, one road per line. A road is described by a pair of integers $s_i,t_i (1\le s_i,t_i\le n; si\ne ti)$ — the numbers of cities, connected by that road. The $i^{th}$ road is oriented from city $s_i$ to city $t_i$. You can consider cities in Treeland indexed from $1$ to $n$.

Output

In the first line print the minimum number of roads to be inversed if the capital is chosen optimally. In the second line print all possible ways to choose the capital — a sequence of indexes of cities in the increasing order.

Problem

Little Pony and Harmony Chest

$\mathrm{Time\;limit:\;4000\;ms}$
$\mathrm{Memory\;limit:\;262144\;KB}$

Description

Princess Twilight went to Celestia and Luna’s old castle to research the chest from the Elements of Harmony.

A sequence of positive integers $b_i$ is harmony if and only if for every two elements of the sequence their greatest common divisor equals $1$. According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:

$$\sum_{i=1}^{n}{|a_i-b_i|}$$

You are given sequence $a_i$, help Princess Twilight to find the key.

Input

The first line contains an integer $n (1\le n\le 100)$ — the number of elements of the sequences $a$ and $b$. The next line contains $n$ integers $a_1,a_2,\cdots,a_n (1\le a_i\le 30)$.

Output

Output the key — sequence bi that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

Problem

方格取数

Time Limit: $5 Sec$
Memory Limit: $64 MB$

Description

在一个$n\times n$的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。

Input

第一行一个数$n$（$n\le 30$），接下来$n$行每行$n$个数描述一个方阵

Output

仅一个数，即最大和

Problem

【SHOI2010】最小生成树

Time Limit: $10 Sec$
Memory Limit: $128 MB$

Description

$Secsa$最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个$n$个点、$m$条边的无向图的最小生成树有一个$Krustal$算法和另一个$Prim$的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图 $3$中所示的都是图 $2$中的无向图的最小生成树：

当然啦，这些都不是今天需要你解决的问题。$Secsa$想知道对于某一条无向图中的边$AB$，至少需要多少代价可以保证$AB$边在这个无向图的最小生成树中。为了使得$AB$边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边 $P_1P_2$，再把图中除了这条边以外的边，每一条的权值都减少$1$。如图 $4$所示就是一次这样的操作：

Input

输入文件的第一行有$3$个正整数$n$、$m$、$Lab$分别表示无向图中的点数、边数、必须要在最小生成树中出现的$AB$边的标号。
接下来$m$行依次描述标号为$1,2,3\cdots, m$的无向边，每行描述一条边。每个描述包含$3$个整数$x$、$y$、$d$，表示这条边连接着标号为$x$、$y$的点，且这条边的权值为$d$。
输入文件保证$1\le x,y\le N$,$x\ne y$,且输入数据保证这个无向图一定是一个连通图。

Output

输出文件只有一行，这行只有一个整数，即，使得标号为$Lab$边一定出现最小生成树中的最少操作次数。