题面翻译
给定一个整数序列，将之分成两个，求这两部分和的绝对值之差的最大值，即
范围：
做法
猜测贪心，考虑一个一定可行的方案，进行邻项交换，看什么样的方案比它优。
我们将正数全部塞到一边，负数全部塞到另一边，令和较大的成为sum1。
我们令正数总和更大，记正数为，负数为。
考虑将一些正数放到第二个序列，记这些正数和为：
若，则，答案不变
若，则，，小于
其余情况同理可证
故而，这种情况就是最优解，直接做做完了
题面翻译
给定一个n，代表一个由n个“BAN”拼成的字符串，每次可以交换两个位置的字符，最小化使得字符串中不存在“BAN”子串的操作数，并输出一种方案
数据范围：
注意：
此题的SPJ疑似有误，口胡了不要直接写代码
做法
注意到，一次交换最多破坏两个“BAN”子串，对于剩下的单个，我们交换一下，所以答案为
对于方案的构造，然后我们跨过中线交换就做完了。（此题好像只能跨过中线交换？我全部邻项交换寄了，但是手模是过的）
题面翻译
给定一个正整数序列，两个绝顶聪明的人进行游戏，求谁有必胜策略：
每次，并选择一个其他位置与交换
若一个人操作前是0，则输掉游戏
数据范围：
此题做法
我们画出流程：
…
由于的对象事实上由上一个玩家选定，归于上一个玩家的策略范畴，我们考虑一个等价转换，将归入上一个玩家：
…
此题有一个很好的性质，上一个人选择的-1对象下一个人不能再次选择并-1，即两次相邻操作独立，
也就是说，对于一个玩家，只要每次选能选的最小值，将之不断-1，就是一个玩家最早的获胜时间，且不受另一个玩家影响
此时最优策略变得显然，两个人都会选取能选的最小值-1，更早将最小值减成0的获胜。
于是，我们只需要比较和能选择的最小值即可，我们发现，当第二个玩家能选到的比第一个玩家更小，当且仅当初始的后成为了整个序列的唯一最小值。直接扫一遍整个序列就做完了
题面翻译
给定一个序列，每次询问一个区间全部归零的最少操作次数，不能归零输出-1。
操作为：将一个奇数长度的区间全部赋值成区间的异或和
数据范围：
此题做法：
考虑对于一个区间，我们怎么在这个区间内操作都不改变区间的异或和。因为奇数长度区间赋值异或和，对于整体区间的异或和，偶数个数消去，剩下一个有贡献的，是这个区间的异或和。
那么，区间异或和为0，才有可能做。
对于本身全是0的区间，不需要操作
对于奇数长度区间，直接一次操作推平即可；
对于偶数长度区间，当且仅当这个区间存在一个长为奇数的异或和为奇数的前缀时有解。
这几个判断都是好做的，就做完了。
前置知识:二项式反演
解决问题：计数问题
f(m):至多m个/至少m个 ⇒ g(m):恰好m个的方案数
前置公式：
将代入二项式定理
二项式定理推论：
组合数分离式：
即从n中选m个，再从m个中选k个，等价于从n直接中选k个，在从剩下的n-k个中选m-k个
从而推出二项式反演公式：
⇔
证明：代入即可
双相关的取出方法：标号点对，考虑对于内部的同一个j，有哪些i会枚举到它
至多问题：
⇔
至少问题：
⇔
注意：二项式反演和多步容斥本质不同
多步容斥：单纯给不少于…计数，对于同一个f(i)，内部不重复，但对于不同的f(i)，由于记重复，要去重
二项式反演：钦定m个必须选，剩下的随便算，对于同一种方案，在同一个f(i)中也可以多次被计数
此题做法
参考了Leasier的题解，更加建议阅读原题解，不建议阅读本人本篇题解，毕竟今天刚学二项式反演,目前还是已知半解的感觉。
容易发现合法序列长度 ——因为每次 a,b 中至少有一个-1。
然后发现每存在一个位置不合法，我们就可以把不合法的位置删掉——反正重复了，删了也不影响剩下的部分。当我们把所有不合法位置删完后，你会发现它变成了一个合法序列。
设f(x)表示长度恰好为 x 的合法序列的方案数，g(x) 表示长度恰好为 x 的不一定合法序列的方案数。
现在考虑 g(x)。注意到其实我们可以任取一个长度为 x的满足不降限制的 a,b序列，于是 。
答案为
然后代入一下式子
注意一下细节，就做完了。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/143154.html