NIRVANA

Problem

【APIO2014】序列分割

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

Description

$\mathrm{小H}$最近迷上了一个分隔序列的游戏。
在这个游戏里，$\mathrm{小H}$需要将一个长度为$n$的非负整数序列分割成$k+1$个非空的子序列。
为了得到$k+1$个子序列，$\mathrm{小H}$需要重复$k$次以下的步骤：

1. $\mathrm{小H}$首先选择一个长度超过$1$的序列（一开始$\mathrm{小H}$只有一个长度为$n$的序列，也就是一开始得到的整个序列）
2. 选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列

每次进行上述步骤之后，$\mathrm{小H}$将会得到一定的分数。这个分数为两个新序列中元素和的乘积。
$\mathrm{小H}$希望选择一种最佳的分割方式，使得$k$轮之后，$\mathrm{小H}$的总得分最大。

Input

输入第一行包含两个整数$n,k\;(k+1\le n)$。
第二行包含$n$个非负整数$a_1,a_2,\cdots,a_n\;(0\le a_i\le10^4)$，表示一开始$\mathrm{小H}$得到的序列。

Output

输出第一行包含一个整数，为$\mathrm{小H}$可以得到的最大分数。

Problem

震波

$\mathrm{Time\;Limit:\;15\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

在一片土地上有$N$个城市，通过$N-1$条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为$1$，其中第i个城市的价值为$value_i$。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理$M$次操作：

• $0\;x\;k$ 表示发生了一次地震，震中城市为$x$，影响范围为$k$，所有与$x$距离不超过$k$的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
• $1\;x\;y$ 表示第$x$个城市的价值变成了$y$。

为了体现程序的在线性，操作中的$x,y,k$都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为$0$。

Input

第一行包含两个正整数$N$和$M$。
第二行包含$N$个正整数，第$i$个数表示$value_i$。
接下来$N-1$行，每行包含两个正整数$u,v$，表示$u$和$v$之间有一条无向边。
接下来$M$行，每行包含三个数，表示$M$次操作。

Output

包含若干行，对于每个询问输出一行一个正整数表示答案。

Problem

【SCOI2012】奇怪的游戏

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

Description

$\mathrm{Blinker}$最近喜欢上一个奇怪的游戏。
这个游戏在一个$N\times M$的棋盘上玩，每个格子有一个数。每次$\mathrm{Blinker}$会选择两个相邻的格子，并使这两个数都加上$1$。
现在$\mathrm{Blinker}$想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出$-1$。

Input

输入的第一行是一个整数$T$，表示输入数据有$T$轮游戏组成。
每轮游戏的第一行有两个整数$N$和$M$， 分别代表棋盘的行数和列数。
接下来有$N$行，每行$M$个数。

Output

对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出$-1$。

Problem

Sum

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

Description

求$ans_1=\sum_{i=1}^n\phi(i)$和$ans_2=\sum_{i=1}^n\mu(i)$。
$n<2^{31}$，$T$组询问。

Input

一共$T+1$行
第$1$行为数据组数$T(T\le10)$
第$2\sim T+1$行每行一个非负整数$N$，代表一组询问

Output

一共$T$行，每行两个用空格分隔的数$ans_1,ans_2$

Problem

【SCOI2012】滑雪与时间胶囊

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

Description

$\mathrm{a180285}$非常喜欢滑雪。他来到一座雪山，这里分布着$M$条供滑行的轨道和$N$个轨道之间的交点（同时也是景点），而且每个景点都有一编号$i$（$1\le i\le N$）和一高度$H_i$。$\mathrm{a180285}$能从景点$i$滑到景点$j$当且仅当存在一条$i$和$j$之间的边，且$i$的高度不小于$j$。 与其他滑雪爱好者不同，$\mathrm{a180285}$喜欢用最短的滑行路径去访问尽量多的景点。如果仅仅访问一条路径上的景点，他会觉得数量太少。于是$\mathrm{a180285}$拿出了他随身携带的时间胶囊。这是一种很神奇的药物，吃下之后可以立即回到上个经过的景点（不用移动也不被认为是$\mathrm{a180285}$滑行的距离）。请注意，这种神奇的药物是可以连续食用的，即能够回到较长时间之前到过的景点（比如上上个经过的景点和上上上个经过的景点）。 现在，$\mathrm{a180285}$站在$1$号景点望着山下的目标，心潮澎湃。他十分想知道在不考虑时间胶囊消耗的情况下，以最短滑行距离滑到尽量多的景点的方案（即满足经过景点数最大的前提下使得滑行总距离最小）。你能帮他求出最短距离和景点数吗？

Input

输入的第一行是两个整数$N$，$M$。
接下来$1$行有$N$个整数$H_i$，分别表示每个景点的高度。
接下来$M$行，表示各个景点之间轨道分布的情况。每行$3$个整数，$U_i,V_i,K_i$。表示
编号为$U_i$的景点和编号为$V_i$的景点之间有一条长度为$K_i$的轨道。

Output

输出一行，表示$\mathrm{a180285}$最多能到达多少个景点，以及此时最短的滑行距离总和。

Problem

【POI2000】病毒

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

Description

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。
示例：
如果$\lbrace011, 11, 00000\rbrace$为病毒代码段，那么一个可能的无限长安全代码就是$010101\cdots$。
如果$\lbrace01, 11, 000000\rbrace$为病毒代码段，那么就不存在一个无限长的安全代码。
任务：
请写一个程序

• 读入病毒代码
• 判断是否存在一个无限长的安全代码
• 将结果输出

Input

第一行包括一个整数$n$，表示病毒代码段的数目。
以下的$n$行每一行都包括一个非空的$01$字符串就是一个病毒代码段。
所有病毒代码段的总长度不超过$30000$。

Output

一行输出一个单词：
$\mathrm{TAK}$：存在这样的代码
$\mathrm{NIE}$：不存在这样的代码

Problem

Mato的文件管理

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

Description

$\mathrm{Mato}$同学从各路神犇以各种方式收集了许多资料，这些资料一共有$n$份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用$\mathrm{Mato}$自己写的程序才能访问。$\mathrm{Mato}$每天随机选一个区间$[l,r]$，他今天就看编号在此区间内的这些资料。$\mathrm{Mato}$有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在$1$单位时间内交换$2$个相邻的文件（因为加密需要，不能随机访问）。$\mathrm{Mato}$想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？

Input

第一行一个正整数$n$，表示$\mathrm{Mato}$的资料份数。
第二行由空格隔开的$n$个正整数，第$i$个表示编号为$i$的资料的大小。
第三行一个正整数$q$，表示$\mathrm{Mato}$会看几天资料。
之后$q$行每行两个正整数$l,r$，表示$\mathrm{Mato}$这天看$[l,r]$区间的文件。

Output

$q$行，每行一个正整数，表示$\mathrm{Mato}$这天需要交换的次数。

Problem

【WC2011】Xor

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

Description

Input

第一行包含两个整数$N$和$M$，表示该无向图中点的数目与边的数目。
接下来$M$行描述$M$条边，每行三个整数$S_i,T_i,D_i$，表示$S_i$与$T_i$之间存在 一条权值为$D_i$的无向边。
图中可能有重边或自环。

Output

仅包含一个整数，表示最大的$\mathrm{Xor}$和（十进制结果），注意输出后加换行回车。

Problem

【SCOI2016】幸运数字

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

Description

$A$国共有$n$座城市，这些城市由$n-1$条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。一些旅行者希望游览$A$国。旅行者计划乘飞机降落在$x$号城市，沿着$x$号城市到$y$号城市之间那条唯一的路径游览，最终从$y$城市起飞离开$A$国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，游览者拍了$3$张照片，幸运值分别是$5,7,11$，那么最终保留在自己身上的幸运值就是 $\mathrm{9\;(5\oplus7\oplus11)}$。有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择$5$和$11$，可以保留的幸运值为$14$ 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。

Input

第一行包含$2$个正整数$n,q$，分别表示城市的数量和旅行者数量。第二行包含$n$个非负整数，其中第$i$个整数$G_i$表示$i$号城市的幸运值。随后$n-1$行，每行包含两个正整数$x,y$，表示$x$号城市和$y$号城市之间有一条道路相连。随后$q$行，每行包含两个正整数$x,y$，表示这名旅行者的旅行计划是从$x$号城市到$y$号城市。

Output

输出需要包含$q$行，每行包含$1$个非负整数，表示这名旅行者可以保留的最大幸运值。

Problem

曼哈顿最小生成树

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

Description

平面坐标系$\mathrm{xOy}$内，给定$n$个顶点$V=(x,y)$。对于顶点$u,\;v$，$u$与$v$之间的距离$d$定义为$|x_u-x_v|+|y_u-y_v|$。你的任务是求出这$n$个顶点的最小生成树。

Input

第一行一个正整数$n$，表示定点个数。
接下来$n$行每行两个正整数$x,\;y$，描述一个顶点。

Output

只有一行，为最小生成树的边的距离和。