# KUNKKA做不了满分的题 ## A. 约瑟夫问题 # 约瑟夫问题 ## 题目描述 $n$ 个人围成一圈，从第一个人开始报数,数到 $m$ 的人出列，再由下一个人重新从 $1$ 开始报数，数到 $m$ 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。 ## 输入格式 输入两个整数 $n,m$。 ## 输出格式 输出一行 $n$ 个整数，按顺序输出每个出圈人的编号。 ## 样例 #1 ### 样例输入 #1 ``` 10 3 ``` ### 样例输出 #1 ``` 3 6 9 2 7 1 8 5 10 4 ``` ## 提示 $1 \le m, n \le 100$ --- ## B. 麦森数（超级难！！） # 题目背景 形如 $2^p$-1 的素数称为麦森数，这时 P 一定也是个素数。但反过来不一定，也就是如果 P 为素数， $2^p$ -1 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 P=3021377，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。 *PS：这和题目没什么太大关系 ^ _ ^* ### 重要说明：此题为转载题目，来源在最后 # 题目要求 输入一个正整数 P ， 输出 $2^p$ - 1的位数，并在下一行输出它的后500位数字，不够的补0。 ## 输入 输入 P ， $1000\leq P\leq 310000$ . ## 输出 两行，第一行是 $2^p-1$ 的位数， 第二行是$2^p-1$的后500位（不够补0） # 样例 ```input1 1279 ``` ```output1 386 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087 ``` # 时限 一秒钟，125MB ## 来源 洛谷题库 | 计算机教育 --- ## C. 土拨鼠可长可短的如意金箍棒 # Background 美鼠王文轩拥有一根别人非常羡慕的可长可短的如意金箍棒. # Description 这一天, 文轩又玩起了他的金箍棒, 他在想, 金箍棒最短可以是多短呢? 我们可以把金箍棒看作是一段一段组成的, 每一段上都有一个0到9的数字. 他想通过变换将金箍棒变短. 变换的方式为: 每一次将各个数字相加, 得到的和就是新的金箍棒状态. 文轩现在想知道, 金箍棒最短是多少? # Format ## Input 一个整数n, 表示金箍棒最初的状态. ## Output 一个整数, 表示最终金箍棒最短的长度. # Samples ## 样例1 ```input1 19 ``` ```output1 1 ``` ### 样例解析 1+9 = 10, 1+0 = 1 ## 样例2 ```input2 998244353 ``` ```output2 2 ``` # Limitation $1 \le n \le 10^{1000}$ --- ## D. 土拨鼠的减法题 # Background 愚蠢的人类憨憨学减法了, 土拨鼠瑞瑞想做一个恶作剧 # Description 给出两个三位整数$A, B$, 允许改写$A, B$中的任意一位(可以不改), 使得$A-B$的值最大, 注意要求更改完的数据也是三位数. # Format ## Input 输入一行两个整数$A, B$. ## Output 输出一行$1$个数字, 表示$A-B$的最大值 # Samples ## 样例1 ```input1 567 234 ``` ```output1 733 ``` ## 样例2 ```input2 999 100 ``` ```output2 899 ``` ## 样例3 ```input3 100 999 ``` ```output3 -99 ``` # Limitation $100 \leq A, B \leq 999$ --- ## E. 愚蠢的土拨鼠 # 背景 从前，有一只愚蠢的土拨鼠正在做一道算术题。 # 说明 愚蠢的土拨鼠不想做算术题，于是他问了最聪明的你。 你能用编程给他解答出来吗？ ## 输入 两个数，a和b(a <= 10)(b <= 10). ## 输出 一个数，表示a+b的和。 # 输入输出样例 ```input1 1 1 ``` ```output1 2 ``` # 提示 第一个样例：1 + 1 = 2 --- ## F. 土拨鼠大战愚蠢的人类 # Background 土拨鼠们与愚蠢的人类展开了旷日持久的战争, 其中间谍战必不可少, 有很多愚蠢的人类化妆成土拨鼠的样子潜入土拨鼠军团 # Description 这一天, 一群可怜的土拨鼠被抓住了, 我们要去营救土拨鼠兄弟. 土拨鼠探长东润获取了一份重要情报, 上面有三种信息, 第一种信息为被抓住的所有土拨鼠的名字, 第二类信息为人类间谍的名字, 第三类信息为土拨鼠特工的名字. 第二, 三类信息可能会有重叠, 这是我们的高级特工潜入到了敌人内部做间谍. 你需要拯救出无辜的土拨鼠兄弟, 顺便还要吃掉那些人类间谍, 下面你需要列出那些应该被吃掉的人类间谍. 注意, 不要伤害到我们的土拨鼠特工兄弟. # Format ## Input 测试数据包含4部分. 第1行为3个整数A,B,C. 其中A表示所有被抓住土拨鼠的数量, B表示人类间谍的数量, C表示土拨鼠特工的数量. 第2行为A个土拨鼠的名字 第3行为B个人类间谍的名字 第4行为C个土拨鼠特工的名字 ## Output 输出那些应该被吃掉的人类间谍的名字, 注意不要伤害到土拨鼠特工, 按照B个人类间谍的顺序输出. 如果没有人类间谍, 你应该输出"No enemy spy". # Samples ```input1 8 4 3 Zhao Qian Sun Li Zhou Wu Zheng Wang Zhao Qian Sun Li Zhao Zhou Zheng ``` ```output1 Qian Sun Li ``` ```input2 2 2 2 Zhi Yuan Zhi Yuan Zhi Yuan ``` ```output2 No enemy spy ``` # Limitation 1s, 1024KiB for each test case. $1 \le A \le 10^6$ --- ## G. 饮料 # 故事背景 夏天到了，土拨鼠想去超市买几瓶不同的饮料放在家里。超市中的饮料各种各样，有的贵，有的便宜，有的甜，有的酸。如果土拨鼠想买 $n$ 瓶饮料，那么他会先看饮料的甜度，再看买这瓶饮料的人数（热度），最后看价格。请你在超市所有的饮料中为土拨鼠按它的想法给他挑出这 $n$ 瓶饮料。 # 题目描述 给定超市中每瓶饮料的名称、甜度、热度（买这瓶饮料的人数）和价格，帮土拨鼠选出他想要的饮料。（价格可能是小数） 方法： 先看甜度，再看热度，最后看价格。 # 输入 第 1 行为两个整数 $m$ 和 $n$，表示超市中的总饮料数 $m$ 和土拨鼠想要的饮料数 $n$ 。 第 2 到 $n$+1 行，每行包含饮料的名称、甜度、热度和价格。保证每瓶饮料的价格不同。 # 输出 $n$ 行。每行一个字符串，表示排序好后第 $i$ 瓶饮料的名称。 # 样例 ```input1 5 3 meizhiyuan 10 30 5 guolicheng 12 30 4 kele 15 40 3 chapai 7 25 6 bingtangxueli 15 15 3 ``` ```output1 kele bingtangxueli guolicheng ``` # 提示 排序方法： 先比甜度，甜度大的排靠前。 甜度相同，再比热度，热度搞得排靠前。 甜度热度都相同，再比价格，价格低的排靠前。 以上为你 $sort$ 排序时的 $compare$ 函数提供了帮助。 --- ## H. 【例15.1】 整型与布尔型的转换

