Problem

【AHOI2009】Mincut最小割

Description

两个国家正在交战，其中国的物资运输网中有个中转站，条单向道路。
设其中第 条道路连接了两个中转站，那么中转站可以通过该道路到达中转站，如果切断这条道路，需要代价。
现在国想找出一个路径切断方案，使中转站不能到达中转站，并且切断路径的代价之和最小。
小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：
问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？
问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？
请你回答这两个问题。

Input

第一行有个正整数，依次为。
第行到第行每行个正整数表示中转站到中转站之间有单向道路相连，单向道路的起点是，终点是，切断它的代价是。
注意：两个中转站之间可能有多条道路直接相连。
同一行相邻两数之间可能有一个或多个空格。

Output

对每条单向边，按输入顺序，依次输出一行，包含两个非即的整数，分别表示对问题一和问题二的回答（其中输出表示是，输出表示否）。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

Problem

【BJWC2017】神秘物质

Description

年，冬。
小诚退休以后，不知为何重新燃起了对物理学的兴趣。他从研究所借了些实验仪器，整天研究各种微观粒子。
这一天，小诚刚从研究所得到了一块奇异的陨石样本，便迫不及待地开始观测。在精密仪器的视野下，构成陨石的每个原子都无比清晰。
小诚发现，这些原子排成若干列，每一列的结构具有高度相似性。于是，他决定对单独一列原子进行测量和测试。
被选中的这列共有个顺序排列的原子。最初，第个原子具有能量。随着时间推移和人为测试，这列原子在观测上会产生两种变化：

• ：当前第个原子和第个原子合并，得到能量为的新原子；
• ：在当前第个原子和第个原子之间插入一个能量为的新原子。

对于一列原子，小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值，称为区间极差。因此，除了观测变化外，小诚还要经常统计这列原子的两类数据：

• ：当前第到第个原子之间的任意子区间中区间极差的最大值；
• ：当前第到第个原子之间的任意子区间中区间极差的最小值。

其中，子区间指的是长度至少是的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿，你能否帮助他实现上述的观测和测量呢？

Input

第一行，两个整数，分别表示最初的原子数目和事件总数。
第二行，个整数，由空格隔开，依次表示每个原子的能量。
接下来行， 每行为一个字符串和两个整数， 描述一次事件，格式见题目描述。

Output

输出若干行， 按顺序依次表示每次和类事件的测量结果。

Problem

【NOI2004】郁闷的出纳员

Description

公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。
这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。
工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。
老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。
好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？

Input

第一行有两个非负整数和。表示下面有多少条命令，表示工资下界。
接下来的行，每行表示一条命令。命令可以是以下四种之一：

命令、命令、命令中的是一个非负整数，命令中的是一个正整数。
在初始时，可以认为公司里一个员工也没有。
命令的条数不超过
命令和命令的总条数不超过
命令的条数不超过
每次工资调整的调整量不超过
新员工的工资不超过

Output

输出行数为命令的条数加一。
对于每条命令，你的程序要输出一行，仅包含一个整数，为当前工资第多的员工所拿的工资数，
如果大于目前员工的数目，则输出。
输出文件的最后一行包含一个整数，为离开公司的员工的总数。

Problem

最大团

Description

给出平面上个点的坐标，和一个半径为的圆心在原点的圆。
对于两个点，它们之间有连边，当且仅当它们的连线与圆不相交。
求此图的最大团。

Input

第一行两个整数和, 表示点数和圆的半径。
接下来行，每行两个整数和，表示第个点的坐标
保证每个点都严格在园外，且两两直线不与圆相切。

Output

输出一个整数：最大团的大小。

Problem

【HEOI2013】Segment

Description

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第条被插入的线段的标号为。
2. 给定一个数，询问与直线相交的线段中，交点最靠上的线段的编号。

Input

第一行一个整数，表示共个操作。
接下来行，每行第一个数为或。
若该数为，则后面跟着一个正整数，表示询问与直线相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。
若该数为，则后面跟着四个正整数，表示插入一条两个端点为,和,的线段。
其中为上一次询问的答案。初始时。

Output

对于每个操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。
若不存在与直线相交的线段，答案为。

