专栏文章

10.16 一中模拟高中3

qqdl66666666
题解参与者 1已保存评论 0

文章操作

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

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

T1

题意

给定 nn 个数 a1,a2...,a3a_{1},a_{2}...,a_{3}，定义不美观度为最大的相邻两数的和。从中去掉 mm 个数，相对位置关系不变（一个数没了，两边的数会相邻），问使剩下的数的不美观度最小是多少？

注意力

注意到一个序列当前的不完美度一定是最大的相邻两数的和，我们对这其操作才会对它的不完美度造成影响，反之则不能。所以我们可以用大根堆堆存储相邻两个数的和以及位置等信息，每次取最大的处理。
去掉一个数后的相邻关系如何维护，用链表（连通块可以用并查集）！

小证

我们找出两个数后应该删掉哪个呢？
答案是删掉较大的那个，简单证明：
设 a,b,c,d(b<=c)a,b,c,d(b<=c)，b+cb+c 是最大的一对，若删掉 bb，会减去 a+ba+b 的贡献，计入 a+ca+c，显然 a+c>a+ba+c>a+b；反之，若删掉 cc，会减去 c+dc+d 的贡献，计入 b+db+d，因为 b+d<c+db+d<c+d，所以删去较大的至少不劣。
CPP
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 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 tid,n,m,cnt;
struct node{
	int l,r; ll w; 
}z[N];
struct ty{
	int x,y,w;
};
bool vis[N];
priority_queue<pair<ll,pair<int,int> > > Q;
int main(){
	freopen("necklace.in","r",stdin);
	freopen("necklace.out","w",stdout);
	read(tid); read(n); read(m);
	for(int i=1;i<=n;i++){
		read(z[i].w); z[i].l = i - 1, z[i].r = i + 1;
	} 
	z[1].l = n; z[n].r = 1;
	for(int i=1;i<=n;i++){
		Q.push({z[i].w + z[z[i].r].w,{i,z[i].r}});
	}
	while(!Q.empty()){
		if(cnt >= (n - m)){
			while(!Q.empty()){
				int idx = Q.top().se.fi,rr = Q.top().se.se; 
				ll w = Q.top().fi;
				Q.pop(); 
//				cerr<< idx << " " << rr << ";\n";
				if(vis[idx]||vis[rr]) continue;
				cout << w;
				return 0;
			}
		}
		int idx = Q.top().se.fi,rr = Q.top().se.se;
//		cerr << Q.top().fi << "?\n";
		Q.pop();
//		cerr << "-->";
		if(vis[idx]||vis[rr]) continue;
		int rs = z[idx].r, ls = z[idx].l;
//		cerr << idx << " " <<  rs <<  " " <<  z[idx].w + z[rs].w << "?\n";
		if(z[idx].w < z[rs].w){
			vis[rs] = true;
			z[idx].r = z[rs].r; z[z[rs].r].l = idx;
//			cerr << idx << " " << z[rs].r << "oooo\n";
			Q.push({z[idx].w + z[z[idx].r].w,{idx,z[idx].r}});
		}
		else{
			vis[idx] = true;
			z[rs].l = ls, z[ls].r = rs;
//			cerr << ls << " " << rs << " " << z[ls].w + z[rs].w << "kkkkkk\n"; 
			Q.push({z[ls].w + z[rs].w,{ls,rs}});			
		}
		cnt++;
	} 
	return 0;
}

T2

题意

统计满足以下条件的二叉树的个数：
  1. 第 ii 个节点的儿子数量在 [li,ri][l_{i},r_{i}] 之间。
  2. 若第 ii 个节点不为叶子，需要满足其儿子最大的节点编号大于 ii。
注意节点选左右儿子是两种状况，答案对 1e9+7 取模。

注意不到

设 f(i,j,k)f(i,j,k) 表示选了 ii 个点，形成了 jj 棵树，有 kk 个儿子节点待定的方案数。相当于我们先保留 kk 个位置，后续会选择合适的儿子来填上，正着考虑以满足条件2。

转移

