2023“钉耙编程”中国大学生算法设计超级联赛（2）
1001 Alice Game
题意：
起初有n个物品，玩家可以有如下操作：
①若该堆物品数量小于等于k，全部拿走。
②若该堆物品数量大于k，则只能选择拿走k个物品，并将剩余物品分成不为空的两堆。
Alice先手，问谁必胜。
分析：
打表可知当n % (4 * k + 2) == k + 1时Alice必败，其他时候必胜。
打表代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
LL f[N];
int sg(int x, int k)
{
if (f[x] != -1)
return f[x];
set<int> S;
if (x <= k && x > 0)
S.insert(sg(0, k));
else
{
for (int i = 2; i <= x - k; i ++)
{
S.insert(sg(i - 1, k) ^ sg(x - (i + k - 1), k));
}
}
for (int i = 0;; i ++)
{
if (S.count(i) == 0)
return f[x] = i;
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int k = 3;
for (int i = 1; i <= 100; i ++)
{
memset(f, -1, sizeof f);
cout << sg(i, k) << " ";
if (i % (4 * k + 2) == 0)
cout << endl;
}
return 0;
}
代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, k;
cin >> k >> n;
if ((n % (4 * k + 2)) == k + 1)
cout << "Bob" << endl;
else
cout << "Alice" << endl;
}
return 0;
}
1002 Binary Number
题意:
给定一个01串，有k次操作，每次选择一个区间将其翻转，求k次操作后的最大结果。
分析:
最高位一定是1。
①n = 1：k为奇数则输出0，k为偶数则输出1
②n > 1：设连续0的段数为m。显然要让结果最大，要尽可能将高位的0翻转。
k < m：则将前k端连续0翻转为1;
k ≥ m：特别的当m = 0，k = 1时将最后一位变为0。其他情况，我们先将m段0翻转为1，然后考虑对较低的位去操作，若k - m是偶数则翻转最后一位k - m次，因此不影响结果；若k - m是奇数可以先翻转最低位一次，再翻转次低位一次，然后将次低位和最低位一起翻转，剩下的操作为偶数不影响结果。综上除了特殊情况其他均输出n个1。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
LL k;
cin >> n >> k;
string s;
cin >> s;
if (n == 1)
{
if (k & 1)
cout << 0 << endl;
else
cout << 1 << endl;
continue;
}
int cnt = 0;
for (int i = 0; i < n;)
{
int j = i + 1;
if (s[i] == '0')
{
while (j < n && s[j] == '0')
j ++;
cnt ++;
}
i = j;
}
if (k < cnt)
{
if (k == 0)
cout << s;
else
{
for (int i = 0; i < n;)
{
int j = i + 1;
if (s[i] == '0')
{
if (k)
{
k --;
cout << 1;
while (j < n && s[j] == '0')
{
cout << 1;
j ++;
}
}
else
cout << 0;
}
else
cout << 1;
i = j;
}
}
}
else
{
if (cnt == 0 && k & 1)
{
for (int i = 0; i < n - 1; i ++)
cout << 1;
cout << 0;
}
else
{
for (int i = 0; i < n; i ++)
cout << 1;
}
}
cout << endl;
}
return 0;
}
1004 Card Game
题意:
给你n个堆,起初第一个堆放了k个东西,下面大上面小,其它堆都是空的,需要通过其它空堆的中转作用将k个东西从第一个堆全部放到第二个堆上(也是下面大上面小),问最多可以成功转移的k的个数是多少。
分析：
找规律。发现f[n] = f[n - 1] * 2 + 1 => f[n] = \(2^{n - 1}\) - 1。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int mod = 998244353;
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
cout << qmi(2, n - 1) - 1 << endl;
}
return 0;
}
1007 foreverlasting and fried-chicken
题意：
给你一个无向图，求出如下图形的数量。
分析：
枚举度大于等于6的点和度大于等于4的点，分别设为u，v。设与u相连的结点数为cnt，u和v均相连的结点数为cnt2，则u，v能组成的目标图形数为\(C_{cnt2}^4·C_{cnt - cnt2}^2\)。倘若暴力枚举cnt2会是\(O^3\)的复杂度，因此考虑用bitset优化。可以用bitset维护一个邻接矩阵g，cnt = g[u].count(),cnt2 = (g[u] & g[v]).count()。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, mod = 1e9 + 7;
bitset<N> g[N];
LL f[N], f2[N];
LL qmi(LL m, LL k)
{
LL res = 1, t = m;
while (k)
{
if (k & 1)
res = res * t % mod;
t = t * t % mod;
k >>= 1;
}
return res;
}
void init()
{
f[0] = f2[0] = 1;
for (int i = 1; i < N; i ++)
{
f[i] = f[i - 1] * i % mod;
f2[i] = f2[i - 1] * qmi(i, mod - 2) % mod;
}
}
LL C(int a, int b)
{
if (a < b || b < 0)
return 0;
else
return f[a] * f2[b] % mod * f2[a - b] % mod;
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
init();
while (t --)
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
g[i].reset();
while (m --)
{
int a, b;
cin >> a >> b;
g[a][b] = g[b][a] = 1;
}
LL res = 0;
for (int i = 1; i <= n; i ++)
{
for (int j = i + 1; j <= n; j ++)
{
int cnt1 = g[i].count(), cnt2 = g[j].count();
if (g[i][j])
cnt1 --, cnt2 --;
int cnt3 = (g[i] & g[j]).count();
res = (res + C(cnt3, 4) * C(cnt1 - 4, 2) + C(cnt3, 4) * C(cnt2 - 4, 2)) % mod;
}
}
cout << res << "\n";
}
return 0;
}
1009 String Problem
题意：
取k个子串，每个子串只包含一种字母，问子串长度之和减去k的最大值是多少。
分析：
双指针枚举满足条件的子串的最长长度，其对答案的贡献为子串长度减1。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 27;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
string s;
cin >> s;
int res = 0;
for (int i = 0; i < s.size();)
{
int j = i + 1;
while (j < s.size() && s[j] == s[i])
j ++;
res += j - i - 1;
i = j;
}
cout << res << endl;
}
return 0;
}
1010 Klee likes making friends
题意：
给定n个元素，每个元素有一个权值，要求每连续m个元素至少要有两个元素被选，求所选元素权值之和的最小值。
分析：
考虑dp。
f[i][j]表示所选方案中最后一个在i倒数第二个在j的权值之和的最小值，且i - j < m。由于[j,i]之间没有元素被选，因此倒数第三个所选的元素k应当在[i - m, j - 1]内。f[i][j] = a[i] + min(f[j][k]), k∈[i - m, j - 1]。 min(f[j][k])可以通过在递推时维护一个后缀最小值来处理。我们可以预处理前m个元素，然后递推，最后对在[n - m + 1, n]内的所有f[i][j]取个min就是答案。
但这样定义状态i×j最大有1e8级别，会MLE。考虑优化，首先很容易想到j可以用相对距离i - j来描述。其次，由于我们每次考虑一个长度为m的区间，因此第一维可以用i % m表示。新的状态可以定义为：f[k][l]表示所选方案中最后一个元素所在位置为k（k = i % m）倒数第二个元素与倒数第一个元素的相对距离为l（l = i - j）的权值之和的最小值。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, M = 20010;
int f[N][N], Min[N][N], pos[M];
int a[M];
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
cin >> a[i];
pos[i] = i % m;
}
for (int i = 0; i <= m; i ++)
{
for (int j = 0; j <= m; j ++)
{
f[i][j] = Min[i][j] = 0x3f3f3f3f;
}
}
for (int i = 2; i <= m; i ++)
{
for (int j = i - 1; j >= 1; j --)
{
f[pos[i]][i - j] = a[i] + a[j];
Min[pos[i]][i - j] = min(Min[pos[i]][i - j - 1], f[pos[i]][i - j]);
}
}
for (int i = m + 1; i <= n; i ++)
{
for (int j = i - 1; j >= i - m + 1; j --)
{
f[pos[i]][i - j] = a[i] + Min[pos[j]][j - (i - m)];
Min[pos[i]][i - j] = min(Min[pos[i]][i - j - 1], f[pos[i]][i - j]);
}
}
int res = 0x3f3f3f3f;
for (int i = n - m + 2; i <= n; i ++)
{
for (int j = i - 1; j >= n - m + 1; j --)
{
res = min(res, f[pos[i]][i - j]);
}
}
cout << res << endl;
}
return 0;
}
1011 SPY finding NPY
题意：
n个人，IQ值为n的全排列，先取前k个人的最大IQ值m，之后从[k + 1, n - 1]位置内去选第一个大于m的人否则选第n个人，问选到IQ为n的概率最大时k的最小值。
分析：
设选到的人在位置a，且在[1, a - 1]内，IQ最大的人在[1, k]的概率：\(\frac{k}{n(a - 1)}\)。则选到IQ为n的概率为：\(\frac{1}{n}\sum_{i=k+1}^{n}{\frac{k}{(i - 1)}} = \frac{k}{n}\sum_{i=k}^{n-1}{\frac{1}{i}}\)。可以用前缀和预处理出\(\sum{\frac{1}{i}}\)，然后枚举k取个min即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
double f[N];
struct Ans
{
int k;
double p;
};
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --)
{
int n;
cin >> n;
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++)
f[i] = f[i - 1] + 1.0 / i;
Ans ans = {0, 1.0 / n};
for (int k = 1; k < n; k ++)
{
double p2 = 1.0 * k / n * (f[n - 1] - f[k - 1]);
if (ans.p < p2)
{
ans = {k, p2};
}
}
cout << ans.k << endl;
}
return 0;
}