2024年3月7日发(作者：)

ｄａｙ１　Ｔ１∶转圈游戏（（ｃｉｒｃｌｅ．ｃｐｐ／ｃ／ｐａｓ）【问题描述】ｎ个小伙伴（编号从０到ｎ－１）围坐一圈玩游戏。按照顺时针方向给ｎ个位置编号，从０到ｎ－１。最初，第０号小伙伴在第０号位置，第１号小伙伴在第１号位置，……，依此类推。游戏规则如下∶每一轮第０号位置上的小伙伴顺时针走到第　ｍ　号位置，第１号位置小伙伴走到第ｍ＋１号位置，……，依此类推，第ｎ一ｍ号位置上的小伙伴走到第０号位置，第ｍ－１　号位置。【输入】ｎ－ｍ＋１号位置上的小伙伴走到第１号位置，……，第　ｎ－１号位置上的小伙伴顺时针走到第现在，一共进行了１０＊轮，请问ｘ号小伙伴最后走到了第几号位置。输入文件名为ｃｉｒｃｌｅ．ｉｎ。输入共１行，包含４个整数ｎ、ｍ、ｋ、ｘ，每两个整数之间用一个空格隔开。【输出】输出文件名为　ｃｉｒｅｌｅ．ｏｕｔ。输出共１行，包含１个整数，表示１０轮后ｘ号小伙伴所在的位置编号。１０　３　４　５ｃｉｒｃｌｅ．ｉｎ【输入输出样例】ｃｉｒｃｌｅ．ｏｕｔ５【数据说明】对于３０？？数据，０＜ｋ＜７；对于８０？？数据，０＜ｋ＜１０７；对于１００？？数据，１＜ｎ＜１，０００，０００，０＜ｍ＜ｎ，１≤ｘ≤ｎ，０＜ｋ＜１０°。

ｄａｙ１　Ｔ２∶火柴排队（ｍａｔｃｈ．ｃｐｐ／ｃ／ｐａｓ））【问题描述】涵涵有两盒火柴，每盒装有ｎ根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为∶Ｚ，（ａ；－ｂ）２，其中ａ表示第一列火柴中第ｉ个火柴的高度，ｂ，表示第二列火柴中第ｉ个火柴的高度。每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对　９９９９，９９７取模的结果。【输入】输入文件为ｍａｔｃｈ．ｉｎ。共三行，第一行包含一个整数ｎ，表示每盒中火柴的数目。第二行有ｎ个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。第三行有ｎ个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。【输出】输出文件为　ｍａｔｃｈ．ｏｕｔ。输出共一行，包含一个整数，表示最少交换次数对９９，９９９９７取模的结果。４ｍａｔｃｈ．ｉｎ【输入输出样例１】ｍａｔｃｈ．ｏｕｔ３２　１４２　３１４【输入输出样例说明】工最小距离是０，最少需要交换１次，比如∶交换第１列的前２根火柴或者交换第２列的前２根火柴。ｍａｔｃｈ．ｉｎ４１　３　４　２１７　２４【输入输出样例２】ｍａｔｃｈ．ｏｕｔ乙【输入输出样例说明】】最小距离是　１０，最少需要交换２次，比如∶交换第１列的中间２根火柴的位置，再交换第２列中后２根火柴的位置。【数据范围】对于１０？？数据，１≤ｎ　≤１０；对于３０？？数据，１≤ｎ　≤１００；对于６０？？数据，１≤ｎ　≤１，０００∶对于１００？？数据，１≤ｎ≤１００，０００，０≤火柴高度≤２３１－１。

