Problem

Shopping Offers

Description

In a shop each kind of product has a price. For example, the price of a flower is ICU (Informatics Currency Units) and the price of a vase is ICU. In order to attract more customers, the shop introduces some special offers.
A special offer consists of one or more product items for a reduced price. Examples: three flowers for ICU instead of , or two vases together with one flower for ICU instead of .
Write a program that calculates the price a customer has to pay for certain items, making optimal use of the special offers. That is, the price should be as low as possible. You are not allowed to add items, even if that would lower the price.
For the prices and offers given above, the (lowest) price for three flowers and two vases is ICU: two vases and one flower for the reduced price of ICU and two flowers for the regular price of ICU.

Input

Your program is to read from standard input. The first line contains the number of different kinds of products in the basket . Each of the next b lines contains three values , , and . The value is the (unique) product code . The value indicates how many items of this product are in the basket . The value p is the regular price per item . Notice that all together at most items can be in the basket. The line contains the number of special offers . Each of the next lines describes one offer by giving its structure and its reduced price. The first number n on such a line is the number of different kinds of products that are part of the offer . The next n pairs of numbers indicate that items with product code are involved in the offer. The last number on the line stands for the reduced price . The reduced price of an offer is less than the sum of the regular prices.

Output

Your program is to write to standard output. Output one line with the lowest possible price to be paid.

Problem

K大数查询

Description

有个位置，个操作。操作有两种，每次操作如果是的形式表示在第个位置到第个位置，每个位置加入一个数；如果是形式，表示询问从第个位置到第个位置，第大的数是多少。

Input

第一行，
接下来行，每行形如或

Output

输出每个询问的结果

Problem

Three Palindromes

Description

Can we divided a given string into three nonempty palindromes?

Input

First line contains a single integer which denotes the number of test cases.
For each test case , there is an single line contains a string which only consist of lowercase English letters.

Output

For each case, output the Yes or No​ in a single line.

Problem

阿狸的打字机

Description

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有个按键，分别印有个小写英文字母和、两个字母。
经阿狸研究发现，这个打字机是这样工作的：

• 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
• 按一下印有的按键，打字机凹槽中最后一个字母会消失。
• 按一下印有的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入，纸上被打印的字符如下：



我们把纸上打印出来的字符串从开始顺序编号，一直到。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数（其中），打字机会显示第个打印的字符串在第个打印的字符串中出现了多少次。
阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

Input

输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。
第二行包含一个整数，表示询问个数。
接下来行描述所有由小键盘输入的询问。其中第行包含两个整数, ，表示第个询问为。

Output

输出行，其中第行包含一个整数，表示第个询问的答案。

Problem

维护序列

题目描述

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为的数列，不妨设为。有如下三种操作形式： 把数列中的一段数全部乘一个值; 把数列中的一段数全部加一个值; 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模的值。

输入输出格式

输入格式
第一行两个整数和(）。第二行含有N个非负整数,从左到右依次为, ()。第三行有一个整数，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作：“ ”(不含双引号)。表示把所有满足的改为。 操作：“ ”(不含双引号)。表示把所有满足的改为。 操作：“ ”(不含双引号)。询问所有满足的的和模的值 。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出格式
对每个操作，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。

Problem

Count on a tree

Description

给定一棵个节点的树，每个点有一个权值，对于个询问，你需要回答和这两个节点间第小的点权。其中是上一个询问的答案，初始为，即第一个询问的是明文。

Input

第一行两个整数。
第二行有个整数，其中第个整数表示点的权值。
后面行每行个整数，表示点到点有一条边。
最后行每行个整数，表示一组询问。

Output

行，表示每个询问的答案。最后一个询问不输出换行符

Problem

Matrix

Time Limit:
Memory Limit:

Description

Given an matrix , whose elements are either or . means the number in the row and column. Initially we have .
We can change the matrix in the following way. Given a rectangle whose upper-left corner is and lower-right corner is , we change all the elements in the rectangle by using “not” operation (if it is a ‘’ then change it into ‘’ otherwise change it into ‘’). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.

1. () changes the matrix by using the rectangle whose upper-left corner is and lower-right corner is .
2. () querys .

Input

The first line of the input is an integer representing the number of test cases. The following X blocks each represents a test case.
The first line of each block contains two numbers and (, ) representing the size of the matrix and the number of the instructions. The following lines each represents an instruction having the format “ ” or “ ”, which has been described above.

Output

For each querying output one line, which has an integer representing .
There is a blank line between every two continuous test cases.

Problem

Intervals

Description

You are given closed, integer intervals and integers .
Write a program that:
reads the number of intervals, their end points and integers from the standard input, computes the minimal size of a set of integers which has at least common elements with interval , for each , writes the answer to the standard output.

Input

The first line of the input contains an integer () – the number of intervals. The following n lines describe the intervals. The line of the input contains three integers , and separated by single spaces and such that and .

Output

The output contains exactly one integer equal to the minimal size of set sharing at least elements with interval , for each .

Problem

可持久化并查集 by zky

Description

个集合 个操作
操作：
合并所在集合
回到第次操作之后的状态(查询算作操作)
询问是否属于同一集合，是则输出否则输出

Input

第一行两个整数
以后行，每行三个或两个整数或，意义如上所述

Ouput

对于每个操作，输出

Problem

【APIO2009】ATM

Description

城中的道路都是单向的。不同的道路由路口连接。按照法律规定，在每个路口都设立了一个银行的取款机。令人奇怪的是，的酒吧都设在路口，虽然并不是每个路口都设有酒吧。
计划实施有史以来最惊天动地的抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的机，最终他将在一个酒吧庆祝他的胜利。
使用高超的黑客技术，他获知了每个机中可以掠取的现金数额。他希望你帮助他计算从市中心出发最后到达某酒吧时最多能抢劫的现金数额。他希望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可以经过同一路口或道路任意多次。但只要他抢劫某个机后，该机就不会再有钱了。

Input

第一行包含两个整数、。表示路口的个数，表示道路条数。接下来行，每行两个整数，这两个整数都在到之间，第行的两个整数表示第i条道路的起点和终点的路口编号。接下来行，每行一个整数，按顺序表示每个路口处的机中的钱数。接下来一行包含两个整数、，表示市中心的编号，也就是出发的路口。表示酒吧数目。接下来的一行中有个整数，表示个有酒吧的路口的编号。

Output

输出一个整数，表示从市中心开始到某个酒吧结束所能抢劫的最多的现金总数。