NIRVANA

Problem

外太空旅行

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

Description

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

Input

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

Output

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

Problem

【AMPPZ2014】Pillars

Time Limit: $5 Sec$
Memory Limit: $256 MB$
$Special\;Judge$

Description

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

Input

第一行包含三个整数$n,m,f$($1\le n,m\le 1000$且$n,m$都为偶数)。
接下来$f$行，每行两个整数$x,y$($1\le x<n$, $1\le y<m$)，表示该障碍物左下角的坐标。

Output

如果无解，输出$NIE$，否则第一行输出$TAK$，第二行输出方案。
方案包含$n\times m-4\times f$个字符，第$i$个字符表示第$i$步的移动方向，用$G$表示上，$D$表示下，$L$表示左，$P$表示右。

Problem

神奇的矩阵

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

Description

给出三个行数和列数均为$N$的矩阵$A$、$B$、$C$，判断$A\times B=C$是否成立。

Input

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

Output

对于每组数据，若$A\times B=C$成立，则输出$Yes$，否则$No$。每个答案占一行。

Problem

【AMPPZ2014】The Captain

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

Description

给定平面上的$n$个点，定义$(x1,y1)$到$(x2,y2)$的费用为$\min(|x1-x2|,|y1-y2|)$，求从$1$号点走到$n$号点的最小费用。

Input

第一行包含一个正整数$n$($2\le n\le 2\times 10^5$)，表示点数。
接下来$n$行，每行包含两个整数$x[i]$,$y[i]$($0\le x[i],y[i]\le 10^9$)，依次表示每个点的坐标。

Output

一个整数，即最小费用。

Problem

【HAOI2016】字符合并

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

Description

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

Input

第一行两个整数$n$，$k$。接下来一行长度为$n$的$01$串，表示初始串。接下来$2^k$行，每行一个字符$c_i$和一个整数$w_i$，$c_i$表示长度为$k$的$01$串连成二进制后按从小到大顺序得到的第$i$种合并方案得到的新字符，$w_i$表示对应的第$i$种方案对应获得的分数。$1\le n\le 300$, $0\le c_i\le 1$, $w_i\ge 1$, $k\le 8$

Output

输出一个整数表示答案

Problem

货车运输

题目描述

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

输入输出格式

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

Problem

【NOIp2008】双栈排序

题目描述

$Tom$最近在研究一个有趣的排序问题。如图所示，通过$2$个栈$S_1$和$S_2$，$Tom$希望借助以下$4$种操作实现将输入序列升序排序。
操作$a$: 如果输入序列不为空，将第一个元素压入栈$S_1$
操作$b$: 如果栈$S_1$不为空，将$S_1$栈顶元素弹出至输出序列
操作$c$: 如果输入序列不为空，将第一个元素压入栈$S_2$
操作$d$: 如果栈$S_2$不为空，将$S_2$栈顶元素弹出至输出序列
如果一个$1\sim n$的排列$P$可以通过一系列操作使得输出序列为$1,2,\cdots(n-1),n$，$Tom$就称$P$是一个“可双栈排序排列”。例如$(1,3,2,4)$就是一个“可双栈排序序列”，而$(2,3,4,1)$不是。下图描述了一个将$(1,3,2,4)$排序的操作序列：$<a,c,c,b,a,d,d,b>$

当然，这样的操作序列有可能有几个，对于上例$(1,3,2,4)$，$<a,c,c,b,a,d,d,b>$是另外一个可行的操作序列。$Tom$希望知道其中字典序最小的操作序列是什么。

输入输出格式

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

Problem

【HAOI2007】上升序列

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

Description

对于一个给定的$S={a_1,a_2,a_3,\cdots,a_n}$,若有$P={a_{x_1},a_{x_2},a_{x_3},\cdots,a_{x_m}}$,满足($x_1 < x_2 < \cdots< x_m$)且($a_{x_1} < a_{x_2} < \cdots < a_{x_m}$)。那么就称$P$为$S$的一个上升序列。如果有多个$P$满足条件，那么我们想求字典序最小的那个。任务给出$S$序列，给出若干询问。对于第$i$个询问，求出长度为$L_i$的上升序列，如有多个，求出字典序最小的那个（即首先$x_1$最小，如果不唯一，再看$x_2$最小……），如果不存在长度为$L_i$的上升序列，则输出$Impossible$.

Input

第一行一个$N$，表示序列一共有$N$个元素第二行$N$个数，为$a_1,a_2,\cdots,a_n$ 第三行一个$M$，表示询问次数。下面接$M$行每行一个数$L$，表示要询问长度为$L$的上升序列。$N\le 10000$，$M\le 1000$

Output

对于每个询问，如果对应的序列存在，则输出，否则输出$Impossible$.

Problem

【SCOI2005】互不侵犯King

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

Description

在$N\times N$的棋盘里面放$K$个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共$8$个格子。

Input

只有一行，包含两个数$N$, $K$ ($1 \le N \le 9$, $0 \le K \le N^2$)

Output

方案数。

Problem

【HAOI2015】树上操作

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

Description

有一棵点数为 $N$ 的树，以点 $1$ 为根，且树点有边权。然后有 $M$ 个
操作，分为三种：
操作 $1$ ：把某个节点 $x$ 的点权增加 $a$ 。
操作 $2$ ：把某个节点 $x$ 为根的子树中所有点的点权都增加 $a$ 。
操作 $3$ ：询问某个节点 $x$ 到根的路径中所有点的点权和。

Input

第一行包含两个整数 $N, M$ 。表示点数和操作数。接下来一行 $N$ 个整数，表示树中节点的初始权值。接下来 $N-1$ 行每行三个正整数 $fr, to$ ， 表示该树中存在一条边 $(fr, to)$ 。再接下来 $M$ 行，每行分别表示一次操作。其中第一个数表示该操作的种类$(1\sim 3)$ ，之后接这个操作的参数$(x\ 或者\ x\ a)$ 。

Output

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。