ｄａｙ１　Ｔ３∶货车运输（ｔｒｕｃｋ．ｃｐｐ／ｃ／ｐａｓ）【问题描述】Ａ　国有ｎ座城市，编号从１到ｎ，城市之间有ｍ条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有ｑ辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。【输入】输入文件名为ｔｒｕｃｋ．ｉｎ。路。输入文件第一行有两个用一个空格隔开的整数ｎ，ｍ，表示Ａ国有ｎ　座城市和　ｍ条道接下来ｍ　行每行３个整数ｘ、ｙ、ｚ，每两个整数之间用一个空格隔开，表示从ｘ号城市到ｙ号城市有一条限重为ｚ的道路。注意∶ｘ不等于ｙ，两座城市之间可能有多条道路。接下来一行有一个整数ｇ，表示有ｑ辆货车需要运货。接下来ｑ行，每行两个整数ｘ、ｙ，之间用一个空格隔开，表示一辆货车需要从ｘ城市运输货物到ｙ城市，注意∶ｘ不等于ｙ。【输出】输出文件名为　ｔｒｕｃｋ．ｏｕｔ。输出共有　ｑ　行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出－１。４３１２４ｔｒｕｃｋ．ｉｎ【输入输出样例】３１１２　３３ｅ－１了ｔｒｕｃｋ．ｏｕｔ１３【数据说明】对于３０？？数据，０＜ｎ＜１，０００，０＜ｍ＜１０，０００，０＜ｑ＜１，０００；对于６０？？数据，０＜ｎ＜１，０００，０＜ｍ＜５０，０００，０＜ｑ＜１，０００；１４ｅ１３对于１００？？数据，０＜ｎ＜１０，０００，０＜ｍ＜５０，０００，０＜ｑ＜３０，０００，０≤ｚ≤１００，０００。

ｄａｙ２　Ｔ１∶积木大赛（ｂｌｏｃｋ．ｃｐｐ／ｃ／ｐａｓ）【题目描述】春春幼儿园举办了一年一度的＂积木大赛＂。今年比赛的内容是搭建一座宽度为ｎ的大厦，大厦可以看成由ｎ块宽度为１的积木组成，第ｉ块积木的最终高度需要是ｈ。在搭建开始之前，没有任何积木（可以看成ｎ块高度为　０　的积木）。接下来每次操作，小朋友们可以选择一段连续区间【Ｌ，Ｒ】，然后将第Ｌ块到第Ｒ块之间（含第Ｌ块和第Ｒ块）所有积木的高度分别增加１。小Ｍ是个聪明的小朋友，她很快想出了建造大厦的最佳策略，使得建造所需的操作次数最少。但她不是一个勤于动手的孩子，所以想请你帮忙实现这个策略，并求出最少的操作次数。【输入】输入文件为ｂｌｏｃｋ　ｉｎ输入包含两行，第一行包含一个整数ｎ，表示大厦的宽度。第二行包含ｎ个整数，第ｉ个整数为ｈｚ。【输出】输出文件为ｂｌｏｃｋ．ｏｕｔ仅一行，即建造所需的最少操作数。ｂｌｏｃｋ．ｉｎ５２３４１２【输入输出样例】ｂｌｏｃｋ．ｏｕｔ合【样例解释】其中一种可行的最佳方案，依次选择［１，５］　［１，３］　［２，３］　［３，３］　［５，５］【数据范围】对于３０？？数据，有１≤ｎ≤１０；对于７０？？数据，有１≤ｎ　≤１０００；对于１００？？数据，有１≤ｎ≤１０００００，０≤ｈ≤１００００。

ｄａｙ２　Ｔ２∶　花匠【问题描述】花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。具体而言，栋栋的花的高度可以看成一列整数ｈ，ｈｚ…，ｈｎ。设当一部分花被移走后，剩下的花的高度依次为ｇｇ…，ｇｍ，则栋栋希望下面两个条件中至少有一个满足∶条件　Ａ∶对于所有的ｉ，９ａｉ　＞９２ｉ－１且ｇ２ｉ＞９２ｔ＋１；请问，栋栋最多能将多少株花留在原地。条件Ｂ∶对于所有的ｉ，ｇ２ｉ＜９２ｚｌ－１，且ｇ２ｉ＜９２４１。注意上面两个条件在ｍ　＝１时同时满足，当ｍ＞１时最多有一个能满足。【输入】输入文件为　ｆｌｏｗｅｒ．ｉｎ。输入的第一行包含一个整数ｎ；表示开始时花的株数。第二行包含ｎ个整数，依次为ｈ，ｈｚ…，ｈｎ，表示每株花的高度。【输出】输出文件为　ｆｌｏｗｅｒ．ｏｕｔ。输出一行，包含一个整数ｍ，表示最多能留在原地的花的株数。ｆｌｏｗｅｒ．ｉｎ【输入输出样例】５３　２　１２足条件Ｂ。【数据范围】对于２０？？数据，ｎ≤１０；与ｆｌｏｗｅｒ．ｏｕｔ了【输入输出样例说明】有多种方法可以正好保留３株花，例如，留下第１、４、５株，高度分别为５、１、２，满对于３０？？数据，ｎ　≤２５；对于７０？？数据，ｎ≤１０００，０≤ｈ；≤１０００；对于　１００？？数据，１≤ｎ≤１００，０００，０≤ｈ；≤１，０００，０００，所有的ｈ；随机生成，所有随机数服从某区间内的均匀分布。

