U129134 小马斯的十道难题

题目难度还好吧，只是比较长。 我把十道题目的背景放上来就更长了。 注：这是 HARD 版本，代码量绝对不小。

现在有十道难题等待解决。加油！ ### 第一题： 众所周知，比赛共两个队，假设这两个队各五名球员(没有替补）。小马斯查到了每名球员的位置，得分，篮板和助攻。他很好奇每场比赛的得分王，篮板王助攻王和MVP是谁。其中得分王指得分最多的球员；篮板王指篮板最多的球员；助攻王指助攻最多的球员。MVP则为贡献值最高球员。 其中位置为PG，SG，SF贡献值为得分+篮板+助攻×2。 位置为PF，C贡献值为得分+篮板×2+助攻。 MVP仅能从总分最高的队伍产生。 球员仅能在得分王，篮板王，助攻王中当选**一项奖项**，且优先级为得分$>$篮板$>$助攻，即如果一位选手同时满足得分王、篮板王、助攻王的条件，他将优先获得得分王，随后才是篮板王，最后是助攻王。 ### 第二题： The parking lot of Atlantis is known to consist of $n × n $ grids. The numbers of one horizontal row and one vertical row are $1, 2, 3... N $. The grid in the $x $ row and $y $ column can be expressed as $(x, y) $. There are now $C $ cars in the parking lot at $(x_ 1,y_ 1),(x_ 2,y_ 2)......(x_ c,y_ c)$。 There are also $B $ mines in the parking lot at $(x)_ 1,y_ 1),(x_ 2,y_ 2)......(x_ b,y_ b)$。 (this $X_ I $not that $X_i$) The scope and impact of mines are as follows: - For the case there are cars or people in the box itself: the car or person in the box disappears, and then the box is damaged. - For the case that there is no car or person in the grid itself: the box is damaged, and the principle that if there is a car or person in its left/ right/ upper/ lower box, the car or person there will disappear; if there is no car or person, the box will be damaged as well. In addition, there is a maintenance team and a destruction team at $(1,1), (n, n) $ in the parking lot. Every time a mine explodes, the maintenance team will repair the grid (if it encounters a grid that is good or has a car, it is a waste of an opportunity; **if it encounters a damaged grid, it will be repaired),** and **will move to the right one** (if it is on the far right of a row, it will go to the first grid in the next row). At the same time, the destruction team will damage the grid (if it has been damaged, it will waste an opportunity, **if there is a car in the grid, the car and the destruction team will disappear**, if the grid is good, it will be damaged), and **will move to the left grid** (if it is on the far left of a row, it will come to the next grid in the previous row). When the maintenance team and the destruction team meet, the two teams disappear immediately. Attention **both teams may also be killed.** ### 第三题 题面是一个 $N$ 次多项式因式分解的结果，形式为 $$\boldsymbol{F(\ x\ )=k(x+a_1)(x+a_2)(x+a_3)}\ldots$$ 格式如下： - 保证$k，a_1\sim a_N$均为正整数。 - 注意 $a_i$ 前面的符号可能为$-$，如$F(\ x\ )=k(x-a_1)(x+a_2)(x-a_3)…$ - 特别地，如果输入没有 $k$，如$F(\ x\ )=(x+a_1)(x+a_2)(x+a_3)……$ 则 $k=1$。 求这个多项式展开按降幂排列后各项的系数。如果你不懂什么是降幂排列，请移步提示说明或自行百度。但奈何他的哥哥[Mars](https://www.luogu.com.cn/user/279197)并不善良，把题目给改了。详见输入输出格式。 ### 第四题 $\color{purple}{Der\ }$决定要学习 $n$ 个新技术。如果想学习一个新技术，有以下条件： 1. 要拥有一定的经验值（但学习不会扣除经验值）； 2. 必须要先学会若干个相关的技术。 学会一个新技术之后，他的经验值会**增加**一个对应的值。已知每个技术的学习条件（即若干个相关的技术）和习得后获得的经验值，以及他已有的经验值，请问他最多能学会几个技术。 ### 第五题 小马斯和奖杯都在一个 $200\times200$ 的矩阵中，每行每列的编号均为 $1\sim200$。奖杯位于 $(1,1)$，小马斯有两个位置可供选择：$(x_1,y_1),(x_2,y_2)$。他只能按 [中国象棋](https://baike.baidu.com/item/%E4%B8%AD%E5%9B%BD%E8%B1%A1%E6%A3%8B/278314?fr=aladdin#4) 中马和象的走法移动。如果你还是不清楚走法，请自行百度或询问家里的长辈。求这两个点到奖杯的最少移动次数。 ### 第六题 假设亚特兰蒂斯中一共有 $N$ 幢建筑排成一条线，每幢建筑的高度 $h_i$ 各不相同。初始时，小马斯可以在任何一幢建筑的顶端。他可以选择一个方向飞，但是不能中途改变方向（因为亚特兰蒂斯变幻莫测，且小马斯急着回家）。因为小马斯不可能会飞，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部（包含初始时的建筑）？ ### 第七题 由于爱情是一份质朴的约定，浪漫的守候，因此计算默契值的方法是： 先求出一个学号的所有约数（约定），然后计算这些约数两两之间的最大公因数（默契），将这些值相加，所得的学号便是小马斯一见钟情的那个人。 小马斯非常希望知道自己命中注定的另一半是谁。然而由于这个值太大了，他自己显然无法计算。因此他需要你的帮助。 此外，由于小马斯心急火燎，他只能给你一秒钟。 ### 第八题  In this year's flood season, many places in our country suffered from continuous heavy rainfall. Since the first ten days of June, the Huaihe River Basin has entered a period of concentrated precipitation. The water level of the main and tributaries of the Huaihe River has risen in an all-round way. Since July 18, the water level of the Huaihe Wangjiaba section, located in Funan County, Fuyang City, Anhui Province, has continued to rise. At 10:00 on July 19, the water level at Wangjiaba station on the Huaihe River rose to 28.74 meters, exceeding the warning water level by 1.24 meters "Protecting Henan from the top and protecting Jiangsu from the bottom.". In a critical moment, take the overall situation into consideration. Wang Jiaba once again "sacrificed" himself. On July 20, according to the order of the state flood control headquarters, the Wangjiaba sluice gate of Huaihe River was opened for flood discharge, and Mengwa flood storage area was opened, and the Huaihe River water flowed to the flood storage area. From the evening of the 19th to the morning of the 20th, more than 2000 residents in the flood storage area completed the evacuation, showing once again the "Wangjiaba spirit" - giving up the small family for everyone, leaving the local to take care of the overall situation! This is also the 16th time since the completion of Wangjiaba sluice. The firefighters were muddy and still rushed forward. Their hands and feet were soaked to molt without shrinking. They sat in the corner of the wall and fell asleep for a second While doing ideological work for the masses, Party members, cadres and volunteers try their best to transfer goods for the masses. They visit each house and ask if there is enough food and vegetables and if there are any difficulties Flood fighting and disaster relief is not only a common battle of the whole nation, but also a battle of dedication and sacrifice. In the course of thousands of years of history, the Chinese people have always been able to work together and overcome numerous natural disasters. This time, it's no exception. The people in the flood storage areas may have nostalgia for their homes, but they are more understanding and cooperation. Life may be inconvenient in this period of time before the water recedes, but they will never be alone, because they stand behind the country. It is the spirit of Wang Jiaba that supports all these things. It is the spirit of giving up the small family and taking into account the overall situation, the spirit of self-improvement without fear of difficulties and dangers, the spirit of solidarity between the army and the people, the spirit of helping the people in the same boat, and the spirit of scientific water control with respect to laws and comprehensive prevention and control. As the premier said, "Wangjiaba spirit" is the precious wealth accumulated by several generations of Wangjiaba people, and it is a true portrayal of the spirit of Huaihe people. Towering China, no fear of floods, one mind, rain or shine. The firemen are fighting against the flood. Obviously, it is difficult to solve the problem of waterlogging by manpower alone, so the National Defense General Administration (NDGA) allocated $m$ super pumps while $n $ cities are waterlogged and need urgent repair. It is now known that: - The amount of waterlogged water in each city is $water $(in km³), - Total pumping capacity of $away $(in km³) per machine, - The cost per machine is $money $. Due to various factors, **a pump can only be used in one city, and a city can only be equipped with one pump at most**. When the total pumping capacity of the pump is $away > = water $. What is the minimum cost of clearing all urban waterlogging. If a city cannot be cleared, output `NO`. ### 第九题 #### 背景 >塔克拉玛干沙漠（维语：تەكلىماكان قۇملۇقى）位于新疆南疆的塔里木盆地中心，是中国最大的沙漠，也是世界第十大沙漠，同时亦是世界第二大流动沙漠。整个沙漠东西长约1000公里，南北宽约400公里，面积达33万平方公里。平均年降水不超过100毫米，最低只有四五毫米；而平均蒸发量却高达2500～3400毫米。这里，金字塔形的沙丘屹立于平原以上300米。狂风能将沙墙吹起，高度可达其3倍。沙漠里沙丘绵延，受风的影响，沙丘时常移动。沙漠里亦有少量的植物，其根系异常发达，超过地上部分的几十倍乃至上百倍，以便汲取地下的水分，那里的动物有夏眠的现象。 >塔克拉玛干沙漠周围有一些小的沙漠，这些并不是自然形成，而是由于土地荒漠化而造成的。小马斯决定改善的正是这样的土地。于是，他前往此处一探究竟。 他发现，这里有 $n$ 个沙漠连成一条线，每片沙漠中有一定地方可以种树。但由于土地荒漠化不断加剧，每个小时可种树的数量在不断减少。同时，由于沙漠之间存在一定距离，因此小马斯需要驱车前往，在途中势必会耽误一些时间。 #### 举例说明 例如：$n=5$ 时，如下表： | 沙漠编号 |1 |2 |3 |4 |5 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | |第 $1$ 小时可植树数量 $sum$ | 10 | 14 |20 | 16 | 9 | |每过 $1$ 小时可植树数量减少量 $\triangle sum$ | 2 | 4 | 6| 5 | 3 | |当前沙漠到下一个相邻沙漠的时间 $time$（单位：小时） |3 | 5 | 4| 4| / | #### 解释 在第 $1$ 个沙漠中植树第 $1$ 小时内可种 $10$ 棵树，第 $2$ 小时内只能种 $8$ 棵树，$\ldots$，第 $5$ 小时以后再也种不了树了。从第 $1$ 个沙漠到第 $2$ 个沙漠需要 $3$ 小时，从第 $2$ 个沙漠到第 $3$ 个沙漠需要 $5$ 小时，以此类推。 #### 问题 由于小马斯体力有限，不可能连续工作太久，因此他研发了一个机器人帮他工作。然而小马斯过于蒟蒻，水平有限，机器人只能工作 $T$ 小时便会报废。为了尽可能改善环境，请你设计一个植树方案，从第 $1$ 个沙漠出发，希望能种最多的树。 假设能植树的数量 **仅和已植树的次数有关，且每次植树的时间都是整数小时**。 换句话说，沙漠在植树时能种的数量才会减少。 ### 第十题  ~~Cherish life and stay away from OI~~ (happy Chinese Valentine's day) As we all know, green waters and green mountains are golden mountains and silver mountains. We must adhere to the harmonious coexistence of man and nature, establish and practice the concept that green waters and green mountains are golden mountains and silver mountains, and adhere to the basic national policies of resource conservation and environmental protection. In the western region of China, due to the distance from the ocean and its remote, it can not be affected by the summer monsoon to produce rainfall, and the climate is dry all year round. Day after day, year after year, the super long sunshine and weathering make the soil erosion serious, land desertification aggravation and dust all over the sky. The harm can be imagined - the sand blown by the wind has caused sandstorms, which has seriously endangered people's health and increased the incidence rate of childhood asthma, pneumonia and bronchitis in adults. - Due to land desertification, a large number of land can not be reclaimed for grazing, which wastes the limited land resources and makes it difficult to overcome poverty. Therefore, little Mars decided to join the ranks of afforestation, with his hands to create green water and green mountains, lit desert oasis this bright pearl light. However, far from being able to hydrolyze the near thirst, people in Northwest China are suffering from the once-in-a-century sandstorm. Due to the underdeveloped economy, backward technical conditions and small production scale, most people here can not use N95 masks and enough water to resist the dust. Seeing this, Mars resolutely took the lead and charged in the front. He was worried about the world first, and then was happy after the world. He undertook the material transportation work to help the local people. Fortunately, Mars has studied in advance the transportation route of masks, water and other materials from the Far East of China to the northwest. These routes (including start and end points) pass through $n $ cities with city numbers of $1 \sim n $ respectively. In addition to the starting point and end point, each other city has two two-way roads connecting to at least two other cities, and each road has a passing fee(Including gasoline and other fees). So now You are Given a map, which contains $C (1 ≤ C ≤ 6200) $ roads directly connecting $2 $ towns. Each road consists of a starting point of $Rs $, an end point of $Re (1 ≤ Rs ≤ n; 1 ≤ Re ≤ n)$, and a cost of $C_i(1 ≤ C_ i ≤ 1000)$. Find the minimum total cost from the starting town $T_S (1 ≤ T_S ≤ n)$to the destination town $T_e (1 ≤ T_e ≤ n) $.

