10.12 一中S模拟
qdl66666666
·
·
个人记录
T1
给定 n 行 m 列的网格，其中一些位置有障碍。
从 (1,1) 到 (n,m) 每次只能向下或向右移动，且不经过障碍可以形成一条路径。
定义 (x_{1},y_{1}) 偏序 (x_{2},y_{2}) 当且仅当 x_{1} > x_{2},y_{1} < y_{2}。
集合 S_{a} 包含障碍 u 当且仅当路径 a 存在点 v，且 u 偏序 v。
你需要选择若干条路径，将这些路径对应的集合 S 按大小升序排序后得到 S_{1},S_{2},⋯,S_{k}。你需要保证任意 1 ≤i<k,S_{i} != S_{i+1} 且
保证 $(1,1)$ 和 $(n,m)$ 不是障碍。
## 题意
偏序可以理解为在自己右下方的障碍。
我们发现一条路径若能包含障碍 $u$，一定满足最小的 $x$ 不会大于 $x_{u}$ 且经过 $u$ 的上部。
[like](https://cdn.luogu.com.cn/upload/image_hosting/vwp37234.png)
所以我们不关心路的形态，只关心有多少个互不相交的连通块，这意味着我们可以从两两连通块的“缝隙”中穿插路径，若有 $k$ 个连通块，就会有 $k+1$ 条路径，当然我们还要考虑边上的连通块，因为路径显然不能绕过连通块跑到网格的外边。
我们要做的第一步是将连通块扩展。
注意到对于一个空地 $(x,y)$，若 $(x+1,y)$ 和 $(x,y+1)$ 都是障碍，则这个位置一定走不到终点，我们不妨把它设成障碍，以最大化每个障碍的影响。
第二步要将连通块进行连接。
连接是八连通的，若满足右上左下关系，则已经扩展为一般连通块；若满足左上右下关系，则没有路径额能从其中穿过，四连通关系不必说，将连通块合并。
用类似洪水填充 $O(n*m)$ 或用并查集判无解。
如何处理边上的连通块？考虑从左上向右下走，所以将边上的连通块分成左下块和右上块。具体来说，将左边界和下边界归为左下，其中的障碍不停向左下角扩展，其它类似。
答案就是连通块个数加一减去是否有左下块和右下块。
```cpp
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 2010;
template<typename TY>
inline void read(TY &s){
ll x = 0,f = 1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
s = x * f;
}
int n,m;
char ch;
bool mp[N][N];
bool f1,f2;
queue<pair<int,int> > Q;
inline void modify(int x,int y){
if(!mp[x][y]) mp[x][y] = 1,Q.push({x,y});
}
inline void check(int x,int y){
if(x < 1 || y < 1 || x + 1 > n || y + 1> m) return;
if(mp[x+1][y]&&mp[x][y+1]) modify(x,y),modify(x+1,y+1);
}
int id[N][N],a[N][N],cnt;
int dx[]={0,0,1,1,1,-1,-1,-1};
int dy[]={1,-1,0,1,-1,0,1,-1};
int main(){
freopen("grid.in","r",stdin);
freopen("grid.out","w",stdout);
read(n); read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> ch;
mp[i][j] = (ch=='#'?1:0);
if(mp[i][j]) Q.push({i,j});
}
}
while(!Q.empty()){
auto u = Q.front(); Q.pop();
if(u.fi==1||u.se==m) f1= true;
if(u.se==1||u.fi==n) f2 = true;
if(u.se==1&&u.fi<n) modify(u.fi+1,u.se);
if(u.fi==n&&u.se>1) modify(u.fi,u.se-1);
if(u.se==m&&u.fi>1) modify(u.fi-1,u.se);
if(u.fi==1&&u.se<m) modify(u.fi,u.se+1);
check(u.fi-1,u.se); check(u.fi,u.se-1);
}
id[1][1] = 1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]) continue;
if(id[i][j]){
if(!mp[i+1][j]) id[i+1][j] = 1;
if(!mp[i][j+1]) id[i][j+1] = 1;
}
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cerr << id[i][j] << ' ';
// }
// cerr << '\n';
// }
if(!id[n][m]){
cout << 0;
return 0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(!mp[i][j]) continue;
if(!a[i][j]) a[i][j] = ++cnt;
for(int k=0;k<8;k++){
int xx = i + dx[k], yy = j + dy[k];
if(a[xx][yy]||!mp[xx][yy]) continue;
a[xx][yy] = a[i][j];
}
}
}
// cerr << f1 <<" " << f2 <<"?\n";
cout << cnt + 1 - f1 - f2;
return 0;
}
```
# T2
给定一个由小写字母组成的字符串矩阵，矩阵维度为 `n×m`，其中每个字符串记为 $s_{i,j}$ (`1 ≤ i ≤ n`，`1 ≤ j ≤ m`）。
需要计算以下表达式的值：
$$
\sum_{i=1}^{n} \sum_{j=1}^{n} \max_{k=1}^{m} \text{LCP}(s_{i,k}, s_{j,k})
$$
## MIN-MAX容斥
设集合 $S$，则有
$$
\max(S) = \sum_{T\subseteq S}(-1)^{|T|-1}min(T)
$$
这个式子有很优美的对称性
$$
\min(S) = \sum_{T\subseteq S}(-1)^{|T|-1}max(T)
$$
奇妙之处就是它能将 $\min$ 和 $\max$ 运算相互转化，且变成求和形式，当其中一个不好求时，可以考虑求另一个转化。
所以这个题的式子变为
$$
\sum_{i=1}^{n} \sum_{j=1}^{n} \min_{k=1}^{m} \text{LCP}(s_{i,k}, s_{j,k})
$$
只需要枚举 $m$ 个字符串的子集求 $\min$ 转化成 $\max$。
## tire树
注意到这样的式子变得可做了。
先考虑 $m = 1$ 时，将所有字符串插入 tire 树，问题转化为遍历 tire 树中的节点，统计以这个点为 $LCA$ 的点对数量，乘以深度就是它的贡献。
再考虑 $m$ 为 2 或 3，可以将每组字符串以组里最小的长度截取，按照每一位排成一个新字符串，那 求得的$lcp$ 的长度除以 $m$ 就是其真实的 $lcp$ 长度。
把新字符串插入到 tire 树中，乘以深度除以组成新字符串的字符串个数就是它的贡献。
复杂度 $O(2^mnm)$。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
template<typename TY>
inline void read(TY &s){
ll x = 0,f = 1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
s = x * f;
}
int n,m;
string s[N][4];
vector<string> p[N];
ll tire[N*3][26],tag[N*3],deep[N*3],idx;
ll ans;
inline void insert(string &s){
int pos = 0;
for(int i=0;i<s.size();i++){
int k = s[i] - 'a';
if(!tire[pos][k]) tire[pos][k] = ++idx,deep[idx] = deep[pos] + 1;
pos = tire[pos][k];
}
tag[pos]++;
}
ll get_min(int x){
// cerr << x << "get_min\n";
for(int i=0;i<=idx;i++){
for(int j=0;j<26;j++){
tire[i][j] = 0;
}
tag[i] = deep[i] = 0;
}
idx = 0;
for(int i=1;i<=n;i++){
int minlen = INT_MAX;
for(auto a : p[i]){
minlen = min(minlen,(int)a.size());
}
string t;
for(int len=0;len<minlen;len++){
for(int j=0;j<x;j++){
t += p[i][j][len];
}
}
// cerr << t << "-->t\n";
insert(t);
}
ll res = 0;
for(int i=idx;i;i--){
ll total = 0, sum = tag[i];
// cerr << "i:" << i << "tag" << tag[i] << "?";
total += 1ll * tag[i] * tag[i];
for(int j=0;j<26;j++){
if(!tire[i][j]) continue;
total += 1ll * sum * tag[tire[i][j]] * 2;
// cerr << total << "?";
sum += tag[tire[i][j]];
tag[i] += tag[tire[i][j]];
}
res += 1ll * total * (deep[i] / x);
}
// cerr << "res = " << res << "\n";
return res;
}
int main(){
freopen("lcp.in","r",stdin);
freopen("lcp.out","w",stdout);
read(n); read(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> s[i][j];
}
}
for(int S=1;S<(1<<m);S++){
int num = __builtin_popcount(S);
for(int i=1;i<=n;i++) p[i].clear();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int num = __builtin_popcount(S);
if((1 << j-1) & S){
p[i].push_back(s[i][j]);
// cerr << s[i][j] << "???????s[i][j]\n";
}
// min - max
}
}
ans += get_min(num) * (num & 1 ? 1 : -1);
}
cout << ans;
return 0;
}
```
# T3
给定一个字符串，每个位置有权值 $w[i]$， 给定数字 $k$，保留字符串的 $k$ 个位置，其他位置两两匹配。
当且仅当$s_{i} != s_{j}$ 时可以匹配，价值是 $100 * |i - j| + w[i] + w[j]$，问能获得的最小权值。
这个题实在过于艰难，以本蒟蒻的水平只理解了表层。
注意到对于按顺序排列的 $a$，$b$，$c$，$d$ 字符集，与其让 $a,b$ 配对 $c,d$，不如让 $a,b/c,d$ 各自两两配对，考虑让挨得近的配对，而权值是加法不变，$|i-j|$ 越小则总价值越小。
所以设 $f[i][j][0/1][c][k]$ 表示到了 $i$ 的位置，前面还有 $j$ 个字符要处理，$0$ 表示还有一种字符为 $c$，$1$ 表示有多种字符要与 $c$ 匹配，保留了 $k$ 个位置。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=2505,inf=0x3f3f3f3f;
int n,k,ans=inf,a[N],f[2][N][2][6][7];
//f[i][j][0/1][c][k]:
//当前到了第 i 个位置，因为 i 只与 i - 1 有关，故滚动数组优化
//前面还有 j 个未匹配的字符
//0:前面未匹配的字符只有一种，其种类为 c
//1:前面未匹配的字符有多种，需要匹配 c
//k:保留了 k 个字符
char s[N];
void chk(int&x,int y) {if(x>y) x=y;}
int main(){
memset(f,0x3f,sizeof f);
f[0][0][0][0][0]=0;
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&k);
for(int i=1,o=1;i<=n;i++,o^=1){
memset(f[o],0x3f,sizeof f[o]);
int p=s[i]-'a';
for(int j=0;j<i&&j<=n/2;j++) // j 是 i 之前未匹配的字符，且未匹配的字符不可能超过一半
for(int u:{0,1})
for(int c=0;c<6;c++)
for(int t=0;t<=k;t++){
int v=f[o^1][j][u][c][t]+j*100+a[i];// j * 100 表示随着位置的向后推移，j 所做的贡献每次会乘 100
if(t<k) chk(f[o][j][u][c][t+1],v-a[i]);// 还能保留字符，保留，贡献少了当前位置的权值
if(!j) chk(f[o][1][0][p][t],v);// 没有剩余的字符，这个字符匹配不上
else if(u){//如果有多种未匹配的字符，需要匹配 c
if(c==p) chk(f[o][j-1][1][c][t],v);//匹配成功，j - 1
else chk(f[o][j+1][1][c][t],v);//失败，j + 1
}
else{//只有一种未匹配的字符，它是 c
if(c==p) chk(f[o][j+1][0][c][t],v);// c == p 不满足题目要求，j + 1
else{
chk(f[o][j-1][0][c][t],v);//可以匹配，j - 1
for(int q=0;q<6;q++) //
if(q!=c&&q!=p) chk(f[o][j+1][1][q][t],v);
}
}
}
}
for(int o:{0,1})
for(int i=0;i<6;i++)
chk(ans,f[n&1][0][o][i][k]);
printf("%d\n",ans==inf?-1:ans);return 0;}
```