今日复习内容：做题
例题1：最大的卡牌价值
问题描述：
给定n副卡牌，每张卡牌具有正反面，正面朝上数字为ai，背面朝上数字为bi。一副卡牌的价值为正面朝上数字之和，一开始所有卡牌都是正面朝上的。小蓝是蓝桥学院最优秀的魔法师，他知道所有卡牌的背面数字bi，他最多可以进行k次 操作，每次可以将一副卡牌翻转，将正面朝上的数字变为背面朝上的数字，或者将背面朝上的数字变为正面朝上的数字。请问，小蓝最多可以使卡牌的价值之和为多少？
输入格式：
第一行输入两个整数n和k，表示卡牌的数量和小蓝可以操作的次数
第二行输入n个整数ai，表示所有卡牌正面的数字
第三行输入n个整数bi，表示所有卡牌背面的数字
数据范围保证：1 <= n <= 1 * 10^5，1 <= ai,bi,k <= 10^9
输出格式：
输出一个整数，表示可以得到的卡牌的最大价值和
参考答案：
n,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
cha = [b[i] - a[i] for i in range(n)]
cha.sort(reverse = True)
tot = sum(a)
for i in range(k):if cha[i] < 0:breaktot += cha[i]
print(tot)运行结果：
以下是我对此题的理解：
这道题的思路比较简单，主要是贪心地选择每次操作翻转能够增加价值的卡牌
1.思路解析
首先，我们需要明确每张卡牌的价值。每张卡牌的价值是正面朝上的数字ai；
接下来，我们需要考虑如何进行操作，以使得卡牌的总价值最大化。由于每次操作可以将一副卡牌翻转，我们可以选择将价值更高的一面朝上；
因此，我们可以计算每张卡牌正反面数字的差值bi - ai，然后将这些差值按照从小到大的顺序排列。这样排列后，我们就可以优先选择能够增加总价值的卡牌进行翻牌操作；
最后，我们通过对差值数组进行遍历，每次选择差值大于等于0的前k个差值进行操作，将它们加到总价值中，得到最终的最大价值。
2.代码解析
首先，读取输入的卡牌数量n，操作次数k，以及每张卡牌正面和背面的数字数组a和b；
计算每张卡牌正反面数字的差值，并将差值数组cha按照从大到小的顺序排序；
初始化总价值tot为所有卡牌正面数字之和；
对差值数组进行遍历，每次选择差值大于等于0的前k个差值进行操作，并将它们加到总价值中。
输出最终的总价值。
3.复杂度分析
时间复杂度：排序差值数组的时间复杂度为O(nlog n)，遍历差值数组的时间复杂度是O(n)，因此时间总复杂度为O(nlog n)。
空间复杂度：除了输入数据所占的空间外，额外使用了大小为O(n)的差值数组和一些额外的变量，因此空间复杂度也为O(n)。
例题2：珠宝的最大交替和
问题描述：
小莉是一位珠宝设计师，她非常喜欢玩珠子。她有一个长度为N的珠串A，每个珠子有不同的颜色和大小，她想要用这个珠串来设计一款新的珠宝。
她将该珠串的交替和定义为：
S = |A1| - |A2| + |A3| - |A4| + ... + (-1)^(N - 1)|AN|
小莉可以进行以下操作，但最多只能进行一次：
选择两个位置i和j(1 <= i <= j <= N)，交换Ai和Aj。
为了让新的珠宝更加漂亮，小莉想要让交替和最大。请你帮她找出最大的交替和。
其中，|X|表示珠子X的大小的绝对值。
输入格式：
第一行包含一个整数N，表示珠串A的长度。
第二行包含N个用空格分开的整数，表示珠串A中每个珠子的大小。
数据范围保证：1 <= N <= 10^5,-10^9 <= Ai <= 10^9
输出格式：
输出一行，表示小莉最多可以通过进行操作获得的最大交替和。
参考答案：
n = int(input())
li = list(map(int,input().split()))
add = []
sub = []
for i in range(n):if i % 2 == 0:add.append(abs(li[i]))else:sub.append(abs(li[i]))
if n == 1:print(add[0])
else:tot = sum(add) - sum(sub)if max(sub) > min(add):tot += 2 * max(sub) - 2 * (min(add))print(tot)运行结果：
以下是我对此题的理解：
首先，我们要明确交替和的定义；
接下来，我们需要考虑如何通过交替珠子的位置，使得交替和最大化。因为只能进行一次操作，我们需要找到一种合适的策略，使得在交换后交替 和能增加尽量多的值。
因此，我们首先将珠串中相邻的珠子按照奇偶性分成两组，分别计算两组中珠子的大小的绝对值之和。然后，我们需要比较两组珠子的大小，选择一种合适的交换策略，使得交替和最大。
接下来是代码：
首先，读取输入的珠串长度N和珠子大小的列表li；
将珠串中相邻的 珠子按照奇偶性分成两组，分别储存在列表add和sub中，其中add储存的是偶数位置珠子大小的绝对值，sub储存的是奇数位置珠子大小的绝对值；
如果珠串长度为1，则交替和就是该珠子大小的绝对值，直接输出；
否则，计算交替和的初始值为tot = sum(sub) - sum(sub)
如果最大的奇数位置的珠子大小的绝对值大于最小的偶数位置的珠子大小的绝对值，说明交换后交替和会增加。
因此，我们选择最大的奇数位置珠子和最小的偶数位置珠子，计算交换后交替和增加的值，并将其加到tot中。
输出最终的交替和。
tot += 2 * max(sub) - 2 * max(add)，这里乘以2是因为交换后有两个珠子的大小发生变化，分别是奇数位置上的最大值和偶数位置上的最小值。
例题3：小蓝的礼物
问题描述：
小蓝想要给他的女朋友小桥买一份生日礼物，她来到了一家礼品店，在店里，她看重了N件物品，每件物品都要一个价格Ai。
小蓝手中有K元钱一张50%的折扣券，可以在购买任意一件物品时使用。使用折扣券后，购买该物品的价格为原来价格的一半向上取整。
对于一件价值为X的物品，当小蓝使用折扣券后，她只需要花费[x / 2]的钱就能带走该商品。
请你帮助小蓝确定，在使用折扣券的情况下，她最多能够购买多少件物品送给小桥当作生日礼物。
输入格式：
第一行是两个整数N和K，分别表示物品的数量和小蓝手中的预算。
接下来一行是N个整数，表示每个物品的价格Ai。
数据范围保证：1 <= N <= 10^5，1 <= Ai <= 10^9，0 <= K <= 10^9
输出格式：
输出一个整数，表示在使用折扣券的情况下，小蓝最多可以购买多少件物品作为生日礼物。
参考答案：
import math
n,k = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
ans = 0
for i in range(n):if k >= li[i]:ans += 1k -= li[i]else:if k >= math.ceil(li[i] / 2):ans += 1break
print(ans)运行结果：
以下是我对此题的理解：
这道题的逻辑如下：
首先，读取输入的物品数量和小蓝手中的预算；
接着，读取每件物品的价格，并将它们储存在列表li中；
对物品价格列表li进行排序，从小到大排序，这样可以方便后续处理；
初始化变量ans为0，用来记录小蓝最多能够购买的物品数量；
使用一个循环遍历所有的物品：
如果小蓝的预算k大于等于当前物品的价格，说明她可以购买该物品，并将购买物品数量加一，同时更新她的预算k，即减去已购物品的价格
否则，如果小蓝的预算k大于等于该物品的价格一半的向上取整，则说明她可以使用折扣，购买数量ans加一，并且由于使用了折扣券，购买后预算要减去相应价格。
如果以上两种情况都不满足，则说明她不能买任何物品，直接跳出循环
最后输出小蓝最多能够购买的物品数量ans。
例题4：鸡哥的购物挑战
问题描述：
鸡哥在“无尽的夏日”购物节上看重了一系列的商品，这些商品的价格各不相同。然而，鸡哥的购物车有一条特殊的规则：购物车里的商品数量必须是偶数。
鸡哥希望在满足购物车前提的条件下，选择总价值最高的商品，他将商品的价格表给了你，希望你能帮他计算出他能购买到的商品的最高总价值是多少。
输入格式：
第一行包含一个整数N(2 <= N <= 10^5)，表示商品的数量。
第二行包含N个整数，表示每个商品的价格Ai（-10^9 <= Ai <= 10^9）
输出格式：
输出一行，表示鸡哥能够买到的商品的最高总价值。
参考答案：
from bisect import *
n = int(input())
li = list(map(int,input().split()))
li.sort()
ind = bisect_left(li,0)
tot = sum(li[ind:])
if (n - ind) % 2 != 0:if ind:tot -= min(abs(li[ind]),abs(li[ind - 1]))else:tot -= li[0]
print(tot)运行结果：
以下是我对此题的理解：
思路如下：
首先读入商品的数量n和每个商品的价格列表li；
将商品价格列表li进行排序，这样可以方便后续处理；
使用bisect_left函数在有序列表中查找0的插入点，这样可以确定商品价格为非负数的商品的起始位置，因为在购买商品时，我更倾向于选择价格为非负数的物品，这样可以使总价格更高；
计算起始位置之后的商品价格的总价值tot，这些商品的价格都是非负数；
如果起始位置之后的商品数量为奇数个，需要考虑一种情况：如果有负数的商品，我们希望可能将正数的商品价格和负数的商品价格想抵消，以保证总价值最高。因此，我们选择绝对值较小的负数商品和与其相邻的非负数商品进行抵消，从而得到最高总价值。
输出最高总价值tot。
if (n - ind) % 2 != 0:
这段代码首先判断(n - ind) % 2是否等于0，即判断起始位置之后的商品是否为奇数个。如果条件成立，说明商品数量是奇数个，需要进行抵消操作。
tot -= min(abs(li[ind]),abs(li[i - 1))：
这是抵消操作，如果存在负数的商品，我们希望尽可能将负数的商品价格与正数的商品价格进行抵消，以保证总价值最高。因此，选择绝对值较小的商品与其相邻的非负数商品进行抵消，使用min函数选择绝对值较小的负数商品，然后将其从总价值tot中减去，以实现抵消效果。
else:
如果起始位置是0，即不存在负数的商品，那么执行以下操作：这种情况下，我们直接将列表中第一个非负数商品加到tot上，因为不存在负数商品需要抵消，直接将第一个非负数商品的价格加到总价值中就行。
综上所述，难一点的操作就是商品数量为奇数时，进行合理的抵消操作，以保证购物车内商品数量为偶数个，并且保证总价值最高。
例题5：神奇是数组
问题描述：
欢迎来到异或王国，这是一个特殊的 王国，对于一个数组，它的价值并非所有数相加，而是所有数异或得到的值。
当然对于某些神奇的数组来说值可能是一样的，给定一个长度为n的数组a，请问有多少个子数组属于神奇数组。
换句话说，在数组a中，存在多少对下标l和r(1 <= l <= r <= n)满足：
输入格式：
第一行输入一个整数n，表示数组a的长度；
第二行输入n个整数，表示数组a的值。
数据保证：1 <= n <= 2 * 10^5,0 <= ai <= 2^20
输出格式：
输出一个整数，表示答案
参考答案：
n = int(input())
li = list(map(int,input().split()))
add = [0]
yh = [0]
for i in range(n):add.append(add[-1] + li[i])yh.append(yh[-1] ^ li[i])
l,r = 1,1
ans = 0
while l <= n and r <= n:while l <= n and r <= n and (add[r] - add[l - 1]) == (yh[r] ^ yh[l - 1]):ans += (r - l + 1)r += 1l += 1
print(ans)运行结果：
以下是我对此题的理解：
主要思路如下：
首先，读取输入的数组长度n和数组a；
初始化两个辅助数组add和yh，分别用来记录前缀和与前缀异或值。这两个数组的目的是为了快速计算子数组的异或值。
add数组记录了数组a的前缀和，即前i个元素的和；
yh数组记录了数组a的前缀异或值，即前i个元素的异或结果。
使用两个指针l和r，分别表示子数组的左右边界，初始时都指向数组的第一个元素
初始化变量ans为0，用来记录符合条件的子数组数量。
进入循环，遍历所有可能的子数组：
在内层循环中，不断移动右边界r，同时检查当前子数组是否满足条件，即该数组的前缀和与前缀异或值是否相等；
然后移动左边界l，继续检查下一个子数组
最后输出符合条件的子数组数量ans。
关键在于利用前缀和与前缀异或值的性质，通过快速计算子数组的异或值，从而高效地判断子数组是否属于神奇数组。
例题6：聪明的小羊肖恩
问题描述：
小羊肖恩是一只非常聪明的绵羊，在牧场里与其他绵羊一起生活。有一天，它在草地上漫步时，发现了一些数字。它猜想这些数字可能在某些方面有用，于是把它们带回了牧场，并开始研究它们。
具体来说，小羊有一个长度为n的数组，第i个数字的值为ai，小羊肖恩心中想了两个数L和R，它想知道有多少对下标对(i,j)满足以下条件：
1 <= i <= j < n，L <= ai + aj <= R
请你帮他找出满足条件的下标对数量。
输入格式：
第一行输入3个整数n，L,R
第二行输入n个整数a1,a2,...,an，表示数组a。
数据范围保证：1 <= n <= 2 * 10^5，1 <= ai <= 10^9，1 <= L <= R <= 10^9
输出格式：
输出一个整数，表示满足条件的下标对数量。
参考答案：
def cul(aa,Z):ans = 0l = 0r = len(aa) - 1while l < r:if aa[l] + aa[r] <= Z:ans += r - ll += 1else:r -= 1return ans
n,L,R = map(int,input().split())
aa = list(map(int,input().split()))
aa.sort()
print(cul(aa,R) - cul(aa,L - 1))运行结果：
以下是我对此题的理解：
主要思路：
首先，定义一个名为cul的函数，用于计算满足条件的下标对数量。函数接受两个参数aa和Z;
在函数内部，初始化变量ans为0，用于记录满足条件的下标对数量；
定义两个指针l和r，分别指向aa的两端；
进入循环，不断移动指针l和r，直到l不小于r为止：
如果数组中l和r指向的元素之和小于等于目标值Z，则将满足条件的下标对数量累加到ans中，并将l向右移动一位；否则，将r向左移动一位。
循环结束后，返回ans作为答案；
在主程序中，首先读取输入的数组长度n，以及范围L和R；
接着读取输入的数组a，并将其排序；
调用cul函数两次，分别传入排序后的数组aa和范围R及L - 1的值，然后将两次调用的结果相减，得出结果。
例题7：冒险者公会
问题描述：
一个地区包含n个村庄，每个村庄发布了一些委托任务，需要冒险者的帮助。
冒险者公会共有m位冒险者，某位冒险者具有能力值xi，这表示他能够完成难度值小于等于x的委托任务。每位冒险者最多只能出击一轮，在这一轮中，他们可以不重复地通过若干个村庄。
当一名冒险者路过一个村庄时，他最多只能完成该村庄的一个委托任务，且这个委托任务的难度不能超过冒险者的能力值。冒险者也可以选择在路过一些村庄时不完成任何委托任务。同样地，每个委托任务只能被完成一次。
无论冒险者完成多少任务，这名冒险者出击一轮的代价都等同于冒险者的能力值。
现在的目标是确定一种冒险者的出勤方案，以使得完成所有村庄的委托任务的总代价最小。
输入格式：
第一行输入两个整数m和n，分别表示冒险者的数量和村庄的数量， 0 < m,n <= 10^3。
第二行m个整数x1,x2,...,xm，代表每位冒险者的能力值, 0 < xi <= 10^3。
接下来n行，每行代表一个村庄，每行第一个整数k表示村庄的委托任务数量，此后k个不大于10^3的正整数表示该村庄的每个委托任务的难度值，0 < k <= 10^3。
输出格式：
在一行中输出一个整数，表示完成所有委托所需的最小总代价。如果不能完成所有的委托，则直接输出-1。
参考答案：
m,n = map(int,input().split())
chan = list(map(int,input().split()))
chan.sort()
flag = True
country = []
for i in range(n):tmpp = list(map(int,input().split()))k = tmpp[0]tmp = tmpp[1:]if k > m:flag = Falsebreaktmp.sort()tmp = [0] * (m - k) + tmpcountry.append(tmp)
if flag:max_ = []for j in range(m):max_.append(0)for i in range(n):max_[j] = max(max_[j],country[i][j])round_ = 0peo = 0while round_ < m and max_[round_] == 0:round_ += 1ans = 0while round_ < m and peo < m:if max_[round_] <= chan[peo]:ans += chan[peo]round_ += 1peo += 1if round_ == m:print(ans)else:print(-1)
else:print(-1)运行结果：
这个题是我今天做的题中最难的。
以下是我对此题的理解：
首先，读取输入的冒险者m和村庄数量n；
读取每位冒险者的能力值，并将其排序；
初始化一个布尔变量flag为True，用于标记是否存在有效的出勤方案；
使用一个列表country来存储每个村庄的委托任务难度值，同时检查每个村庄的任务数量是否超过冒险者的数量；
如果存在有效方案，将每个村庄的任务难度值排序，并在前面补0，使得列表长度为m；
初始化一个列表max_用于记录每个冒险者在所有村庄中能够完成的最难任务难度；
初始化变量round_为0，用于表示当前轮次；
初始化变量peo为0，用于表示当前选择的冒险者；
进入两层循环，外层循环是轮次，内层循环是冒险者的选择。
在内层循环中，检查当前轮次下，冒险者是否能够完成任务。如果能完成，则累加代价并移动到下一轮次和下一位冒险者。如果某轮次无法完成任务，输出-1表示不存在有效的出勤方案。
如果能够完成所有村庄的任务，输出最小的总代价。否则，输出-1表示不存在有效的出勤方案。
这个题我做的时候就不是很熟练，所以得多记点笔记。
m,n = map(int,input().split())
这一行代码用来读取输入的两个整数，分别表示冒险者的数量和村庄的数量；
chan = list(map(int,input().split()))
chan.sort()
这一行代码读取每个冒险者的能力值，并将其存储在列表chan中，然后对该列表进行排序；
flag = True
country = []
这行代码初始化一个布尔变量flag为True，用于标记是否存在有效的出勤方案，并初始化一个空列表country，用于存储每个村庄的任务难度值。
for i in range(n):
tmpp = list(map(int,input().split()))
k = tmpp[0]
tmp = tmpp[1:]
if k > m:
flag = False
break
tmp.sort()
tmp = [0] * (m - k) + tmp
country.append(tmp)
这个循环用于读取每个村庄的任务信息。首先，读取一个列表tmpp，其中第一个元素k表示该村庄的任务数量，剩下的元素表示每个人物的难度值。如果任务数量k超过了冒险者的数量m，则将flag设为False，表示不存在有效的出勤方案。然后，对人物难度进行排序，并在前面补0使得列表长度为冒险者数量m，然后将其添加到country列表中。
if flag:
max_ = []
for j in range(m):
max_.append(0)
如果存在有效的出勤方案，就创建一个长度为冒险者数量的列表max_，用于记录每个冒险者在所有村庄中能够完成的最难任务难度。
for i in range(n):
max_[j] = max(max_[j],country[i][j])
这个循环用于更新max_列表中每个位置的值，使其表示每个冒险者在所有村庄中能够完成的最难任务难度。
round = 0
peo = 0
初始化变量round为当前轮次，peo表示当前选择的冒险者
while round_ < m and max_[round_] == 0:
round_ += 1
这个循环用于跳过一些没有任务的轮次
ans = 0
while round_ < m and peo < m:
if max_[round_] <= chan[peo]:
ans += chan[peo]
round_ += 1
peo += 1
这个循环用于在每个轮次中选择能够完成冒险任务的冒险者，并累计其能力值作为总价值
if round_ == m:
print(ans)
else:
print(-1)
如果能够完成所有村庄的任务，则输出最小的总代价，否则输出-1表示不存在有效的出勤方案。
OK,这就是我今天的学习成果。
这篇就到此为止了，下一篇继续！
