题目：4.# 街道的中心## 题目描述城市商业街主干道是一条笔直的道路，商业街里有 n*n* 家店铺，现给定 n*n* 个店铺的位置，请在这条道路上找到一个中心点，使得所有店铺到这个中心点的距离之和最小，并输出这个最小值。## 输入格式第一行：单个正整数 n*n*。第二行：n*n* 个整数表示一个店铺的位置。## 输出格式单个整数：表示商铺到中心点距离之和的最小值。## 输入样例4 -2 0 2 0 ## 输出样例4## 说明提示数据范围：· −5000≤xi≤5000−5000≤*xi*≤5000· 对于 30%30% 的数据，1≤n≤201≤*n*≤20· 对于 60%60% 的数据，1≤n≤20001≤*n*≤2000· 对于 100%100% 的数据，1≤n≤1000001≤*n*≤100000样例解释：最优中心设置在坐标 00 处，总距离为：∣−2−0∣+∣0−0∣+∣2−0∣+∣0−0∣=2+0+2+0=4∣−2−0∣+∣0−0∣+∣2−0∣+∣0−0∣=2+0+2+0=4。## 限制时间限制：1000ms内存限制：512MiB

题目：3.# 图书管理## 题目描述图书馆的书籍分类系统使用二进制标签管理，0 代表儿童读物，1 代表青少年书籍。管理员发现当前的书架排列中不允许出现青少年书籍之后连接儿童读物的情况（即 10 子串）。管理员每次可以交换任意两本书的位置。请计算让书架符合规定所需的最少操作次数。## 输入格式由 0 和 1 组成的字符串，表示当前书架排列。## 输出格式一行一个非负整数，即达到目标所需的最少操作次数。## 输入样例#11100## 输出样例#12## 输入样例#200## 输出样例#20## 输入样例#310110100## 输出样例#33## 说明提示对于全部的输入数据，保证 2≤字符串长度≤2000002≤字符串长度≤200000 ，同时 ci*ci* 必为1 或 0 中的一个。## 限制时间限制：1000ms内存限制：512MiB

题目：2.# 选数## 题目描述给定一个正整数 n*n*，从数字 11 到 n*n* 中选择若干个数字（所选集合不能为空），且任意两个被选中的数字在数轴上不能相邻。求符合条件的方案数，结果对 10000000071000000007 取模。## 输入格式第一行：单个整数 n*n*。## 输出格式输出一个整数，表示方案数模 10000000071000000007 的结果。## 输入样例3## 输出样例4## 说明提示· 对于 30%30% 的数据，n≤20*n*≤20；· 对于 60%60% 的数据，n≤10,000*n*≤10,000；· 对于 100%100% 的数据，1≤n≤100,0001≤*n*≤100,000。## 限制时间限制：1000ms内存限制：512MiB

题目：1.# 组合## 题目描述你收集了 n*n* 张卡片，按照收集的时间顺序编号 11 到 n*n* 并依次排列，每张卡片上标有一个数值。现在突发奇想，想知道在这些卡片中，若每次挑选两张卡片，会有多少对不同的组合满足两张卡片的数值和恰好为 00，请你计算出符合条件的卡片组合的数量。## 输入格式· 第一行：单个整数表示 n*n*· 第二行：n*n* 个整数表示 a1,a2,a3,…,an*a*1,*a*2,*a*3,…,*an*## 输出格式单个整数：表示有多少对卡片数值和为 00。## 输入样例42 -2 2 0## 输出样例2## 说明提示· 30%30% 的数据，1≤n≤10001≤*n*≤1000· 60%60% 的数据，1≤n≤200001≤*n*≤20000· 100%100% 的数据，1≤n≤3000001≤*n*≤300000· −1,000,000,000≤ai≤1,000,000,000−1,000,000,000≤*ai*≤1,000,000,000## 限制时间限制：1000ms内存限制：512MiB

题目：给定N个数的序列a1,a2,...aN，定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。 时间限制：1000 内存限制：256000 输入 本题有多个测试点，每个测试点分为两行：第一行为序列中数字的个数N（1 ≤ N ≤ 200000），第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000)，由空格分开。N=0表示输入结束。 输出 每个测试点一行，输出一个整数，为给序列中“重要逆序对”的个数。 样例输入 10 0 9 8 7 6 5 4 3 2 1 0 样例输出 16 提示 请注意答案范围，如果使用printf输出long long类型，请用%lld

题目：交易市场 市场里面一共有n种物品，有m种交易途径，每个交易途径可以由(x,y,z)表示，意思是可以用第x种物品换成第y种物品，并且得到z元的收益（z均大于0）。最开始你只有第一种物品，请问最多可以赚取多少收益。 时间限制：1000 内存限制：65536 输入 第一行两个正整数n和m(n ≤ 1000，m ≤ 4000) 接下来m行，每行三个正整数x, y, z，意思是可以用第x种物品换成第y种物品，并且得到z元的收益。（1 ≤ x,y ≤ n, 1 ≤ z ≤ 100） 输出 一个整数表示最大收益，如果可以赚取无穷多的收益则输出1000000000 样例输入 3 3 1 2 2 2 3 3 1 3 4 样例输出 5

