A – Takahashikun, The Strider
SB 题，不解释。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
int x;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int main()
{
scanf("%d", &x), printf("%d\n", 360 / gcd(x, 360));
return 0;
}
B – Extension
不难，直接容斥即可。
// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3030, mod = 998244353;
int n, m, a, b, dp[MAX_N][MAX_N];
int main()
{
scanf("%d%d%d%d", &a, &b, &n, &m);
dp[a][b] = 1;
for (int i = a; i <= n; i++)
for (int j = b; j <= m; j++)
if (i != a || j != b)
dp[i][j] = (0LL + 1LL * dp[i - 1][j] * j % mod + 1LL * dp[i][j - 1] * i % mod + mod - 1LL * dp[i - 1][j - 1] * (i - 1) % mod * (j - 1) % mod) % mod;
printf("%d\n", dp[n][m]);
return 0;
}
C – Shift
考虑把 0 看作分隔符，然后可以把操作看成把一个段内的 1 放到另外一个段里面然后造出一个新的字符串。这个东西可以考虑 DP，设置 dp[i][j][k] 为到前 \(i\) 个单元、放了 \(j\) 个\(1\) 且操作次数为 \(k\)。考虑暴力转移 + 剪枝，就能过了。
// C.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 330, mod = 998244353;
int threshold, len, n, pre[MAX_N], dp[MAX_N][MAX_N][MAX_N], units[MAX_N];
char str[MAX_N];
int main()
{
scanf("%s%d", str + 1, &threshold), len = strlen(str + 1);
int last_pos = 0, ones = 0;
for (int i = 1; i <= len; i++)
ones += str[i] == '1';
for (int i = 1; i <= len + 1; i++)
if (str[i] != '1')
units[++n] = i - last_pos - 1, last_pos = i;
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + units[i];
dp[0][0][0] = 1, threshold = min(threshold, ones);
for (int i = 0; i < n; i++)
for (int j = pre[i]; j <= pre[n]; j++)
for (int k = 0; k <= threshold; k++)
if (dp[i][j][k])
{
for (int g = max(j, pre[i + 1]); g <= pre[n]; g++)
if (k + g - j - units[i + 1] <= threshold)
{
if (i + 1 == n && g - j > units[i + 1])
break;
int cost = g - j <= units[i + 1] ? 0 : g - j - units[i + 1];
dp[i + 1][g][k + cost] = (0LL + dp[i + 1][g][k + cost] + dp[i][j][k]) % mod;
}
}
int ans = 0;
for (int i = 0; i <= threshold; i++)
ans = (0LL + ans + dp[n][ones][i]) % mod;
printf("%d\n", ans);
return 0;
}
D – Secret Passage
大概是能想出来的，但是写起来有点麻烦。 先定下终串的长度 \(|T|\)，然后在前 \(|S| – |T|\) 个字符中选一半留下、一半抛弃（前两个中有一个必须要选，而且必须要合法），然后再找一个 \(|T| – \frac{|S| – |T|}{2}\) 的后缀当作子序列插到 \(T\) 里。然后求本质不同的串。 那么，我们先求一个方案数：有 \(j\) 个额外的 \(0\) 和 \(k\) 个额外的 \(1\)，然后有 \(i\) 后缀作子序列。求完这个之后，我们还需要判合法性。 判断合法性，我们可以维护一个 vis 数组来记录前 \(i\) 个字符被抽走了 \(j\) 个 \(0\)、\(k\) 个 \(1\) 之后还剩多少个字符给剩下的 \(|S|-(i-j-k)\) 的前缀。如果有余（指大于等于 0），那么就是合法的。
// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 330, mod = 998244353;
int n, dp[MAX_N][MAX_N][MAX_N], vis[MAX_N][MAX_N][MAX_N];
bool verdict[MAX_N][MAX_N][MAX_N];
char str[MAX_N];
int main()
{
scanf("%s", str + 1), n = strlen(str + 1);
dp[n][0][0] = 1;
for (int i = n; i >= 1; i--)
for (int j = 0; j + (n - i) <= n - 1; j++)
for (int k = 0; j + k + (n - i) <= n - 1; k++)
if (str[i] == '0')
{
dp[i - 1][j][k] = (0LL + dp[i - 1][j][k] + dp[i][j][k]) % mod;
dp[i][j][k + 1] = (0LL + dp[i][j][k + 1] + dp[i][j][k]) % mod;
}
else
{
dp[i - 1][j][k] = (0LL + dp[i - 1][j][k] + dp[i][j][k]) % mod;
dp[i][j + 1][k] = (0LL + dp[i][j + 1][k] + dp[i][j][k]) % mod;
}
memset(vis, -1, sizeof(vis)), vis[0][0][0] = 0;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= (i >> 1); j++)
for (int k = 0; j + k <= (i >> 1); k++)
if (vis[i][j][k] != -1)
{
int c = vis[i][j][k];
if (i + 1 <= n && c != 0)
{
if (str[i + 1] == '0')
vis[i + 1][j + 1][k] = max(vis[i + 1][j + 1][k], c - 1);
if (str[i + 1] == '1')
vis[i + 1][j][k + 1] = max(vis[i + 1][j][k + 1], c - 1);
}
if (i + 2 <= n)
{
if (str[i + 1] == '0' || str[i + 2] == '0')
vis[i + 2][j + 1][k] = max(vis[i + 2][j + 1][k], c);
if (str[i + 1] == '1' || str[i + 2] == '1')
vis[i + 2][j][k + 1] = max(vis[i + 2][j][k + 1], c);
vis[i + 2][j][k] = max(vis[i + 2][j][k], c + 1);
}
}
for (int i = 0; i <= n; i++)
for (int j = n; j >= 0; j--)
for (int k = n; k >= 0; k--)
{
verdict[i][j][k] = vis[i][j][k] != -1;
if (i > 0)
verdict[i][j][k] |= verdict[i - 1][j][k];
verdict[i][j][k] |= verdict[i][j + 1][k] || verdict[i][j][k + 1];
}
int ans = 0;
for (int i = 0; i <= n; i++)
for (int j = 0; j + (n - i) <= n; j++)
for (int k = 0; j + k + (n - i) <= n; k++)
if (dp[i][j][k] && (n - i) + j + k != 0 && verdict[i][j][k])
ans = (0LL + ans + dp[i][j][k]) % mod;
printf("%d\n", ans);
return 0;
}
E – Permutation Cover
这个题很好啊。
我们首先要知道，有解需要满足 \(2\min\{a_i\} \geq \max\{a_i\}\)，考虑在出现最大值的分界点会出现三个相同的数，这样就 GG 了。
如果有解，我们可以先考虑构造第一个前缀出来，这样我们后面就可以贪心的去拼接了。每次我们枚举拼在上一个段后面的段长，然后找字典序最小的。如果我们在 \(a_i\) 中先扣除掉这个前缀的频数，然后再来判：如果满足 \(2\min\{a_i\} \geq \max\{a_i\}\)，那我们可以先直接 1、2、3、4 这样去搞，这样字典序最小且对 \(a_i\) 只有 1 的扣除。这样下去会出现 \(2\min\{a_i\} + 1 = \max\{a_i\}\) 的情况，然而这种情况下也是有解法的：我们可以考虑让 \(a_i\) 最大的 \(i\) 排在让 \(a_j\) 最小的 \(j\) 前面，然后再和剩下的那些项去归并。
// E.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1050;
int n, sum, ai[MAX_N], res[MAX_N], candid[MAX_N], pos[MAX_N];
int upper, lower, sa[MAX_N], sb[MAX_N], ans[MAX_N], ansptr;
bool compare(const int &x, const int &y)
{
if ((ai[x] == lower) == (ai[y] == lower))
return x < y;
else
return (ai[x] == lower) < (ai[y] == lower);
}
void solve(int len)
{
bool found = false;
for (int i = 1; i <= len; i++)
ai[pos[i]]--;
int min_val = *min_element(ai + 1, ai + 1 + n), max_val = *max_element(ai + 1, ai + 1 + n);
if ((min_val << 1) >= max_val)
{
for (int i = 1; i <= len; i++)
res[i] = pos[i];
sort(res + 1, res + 1 + len), found = true;
}
else if (((min_val << 1) | 1) == max_val)
{
upper = max_val, lower = min_val;
int ptra = 1, ptrb = 1, la = 0, lb = 0, ptr = 0;
for (int i = 1; i <= len; i++)
if (ai[pos[i]] == min_val || ai[pos[i]] == max_val)
sa[++la] = pos[i];
else
sb[++lb] = pos[i];
sort(sa + 1, sa + 1 + la, compare), sort(sb + 1, sb + 1 + lb);
// merge;
while (ptra <= la && ptrb <= lb)
if (sa[ptra] < sb[ptrb])
res[++ptr] = sa[ptra++];
else
res[++ptr] = sb[ptrb++];
while (ptra <= la)
res[++ptr] = sa[ptra++];
while (ptrb <= lb)
res[++ptr] = sb[ptrb++];
found = true;
for (int i = len + 1; i <= n; i++)
if (ai[pos[i]] == min_val)
found = false;
found |= (ai[sa[1]] == max_val);
}
for (int i = 1; i <= len; i++)
ai[pos[i]]++;
if (!found)
res[1] = 0;
}
bool lexicographicalCompare(int *s1, int *s2)
{
int ptr = 1;
while (s1[ptr] == s2[ptr])
ptr++;
return s1[ptr] < s2[ptr];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &ai[i]), sum += ai[i], pos[i] = i;
if (((*min_element(ai + 1, ai + 1 + n)) << 1) < *max_element(ai + 1, ai + 1 + n))
puts("-1"), exit(0);
solve(n);
for (int i = 1; i <= n; i++)
ans[++ansptr] = res[i], ai[res[i]]--, pos[i] = res[i];
while (ansptr < sum)
{
memset(candid, 0, sizeof(candid)), candid[1] = n + 1;
int len = 0;
for (int i = 1; i <= n; i++)
{
solve(i);
if (res[1] != 0 && lexicographicalCompare(res, candid))
{
len = i;
for (int j = 1; j <= i; j++)
candid[j] = res[j];
}
}
for (int i = 1; i + len <= n; i++)
pos[i] = pos[i + len];
for (int i = 1; i <= len; i++)
ans[++ansptr] = pos[n - len + i] = candid[i], ai[candid[i]]--;
}
for (int i = 1; i <= ansptr; i++)
printf("%d ", ans[i]);
puts("");
return 0;
}