Problem

Problem

向量

Description

你要维护一个向量集合，支持以下操作：

1. 插入一个向量
2. 删除插入的第个向量
3. 查询当前集合与点积的最大值是多少，如果当前是空集输出0

Input

第一行输入一个整数，表示操作个数
接下来行，每行先是一个整数表示类型，如果，输入向量；如果，输入表示删除第个向量；否则输入，查询与向量点积最大值是多少
保证一个向量只会被删除一次，不会删没有插入过的向量

Output

对于每条的询问，输出一个答案

Problem

二叉树

Description

现在有一棵二叉树，所有非叶子节点都有两个孩子。
在每个叶子节点上有一个权值（有个叶子节点，满足这些权值为的一个排列）。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换，使得最终所有叶子节点的权值按照中序遍历写出来，逆序对个数最少。

Input

第一行一个整数。
下面每行一个数，

• 如果，表示这个节点非叶子节点，递归地向下读入其左孩子和右孩子的信息，
• 如果，表示这个节点是叶子节点，权值为。

Output

一行，最少逆序对个数。

Problem

算术天才⑨与等差数列

Description

算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为的序列，其中第个数为。
他想考考你，每次他会给出询问，问区间内的数从小到大排序后能否形成公差为的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。

Input

第一行包含两个正整数，分别表示序列的长度和操作的次数。
第二行包含个整数，依次表示序列中的每个数。
接下来行，每行一开始为一个数，
若，则接下来两个整数，表示把修改为。
若，则接下来三个整数，表示一个询问。
在本题中，都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。

Output

输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。

Problem

【USACO2008 Open】奶牛的邻居

Description

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标．当满足下列两个条件之一，两只奶牛和是属于同一个群的：

1. 两只奶牛的曼哈顿距离不超过，即.
2. 两只奶牛有共同的邻居，即存在一只奶牛，使与与均同属一个群．

给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛。

Input

第行输入和，之后行每行输入一只奶牛的坐标。

Output

仅一行，先输出牛群数，再输出最大牛群里的牛数，用空格隔开。

Problem

【Usaco2008 Jan】猜数游戏

Description

为了提高自己低得可怜的智商，奶牛们设计了一个新的猜数游戏，来锻炼她们的逻辑推理能力。
游戏开始前，一头指定的奶牛会在牛棚后面摆堆干草，每堆有若干捆，并且没有哪两堆中的草一样多。
所有草堆排成一条直线，从左到右依次按编号，每堆中草的捆数在之间。
然后，游戏开始。
另一头参与游戏的奶牛会问那头摆干草的奶牛个问题，问题的格式如下：
编号为的草堆中，最小的那堆里有多少捆草？
对于每个问题，摆干草的奶牛回答一个数字，但或许是不想让提问的奶牛那么容易地得到答案，又或许是她自己可能记错每堆中干草的捆数，总之，她的回答不保证是正确的。
请你帮助提问的奶牛判断一下，摆干草的奶牛的回答是否有自相矛盾之处。

Input

• 第行: 个用空格隔开的整数：和
• 第行: 每行为个用空格隔开的整数，描述了一个问题以及它对应的回答

  Output

  如果摆干草的奶牛有可能完全正确地回答了这些问题，输出；否则输出个中的数，表示这个问题的答案与它之前的那些回答有冲突之处。
  注意：如果有冲突出现输出一个数，使得前个命题不冲突。
  阅读全文 »

Problem

【HEOI2014】大工程

Description

国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。
我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。
在两个国家之间建一条新通道需要的代价为树上的最短路径。
现在国家有很多个计划，每个计划都是这样，我们选中了个点，然后在它们两两之间新建条新通道。
现在对于每个计划，我们想知道：

1. 这些新通道的代价和
2. 这些新通道中代价最小的是多少
3. 这些新通道中代价最大的是多少

Input

第一行表示点数。
接下来行，每行两个数表示和之间有一条边。
点从开始标号。接下来一行表示计划数。
对每个计划有行，第一行表示这个计划选中了几个点。
第二行用空格隔开的个互不相同的数表示选了哪个点。

Output

输出行，每行三个数分别表示代价和，最小代价，最大代价。

Problem

【ZJOI2007】棋盘制作

Description

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。而我们的主人公，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友决定将棋盘扩大以适应他们的新规则。
找到了一张由个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。不过还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。于是找到了即将参加全国信息学竞赛的你，你能帮助他么？

Input

第一行包含两个整数和，分别表示矩形纸片的长和宽。
接下来的行包含一个的矩阵，表示这张矩形纸片的颜色（表示白色，表示黑色）。

Output

包含两行，每行包含一个整数。
第一行为可以找到的最大正方形棋盘的面积；
第二行为可以找到的最大矩形棋盘的面积。

Problem

楼房重建

Description

的楼房外有一大片施工工地，工地上有栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。
为了简化问题，我们考虑这些事件发生在一个二维平面上。在平面上点的位置，第栋楼房可以用一条连接和的线段表示，其中为第栋楼房的高度。如果这栋楼房上任何一个高度大于的点与的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。
施工队的建造总共进行了天。初始时，所有楼房都还没有开始建造，它们的高度均为。在第天，建筑队将会将横坐标为的房屋的高度变为(高度可以比原来大——修建，也可以比原来小——拆除，甚至可以保持不变——建筑队这天什么事也没做)。请你帮数数每天在建筑队完工之后，他能看到多少栋楼房？

Input

第一行两个正整数。
接下来行，每行两个正整数。

Output

行，第行一个整数表示第天过后能看到的楼房有多少栋。

Problem

【CERC2007】Robotic Sort

Description

Input

输入共两行，第一行为一个整数，表示物品的个数，。
第二行为个用空格隔开的正整数，表示个物品最初排列的编号。

Output

输出共一行，个用空格隔开的正整数，表示第次操作前第小的物品所在的位置。
注意：如果第次操作前，第小的物品己经在正确的位置上，我们将区间反转(单个物品)。