专栏文章

10.23 高中模拟3

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

文章操作

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

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

T1

题意

给定 mm 个关系形如 p−>q,rp->q,r，表示在 [l,r][l,r] 中，如果[l,k][l,k] 满足 qq，[k+1,r][k+1,r] 满足 rr，则 [l,r][l,r] 满足 pp。问 [1,n][1,n] 最后满足几种句法，特别的规定长度为一的序列 xx 满足 xx。

做法

不难发现大区间只会被小区间所影响，区间DP。转移和初始化题目已告诉，设 f(l,r,p)f(l,r,p) 表示 [l,r][l,r] 是否满足 pp，枚举中断点 kk，枚举 mm 种句法匹配，时间复杂度 O(n3m)O(n^3m)。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 110;
const int M = 310;
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;
int a[N];
struct node{
	int p,q,r; 
}z[M];
bool vis[N][N]; 
bool f[N][N][M];
//f[l][r][p] 表示 [l,r] 中是否满足语法 p
//时间复杂度 O(n^3m) 空间 O(n^2m) 
void dfs(int l,int r){
	if(vis[l][r]) return;
	vis[l][r] = true;
	for(int k=l;k<r;k++){
		dfs(l,k); dfs(k+1,r);
		for(int i=1;i<=m;i++){
			int ps = z[i].p , qs = z[i].q, rs = z[i].r;
			if(f[l][r][ps]) continue;
			if(f[l][k][qs] && f[k+1][r][rs]) f[l][r][ps] = true;
		}
	}
}
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	read(m);
	for(int i=1;i<=m;i++){
		read(z[i].p); read(z[i].q); read(z[i].r);
	}
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i]);
		f[i][i][a[i]] = true;
		vis[i][i] = true;
	}
	dfs(1,n);
	bool flag = false;
	for(int i=1;i<=m;i++){
		if(f[1][n][i]){
			flag = true;
			cout << i << " ";
		} 
	}
	if(!flag) cout << "-1";
	return 0;
}

T2

题意

树上第 kk 大菊花？ 给定一颗无根树，要求菊花是以一个点为中心，出度至少为 33 的图，问树上前 kk 大菊花权值绝对值的异或和。

思路

这是一道很好的关于选前 kk 大的题，首先暴力求出每一朵菊花肯定是没有前途的。
先考虑一棵菊花的情况，设我们要求的菊花有 mm 条出边，权值最大的菊花，一定是与它相连的节点按权值排完序后，选最前面的 mm 个。那我们能不能快速求出前 kk 大的来呢，兄弟可以的。
使用多指针+堆来干这件事，我们维护最后的指针 p1p_1 和倒数第二个指针 p2p_2，此时我们有两种选择：
  1. 继续移动 p1p_1。
  2. 将 p1p_1 固定看作边界，p2p2 变为 p1p_1 移动，p3p_3 变为 p2p_2。
将移动的不同情况和权值扔到堆里去维护，每次取最大的更新，这样我们就能保证选出前 kk 个一定是前 kk 大，且没有重复。
为什么呢？考虑画图证： 注意到每次更新的状态总是小于前驱状态。有人说万一 adeade 大于 abfabf，但是 abfabf 先被处理怎么办？如果 ade>abfade>abf，因为 adeade 小于它的前驱状态 aceace，所以 ace>abface>abf，所以 aceace 一定比 abfabf 先处理，从而让 adeade 也在堆中。

实现

所以我们开一个堆维护每种菊花，只需要记录一下 p1p_1，p2p_2 的位置，移动时更新权值。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 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,k;
ll ans,a[N]; 
vector<int> e[N];
struct node{
	int id,l,r,lst;
	ll sum;
};
bool operator<(const node &a,const node &b){
	return a.sum < b.sum;
}
bool cmp(const int &x,const int &y){
	return a[x] > a[y];
}
priority_queue<node> Q; 
int main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	read(n); read(k);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	int u,v;
	for(int i=1;i<n;i++){
		read(u); read(v);
		e[u].push_back(v);
		e[v].push_back(u);
	} 
	for(int i=1;i<=n;i++){
		if(e[i].size() < 3) continue;
		sort(e[i].begin(),e[i].end(),cmp);
		ll res = a[i] + a[e[i][0]] + a[e[i][1]];
		for(int j=2;j<int(e[i].size());j++){
			res += a[e[i][j]];
			Q.push({i,j-1,j,int(e[i].size()),res});
		} 
	}
	while(k--){
		auto x = Q.top(); Q.pop();
		int id = x.id , l = x.l , r = x.r, lst = x.lst;
		ll sum = x.sum;
		ans ^= abs(sum);
		if(x.r + 1 < x.lst) Q.push({id,l,r+1,lst,sum - a[e[id][r]] + a[e[id][r+1]]});
		if(x.l >= 0 && x.l + 1 < x.r) Q.push({id,l-1,l+1,r,sum - a[e[id][l]] + a[e[id][l+1]]});
	}
	cout << ans;
	return 0;
}