说明

将一个整型变量的值赋给一个布尔型变量，再将这个布尔型变量的值赋给一个整型变量，得到的值是多少？

输入格式

一个整型范围内的整数，即初始时整型变量的值。

输出格式

一个整数，经过上述过程后得到的结果。

样例

3
1
--- ## I. 愚蠢的土拨鼠 # Background 2222年250月99日下午，土拨鼠国举行了PSC-E的初赛，土拨鼠愚愚也参加了，但他是一个K++小白选手，他基本上一道也不会。所以，他就把所有选择题都蒙了A。他想知道，自己有多大的概率能考到满分(我们假设每道选择题的答案都是ABCD中的一个，而且可能性均等，况且，这次考试全是选择题)。 # Description 给你这次考试选择题的个数x，输出愚愚考满分的概率(分数表示) # Format ## Input 一个整数x ## Output 一个普通分数，愚愚考满分的概率。 # Samples ```input1 1 ``` ```output1 1/4 ``` ```input2 2 ``` ```output2 1/16 ``` ```input3 15 ``` ```output3 1/1073741824 ``` # Limitation 对于20%的数据，x<32；对于100%的数据，x<128 --- ## J. 练14.1 歌手大奖赛

说明

歌手大奖赛上$6$名评委给一位参赛者打分，$6$个人打分的平均分为$9.6$分；如果去掉一个最高分，这名参赛者的平均分为$9.4$分；如果去掉一个最低分，这名参赛者的平均分为$9.8$分；如果去掉一个最高分和一个最低分，这名参赛者的平均是多少？