设好了状态，我们分类讨论第 ii 个点的儿子数 ll 进行转移：
若 l=0:l=0:
  • 新开一棵树：f(i,j,k)−>f(i+1,j+1,k)f(i,j,k) -> f(i+1,j+1,k)
  • 把这个点放在缺失的儿子上： f(i,j,k)×k−>f(i+1,j,k−1)f(i,j,k)\times k -> f(i+1,j,k-1)
若 l=1:l=1:
  • 新开一颗树：f(i,j,k)×2−>f(i+1,j+1,k)f(i,j,k)\times 2 -> f(i+1,j+1,k)
  • 补儿子：f(i,j,k)×2−>f(i+1,j+1,k)f(i,j,k)\times 2 -> f(i+1,j+1,k)
注意到这里要乘二，因为 ii 的儿子可以有左右两种位置选择。
若 l=2:l=2:
  • 新开一棵树：f(i,j,k)−>f(i+1,j+1,k)f(i,j,k) -> f(i+1,j+1,k)
  • 补儿子： f(i,j,k)×k−>f(i+1,j,k−1)f(i,j,k)\times k -> f(i+1,j,k-1)
  • 将一颗没有父亲的树挂在它的其中一个儿子的位置上，因为他有两个儿子，只要保证另外一个的编号大于自己即可，这棵树可以挂在两种位置，有 jj 棵树选择：f(i,j,k)×2×j−>f(i+1,j,k+1)f(i,j,k)\times 2\times j -> f(i+1,j,k+1)
  • 进行操作三后把以它为根的树挂在另一颗树上，可以挂在 kk 棵树上，有 (j−1)(j-1) 棵树选择挂在左右两个位置：
  • f(i,j,k)×2×k×(j−1)−>f(i+1,j,k+1)f(i,j,k)\times 2\times k\times (j-1) -> f(i+1,j,k+1)
所以这道题就做完了，相当于正着考虑，预留儿子的位置维护森林，分类讨论计算方案数。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 310; 
const int mod = 1e9 + 7;
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 tid,T;
ll f[N][N][N];
int n,l[N],r[N]; 
inline void add(ll &x,ll y){
	x += y; if(x > mod) x -= mod;
}
void solve(){
	read(n);
	for(int i=1;i<=n;i++){
		read(l[i]); read(r[i]);
	}
	for(int i=0;i<=n;i++)
	for(int j=0;j<=n;j++){
		for(int k=0;k<=n;k++){
			f[i][j][k] = 0;
		}
	}
	f[0][0][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
//			if(j > i) continue;
			for(int k=0;k<=n;k++){
				if(!f[i-1][j][k]) continue;
				if(!l[i]){
					add(f[i][j+1][k],f[i-1][j][k]);
					if(k) add(f[i][j][k-1],f[i-1][j][k]*k%mod); 
				}
				if(l[i]<=1&&r[i]>=1){
					add(f[i][j+1][k+1],2 * f[i-1][j][k]%mod);
					add(f[i][j][k],2*f[i-1][j][k]*k%mod);
				} 
				if(r[i]==2){//编号大于关系
					add(f[i][j+1][k+2],f[i-1][j][k]%mod);
					add(f[i][j][k+1],f[i-1][j][k]*k%mod);
					add(f[i][j][k+1],2*f[i-1][j][k]*j%mod);
					if(j>1) add(f[i][j-1][k],f[i-1][j][k]*(j-1)%mod*2*k%mod);
				} 
			}
		}
	}
	cout << f[n][1][0] << "\n"; 
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	read(tid); read(T);
	while(T--){
		solve();
	}
	return 0;
}

T3

题意

给定字符串 s,ts,t，ss 中第 ii 个字符的美观度为 wiw_{i}，每次可以选择一种字符最左边或最右边的位置删除，问在能得到 tt 的前提下，删去的字符的最小美观度和是多少？

sub7

字符串全是 aa，那么我们就固定了选中间长为 mm 的一段 aa，用前缀和维护删去的数的和，取最小即可。

sub1,2,3,4,5,6