T3

题意

给你一颗基环树，要求你将点集分别划分成 k=1−nk=1-n 个集合。定义分歧边为：
  • 边 (x,y)(x,y) 上的符号是 ++,但 px!=pyp_x != p_y。
  • 边 (x,y)(x,y) 上的符号是 −-,但 px=pyp_x = p_y。
其中 pip_i 表示 ii 所属的集合。
你需要通过适当的划分，最小化 k=1−nk=1-n 的分歧边数量。

思路

首先可以倒着考虑，分连通块变为合并连通块。
我们发现最后的答案就是 ++ 号的数量。我们要最小化分歧边数量，就要先连 ++ 边，迫不得已连 −- 边。
但这是一颗基环树，当连接了环上 s−1s-1 条边时最后一条已经自动连通了，也就是说倒数第二条边连接时一定会有额外的代价：
  • 如果最后一条边是 +，那么在合并倒数第二条边时代价额外减小 11；
  • 如果最后一条边是 -，那么在合并倒数第二条边时代价额外增加 11。
根据贪心，+ 一定在 - 之前被选中合并其端点。因此第一种情况出现的唯一可能是整个环都是 +，这种情况下我们应当优先把环上的边的端点所在集合合并。 否则环上存在 -，一定对应第二种情况，这时：
  • 如果环上仅有一条 - 边，那么倒数第二条边一定是 +，则合并倒数第二条边时代价变化是 +1−1=0+1-1=0，所以应当把倒数第二条边留着，先把挂着的数上的 + 合并完之后再合倒数第二条边，最后把树上的 - 边合并；
  • 如果环上有多于一条 - 边，那么优先把环上及树上的 + 边端点合并，然后优先把挂着的树上的 - 边端点合并，最后再把环上的 - 边端点合并。

实现

我们按照如下顺序把边的端点合并到一个集合，就得到了各个 kk 的最优解：
  • 如果环上 - 边数量 ≠1\neq 1，则：环上的 + 边；树上的 + 边；树上的 - 边；环上的 - 边。
  • 如果环上 - 边数量 =1=1，则：树上的 + 边；环上的 + 边；树上的 - 边。
并查集+dfs找环，如果一条边两端在已在同一连通块中，说明它是环上的边，这个环就是树上 s−>ts->t 和 (s,t)(s,t)。
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 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;
vector<int> e[N];
int f[N];
int cnt,c0,c1,s,t;
int find(int x){
	if(f[x] != x) f[x] = find(f[x]);
	return f[x];
}
int a[N],cc,ans[N];
bool flag;
void dfs(int u,int fa,int l){
//	cerr << u <<"u\n";
	a[l] = u;
	if(u == t){
		flag = true;
		cc = l;
		return;
	}
	for(auto x : e[u]){
		if(x == fa) continue;
		dfs(x,u,l+1);
		if(flag) return;
	}
}
map<int,map<int,int> > mp;
int main(){
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	read(n);
	int u,v,w;
	char ch;
	for(int i=1;i<=n;i++){
		f[i] = i;
	} 
	for(int i=1;i<=n;i++){
		read(u); read(v); cin >> ch; 
		if(ch=='+') w = 1,c1++;
		else w = 0,c0++;
		e[u].push_back(v);
		e[v].push_back(u);
		mp[u][v] = mp[v][u] = w; 
		int fu = find(u), fv = find(v);
		if(fu == fv) s = u, t = v;
		else f[fv] = fu;
	}
//	cerr << s << " " << t << "st\n";
	dfs(s,0,1);
	if(mp[s][t]==0) cnt++;
	for(int i=1;i<cc;i++){
//		cerr << a[i] << " ";
		if(mp[a[i]][a[i+1]]==0) cnt++;
	}
	int res = c1;
	ans[n] = c1;
	if(cnt == 0){
		for(int i=n-1;i;i--){
			if(c1){
				c1--; res--; cc--;
				if(cc == 1) res--,c1--,cc--; 
			}
			else{
				c0--; res++; 
			}
			ans[i] = res;
		}
	}
	else if(cnt == 1){
		for(int i=n-1;i;i--){
			if(c1){
				c1--; res--;
				if(!c1) res++,c0--;
			}
			else c0--,res++;
			ans[i] = res;
		}
	}
	else{
		for(int i=n-1;i;i--){
			if(c1){
				c1--; res--;
			}
			else{
				c0--; res++;
				if(c0==1){
					c0--; res++; 
				}
			}
			ans[i] = res; 
		}
	}
	for(int i=1;i<=n;i++){
		cout << ans[i] << "\n";
	}
	return 0;
}

