2024.10.15 模拟赛
T1 count
简要题意
给定一个长度为 \(n\) 的数组求其中正整数数量，\(n≤100\)
solution
哇，还是太难了
输入的时候如果是正数就 cnt++ 输出 \(cnt\) 即可
人机题，不放代码了
T2 sigma
简要题意
给定 \(n\) 个双端队列，其中第 \(i\) 个队列内有 \(c_i\) 个整数元素。进行 \(m\) 次弹出操作。每次操作可以任意选定一个队列，并将其头部或尾部的元素弹出。希望弹出的 \(m\) 个元素的和尽可能大。计算并输出这个最大元素和。
solution
非常好 dp，很难想到是背包
设 \(f[i]\) 表示弹出个数不超过 \(i\) 的最大元素和，\(w[i][j]\) 表示第 \(i\) 组共弹出 \(j\) 个数的最大元素和。
根据背包 dp 的性质，根本不需要当前队列顺序，从第一个队列开始算就行了，对于每一个队列 dp 一遍就行。操作次数是体积，元素是价值。
那么显然有转移方程
\[f_j=\max\{f_j,f_{j-k}+w_{i,k}\} \]问题在于我们的 \(w\) 怎么求。对于第 \(i\) 的队列，所有元素和显然为 \(s_{c_i}\)，减去前 \(r\) 在加上前 \(l\) 就是弹出部分。所以为 s[c[i]]-s[r]+s[l-1]，那么 \(w\) 取个 \(max\) 就可以了。
复杂度 \(O(n^2m)\)，显然跑不满，所以能过
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e2 + 5;
const int M = 1e5 + 5;
int n, m;
int f[M], w[N][N];
/*
f[i] 弹出个数不超过 i 的最大元素和
w[i][j] 第 i 组共弹出 j 个数的最大元素和
*/
int s[N];
signed main()
{
cin >> n >> m;
for (rint i = 1; i <= n; i++)
{
int t;
cin >> t;
for (rint j = 1; j <= t; j++)
{
int x;
cin >> x;
s[j] = s[j - 1] + x;
}
for (rint j = 1; j <= t; j++)
{
for (rint l = 1; l <= j + 1; l++)
{
//t - j = r - l + 1
int r = t + l - 1 - j;
w[i][j] = max(w[i][j], s[t] - s[r] + s[l - 1]);
}
}
for (rint j = m; j >= 0; j--)
for (rint k = 0; k <= j && k <= t; k++)
f[j] = max(f[j], f[j - k] + w[i][k]);
}
cout << f[m] << endl;
return 0;
}
T3 move
简要题意
对于两个字符串 \(a,b\)，使用恰好 \(k\) 次操作使 \(a\) 变成 \(b\)，操作为将字符串从中间任意位置截断，得到前后两个非空子串。将两个子串交换位置后重新连接，得到新字符串。(如将 abc -> a ,bc -> bca)，求不同的方案数。\(n≤10^5,0≤k≤10^5\)
solution
神仙题！
我们将原字符串收尾相连，看成一个环。那么，每次操作，是不是就是将断开位置改变了？那么对于答案直接影响的就是最后一次操作你所在的位置是否是正确切割位置。由于操作必须改变原字符串，所以需要考虑断开位置每一次必须改变，否则可以直接乘法原理推式子。
考虑 dp，\(f[i][0]\) 表示对 \(a\) 进行恰好 \(i\) 次操作, 与 \(b\) 相同的方案数，\(f[i][1]\) 表示对 \(a\) 进行恰好 \(i\) 次操作, 与 \(b\) 不同的方案数。
我们先要求出一个 cnt 表示正确切割位置的数量。
那么 \(f[i][0]\)，就暗示已经占用一个正确切割位置，由于每次必须改变位置，所以为 \((cnt-1)\times f[i-1][0]\)，而对于 \(f[i-1][1]\)，只要它下一步是 \(cnt\) 中的一个即可。那么转移为：
\[f_{i,0}=(cnt-1)\times f_{i-1,0}+cnt \times f_{i-1,1} \]至于 \(f[i][1]\) 就同理即可
\[f_{i,1}=(len-cnt)\times f_{i-1,0}+(len-cnt-1)\times f_{i-1,1} \]最终答案为 \(f_{k,0}\)
标程还写了个破环为链的过程，但我认为没有必要，因为这个环是假设的而且也说到了破换位置不能不变，所以不破环为链直接 dp 仍然具有正确性。
复杂度 \(O(n^2+k)\)
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
string a, b;
int k;
int f[N][2];
//f[i][0] 对 a 进行恰好 i 次操作, 与 b 相同的方案数
//f[i][1] 对 a 进行恰好 i 次操作, 与 b 不同的方案数
signed main()
{
cin >> a >> b; cin >> k;
int cnt = 0;
if (a == b) cnt = 1;
int len = a.size();
for (rint i = len - 1; i >= 1; i--)
if (a.substr(i) + a.substr(0, i) == b)
// 从第 i 个字符往后 + 从 0 到 i 刚好是 b
cnt++;
if (a == b) f[0][0] = 1;
else f[0][1] = 1;
for (rint i = 1; i <= k; i++)
{
// cnt - 1 是因为当前处于一个合法断开点不能原地踏步
f[i][0] = ((cnt - 1) * f[i - 1][0] + cnt * f[i - 1][1]) % mod;
f[i][1] = ((len - cnt) * f[i - 1][0] + (len - cnt - 1) * f[i - 1][1]) % mod;
}
cout << f[k][0] << endl;
return 0;
}