输入格式

无

输出格式

使用%5.2f按实数格式输出，保留$2$位小数。

样例

无
无
--- ## K. liaoleqian的梦想(暂无数据) # 背景 土拨鼠liaoleqian梦想成为一名伟大的程序员。在他成为程序员的路上，遇见了一个矩阵，想要成功越过矩阵，需要你——土拨鼠的帮助。 # 题目描述 将n*n(n<=10000)的矩阵翻转180度后将第m行的数据全部加k(k<=100000)。 ## 输入 共n+1行. 第一行 n，m，k； 后面的n行为n*n的正方形矩阵。 ## 输出 一个反转完成的土拨鼠矩阵。 # 样例 ### 输入 ```输入 3 2 5 1 2 3 3 2 1 1 3 2 ``` ### 输出 ```输出 1 3 2 8 7 6 1 2 3 ``` # 数据说明 对于100%的数据，保证n<=10000;k<=100000; 矩阵的各项数据小于100000； 时间限制：1.5秒； --- ## L. 【例14.3】 数学课上

说明

给出一个浮点数，怎么判断这个数离前后相邻两个整数哪个更近，输出距离更近的整数。请你按照四舍五入原则编程输出这个数。

输入格式

输入一行，包含 $1$ 个数：$n$（$0.0≤n≤100000.0$）,表示题目要求输入的浮点数。题目保证输入浮点数小数点后保留最多 $8$位。

输出格式

输出共计 $1$ 行，包含 $1$ 个数，表示题目所求的距离更近的整数。

样例

4.5
5
--- ## M. 练15.2 智商问题

说明

智商（IQ）反映人的聪明程度，它是法国心理学家比奈提出的。他将一般人的平均智商定为$100$。分数越高，表示越聪明，智商就越高，$140$分及以上者称为天才。
试编一程序，输入一个$200$以内的整数作为IQ值，判断是不是天才。

输入格式

一行一个整数，表示IQ的值。

输出格式

输出“天才”或不输出。

样例