暴力 DPDP，设 f(i,j)f(i,j) 表示匹配到 sis_{i}，tjt_{j} 的删去字符的最小美观度和。
若 si+1=tj+1s_{i+1}=t_{j+1}，f(i,j)−>f(i+1,j+1)f(i,j) -> f(i+1,j+1)
若 si+1!=tj+1s_{i+1}!=t_{j+1}，如果 j<mp[si+1].fij < mp[s_{i+1}].fi 或 j+1>mp[si+1].sej+1 > mp[s_{i+1}].se，f(i,j)+wi+1−>f(i+1,j)f(i,j) + w_{i+1} -> f(i+1,j)，换句话说，如果 jj 这个位置处于 si+1s_{i+1} 在 tt 中第一次出现的位置和最后一次出现的位置中间，说明后面还要匹配 si+1s_{i+1}，如果将此时的 si+1s_{i+1} 删去，就只能根据题目要求将这个数前面或后面的相同字符删去，这样就不能匹配 tt，所以不能删去。
复杂度 O(nm)O(nm)。
CPP
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int SN = 4e3 + 10;
const int N = 5e5 + 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 tid,T;
int n,m;
string s,t;
ll w[N],ans;
pair<int,int> mp[30];
ll f[SN][SN],sum[N]; 
void solve7(){
	read(n); read(m);
	cin >> s >> t;
	for(int i=1;i<=n;i++){
		read(w[i]);
	}
	int l = 1, r = n,cnt = 0;
	ll res = 1e18;
	for(int i=1;i<=n;i++){
		sum[i] = sum[i - 1] + w[i];
	}
	for(int i=1;i<=n-m+1;i++){
		int j = i + m - 1; 
		res = min(res,sum[i-1] + sum[n] - sum[j]);
	}
	if(res == 1e18) cout << "-1\n"; 
	else cout << res << "\n";
}
void solve_dp(){
	while(T--){
		read(n); read(m);
		cin >> s >> t;
		s = "#" + s, t = "." + t;
		for(int i=0;i<27;i++){
			mp[i].fi = m + 1;
			mp[i].se = 0;
		}
		for(int i=1;i<=m;i++){
			if(mp[t[i]-'a'].fi == m + 1) mp[t[i]-'a'].fi = i;
			mp[t[i]-'a'].se = i;
		} 
		for(int i=1;i<=n;i++){
			read(w[i]);
		} 
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				f[i][j] = 1e18;
			}
		}
		f[0][0] = 0; 
		for (int i = 1; i <= n; i++) {
            int c = s[i] - 'a';
            if (0 < mp[c].fi || 1 > mp[c].se) {
                if (f[i - 1][0] != 1e18) {
                    f[i][0] = f[i - 1][0] + w[i];
                }
            }
        }
		for(int i=0;i<=n;i++){
			for(int j=0;j<=min(i,m);j++){
				if(s[i+1]==t[j+1]){
					f[i+1][j+1] = min(f[i+1][j+1],f[i][j]);
				}
				if(j < mp[s[i+1]-'a'].fi || j + 1 > mp[s[i+1]-'a'].se)
					f[i+1][j] = min(f[i+1][j],f[i][j] + w[i+1]);
			}
		} 
		if(f[n][m]==1e18) cout << "-1\n"; 
		else cout << f[n][m] << "\n";
	}
}
int main(){
	freopen("letter.in","r",stdin);
	freopen("letter.out","w",stdout);
	read(tid); read(T);
	if(tid==7){
		while(T--) solve7();
		return 0;
	}
	solve_dp();
	return 0;
}

T4

题意

给定 n×mn\times m 的网格，每个格子上有个字符 U/D/R/LU/D/R/L，表示在这个格子不能走向那个方向的格子。 给定 qq 次询问，问从 a,ba,b 到 c,dc,d 的所有路径上的点的个数。

sub1,2

