Problem

Tree

Description

给你一棵树以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于

Input

（） 接下来行边描述管道，按照题目中写的输入 接下来是

Output

一行，有多少对点之间的距离小于等于

Problem

【AMPPZ2014】Petrol

Description

给定一个个点、条边的带权无向图，其中有个点是加油站。
每辆车都有一个油量上限，即每次行走距离不能超过，但在加油站可以补满。
次询问，每次给出，表示出发点是，终点是，油量上限为，且保证点和点都是加油站，请回答能否从走到。

Input

第一行包含三个正整数(,)，表示点数、加油站数和边数。
第二行包含个互不相同的正整数，表示每个加油站。
接下来行，每行三个正整数,,(,,)，表示和之间有一条长度为的双向边。
接下来一行包含一个正整数()，表示询问数。
接下来行，每行包含三个正整数(,,)，表示一个询问。

Output

输出行。第行输出第个询问的答案，如果可行，则输出，否则输出。

Problem

【AMPPZ2014】Pillars

Time Limit:
Memory Limit:

Description

给定一个的矩形，其中有f个的障碍物，其中任意两个障碍物中心之间的欧几里得距离至少为，
且每个障碍物的中心到边缘的距离至少为。请找到一条从左下角出发经过所有没有障碍物的点各一次的且最后回到左下角的回路。

Input

第一行包含三个整数(且都为偶数)。
接下来行，每行两个整数(, )，表示该障碍物左下角的坐标。

Output

如果无解，输出，否则第一行输出，第二行输出方案。
方案包含个字符，第个字符表示第步的移动方向，用表示上，表示下，表示左，表示右。

Problem

外太空旅行

Time Limit:
Memory Limit:

Description

在人类的触角伸向银河系的边缘之际，普通人上太空旅行已经变得稀松平常了。某理科试验班有个人，现在班主任要从中选出尽量多的人去参加一次太空旅行活动。
可是名同学并不是和平相处的。有的人，比如小和小整天狼狈为奸，是好朋友；但还有的人，比如杜鲁门和赫鲁晓夫就水火不相容。这名同学，由于是理科生，都非常的理性，所以“朋友的朋友就是朋友”和“敌人的朋友就是敌人”这两句话对这些同学无效。换句话说，有可能小和小是朋友，小和小是朋友，但是小和小两人势如水火。
任意两个人之间要不就是敌人，要不就是朋友。
因为在太空船上发生人员斗殴事件是很恶劣也很危险的，因此选出来参加旅行活动的同学必须互相之间都是朋友。你的任务就是确定最多可以选多少人参加旅行。

Input

第一行一个整数()。所有的同学按照编号。
接下来若干行，每行两个用空格隔开的整数 ()，表示和是朋友。
注意：如果一个数对或者没有在文件中出现，那么编号为和的两个同学就是敌人。

Output

仅仅一个数，即最多可以选多少人参加活动。

Problem

神奇的矩阵

Time Limit:
Memory Limit:

Description

给出三个行数和列数均为的矩阵、、，判断是否成立。

Input

题目可能包含若干组数据。
对于每组数据，第一行一个数，接下来给出三个的矩阵，依次为、、三个矩阵。

Output

对于每组数据，若成立，则输出，否则。每个答案占一行。

Problem

【AMPPZ2014】The Captain

Description

给定平面上的个点，定义到的费用为，求从号点走到号点的最小费用。

Input

第一行包含一个正整数()，表示点数。
接下来行，每行包含两个整数,()，依次表示每个点的坐标。

Output

一个整数，即最小费用。

NOIp2017滚粗记

Problem

货车运输

题目描述

国有 座城市，编号从 到 ，城市之间有 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入输出格式

输入格式：
输入文件名为 。
输入文件第一行有两个用一个空格隔开的整数 , ，表示 国有 座城市和 条道路。 接下来 行每行 个整数 、 、 ，每两个整数之间用一个空格隔开，表示从 号城市到 号城市有一条限重为 的道路。注意： 不等于 ，两座城市之间可能有多条道路 。
接下来一行有一个整数 ，表示有 辆货车需要运货。
接下来 行，每行两个整数 、，之间用一个空格隔开，表示一辆货车需要从 城市运输货物到 城市，注意： 不等于 。
输出格式：
输出文件名为 。
输出共有 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出。

Problem

【NOIp2008】双栈排序

题目描述

最近在研究一个有趣的排序问题。如图所示，通过个栈和，希望借助以下种操作实现将输入序列升序排序。
操作: 如果输入序列不为空，将第一个元素压入栈
操作: 如果栈不为空，将栈顶元素弹出至输出序列
操作: 如果输入序列不为空，将第一个元素压入栈
操作: 如果栈不为空，将栈顶元素弹出至输出序列
如果一个的排列可以通过一系列操作使得输出序列为，就称是一个“可双栈排序排列”。例如就是一个“可双栈排序序列”，而不是。下图描述了一个将排序的操作序列：

当然，这样的操作序列有可能有几个，对于上例，是另外一个可行的操作序列。希望知道其中字典序最小的操作序列是什么。

输入输出格式

输入格式：
输入文件的第一行是一个整数。
第二行有个用空格隔开的正整数，构成一个的排列。
输出格式：
输出文件共一行，如果输入的排列不是“可双栈排序排列”，输出数字；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

Problem

【HAOI2016】字符合并

Description

有一个长度为 的 串，你可以每次将相邻的 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 个字符确定。你需要求出你能获得的最大分数。

Input

第一行两个整数，。接下来一行长度为的串，表示初始串。接下来行，每行一个字符和一个整数，表示长度为的串连成二进制后按从小到大顺序得到的第种合并方案得到的新字符，表示对应的第种方案对应获得的分数。, , ,

Output

输出一个整数表示答案