T4

题意

给定无向完全图，定义权值 val(i,j)=ai⊕aj⊕wlcp(si,sj)val(i,j)=a_i\oplus a_j\oplus w_{lcp(s_i,s_j)} 求 ∑i=1nmin⁡1<=j<=n，j!=ival(i,j)\sum_{i=1}^{n}\min_{1<=j<=n，j!=i} val(i,j)

暴力

O(n2)O(n^2) 枚举点对，查询 lca 求 lcp，取 min⁡\min 统计。

sub2

ww 相等表示边权与两个字符串的lcp无关，式子简化为一个点对 nn 个点的最小异或和 ，将 aia_i 插入 01trie，贪心查询并且每一次删除和自己相等的 aa 值。
CPP
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 3e5 + 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,k;
ll w[N],a[N],p[N];
int fa[N],son[N],deep[N],siz[N],top[N];
vector<int> e[N];
void dfs1(int u){
	deep[u] = deep[fa[u]] + 1; siz[u] = 1;
	for(auto x : e[u]){
		if(x == fa[u]) continue;
		fa[x] = u;
		dfs1(x);
		siz[u] += siz[x];
		if(!son[u]||siz[son[u]] < siz[x]) son[u] = x;
	}
} 
void dfs2(int u,int topx){
	top[u] = topx;
	if(son[u]) dfs2(son[u],topx);
	for(auto x : e[u]){
		if(x == fa[u] || x == son[u]) continue;
		dfs2(x,x);
	}
}
inline int lca(int x,int y){
	while(top[x] != top[y]){
		if(deep[top[x]] < deep[top[y]]) swap(x,y);
		x = fa[top[x]];
	}
	return deep[x] < deep[y] ? x : y;
}
inline int lcp(int x,int y){
	return deep[lca(p[x],p[y])]-1;
}
struct node{
	int siz;
	int ch[2];
}trie[N*31];
int idx;
inline void insert(int x,int v){
	int pos = 0;
	for(int i=31;i>=0;i--){
		bool now = (x & (1 << i));
		if(!trie[pos].ch[now]){
			trie[pos].ch[now] = ++idx;
		}
		pos = trie[pos].ch[now];
		trie[pos].siz += v;
	}
} 
inline ll query(int x){
	int pos = 0; ll res = 0;
	for(int i=31;i>=0;i--){
		bool now = (x & (1 << i));
		if(trie[pos].ch[now] && trie[trie[pos].ch[now]].siz) pos = trie[pos].ch[now];
		else if(trie[pos].ch[!now] && trie[trie[pos].ch[!now]].siz){
			pos = trie[pos].ch[!now];
			res |= (1 << i);
		} 
	}
	return res;
}
int main(){
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
	bool f = false;
	read(n); read(m); read(k);
	for(int i=0;i<=m;i++){
		read(w[i]);
		if(i&&w[i]!=w[i-1]) f = true; 
	}
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	int u,v; char ch; 
	for(int i=1;i<k;i++){
		read(u); read(v); cin >> ch;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1); dfs2(1,1);
	for(int i=1;i<=n;i++){
		read(p[i]);
	}
	if(!f){
		for(int i=1;i<=n;i++) insert(a[i],1);
		ll ans = 0; 
		for(int i=1;i<=n;i++){
			insert(a[i],-1);
			ans += query(a[i] ^ w[0]);
			insert(a[i],1);
		}
		cout << ans;
		return 0;
	} 
	if(n <= 1000 && m <= 100){
		ll ans = 0; 
		for(int i=1;i<=n;i++){//暴力复杂度 O(n^2logm) 
			ll minn = LLONG_MAX; 
			for(int j=1;j<=n;j++){
				if(i == j) continue;
				ll val = a[i] ^ a[j] ^ (w[lcp(i,j)]);
				minn = min(minn,val);
			}
			ans += minn;
		}
		cout << ans;
		return 0;
	}
	cout << "0\n";
	return 0;
}

评论

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

正在加载评论...