150
天才
--- ## N. 大中华寻宝记 # Background 神兽线（G112京沪高速，G17沈海高速）开通了！将方便多个神兽村的联通。现在，需要得到每一个村到其他的村的最短距离。 # Description Given two integers x and y, print the sum. # Format ## Input Two integers x and y, satisfying $0\leq x,y\leq 32767$ . ## Output One integer, the sum of x and y. # Samples ```input1 123 500 ``` ```output1 623 ``` # Limitation 1s, 1024KiB for each test case. --- ## O. 愚人耶( •̀ ω •́ )(2) # 题目背景 注意：题里都是反义词 # 今天是愚人节，学校决定， # 让学生评语刘老师， # 大家给的都是A clever groundhog ## 输入 无 ## 输出 学生们的评语 # 提示 刘老师常说的话，评语同学的话,cout << 《汉字》； --- ## P. 土拨鼠凯旋~战斗胜利! # Background 经过短暂的战争, 土拨鼠军团战胜了人类, 抓获了不少人类俘虏. # Description 土拨鼠舒舒想要从土拨鼠团长处购买至少m个人类奴隶, 而人类奴隶是一车车的往回运输, 每一车有不同数量的人数$a_i$, 一共有$n$车. 为了方便, 团长要求舒舒必须整车的买入奴隶, 也可以连续的购买几车奴隶. 由于人类奴隶饭量很大, 舒舒希望尽量少的购买奴隶. 问舒舒最少可以购买多少奴隶? # Format ## Input 第1行两个整数$n, m$ 第2行$n$个整数$a_i$ ## Output 第1行1个整数, 表示舒舒购买的奴隶个数. 第2行1个整数, 表示应该从第几车开始购买, 如果有多个选择, 则输出第一个选择. 如果无法购买到m个奴隶, 则直接输出-1; # Samples ```input1 10 15 5 1 3 5 10 7 4 9 2 8 ``` ```output1 15 4 ``` ## 样例1解释 从第4车开始购买, 连续买两车, 可以购买得到15个人类奴隶 ```input2 10 100 5 1 3 5 10 7 4 9 2 8 ``` ```output2 -1 ``` # Limitation 1s, 1024KiB for each test case. --- ## Q. 蜜汁 # Background 小 $Q$ 是一个劳逸结合的孩子（☞学习两分钟，游戏两小时） # Description 小 $Q$ 玩到了一个游戏，大概是这样的： > 有一个迷宫，迷宫四处全是危险，但值得庆幸的是这个迷宫的路是一些圆，可以走，要从一个坐标走到目标点。 小 $Q$ 并不会，所以他来请教你，你只需要判断这个是否有解就可以啦。 原始有一个在 $(0,0)$ 点半径为 $1$ 的圆。 $\color{white}{\texttt{有解输出1，无解输出0}}$ # Format ## Input 第一行一个整数 $T$ 表示有 $T$ 关。 接下来第一行两个数字 $x_e, y_e$ 表示终止点。 然后就是一个整数 $n$。 然后 $n$ 行，三个数，代表圆的中心的坐标，以及半径长度。 ## Output $T$ 行，每行一个数，表示答案。 # Limitation $1 \le T \le 10$ $-10^8 \le x, y,x_e,y_e\leq10^8$ $1 \le r\le 10^8$ $1\le n \le 1000$ --- ## R. 土拨鼠进监狱 # Background 土拨鼠进监狱了，他需要写出n的全排列才能出狱。 # Description 给出n，输出n的全排列。 # Format ## Input 一行，一个数n ## Output $n!$行，每行是n的一个全排列，按字典序输出。 # Samples ```input1 3 ``` ```output1 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 ``` # Limitation 1秒，256mb。$n<=8$ --- ## S. 土拨鼠和猴子 # 土拨鼠和猴子打架 一只土拨鼠和n只喜欢吃shi味干脆面的猴子打架 土拨鼠输了 伤心的回家找妈妈 # 题目 猴子因为经常吃 shi味干脆面 所以他进化了 两只土拨鼠妈妈可以在一个小时内打败一只猴子 而猴子因为喜欢乱喷shi 每隔半个小时就会变得虚弱 如果超过一个小时吃不shi味干脆面 就会缩水 变成一只狗 丧失战斗能力 ## 输入 输入猴子数量 # 输出 输出最少需要多少土拨鼠妈妈 ``` --- ## T. 土拨鼠解密码 # Background 土拨鼠被困在了密室里，她想要出去。墙上有一个密码锁，只要打出所有数字就可以了。但按键只剩下$+5$键，$+7$键与$\sqrt \ $键，只要用这三个键从$0$开始一直打倒出现所有密码就行了。（不能大于100，不能出现非整数，不能重复） 举例：要打出$2$来： $0\to5\to12\to17\to24\to29\to36\to6\to11\to16\to4\to2$，就能得到$2$。 你要输出的就是这种格式。 # Description 给出1个数$a$，给出一条能够按题目要求得到这个数的路径，如果不行输出"Tuboshu will die in here". # Format ## Input 1个$a$，表示要得到的密码。 如果有多个解，请输出字典序最小的。 比如 $12393$ 和 $12344$要输出$12393$，因为第五项$3$更小。必须按顺序打出。 ## Output 一个字符链，表示得到密码的过程，具体格式为： a to b to c to d to e 注意，每得到一个密码，需要紧跟着输出一个“Yell。（如果得不到密码，请输出："Tuboshu will die in here".）。 # Samples ```input1 2 ``` ```output1 0 to 5 to 12 to 17 to 24 to 29 to 36 to 6 to 11 to 16 to 4 to 2Yell ``` # Limitation $$ 1\le a_i\le100 $$ --- ## U. 幻想乡 Wi-Fi 搭建计划 ## 题目描述 傲娇少女幽香是一个很萌很萌的妹子。随着科技的进步，幻想乡的大家也开始使用手机了。这时幽香发现没人来她的太阳花田玩了，她感到很伤心，于是向别人打听了一下，才知道原来大家都嫌弃这里没有 Wi-Fi，手机上网还需要流量。 怎么办呢？幽香决定赶快搭建几个 Wi-Fi 点，让所有人都能在太阳花田里畅快地上网。 我们可以近似地把太阳花田看成一个 $y$ 轴在 $[0,R]$ 之间，$x$ 坐标在 $(-\infty,+\infty)$（也就是在 $x$ 轴上无限延伸）的无限长方形。 太阳花田里面有 $n$ 个景点，是游客们经常光顾的，幽香认为只要让这些景点尽量被 Wi-Fi 覆盖，那么游客们就肯定心满意足了。 八云紫表示她可以帮幽香架设 Wi-Fi 路由器。现在通用的路由器，每个的覆盖半径正好也是 $R$。八云紫扫视了一遍地图，发现在太阳花田外面，只有 $m$ 个有网络的地点，她只可以在那里架设路由器。如果你在点 $p$ 搭建了路由器，那么位于 $q$ 的地点，只要 $p$ 和 $q$ 的欧几里得距离小于等于 $R$，$q$ 点就会被 Wi-Fi 覆盖。 同时八云紫表示，架设难度随着地点的不同而不同，所以收费也不一样，在第 $i$ 个位置架设需要 $c_i$ 的钱。 现在幽香想要覆盖尽量多的景点，在这个前提下，幽香也想要尽量节省钱。你能帮助她吗？ ## 输入格式 输入第一行三个整数 $n,m,R$，分别表示景点的数量，网络架设地点的数量和太阳花田的宽度。 接下来 $n$ 行，每行两个整数 $x,y$，满足 $|x|\le 10^8,0\le y\le R$，表示一个景点。两个景点的位置不会重合。 接下来 $m$ 行，每行三个整数 $x,y,c$，满足 $|x|\le 10^9$，$-10^8\lt y\lt 0$ 或者 $R\lt y\lt 10^8$，表示一个网络架设点的位置和花费。两个网络架设点不会重合。 ## 输出格式 输出第一行表示最多覆盖的景点数。 第二行表示在覆盖景点数最多的前提下，最少的花费。 ## 样例 #1 ### 样例输入 #1 ``` 10 10 10000 6743 2963 3505 1986 3565 7235 1735 5522 16877 5597 11621 6 3100 8243 1750 6173 5709 7671 7915 3915 14339 -438 3075 4278 15210 8371 13996 19000 6750 17049 -4969 7788 737 16339 2934 904 14023 2322 8982 14759 4311 13102 11458 5554 4135 12183 576 5087 -2459 6787 ``` ### 样例输出 #1 ``` 10 10438 ``` ## 提示 - 对于 $10\%$ 的数据，$n,m\le 20$； - 对于另 $30\%$ 的数据，$n,m\le 100$，所有网络架设点的 $y$ 坐标都大于 $R$； - 对于另 $60\%$ 的数据，$n,m\le 100$。 对于全部数据，$1\le R\le 10^8,0\le c\le 10^4$。 --- ## V. [IOI2023] 封锁时刻 # [IOI2023] 封锁时刻 ## 题目背景 这是一道交互题，你只需要实现代码中要求的函数。 你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。 本题仅支持 C++ 语言提交。 ## 题目描述 匈牙利有 $N$ 个城市，编号依次为 $0$ 到 $N - 1$。 这些城市之间由 $N - 1$ 条双向道路连接，编号为 $0$ 至 $N - 2$。对每个 $j$（$0 \le j \le N - 2$），第 $j$ 条道路连接城市 $U[j]$ 和城市 $V[j]$，其长度为 $W[j]$，表示这两个城市之间的交通时间为 $W[j]$ 个时间单位。每条道路连接两个不同的城市，且每两个城市之间最多由一条道路连接。 两个不同城市 $a$ 和 $b$ 之间的一条**路径**是一个由不同城市组成的序列 $p_0, p_1, \ldots, p_t$，满足以下条件： * $p_0 = a$， * $p_t = b$， * 对每个 $i$（$0 \le i \lt t$），存在一条道路连接 $p_i$ 和 $p_{i + 1}$。 利用这些道路从任意一个城市到任意一个其他的城市都是有可能的。换言之，任意两个不同城市之间都存在路径。 可以证明两个不同城市之间的路径是唯一的。 一条路径 $p_0, p_1, \ldots, p_t$ 的**长度**是这条路径上连接相邻城市的 $t$ 条道路的长度之和。 在匈牙利，很多人都会在建国日去参加在两个主要城市举行的庆祝活动。当庆祝活动结束时，他们会回家。政府为了防止人群干扰当地人，所以决定在特定时刻封锁城市。每个城市被政府分配一个非负的**封锁时刻**。政府决定所有城市的封锁时刻总和不得超过 $K$。具体来说，对每个 $i$（$0 \leq i \leq N - 1$），分配给城市 $i$ 的封锁时刻是一个非负整数 $c[i]$。所有 $c[i]$ 之和不超过 $K$。 考虑一个城市 $a$ 和某个封锁时刻的分配方案，我们说城市 $b$ 是从城市 $a$ 可达的当且仅当以下两种情况中的任意一种情况成立。 情况 1：$b = a$。 情况 2：这两个城市之间的路径 $p_0, \ldots, p_t$ （$p_0 = a$ 且 $p_t = b$）满足以下条件： * 路径 $p_0, p_1$ 的长度最多为 $c[p_1]$，并且 * 路径 $p_0, p_1, p_2$ 的长度最多为 $c[p_2]$，并且 * $\ldots$ * 路径 $p_0, p_1, p_2, \ldots, p_t$ 的长度最长为 $c[p_t]$。 今年，两个主要的庆祝地点位于城市 $X$ 和 $Y$。 对于每一个封锁时刻的分配方案，可以定义一个**便利分数**，其定义为下面两个数字之和： - 从城市 $X$ 可达的城市个数。 - 从城市 $Y$ 可达的城市个数。 注意如果一个城市既能从城市 $X$ 可达也能从城市 $Y$ 可达，那么它在计算便利分数时计算两次。 你的任务是计算能被某个封锁时刻分配方案实现的最大便利分数。 ## 输入格式 令 $C$ 表示场景数，即调用 `max_score` 的次数。 评测程序实例按以下格式读取输入： * 第 $1$ 行：$C$ 以下是 $C$ 个场景的描述。 评测程序实例按以下格式读取每个场景的描述： * 第 $1$ 行：$N \; X \; Y \; K$ * 第 $2 + j$ 行（$0 \le j \le N - 2$）：$U[j] \; V[j] \; W[j]$ ## 输出格式 评测程序实例按以下格式为每个场景打印单独一行 * 第 $1$ 行： `max_score` 的返回值 ## 样例 #1 ### 样例输入 #1 ``` 2 7 0 2 10 0 1 2 0 3 3 1 2 4 2 4 2 2 5 5 5 6 3 4 0 3 20 0 1 18 1 2 1 2 3 19 ``` ### 样例输出 #1 ``` 6 3 ``` ## 提示 #### 【实现细节】 你要实现以下函数。 ``` int max_score(int N, int X, int Y, int64 K, int[] U, int[] V, int[] W) ``` * $N$：城市的个数 * $X$，$Y$：两个主要庆祝城市 * $K$：封锁时刻总和的上界 * $U$，$V$： 长度为 $N - 1$ 的描述道路连接情况的数组 * $W$：长度为 $N - 1$ 的描述道路长度的数组 * 该函数要返回能被某个封锁时刻分配方案实现的最大便利分数 * 每个测试用例可以多次调用该函数 #### 【例子】 考虑以下调用： ``` max_score(7, 0, 2, 10, [0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3]) ``` 这对应以下道路网络： ![](https://cdn.luogu.com.cn/upload/image_hosting/wf5uw4qd.png) 假设封锁时刻如下分配： | **城市** | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | |:----------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| | **封锁时刻** | $0$ | $4$ | $0$ | $3$ | $2$ | $0$ | $0$ | 注意所有封锁时刻之和为 $9$，不超过 $K = 10$。城市 $0$，$1$ 和 $3$ 都是从城市 $X$（$X = 0$）可达的，而城市 $1$，$2$ 和 $4$ 都可以从城市 $Y$（$Y = 2$）可达。 因此，便利分数为 $3+3 = 6$。不存在封锁时刻分配方案使得便利分数大于 $6$，所以该函数应该返回 $6$。 考虑另外一个调用： ``` max_score(4, 0, 3, 20, [0, 1, 2], [1, 2, 3], [18, 1, 19]) ``` 这对应以下道路网络： ![](https://cdn.luogu.com.cn/upload/image_hosting/zcw4gdi5.png) 假设封锁时间如下分配： | **城市** | $0$ | $1$ | $2$ | $3$ | |:----------------:|:---:|:---:|:---:|:---:| | **封锁时刻** | $0$ | $1$ | $19$| $0$ | 城市 $0$ 从城市 $X$（$X = 0$）可达，而城市 $2$ 和 $3$ 都是可以从城市 $Y$（$Y=3$）可达的。因此，便利分数是 $1 + 2 = 3$。不存在封锁时刻分配方案使得便利分数大于 $3$，所以函数应该返回 $3$。 #### 【约束条件】 * $2 \le N \le 200\,000$ * $0 \le X \lt Y \lt N$ * $0 \le K \le 10^{18}$ * $0 \le U[j] \lt V[j] \lt N$ (对每个 $j$ 满足 $0 \le j \le N - 2$) * $1 \le W[j] \le 10^6$ (对每个 $j$ 满足 $0 \le j \le N - 2$) * 利用这些道路可以从任意一个城市走到任意另外一个城市。 * $S_N \le 200\,000$，其中 $S_N$ 是所有调用函数 `max_score` 的 $N$ 的总和。 #### 【子任务】 我们说一个道路网络是**线性的**如果道路 $i$ 连接城市 $i$ 和 $i+1$（对每个$0 \le i \le N - 2$ 的 $i$）。 1. （8 分）从城市 $X$ 到城市 $Y$ 的路径长度大于 $2K$。 1. （9 分）$S_N \le 50$，道路网络是线性的。 1. （12 分）$S_N \le 500$，道路网络是线性的。 1. （14 分）$S_N \le 3\,000$，道路网络是线性的。 1. （9 分）$S_N \le 20$ 1. （11 分）$S_N \le 100$ 1. （10 分）$S_N \le 500$ 1. （10 分）$S_N \le 3\,000$ 1. （17 分）无额外的约束条件。 --- ## W. 无 # Background Special for beginners, ^_^ # Description Given two integers x and y, print the sum. # Format ## Input Two integers x and y, satisfying $0\leq x,y\leq 32767$ . ## Output One integer, the sum of x and y. # Samples ```input1 123 500 ``` ```output1 623 ``` # Limitation 1s, 1024KiB for each test case. --- ## X. 给雷姆酱送白丝 # [REMOI 114514 Loli组]给雷姆酱送白丝 ## 题目描述 Shiro是雷姆的舔狗。有一次Shiro在与雷姆的视频通话中得知雷姆的白丝已经很久没有换过了，如果Shiro愿意给雷姆送上一双崭新的白丝，那么雷姆就会将她用了很久的白丝送给Shiro。这对于舔狗Shiro来说可是不可多得的好机会，他内心十分坚毅！ Shiro是一名大陆国人，而雷姆是日本鬼族。Shiro已经到达了韩国，他打算依靠连接两岸的海域上的岛屿来到达日本。 在这片海域上一共有 $n$ 座岛屿排成一排，标号为 $1,2,3, \ldots ,n$。每座岛屿有两个权值，分别为劳累度 $a_i$ 和坚毅度 $b_i$。 对于一座劳累度为 $a$，坚毅度为 $b$ 的小岛，如果这个小岛满足 $(a\oplus c) \leq \min(b,d)$，Shiro到达这座岛探险就会对拿到雷姆的白丝充满信心，其中 $c$ 表示Shiro到岛上去之前就有的劳累度（称作初始劳累度），同理 $d$ 代表Shiro的初始坚毅度。$\oplus$ 表示二进制异或（即二进制表示下不进位的加法）。 为了更加方便地拿到雷姆的白丝，Shiro会向你询问 $q$ 次，每次给出一个区间 $[l_i,r_i]$ 和两个数 $c_i,d_i$，你需要告诉Shiro若她的初始劳累度为 $c_i$，初始坚毅度为 $d_i$，则有多少个标号在 $[l_i,r_i]$ 这个区间内的岛屿能让Shiro对拿到雷姆的白丝充满信心。 ## 输入格式 第一行两个正整数 $n,q$ 分别表示岛屿的数量和询问的数量。 接下来 $n$ 行，每行两个整数 $a_i,b_i$ 分别表示第 $i$ 座岛屿的劳累度和坚毅度。 接下来 $q$ 行，每行四个正整数 $l_i,r_i,c_i,d_i$ 分别表示区间左端点，区间右端点，初始劳累度与初始坚毅度。 ## 输出格式 输出一共 $q$ 行，每行一个整数对应一个询问的答案。 ## 样例 #1 ### 样例输入 #1 ``` 4 2 1 1 4 2 5 1 2 7 1 4 6 5 2 4 3 3 ``` ### 样例输出 #1 ``` 2 1 ``` ## 样例 #2 ### 样例输入 #2 ``` 20 10 215 144 2 110 174 132 214 142 116 108 155 192 236 208 216 214 99 220 236 118 190 81 230 131 10 238 189 198 183 13 45 193 14 234 208 192 126 19 49 38 7 14 251 184 2 18 89 76 11 15 49 196 8 11 83 139 10 15 119 239 9 16 148 120 11 17 225 34 15 16 3 46 14 15 86 227 7 18 252 103 ``` ### 样例输出 #2 ``` 7 2 2 2 1 3 1 1 0 7 ``` ## 提示 测试点 $1,2$ 满足 $1\leq n,q\leq 5000$。 测试点 $3,4$ 满足 $1\leq n,q\leq 10^4$。 测试点 $5,6,7$ 满足 $1\leq n,q\leq 10^5$ 且 $\max\{d_i\}\leq \min\{b_i\}$。 测试点 $8,9,10,11$ 满足 $1\leq n,q\leq 10^5$ 且 $\min\{d_i\}\geq \max\{b_i\}$。 测试点 $12,13$ 满足 $1\leq n,q\leq 10^5$ 且 $l_i=1,r_i=n$。 测试点 $14,15,16$ 满足 $1\leq n,q\leq 7\times 10^4$。 测试点 $17,18,19,20$ 满足 $1\leq n,q\leq 10^5$。 所有数据满足 $1\leq n,q\leq 10^5$， $1\leq a_i,b_i,c_i,d_i\leq 2^{24}-1$。 ---