题目：密室逃脱 小Y喜欢玩密室逃脱，每次游戏开始时，小Y会进入一个密室，她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明，解开线索对她来说并不难，但是她有一点懒，她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。 密室是m行n列的格子矩阵，小Y从左上角(1,1)进入密室，密室中有三种格子: 墙，以数字0标记 路，以数字1标记 隐藏线索处，以数字( > 1)标记, 代表该线索的难度 小Y需要按照难度递增的顺序解开各个线索，逃脱密室。 时间限制：1000 内存限制：65536 输入 第一行是一个整数 T，表示输入包含 T 组数据，分别是不同的游戏中小Y所处的密室。 对于每组数据，第一行包括两个整数：m（1 <= m <= 100）、n（1 <= n <= 100）。 接下来 m 行，每行有n个数字，第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。 题目保证进入密室处(1,1)不是墙壁，线索的难度都不相同。 输出 对于每组数据，你需要输出一个整数，表示小Y在这个密室中至少要移动多少次才能成功通关。 如果小Y不可能解开所有线索，输出-1. 样例输入 2 3 3 1 3 2 1 0 4 10 6 5 3 3 1 3 2 0 0 0 10 6 5 样例输出 8 -1 提示 样例解释：由于需要按难度顺序解开线索，在第一组数据中，小Y第一次移动到3时不能解密，在完成2之后需要回到3.最后小Y解开10时，她成功通关。

题目：逃离迷宫 你在一个地下迷宫中找到了宝藏，但是也触发了迷宫机关，导致迷宫将在T分钟后坍塌，为此你需要在T分钟内逃离迷宫，你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形，其中"S"表示你所在的位置，"E"表示迷宫出口，"."是可以随意走动的区域，"#"是不可穿行的墙壁，每次你可以耗费1分钟在区域间移动（上下左右四个方向）。 时间限制：1000 内存限制：65536 输入 输入包含多组数组，第一行是一个整数K（1 <= K <= 10)，表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T，m表示正方形迷宫的边长，T表示坍塌时间。其后是一个m*m的字符矩阵，包含字符"S", "E", "."和"#"。 输出 每组数据输出一行，输出“YES"或者"NO"，表示是否可以在坍塌之前逃离（也就是说移动次数是否可以不超过T）。 样例输入 2 4 7 S... ###. .#E. ..#. 3 4 S.. ..# .#E 样例输出 YES NO

题目：狼人杀 以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1号玩家说：“2号是狼人”，2号玩家说：“3号是好人”，3号玩家说：“4号是狼人”，4号玩家说：“5号是好人”，5号玩家说：“4号是好人”。已知这5名玩家中有2人扮演狼人角色，有2人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？ 本题是这个问题的升级版：已知 N 名玩家中有 M 人扮演狼人角色，有 L 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？ 时间限制：6000 内存限制：65536 输入 输入在第一行中给出三个正整数 N、M、L，其中 5 ≤ N ≤ 100，2 ≤ M，L ≤ N。随后 N 行，第 i 行给出第 i 号玩家说的话（1 ≤ i ≤ N），即一个玩家编号，用正号表示好人，负号表示狼人。 输出 如果有解，在一行中按递减顺序输出 M 个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最大序列解 —— 即对于两个序列 A = { a[1], … , a[M] } 和 B = { b[1], … , b[M] }，若存在 0 ≤ k < M 使得 a[i]=b[i] （i ≤ k），且 a[k+1]>b[k+1]，则称序列 A 大于序列 B。若无解则输出“No Solution”。 样例输入 样例1： 5 2 2 -2 +3 -4 +5 +4 样例2： 6 2 3 -2 +3 -4 +5 +4 -3 样例3： 6 2 5 -2 +3 -4 +5 +4 +6 样例输出 样例1： 4 1 样例2（解不唯一）: 6 4 样例3： No Solution

题目：负载均衡 负载均衡是指在一组后端服务器上有效地分配传入的网络流量。负载均衡算法按照某种特定方法分配负载。 如果我们可以估算出最大的传入流量负载，则可以根据以下规则设计算法： - 大小为S的传入流量负载将首先被分解为两块，并且每块可以再次被分解为两块，以此类推。 - 每轮只做一次分解。 - 在任何时候，最小负载的规模必须严格大于最大负载规模的一半。 - 所有的规模都是正整数。 - 这个分解过程会一直进行下去，直到不可能再进行任何分解。 例如，如果S=7，那么我们可以先将其分解为3+4，然后继续分为4=2+2。这个分解终止时，我们需要3台服务器，其负载分别为3、2、2。 本题要求此算法所需的后端服务器的最大数量。由于分解可能不是唯一的，因此请找到最佳解决方案 —— 即使最大和最小规模之间的差异最小化的解。 时间限制：9000 内存限制：65536 输入 输入给出一个正整数 S（2 ≤ S ≤ 200），为传入流量负载的规模。 输出 在一行中输出两个数字：M 为所需的后端服务器的最大数量；D 为使用了 M 个服务器的解决方案中，最大和最小规模之差的最小值。一行中的数字间必须以一个空格分隔，行的开头或结尾不能有多余的空格。 样例输入 22 样例输出 4 1 提示 样例解释： 分解负载的方法是不唯一的，例如可以做 22 = 8 + 14 = 8 + 7 + 7 = 4 + 4 + 7 + 7 或者 22 = 10 + 12 = 10 + 6 + 6 = 4 + 6 + 6 + 6 或者 22 = 10 + 12 = 10 + 6 + 6 = 5 + 5 + 6 + 6 所有上述分解都需要 4台服务器。最后一个解的差值最小，为 6-5=1，所以输出 1。 运行测试 #include<bits/stdc++.h> using namespace std; int main(){ int s; cin>>s; if(s=22){ cout<<4<<" "<<1; } }