NIRVANA

Problem

BZOJ3676【APIO2014】回文串

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

Description

给你一个由小写拉丁字母组成的字符串 $s$。我们定义 $s$ 的一个子串的存在值为这个子串在 $s$ 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 $s$，求所有回文子串中的最大存在值。

Input

输入只有一行，为一个只包含小写字母$(a-z)$的非空字符串 $s$。

Output

输出一个整数，表示所有回文子串中的最大存在值。

Problem

BZOJ3676【NOI2015】品酒大会

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

Description

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。
在大会的晚餐上，调酒师 $Rainbow$ 调制了 $n$ 杯鸡尾酒。这 $n$ 杯鸡尾酒排成一行，其中第 $i$ 杯酒 $(1\le i\le n)$ 被贴上了一个标签 $s_i$，每个标签都是 $26$ 个小写英文字母之一。设 $str(i,j)$ 表示第 $i$ 杯酒到第 $j$ 杯酒的 $j-i+1$ 个标签顺次连接构成的字符串。若 $str(l_1,r_1)=str(l_2,r_2)$，其中$1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le n$，$l_1\ne l_2$，$r_1-l_1+1=r_2-l_2+1=p$，则称第 $l_1$ 杯酒与第 $l_2$ 杯酒是“$p$ 相似”的。当然两杯“$p$ 相似” $(p>1)$ 的酒同时也是“$1$ 相似”、“$2$ 相似”、……、“$(p-1)$ 相似”的。特别地，对于任意的$1\le p,q\le n, p\ne q$，第 $p$ 杯酒和第 $q$ 杯酒都是“$0$ 相似”的。
在品尝环节上，品酒师 $Freda$ 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 $i$ 杯酒$(1\le i\le n)$ 的美味度为 $a_i$。现在 $Rainbow$ 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 $i$ 杯酒与第 $j$ 杯酒调兑在一起，将得到一杯美味度为 $a_i\times a_j$ 的酒。现在请各位品酒师分别对于 $p = 0,1,2,\cdots ,p-1$，统计出有多少种方法可以选出 $2$ 杯“$p$ 相似”的酒，并回答选择 $2$ 杯“$p$相似”的酒调兑可以得到的美味度的最大值。

Input

第 $1$ 行包含 $1$ 个正整数 $n$，表示鸡尾酒的杯数。
第 $2$ 行包含一个长度为 $n$ 的字符串 $S$，其中第 i 个字符表示第 $i$ 杯酒的标签。
第 $3$ 行包含 $n$ 个整数，相邻整数之间用单个空格隔开，其中第 $i$ 个整数表示第 $i$ 杯酒的美味度 $a_i$。

Output

输出文件包括 $n$ 行。第 $i$ 行输出 $2$ 个整数，中间用单个空格隔开。第 $1$个整数表示选出两杯“$i-1$ 相似”的酒的方案数，第 $2$ 个整数表示选出两杯“$i-1$ 相似”的酒调兑可以得到的最大美味度。若不存在两杯“$i-1$ 相似”的酒，这两个数均为 $0$。

Problem

Tree

Time Limit: $30 Sec$
Memory Limit: $512 MB$

Description

给定$N$个点以及每个点的权值，要你处理接下来的$M$个操作。操作有$4$种。操作从$0$到$3$编号。点从$1$到$N$编号。
$0$.后接两个整数 $(x, y)$，代表询问从$x$到$y$的路径上的点的权值的$xor$和。保证$x$到$y$是联通的。
$1$.后接两个整数 $(x, y)$，代表连接$x$到$y$，若x到y已经联通则无需连接。
$2$.后接两个整数 $(x, y)$，代表删除边$ (x, y)$，不保证边 $(x, y)$ 存在。
$3$.后接两个整数 $(x, y)$，代表将点$x$上的权值变成$y$。

Input

第$1$行两个整数，分别为$N$和$M$，代表点数和操作数。
第$2$行到第$N+1$行，每行一个整数，整数在 $[1, 10^9]$ 内，代表每个点的权值。
第$N+2$行到第$N+M+1$行，每行三个整数，分别代表操作类型和操作所需的量。

Output

对于每一个$0$号操作，你须输出$x$到$y$的路径上点权的$xor$和。

Problem

Beauty Contest

Description

贝茜在牛的选美比赛中赢得了冠军”牛世界小姐”。因此,贝西会参观$N$($2\le N\le 50000$)个农场来传播善意。世界将被表示成一个二维平面,每个农场位于一对整数坐标$(x,y)$($-10000\le x,y \le 10000$)。没有两个农场共享相同的一对坐标。
尽管贝西沿直线前往下一个农场，但牧场之间的距离可能很大,所以她需要一个手提箱保证在每一段旅程中她有足够吃的食物。她想确定她可能需要旅行的最大可能距离,她要知道她必须带的手提箱的大小。帮助贝西计算农场的最大距离。

Input

第$1$行一个整数$n$，第$2\sim n+1$行两个整数$x_i\ y_i$表示$n$个农场中第$i$个的坐标

Output

一行，最远距离的平方

Problem

序列

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

Description

给出一个长度为$N$的正整数序列$C_i$，求一个子序列，使得原序列中任意长度为$M$的子串中被选出的元素不超过$K(K,M\le 100)$ 个，并且选出的元素之和最大。

Input

第$1$行三个数$N,M,K$。 接下来$1$行$N$个正整数表示$C_i$。

Output

最大和。

Problem

【SHOI2003】Pacman 吃豆豆

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

Description

