专栏文章

10.12 一中S模拟

qqdl66666666
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmesty
此快照首次捕获于
2025/12/02 04:47
3 个月前
此快照最后确认于
2025/12/02 04:47
3 个月前
查看原文

T1

给定 nn 行 mm 列的网格，其中一些位置有障碍。
从 (1,1)(1,1) 到 (n,m)(n,m) 每次只能向下或向右移动，且不经过障碍可以形成一条路径。
定义 (x1,y1)(x_{1},y_{1}) 偏序 (x2,y2)(x_{2},y_{2}) 当且仅当 x1>x2,y1<y2x_{1} > x_{2},y_{1} < y_{2}。
集合 SaS_{a} 包含障碍 uu 当且仅当路径 aa 存在点 vv，且 uu 偏序 vv。
你需要选择若干条路径，将这些路径对应的集合 SS 按大小升序排序后得到 S1,S2,⋯,SkS_{1},S_{2},⋯,S_{k}。你需要保证任意 1≤i<k,Si!=Si+11 ≤i<k,S_{i} != S_{i+1} 且 Si⊆Si+1S_{i}⊆S_{i+1}，求最多能选出几条路径。
保证 (1,1)(1,1) 和 (n,m)(n,m) 不是障碍。

题意

偏序可以理解为在自己右下方的障碍。
我们发现一条路径若能包含障碍 uu，一定满足最小的 xx 不会大于 xux_{u} 且经过 uu 的上部。 like
所以我们不关心路的形态，只关心有多少个互不相交的连通块，这意味着我们可以从两两连通块的“缝隙”中穿插路径，若有 kk 个连通块，就会有 k+1k+1 条路径，当然我们还要考虑边上的连通块，因为路径显然不能绕过连通块跑到网格的外边。
我们要做的第一步是将连通块扩展。
注意到对于一个空地 (x,y)(x,y)，若 (x+1,y)(x+1,y) 和 (x,y+1)(x,y+1) 都是障碍，则这个位置一定走不到终点，我们不妨把它设成障碍，以最大化每个障碍的影响。
第二步要将连通块进行连接。
连接是八连通的，若满足右上左下关系，则已经扩展为一般连通块；若满足左上右下关系，则没有路径额能从其中穿过，四连通关系不必说，将连通块合并。
用类似洪水填充 O(n∗m)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，其中每个字符串记为 si,js_{i,j} (1 ≤ i ≤ n，1 ≤ j ≤ m）。
需要计算以下表达式的值：
∑i=1n∑j=1nmax⁡k=1mLCP(si,k,sj,k)\sum_{i=1}^{n} \sum_{j=1}^{n} \max_{k=1}^{m} \text{LCP}(s_{i,k}, s_{j,k})

MIN-MAX容斥

设集合 SS，则有
max⁡(S)=∑T⊆S(−1)∣T∣−1min(T)\max(S) = \sum_{T\subseteq S}(-1)^{|T|-1}min(T)
这个式子有很优美的对称性
min⁡(S)=∑T⊆S(−1)∣T∣−1max(T)\min(S) = \sum_{T\subseteq S}(-1)^{|T|-1}max(T)
奇妙之处就是它能将 min⁡\min 和 max⁡\max 运算相互转化，且变成求和形式，当其中一个不好求时，可以考虑求另一个转化。
所以这个题的式子变为
∑i=1n∑j=1nmin⁡k=1mLCP(si,k,sj,k)\sum_{i=1}^{n} \sum_{j=1}^{n} \min_{k=1}^{m} \text{LCP}(s_{i,k}, s_{j,k})
只需要枚举 mm 个字符串的子集求 min⁡\min 转化成 max⁡\max。

tire树

注意到这样的式子变得可做了。
先考虑 m=1m = 1 时，将所有字符串插入 tire 树，问题转化为遍历 tire 树中的节点，统计以这个点为 LCALCA 的点对数量，乘以深度就是它的贡献。
再考虑 mm 为 2 或 3，可以将每组字符串以组里最小的长度截取，按照每一位排成一个新字符串，那 求得的lcplcp 的长度除以 mm 就是其真实的 lcplcp 长度。
把新字符串插入到 tire 树中，乘以深度除以组成新字符串的字符串个数就是它的贡献。
复杂度 O(2mnm)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]w[i]， 给定数字 kk，保留字符串的 kk 个位置，其他位置两两匹配。
当且仅当si!=sjs_{i} != s_{j} 时可以匹配，价值是 100∗∣i−j∣+w[i]+w[j]100 * |i - j| + w[i] + w[j]，问能获得的最小权值。
这个题实在过于艰难，以本蒟蒻的水平只理解了表层。
注意到对于按顺序排列的 aa，bb，cc，dd 字符集，与其让 a,ba,b 配对 c,dc,d，不如让 a,b/c,da,b/c,d 各自两两配对，考虑让挨得近的配对，而权值是加法不变，∣i−j∣|i-j| 越小则总价值越小。
所以设 f[i][j][0/1][c][k]f[i][j][0/1][c][k] 表示到了 ii 的位置，前面还有 jj 个字符要处理，00 表示还有一种字符为 cc，11 表示有多种字符要与 cc 匹配，保留了 kk 个位置。
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;}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...