Problem

【HNOI2008】Cards

Description

小春现在很清闲，面对书桌上的张牌，他决定给每张染色。
目前小春只有种颜色：红色，蓝色，绿色。他询问有多少种染色方案，很快就给出了答案。
进一步，小春要求染出张红色，张蓝色，张绿色。他又询问有多少种方案，想了一下，又给出了正确答案。
最后小春发明了种不同的洗牌法，他又问有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。
发现这个问题有点难度，决定交给你。
答案可能很大，只要求出答案除以的余数（为质数）。

Input

第一行输入个整数：。。
接下来行，每行描述一种洗牌法，每行有个用空格隔开的整数，恰为到的一个排列，表示使用这种洗牌法，第位变为原来的位的牌。
数据保证任意多次洗牌都可用种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。

Output

不同染法除以的余数。

Problem

概率好题

Description

甲乙进行比赛，他们各有个集合，每次随机从他们拥有的每个集合中都取出一个数。
，同理。若甲胜；若平局；否则乙胜。
分别求出甲胜、平局、乙胜的概率。
（显然这个概率是有理数，记为，则输出答案为（逆元）
注意：多组数据

Input

一个数，数据组数
对于每组数据 输入顺序为

1
2

k1 L1 R1 ... Lk1 Rk1
k2 L1 R1 ... Lk2 Rk2

Output

甲胜、平局、乙胜的概率。

Problem

Synchronized Subsequence

Statement

You are given a string of length , containing occurrences of a and occurrences of b.
You will choose some of the characters in . Here, for each , it is not allowed to choose exactly one of the following two: the occurrence of a and the occurrence of b. (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order).
Find the lexicographically largest string that can be obtained in this way.

Constraints

is a string of length containing occurrences of a and occurrences of b.

Input

Input is given from Standard Input in the following format:

Output

Print the lexicographically largest string that satisfies the condition.

Problem

【POI2007】对称轴osi

Description

小朋友——一个闻名遐迩的年轻数学家——有一个小MM，。小朋友非常喜欢他的MM，所以他很乐意帮助他的MM做数学作业。但是，就像所有科学的容器一样，FGD的大脑拒绝不停地重复思考同样的问题。不幸的是，是一个十分用功的学生，所以她不停地让帮助她检查她的作业。
一个阳光明媚的周末，的数学老师布置了非常多的寻找多边形的对称轴的题，足够她做相当长的一段时间了。在此之前已经决定去海边度过这个难得的假期，不过他还是觉得应该帮助他的MM对付可爱的数学作业。很快地，他找到了解决方案，最好写一个程序来帮助检查她的数学作业。
因为并非一个计算机科学家，所以他找到了他的好朋友你，请你帮助他完成这个任务。
请写一个程序：读入多边形的描述计算出每个多边形的对称轴数将计算的结果输出。

Input

输入的第一行包含一个正整数，为多边形的边数。
接下来，为个多边形的描述。
每个描述的第一行为一个正整数，表示了多边形的点数。
后面行每行两个整数和，依次表示多边形的顶点坐标。
多边形不一定是凸的，但是不自交。任何两条边都只有最多一个公共点，即它们的公共端点。此外，没有两条连续的边平行。

Output

你的程序应该输出正好行，第k行包含了一个整数——表示第个多边形有多少个对称轴。

Problem

【TJOI2018】Party

Description

小豆参加了的游园会，会场上每完成一个项目就会获得一个奖章，奖章只会是N,O,I的字样。在会场上他收集到了个奖章组成的串。
兑奖规则是奖章串和兑奖串的最长公共子序列长度为小豆最后奖励的等级。
现在已知兑奖串长度为，并且在兑奖串上不会出现连续三个奖章为NOI，即奖章中不会出现子串NOI。
现在小豆想知道各个奖励等级会对应多少个不同的合法兑奖串。

Input

第一行两个数，分别代表兑奖串的长度，小豆收集的奖章串的长度。
第二行一共个字符，表示小豆得到奖章串。

Output

一共行，第行表示小豆最后奖励等级为的不同的合法兑奖串的个数，可能这个数会很大，结果对取模。