两个$\mathrm{PACMAN}$吃豆豆。一开始的时候，$\mathrm{PACMAN}$都在坐标原点的左下方，豆豆都在右上方。$\mathrm{PACMAN}$走到豆豆处就会吃掉它。$\mathrm{PACMAN}$行走的路线很奇怪，只能向右走或者向上走，他们行走的路线不可以相交。 请你帮这两个$\mathrm{PACMAN}$计算一下，他们俩加起来最多能吃掉多少豆豆。

Input

第一行为一个整数$N$，表示豆豆的数目。 接下来 $N$ 行，每行一对正整数，表示第$i$个豆豆的坐标。任意两个豆豆的坐标都不会重合。

Output

仅有一行包含一个整数，即两个$\mathrm{PACMAN}$加起来最多能吃掉的豆豆数量

Problem

学习小组

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

Description

坑校准备鼓励学生参加学习小组。
共有$n$个学生，$m$个学习小组，每个学生有一定的喜好，只愿意参加其中的一些学习小组，但是校领导为学生考虑，规定一个学生最多参加$k$个学习小组。财务处的大叔就没那么好了，他想尽量多收钱，因为每个学生参加学习小组都要交一定的手续费，不同的学习小组有不同的手续费。然而，事与愿违，校领导又决定对学习小组组织者进行奖励，若有$a$个学生参加第i个学习小组，那么给这个学习小组组织者奖励$C_i\times a^2$元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱（若为负数，则输出负数）（$支出=总奖励费-总手续费$）。

Input

输入有若干行，第一行有三个用空格隔开的正整数$n、m、k$。接下来的一行有$m$个正整数，表示每个$C_i$。第三行有$m$个正整数，表示参加每个学习小组需要交的手续费$F_i$。再接下来有一个$n$行$m$列的矩阵，表若第$i$行$j$列的数字是$1$，则表示第$i$个学生愿意参加第$j$个学习小组，若为$0$，则为不愿意。

Output

输出只有一个整数，为最小的支出。

Problem

【HNOI2001】软件开发

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

Description

某软件公司正在规划一项$n$天的软件开发计划，根据开发计划第$i$天需要$n_i$个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，$A$种方式的消毒需要$a$天时间，$B$种方式的消毒需要$b$天（$b>a$），$A$种消毒方式的费用为每块毛巾$f_A$, $B$种消毒方式的费用为每块毛巾$f_B$，而买一块新毛巾的费用为$f$（新毛巾是已消毒的，当天可以使用）；而且$f>f_A>f_B$。公司经理正在规划在这$n$天中，每天买多少块新毛巾、每天送多少块毛巾进行$A$种消毒和每天送多少块毛巾进行$B$种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行$A$种消毒和多少毛巾进行$B$种消毒，使公司在这项$n$天的软件开发中，提供毛巾服务的总费用最低。

Input

第$1$行为$n,a,b,f,f_A,f_B$. 第$2$行为$n_1,n_2,\cdots,n_n$. （注：$1\le f,f_A,f_B\le 60,1\le n\le 1000$）

Output

最少费用

Problem

游行

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

Description

每年春季，在某岛屿上都会举行游行活动。
在这个岛屿上有$N$个城市，$M$条连接着城市的有向道路。
你要安排英雄们的巡游。英雄从城市$s_i$出发，经过若干个城市，到城市$t_i$结束，需要特别注意的是，每个英雄的巡游的$s_i$可以和$t_i$相同，但是必须至少途径2个城市。
每次游行你的花费将由$3$部分构成：

• 每个英雄游行经过的距离之和，需要特别注意的是，假如一条边被途径了$k$次，那么它对答案的贡献是$k\times c_i$，$c_i$表示这条边的边权。
• 如果一个英雄的巡游的$s_i$不等于$t_i$，那么会额外增加$C$的费用。因为英雄要打的回到起点。
• 如果一个城市没有任何一个英雄途经，那么这个城市会很不高兴，需要$C$费用的补偿。

你有无数个的英雄。你要合理安排游行方案，使得费用最小。
由于每年，$C$值都是不一样的。所以你要回答$Q$个询问，每个询问都是，当$C$为当前输入数值的时候的答案。

Input

第一行正整数$N,M,Q$ 。
接下来的$M$行，每行$a_i,b_i,c_i$，表示有一条从$a_i$到$b_i$，边权为$c_i$的有向道路。保证不会有自环，但不保证没有重边。
接下来$Q$行，每行一个$C$，表示询问当每次费用为$C$时的最小答案。

Output

$Q$行，每行代表一个询问的答案。

Problem

【HNOI2007】梦幻岛宝珠

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

Description

给你N颗宝石，每颗宝石都有重量和价值。要你从这些宝石中选取一些宝石，保证总重量不超过W，且总价值最大，输出最大的总价值。
数据范围：$N\le 100，W\le 2^{30}$，且保证每颗宝石的重量可以表示为$a\times 2^b$的形式（其中$a\le 10,b\le 30$）

Input

输入文件中包含多组数据。每组数据的格式如下：第一行是两个正整数$n$和$W$，$1\le n\le 100,1\le W\le 2^{30}$，分别表示宝石的数目和最多能带走的宝石重量。接下来的$n$行，每行有两个正整数$weight_i$和$value_i$，$1\le weight_i\le 2^{30}, 0\le value_i\le 2^{30}$，分别表示第i颗宝石的重量和价值，且保证$weight_i$能写成$a\times 2^b(1\le a\le 10,0\le b\le 30)$的形式。同一行的两个正整数之间用空格隔开。最后一组数据的后面有两个$-1$，表示文件的结束。这两个$-1$并不代表一组数据，你不需对这组数据输出结果。并且输入文件中数据的组数不超过$20$。

Output

对于输入的每组数据，输出一个整数$C$，表示小P最多能带走的宝石的总价值。每个结果整数$C$单独占一行，且保证$C$不会超过$2^{30}$。