Problem

【APIO2014】序列分割

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

Description

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

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

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

Input

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

Output

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

Read more »

Problem

震波

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

Description

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

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

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

Input

第一行包含两个正整数NNMM
第二行包含NN个正整数,第ii个数表示valueivalue_i
接下来N1N-1行,每行包含两个正整数u,vu,v,表示uuvv之间有一条无向边。
接下来MM行,每行包含三个数,表示MM次操作。

Output

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

Read more »

Problem

【SCOI2012】奇怪的游戏

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

Description

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

Input

输入的第一行是一个整数TT,表示输入数据有TT轮游戏组成。
每轮游戏的第一行有两个整数NNMM, 分别代表棋盘的行数和列数。
接下来有NN行,每行MM个数。

Output

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

Read more »

Problem

Sum

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

Description

ans1=i=1nϕ(i)ans_1=\sum_{i=1}^n\phi(i)ans2=i=1nμ(i)ans_2=\sum_{i=1}^n\mu(i)
n<231n<2^{31}TT组询问。

Input

一共T+1T+1
11行为数据组数T(T10)T(T\le10)
2T+12\sim T+1行每行一个非负整数NN,代表一组询问

Output

一共TT行,每行两个用空格分隔的数ans1,ans2ans_1,ans_2

Read more »

Problem

【SCOI2012】滑雪与时间胶囊

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

Description

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

Input

输入的第一行是两个整数NNMM
接下来11行有NN个整数HiH_i,分别表示每个景点的高度。
接下来MM行,表示各个景点之间轨道分布的情况。每行33个整数,Ui,Vi,KiU_i,V_i,K_i。表示
编号为UiU_i的景点和编号为ViV_i的景点之间有一条长度为KiK_i的轨道。

Output

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

Read more »

Problem

【POI2000】病毒

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

Description

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

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

Input

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

Output

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

Read more »

Problem

Mato的文件管理

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

Description

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

Input

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

Output

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

Read more »

Problem

【WC2011】Xor

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

Description

![](https://www.lydsy.com/JudgeOnline/images/2606_1.jpg)

Input

第一行包含两个整数NNMM,表示该无向图中点的数目与边的数目。
接下来MM行描述MM条边,每行三个整数Si,Ti,DiS_i,T_i,D_i,表示SiS_iTiT_i之间存在 一条权值为DiD_i的无向边。
图中可能有重边或自环。

Output

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

Read more »

Problem

【SCOI2016】幸运数字

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

Description

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

Input

第一行包含22个正整数n,qn,q,分别表示城市的数量和旅行者数量。第二行包含nn个非负整数,其中第ii个整数GiG_i表示ii号城市的幸运值。随后n1n-1行,每行包含两个正整数x,yx,y,表示xx号城市和yy号城市之间有一条道路相连。随后qq行,每行包含两个正整数x,yx,y,表示这名旅行者的旅行计划是从xx号城市到yy号城市。

Output

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

Read more »

Problem

曼哈顿最小生成树

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

Description

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

Input

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

Output

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

Read more »