注意到给的限制很难搞，但是形成了有向无向关系，想到了缩点成 DAGDAG，一个缩点内部的点能互相到达。
从 a,ba,b 跑缩出来的图，能到达的点打上标记；建反图，从 c,dc,d 再跑一遍，如果说一个点能从起点跑到和从终点反向跑到，那他就是路径上的点。
遍历每个点建图，tarjantarjan 缩点后在 DAGDAG 上遍历。
复杂度 O(Q×n×m)O(Q\times n\times m)。
CPP
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N = 3e3+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 dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int mp[N][N],id[N][N],idx;
unordered_map<int,unordered_map<int,bool> > p; 
int tid,n,m,q,cnt;
pair<int,int> E[N*N];
vector<int> e[N*N],ne[N*N];
inline void chk(int x,int y){
	for(int i=0;i<4;i++){
		if(i == mp[x][y]) continue;
		int xx = x + dx[i], yy = y + dy[i];
		if(xx < 1 || xx > n || yy < 1 || yy > m||p[id[x][y]][id[xx][yy]]||p[id[xx][yy]][id[x][y]]) continue; 
		e[id[x][y]].push_back(id[xx][yy]); 
		p[id[x][y]][id[xx][yy]] = true;
		if(abs(mp[xx][yy]-i)!=2){
			e[id[xx][yy]].push_back(id[x][y]);
			p[id[xx][yy]][id[x][y]] = true;
		}
		else{
			E[++cnt] = {id[x][y],id[xx][yy]};
		}
	}
}
int dfn[N*N],low[N*N],tim,stk[N*N],scc[N*N],tot,top,siz[N*N]; 
//vector<int> h[N*N];
void tarjan(int u){
//	cerr << "?";
	dfn[u] = low[u] = ++tim; stk[++top] = u;
	for(auto x : e[u]){
		if(!dfn[x]){
			tarjan(x);
			low[u] = min(low[u],low[x]); 
		}
		else if(!scc[x]) low[u] = min(low[u],dfn[x]);
	} 
	if(dfn[u] == low[u]){
		tot++;
		while(1){
			int v = stk[top--];
			scc[v] = tot;
			siz[tot]++;
//			h[tot].push_back(v);
			if(u == v) break;
		}
	}
}
bool vis[N*N],is[N*N];
void dfs1(int u){
	if(vis[u]) return;
	vis[u] = true;
	for(auto x : e[u]){
		dfs1(x);
	}	
}
void dfs2(int u){
	if(is[u]) return;  
	is[u] = true;
	for(auto x : ne[u]){
		dfs2(x);
	}
}
int main(){
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	read(tid); read(n); read(m); read(q);
	char ch;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> ch;
			id[i][j] = ++idx;
			if(ch=='U') mp[i][j] = 0;
			if(ch=='R') mp[i][j] = 1;
			if(ch=='D') mp[i][j] = 2;
			if(ch=='L') mp[i][j] = 3; 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			chk(i,j);
		}
	}
	for(int i=1;i<=idx;i++){
		if(!dfn[i]) tarjan(i);
	}
//	cerr << "\n";
	for(int i=1;i<=idx;i++) e[i].clear();
	for(int i=1;i<=cnt;i++){
		int u = E[i].fi, v = E[i].se;
		if(scc[u]!=scc[v]){
//			cerr << u << " " << v  << "u->v\n";
//			cerr << scc[u] << " " << scc[v] <<"scc\n";
			e[scc[u]].push_back(scc[v]);
			ne[scc[v]].push_back(scc[u]);
		} 
	}
//	for(int i=1;i<=tot;i++){
//		cerr << i <<":";
//		for(auto x : h[i]){
//			cerr << x << " ";
//		}
//		cerr << "\n";
//	} 
//	cerr << "_____\n";
	int a,b,c,d;
	while(q--){
		read(a); read(b); read(c); read(d);
		dfs1(scc[id[a][b]]);
//		for(int i=1;i<=tot;i++){
//			cerr << vis[i] << " ";
//		} 
//		cerr << "dfs1\n";
		dfs2(scc[id[c][d]]);
		ll res = 0;
		for(int i=1;i<=tot;i++){
			if(vis[i] && is[i]) res+=siz[i];
//			cerr << is[i] << " ";
		}
//		cerr << "dfs2\n";
		if(vis[scc[id[c][d]]] && is[scc[id[c][d]]]) cout << res << "\n"; 
		else cout << "-1\n";
		for(int i=1;i<=tot;i++){
			vis[i] = is[i] = false;
		}
	}
	return 0;
}

评论

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

正在加载评论...