2023“钉耙编程”中国大学生算法设计超级联赛（2）部分题解
7.20
1002 Binary Number
可以发现，每个位置最多修改两次，再多了没有意义。
当k为0时，无法修改直接输出。
当n为1时，看k的奇偶性，若为奇数则将其翻转输出，否则直接输出。
当n不为1时：
如果给定的次数k小于序列中连续0串的个数，那一定贪心地从前往后修改得到的答案最优，
否则，一定可以将整个序列全部转化为1，即，先将所有的连续0串转化为1，剩下的次数若为偶数，随机挑一段不断操作，若为奇数，则在前一步操作时将一个1变为0，再将其变为1，则剩余的次数变为了偶数次。
这其中有个特殊情况就是序列全为1且k为1，这时必须将一位变为0，选择将最后一位变为0。
1007 foreverlasting and fried-chicken
可以设这个给定的图中度为6和4的顶点为\(u, v\)，求出所有与\(u, v\)都有连边的点的个数\(tot\)， 和与\(u\)有连边的点的个数\(tot_u\), 与\(v\)有连边的点的个数\(tot_v\)，则这两个点贡献的答案为：
\(ans(u, v) = C_{tot}^{4} \cdot C_{tot_u - 4}^{2} + C_{tot}^{4} \cdot C_{tot_v - 4}^{2}\)
最终答案为：
\(\sum_{u = 1}^{n-1} \sum_{v = u + 1}^{n} \ ans(u, v)\)
复杂度为\(O(n^3)\)， 考虑使用bitset优化
枚举\(u, v\)两个点不变，对每个节点设一个1000位的bitset，若此节点与i节点有连边，则将第i位设为1，否则为0
判断与两个节点都有连边的节点数可以将两个节点的bitset按位与，然后使用count()函数求得。
1001 Alice Game
考虑将k，n不同值的sg函数打表求出来然后找规律。
首先，当\(n = 0\)时，先手无法行动必输，此时\(sg(0) = 0\)，
考虑当\(1 \leq n \leq k\)，这时先手只能执行第一步，将整个序列全部吃掉，因此这个局面只有一个\(sg(0) = 0\)的后继，根据sg函数的定义，此时\(sg(n) = mex ( \ \{ 0 \} \ ) = 1\).
当$n = k + 1 \(时,先手既不能执行第一步也不能执行第二步,因此\)sg(k + 1) = 0$.
当\(n \geq k + 2\)时,先手可以执行第二步,吃掉其中\(k\)个之后,还剩\(n - k\)个,考虑将这\(n - k\)个分成两部分,有\((1 , n - k - 1), (2, n - k - 2), ..., ( \lfloor \frac{n - k}{2} \rfloor , n - k - \lfloor \frac{n - k}{2} \rfloor )\)这些分法, 每次分成两部分之后可以将两段序列看成两个独立的游戏, 因此:
\(sg(n) = mex ( \ \{ sg(1) \ xor \ sg(n - k - 1), \ ... \ , sg(\lfloor \frac{n - k}{2} \rfloor) \ xor \ sg(n - k - \lfloor \frac{n - k}{2} \rfloor) \} \ )\)
打表代码
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 1000005;
int k = 0;
int sgg[N];
int sg(int n) {
if(n == 0) return 0;
if(n <= k) return sgg[n] = 1;
if(n == k + 1) return sgg[n] = 0;
if(sgg[n]) return sgg[n];
map<int, bool> mp;
mp.clear();
for(int i = 1; i <= (n - k) / 2; i++) {
mp[sg(i) ^ sg(n - k - i)] = true;
}
for(int i = 0; i <= n; i++) {
if(!mp[i]) return sgg[n] = i;
}
}
int main() {
cin >> k;
vector<int> tmp;
for(int i = 1; i <= 80; i++) {
cout << "i = " << i << " sg = " << sg(i) << endl;
if(sg(i) == 0) tmp.push_back(i);
}
cout << "sg(n) = 0 : ";
for(auto v : tmp) {
cout << v << " ";
}
return 0;
}
可以发现,对于每个k, 第一个\(sg = 0\)的位置为k + 1,此后每隔\(4k + 2\)个再次出现\(sg = 0\)
答案就是\((n - k - 1) mod (4k + 2)\), 特判$n \leq k $的情况.
1011 SPY finding NPY
如果在第i位选到了最大值,需要两个前提:
1.最大值出现在第i位.
2.第1至i - 1 位中的最大值出现在第1至k位.
设\(f(i)\)表示在第i位选到最大值的概率,则可得:
\(f(i) = \frac {1}{n} \cdot \frac {k}{i - 1}\)
则能选到最大值的概率为:
$g(k) = \sum {i = k + 1} ^ {n} f(i) = \frac{k}{n} \cdot \sum^{n - 1} \frac{1}{i} $
枚举k, 使用前缀和预处理$\sum_{i = k}^{n - 1} \frac{1}{i} $即可.
1010 Klee likes making friends
考虑dp
设\(f(i)(j)\)表示前i个人中,必选第i个人,且与选的上一个人距离为j时的答案.
假设当前在第i位,与上一个人距离为j, 则上一个人位置为i - j, 现在考虑倒数第三个人的位置. 我们需要保证\([i - m, i - 1]\) 这个长度为m的区间内存在至少两个人,因此倒数第三个人的位置可以存在的区间为\([i - m, i - j)\), 倒数第三个人到上一个人的距离k的范围为\((0, m - j]\), 因此状态转移方程为:
\(f(i)(j) = a_i + min \{ f(i - j)(k) \} \quad (k \in (0, m - j])\)
这样时间复杂度没问题,但是空间过大. 发现j最大为m, 即\(i - j \geq i - m\) 只需要记录i前面m个信息,因此将第一维变为滚动数组即可.