ｄａｙ２　Ｔ３∶华容道【问题描述】小Ｂ　最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，，他想到用编程来完成华容道∶给定一种局面，华容道是否根本就无法完成，如果能完成，最少需要多少时间。小Ｂ玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的∶１．在一个ｎ＊ｍ棋盘上有ｎ＊ｍ个格子，其中有且只有一个格子是空白的，其余ｎ＊ｍ－１个格子上每个格子上有一个棋子，每个棋子的大小都是１＊１的；２．　有些棋子是固定的，有些棋子则是可以移动的；３．　任何与空白的格子相邻（有公共的边）的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。给定一个棋盘，游戏可以玩ｑ次，当然，每次棋盘上固定的格子是不会变的，但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第ｉ次玩的时候，空白的格子在第　ＥＸ；行第　ＥＹ；列，指定的可移动棋子的初始位置为第　ＳＸ，行第ＳＹ列，目标位置为第ＴＸ行第ＴＹ，列。假设小　Ｂ　每秒钟能进行一次移动棋子的操作，而其他操作的时间都可以忽略不计。请你告诉小Ｂ每一次游戏所需要的最少时间，或者告诉他不可能完成游戏。【输入】输入文件为　ｐｕｚｚｌｅ．ｉｎ。第一行有３个整数，每两个整数之间用一个空格隔开，依次表示ｎ、ｍ和　ｑ；接下来的ｎ行描述一个ｎ＊ｍ的棋盘，每行有ｍ个整数，每两个整数之间用一个空格隔开，每个整数描述棋盘上一个格子的状态，０表示该格子上的棋子是固定的，１表示该格子上的棋子可以移动或者该格子是空白的。接下来的ｑ行，每行包含６个整数依次是ＥＸ、ＥＹ、ＳＸ、ＳＹ、ＴＸ、ＴＹ，每两个整数之间用一个空格隔开，表示每次游戏空白格子的位置，指定棋子的初始位置和目标位置。【输出】输出文件名为　ｐｕｚｚｌｅ．ｏｕｔ。输出有ｑ行，每行包含１个整数，表示每次游戏所需要的最少时间，如果某次游戏无法完成目标则输出－１。ｐｕｚｚｌｅ．ｉｎ３　４　２ｏ１　１　１ｏ　１１　ｏｏ　１ｏｏ３２１２２　２【输入输出样例】ｐｕｚｚｌｅ．ｏｕｔ－１乙１２　２　２３２

【输入输出样例说明】棋盘上划叉的格子是固定的，红色格子是目标位置，圆圈表示棋子，其中绿色圆圈表示目标棋子。１．第一次游戏，空白格子的初始位置是（３．２）（图中空白所示），游戏的目标是将初始位置在（１．２）上的棋子（图中绿色圆圈所代表的棋子）移动到目标位置（２．２）（图中红色的格子）上。移动过程如下∶Ｏ２．第二次游戏，空白格子的初始位置是（１．２）（图中空白所示），游戏的目标是将初始位置在（２，２）上的棋子（图中绿色圆圈所示）移动到目标位置（３，２）上。初始状态Ｏ法完成。。。。。。０初始状态ＯＯ勺第一步之后第二步之后ＯＯＯＯ。。ＯＯＯ要将指定块移入目标位置，必须先将空白块移入目标位置，空白块要移动到目标位置，必然是从位置（２，２）上与当前图中目标位置上的棋子交换位置，之后能与空白块交换位置的只有当前图中目标位置上的那个棋子，因此目标棋子永远无法走到它的目标位置，游戏无【数据范围】对于３０？？数据，１≤ｎ，ｍ　≤１０，ｑ＝１；对于６０？？数据，１≤ｎ，ｍ　≤３０，ｑ≤１０；对于１００？？数据，１≤ｎ，ｍ　≤３０，ｑ≤５００。