T1.将军棋
其实挺水的一道题，但是出题人丧心病狂强迫分类讨论，故意增加码量。
\(A\) 挨着查直到队伍不同
\(B、C\) 记录每种颜色最后出现的位置，枚举是哪一种颜色。对于 \(B\) 枚举两个，如果都不是，那就是第三个；对于 \(C\) 手动二分。
\(D\)、100 先判断是否为新颜色，若不是再二分。
二分显然就是查 \([mid, i - 1]\) 和 \([mid, i]\) 队伍数量是否相同，相同说明 \(i\) 这个队伍在 \([mid, i - 1]\) 中出现过，找到最后一个这样的位置。注意到前 \(i-1\) 的颜色我们已知，所以根本不需要查询，直接暴力找出来即可。
代码
#define sandom signed
#include "generals.h"
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
const int Z = 1010;
int n, m, k = 1;
int dp[Z][Z];
bool vs[Z];
vector<int> ans;
inline int ask(int l, int r)
{
if (dp[l][r]) return dp[l][r];
return dp[l][r] = query(l, r);
}
inline int count(int l, int r)
{
int cnt = 0; memset(vs, 0, sizeof(vs));
rep(i, l, r) if (!vs[ans[i - 1]]) cnt++, vs[ans[i - 1]] = 1;
return cnt;
}
inline bool check(int j, int i) { return count(j, i - 1) == ask(j, i); }
inline int getcol(int i)
{
int l = 1, r = i - 1, res = 0;
while (l <= r)
{
int mid = l + r >> 1;
if (check(mid, i)) res = mid, l = mid + 1;
else r = mid - 1;
}
return res - 1;
}
int pos[10];
inline bool cmp(int x, int y) { return x > y; }
vector<int> getColor(int T, int n, int Q)
{
ans.push_back(++m); pos[k = 1] = 1;
if (T <= 15)//队伍连续
{
rep(i, 2, n)
{
if (ask(k, i) == 1) ans.push_back(m);
else k = i, ans.push_back(++m);
}
}
else if (T <= 34)//最多3个队伍
{
rep(i, 2, n)
{
sort(pos + 1, pos + 5, cmp);
if (pos[1] && check(pos[1], i)) ans.push_back(ans[pos[1] - 1]), pos[1] = i;
else if (pos[2] && check(pos[2], i)) ans.push_back(ans[pos[2] - 1]), pos[2] = i;
else if (pos[3]) ans.push_back(ans[pos[3] - 1]), pos[3] = i;
else ans.push_back(++m), pos[3] = i;//新颜色
}
}
else if (T <= 48)//最多4个队伍
{
rep(i, 2, n)
{
sort(pos + 1, pos + 5, cmp);
if (!pos[2] && check(pos[1], i)) ans.push_back(ans[pos[1] - 1]), pos[1] = i;
else if (pos[2] && check(pos[2], i))
{
if (pos[1] && check(pos[1], i)) ans.push_back(ans[pos[1] - 1]), pos[1] = i;
else ans.push_back(ans[pos[2] - 1]), pos[2] = i;
}
else if (pos[3] && check(pos[3], i)) ans.push_back(ans[pos[3] - 1]), pos[3] = i;
else if (pos[4]) ans.push_back(ans[pos[4] - 1]), pos[4] = i;
else ans.push_back(++m), pos[4] = i;//新颜色
}
}
else//二分查询
{
rep(i, 2, n)
{
if (ask(1, i) == ask(1, i - 1) + 1) ans.push_back(++m);
else ans.push_back(ans[getcol(i)]);
}
}
return ans;
}
T2.小明的变换
考场推了个假结论，然而是一道模拟题。
操作其实就是把相同的数放在后面，尝试匹配 \(a、b\) 的每一项，如果能匹配直接匹配，如果不能开个桶记录 \(a\) 中前面出现过的数，当后面有相同的需要时，从前面的桶中直接拿。全部匹配成功就是有解。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#include <cstring>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; typedef long long ll; typedef unsigned long long ull;
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
}; using namespace IO;
const int Z = 1e6 + 10;
int n, a[Z], b[Z], cnt[Z];
sandom main()
{
fre(trans, trans);
int T = read();
while (T--)
{
memset(cnt, 0, sizeof(cnt));
n = read();
rep(i, 1, n) a[i] = read();
rep(i, 1, n) b[i] = read();
int i = 1, op = 1;
rep(j, 1, n)
{
while (b[j] != a[i] && i <= n) cnt[a[i++]]++;//找到匹配项
if (i > n) { op = 0; break; }//匹配不上
if (cnt[a[i]]) cnt[a[i]]--;//如果前面有直接拿过来
else i++;//否则判定为匹配对
}
if (op) puts("YES");
else puts("NO");
}
return 0;
}
T3.小明过生日
题意：有一个长度为 \(n\) 的字符串，给定一个序列 \(a\)，当满足前 \(a_1\) 个字符，接着 \(a_2\) 个字符，接着 \(a_3\) 个字符…… 为回文串时，且构造出的 \(b\) 同理时，字符串中所有字符都相同。
根据回文串，给已知相同的字符连边，转化为图论问题，构造出\(b\)使得\(n\)个点之间连通。
一个点在一个序列中最多连一条边，那么整张图最多 \(2n\) 条边，想要连通至少需要 \(2(n-1)\) 条边。发现每一个奇数段都有一个点没有连边，但是我们最多只能少 \(2\) 条边，所以当\(a\)中奇数段超过\(2\)时，无解。
根据回文串的性质：错位回文则全部字符相同。一个奇数段\(k\)与一个相差为1的偶数段\(k-1\)，可以满足前\(k\)连通，并且\(k\)处恰好留出一个接口，连接下一条边。通过规律发现以下构造方法：把奇数段放在首尾两段。
\(b\)为\(a_1-1、a_2、a_3、a_m-1\)，手磨一下不难发现是对的。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
using namespace std; typedef long long ll; typedef unsigned long long ull;
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2; int wrt[20], Tp = 0;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
inline void write(int x) { if (x < 0) putchar('-'), x = -x; do { wrt[++Tp] = x % 10, x /= 10; } while (x); while (Tp) putchar(wrt[Tp--] | 48); putchar(' '); }
}; using namespace IO;
const int Z = 1e5 + 10;
int n, m, k;
int a[Z], b[Z];
sandom main()
{
fre(birth, birth);
n = read(), m = read();
if (m == 1)
{
int x = read();
write(x), putchar('\n');
write(2), putchar('\n');
write(x - 1), write(1), putchar('\n');
return 0;
}
rep(i, 1, m) if ((a[i] = read()) & 1) k++;
if (k > 2) { puts("-1"); return 0; }
rep(i, 2, m) if (a[i] & 1)
{
if (a[1] & 1) swap(a[i], a[m]);
else swap(a[i], a[1]);
}
rep(i, 1, m) write(a[i]); putchar('\n');
rep(i, 1, m) b[i] = a[i]; b[1]--, b[m]++;
write(m), putchar('\n');
rep(i, 1, m) write(b[i]);
return 0;
}
T4.小明爱数数
本来以为和数列挺像的，所以弄了四维\(dp\)，发现复杂度严重不对，就没继续想了。
定义 \(dp[i][j][k]\) 表示考虑了前\(i\)个数，当前\(MEX\)为\(k\)，已经有了\(j\)个不同的大于\(k\)的数。转移如下：
1.对\(MEX\)不产生影响：
选择小于\(MEX\)的：\(ddp[i][j][k] += dp[i-1][j][k] * k\)
选择大于\(MEX\)且出现过的：\(dp[i][j][k] += dp[i-1][j][k] * j\)
选择大于\(MEX\)且未出现过的，但是因为不确定具体是谁，所以此处不计算贡献，把贡献看作单位1：\(dp[i][j][k] += dp[i-1][j - 1][k]\)
2.对\(MEX\)产生影响：
显然就是选择了\(MEX\)。枚举直接的 \(MEX\) 是 \(t\)，则就是 \(i\) 这个位置放了 \(t\) 使得 \(MEX\)由\(t\)变为\(k\)，此时\(t->k\)中间的数一定都出现过，共有\(k-t-1\)个。因为在\(j\)处没有计算贡献，所以现在可以从\(j\)强制选这\(k-t-1\)个，剩下的还是不计算贡献，那么转移就是\(dp[i][j][k] += dp[i-1][j + k - t - 1][t] * A_{j + k - t - 1}^{k - t - 1}\)。
时间复杂度\(O(n^2k^2)\)，对第二种转移用前缀和优化，令\(s=j+k-1\)，那么累加的答案就是\(dp[s-t][t]*\frac{(s-t)!}{j!}\)，令\(sum[x][y]=\sum\limits_{t=0}^{y}dp[x-t][t] * (x-t)!\)，注意边界问题。
我一直以为是边界写错了，调了一个半小时，结果是tm数组越界了。
代码
#define sandom signed
#define fre(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#include <iostream>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define dwn(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std; typedef long long ll; typedef unsigned long long ull;
#define int long long
namespace IO
{
const int bif = 1 << 18; char buf[bif], *p1, *p2;
inline char getc() { if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, bif, stdin); if (p1 == p2) return EOF; } return *p1++; }
inline int read() { int x = 0, f = 0; char c = getc(); while (!isdigit(c)) f |= c == '-', c = getc(); while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getc(); return f ? -x : x; }
}; using namespace IO;
const int Z = 2100, mod = 998244353;
inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; }
inline int qpow(int a, int b, int c) { int res = 1; while (b) { if (b & 1) res = res * a % c; a = a * a % c; b >>= 1; } return res; }
int n, m, k, ans;
int l[Z], r[Z];
int fac[Z], inv[Z];
inline void init()
{
fac[0] = 1;
rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
inv[n] = qpow(fac[n], mod - 2, mod);
dwn(i, n - 1, 0) inv[i] = inv[i + 1] * (i + 1) % mod;
}
inline int A(int n, int m) { return n < m ? 0 : fac[n] * inv[n - m] % mod; }
int dp[2][Z][Z], sum[Z][Z];
//dp[i][j][k]：前i个数，MEX为k，有j个不同的数大于MEX
sandom main()
{
fre(numb, numb);
n = read(), k = read();
init();
rep(i, 1, n)
{
int b = read();
l[i] = max(b - k, 0);
r[i] = min(b + k, i);
}
dp[0][0][0] = 1;
rep(i, 1, n)
{
int u = i & 1, v = i - 1 & 1;
rep(j, max(l[i] - 1, 0), i - 1) rep(k, l[i - 1], min(r[i - 1], j)) sum[j][k] = ((k ? sum[j][k - 1] : 0) + dp[v][j - k][k] * fac[j - k]) % mod;
rep(j, 0, i) rep(k, l[i], r[i])
{
if (j + k > i) break;//后面一定不合法
dp[u][j][k] += dp[v][j][k] * k;//选择小于mex的
dp[u][j][k] += dp[v][j][k] * j;//选择大于mex且出现过的
if (j) dp[u][j][k] += dp[v][j - 1][k];//选择大于mex且未出现过的，但是不计算贡献
// rep(t, l[i - 1], r[i - 1])
// if (k > t) dp[u][j][k] += dp[v][j + k - t - 1][t] * A(j + k - t - 1, k - t - 1);
if (k) dp[u][j][k] += sum[j + k - 1][min(k - 1, r[i - 1])] * inv[j];//选择mex，利用前缀和优化
dp[u][j][k] %= mod;
}
rep(j, 0, i - 1) rep(k, l[i - 1], r[i - 1]) dp[v][j][k] = sum[j][k] = 0;
}
rep(j, 0, n) rep(k, l[n], r[n]) (ans += dp[n & 1][j][k] * A(n - k, j)) %= mod;
cout << (ans + mod) % mod;
return 0;
}