无

无

## 第一题 ### 数据范围 对于 $100\%$ 的数据，$P$的情况仅为 `PG, SG, SF, PF, C` 五种。 保证两队得分不相等，且得分王、篮板王、助攻王、MVP球员可以严格确定。 ### 实用工具 为了简化本题代码量，这里介绍一个库函数： `max_element(a+1,a+n+1)` 返回数组 $a[1]\sim a[n]$ 中的最大元素的地址。可以通过 `max_element(a+1,a+n+1)-a` 得到其下标。 ### 样例解释 得分王为 `Harden 39`，篮板王为 `Davis 11`，助攻数最多为 `Harden 12`，由于其已经拿到得分王，故助攻王为 `James 11`。 计算可得 1 队总得分更高，因此 MVP 从该队产生。计算可得 `Harden` 贡献值为 $69$，故 MVP 为 `Harden`。 ## 第二题 ### DATA RANGE For data of $10 \% $, $1 < = n < = 10$ For the other $10 \% $ data, $B = C = 0$ For data of $100 \% $, $1 < = n < = 100, \ \ 0 < = B < = 100, \ \ 0 < = C < = 200, \ \ 1 < = x, y, P, Q, I, J < = n, 1 < = T < = 100 $. ------------ ### Sample explanation: Since there are no cars, each can be parked. Since there is no bomb explosion, the **maintenance team and the destruction team will not repair / destroy any grid**, so output `none yet`. ## 第三题 ### 数据范围： 对于 $10\%$ 的数据，$N=2$。 对于另外 $10\%$ 的数据，$k=1$。 对于 $100\%$ 的数据，$2