E - Chain Contestant
给定一个由 \(A - J\) 组成的串，求从中选出子序列满足相同的字符必须相临的方案数。
如果直接 \(dp\) , 无法得知前面是否已经出现过某种颜色。发现字符种类仅有 \(10\) 种，于是可以状态压缩记录某种颜色是否出现过。
令 \(dp[i][j][k]\) 为从前 \(i\) 个字符中选择，颜色状态为 \(j\)， 最后选择的颜色为 \(k\) 的合法方案数。
初始状态为 \(dp[i][1 << col_i][col_i] = 1\)
\(dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - (1 << k)][t]\;\;(选)\)
\(dp[i][j][k] = dp[i - 1][j][k]\;\;(不选)\)
答案即为 \(\sum\limits_{i = 0}^{1023}\sum\limits_{j = 0}^9dp[n][i][j]\)。 复杂度 \(O(2^{10} * n * 10)\)
Sample Code (C++)
int n;
char str[N];
LL dp[N][1 << M][M];
int main()
{
cin >> n >> (str + 1);
for(int i = 1; i <= n; ++ i)
{
int col = str[i] - 'A';
dp[i][1 << col][col] = 1;
for(int j = 0; j < (1 << 10); ++ j)
{
for(int k = 0; k < 10; ++ k)
if(j >> k & 1)
{
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % P;
if(col == k) dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % P;
}
if(j >> col & 1)
for(int t = 0; t < 10; ++ t)
if((j - (1 << col)) >> t & 1)
dp[i][j][col] = (dp[i][j][col] + dp[i - 1][j - (1 << col)][t]) % P;
}
}
LL res = 0;
for(int i = 0; i < (1 << 10); ++ i)
for(int j = 0; j < 10; ++ j)
res = (res + dp[n][i][j]) % P;
cout << res << endl;
return 0;
}
F - Dist Max 2
给一组点，定义两点之间的距离为 \(min(|x_i - x_j|, |y_i - y_j|)\), 求两个不同点的最大距离。
最小值最大化问题，考虑二分答案。
若一个答案 \(k\) 合法，则必须满足存在两个点使得 \(|x_i - x_j| \ge k\), 并且 \(|y_i - y_j| \ge k\), 于是可以考虑一个类似于滑动窗口的做法，将点按照 \(x\) 排序，对于当前点 \(P\) 来说，若队列中的点 \(Q\) 与 \(P\) 的 \(x\) 坐标差 \(\ge k\) , 则 \(Q\) 可以加入答案集合，维护答案集合的最大值和最小值，判断当前点是否可以从答案集合中找出一个合法点，即 \(y_{max} - y_p \ge k\) 或 \(y_p - y_{min} \ge k\) 。
复杂度 \(O(nlogn + nlogx_{max})\)
Sample Code (C++)
vector<PII> v;
bool check(int mid)
{
queue<PII> q; int Max = 0, Min = INF;
for(auto p : v)
{
while(!q.empty() && p.fi - q.front().fi >= mid)
{
Max = max(Max, q.front().se);
Min = min(Min, q.front().se);
q.pop();
}
if(Max - p.se >= mid || p.se - Min >= mid) return 1;
q.push(p);
}
return 0;
}
int main()
{
IOS; int n; cin >> n;
for(int i = 0; i < n; ++ i) { int x, y; cin >> x >> y; v.push_back({x, y}); }
sort(v.begin(), v.end());
int l = 0, r = 1e9, res;
while(l <= r)
{
int mid = l + r >> 1;
if(check(mid)) { res = mid; l = mid + 1; }
else r = mid - 1;
}
cout << res << endl;
return 0;
}