2023.09.26 联考总结&题解

T1 derby

你考虑直接贪心进行匹配即可，就是说对于每一个 \(1\) 去匹配最大的 \(0\)

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> A[2],B[2];

int main(){
	freopen("derby.in","r",stdin);
	freopen("derby.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i = 1,x,y; i <= n; ++i){
		scanf("%d%d",&x,&y);A[x].push_back(y);
	}
	for(int j = 1,x,y; j <= m; ++j){
		scanf("%d%d",&x,&y);B[x].push_back(y);
	}
	
	sort(A[0].begin(),A[0].end(),greater<int>());
	sort(A[1].begin(),A[1].end(),greater<int>());
	sort(B[0].begin(),B[0].end(),greater<int>());
	sort(B[1].begin(),B[1].end(),greater<int>());
	
	long long ans = 0;
	
	for(int i = 0,j = 0; i < A[0].size() && j < B[1].size();){
		while(A[0][i] >= B[1][j] && i < A[0].size()) ++i;
		if(i < A[0].size() && A[0][i] < B[1][j]) ans += A[0][i++] + B[1][j++];
	}
	for(int i = 0,j = 0; i < A[1].size() && j < B[0].size();){
		while(A[1][i] <= B[0][j] && j < B[0].size()) ++j;
		if(j < B[0].size() && A[1][i] > B[0][j]) ans += A[1][i++] + B[0][j++];
	}
	printf("%lld",ans);
} 

T2 tree

考虑我们可以启发式合并，就是开一个桶和一个 vector （当然我不知道为什么用了 set），然后做启发式合并

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 1e6 + 8,MOD = 1e9 + 7; 

int n,k;
int a[NN];

int pos[NN];
set<int> s[NN];

ll ansa,ansb;

struct Edge{
	int to,next;
}edge[NN];
int head[NN],cnt;
void init(){
	for(int i = 1; i <= n; ++i) head[i] = -1,pos[i] = i;
	cnt = ansa = ansb = 1;
}
void add_edge(int u,int v){
	edge[++cnt] = {v,head[u]};
	head[u] = cnt;
}

int siz[NN],son[NN];
void dfs(int u){
	siz[u] = 1;
	for(int i = head[u]; i != -1; i = edge[i].next){
		int v = edge[i].to;
		dfs(v);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]]) son[u] = v;
	}
	
	for(int i = head[u]; i != -1; i = edge[i].next){
		int v = edge[i].to;
		if(v == son[u]) continue;
		for(auto i : s[pos[v]]){
			s[pos[son[u]]].insert(i);
		}
	}
	if(son[u]) swap(pos[u],pos[son[u]]);
	s[pos[u]].insert(a[u]);
	ll resa = s[pos[u]].size(),resb = siz[u];
	if(ansa * resb > resa * ansb) ansa = resa,ansb = resb;
	return;
}

ll ksm(ll x,ll k){
	ll res = 1;
	while(k){
		if(k&1) res = res * x % MOD;
		x = x * x % MOD;
		k >>= 1; 
	}
	return res;
}

int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	scanf("%d%d",&n,&k);init();
	for(int i = 1; i <= n; ++i) scanf("%d",&a[i]);
	for(int i = 2,u; i <= n; ++i) scanf("%d",&u),add_edge(u,i);
	dfs(1);
	printf("%lld",ansa * ksm(ansb,MOD-2) % MOD);
}
/*
11 4
1 2 1 3 2 4 2 4 3 3 4
1 1 1 2 2 3 3 3 8 8
*/

T3 walpurgis

对于询问，反建 Trie 树。

我们可以发现，插入操作相当于进行一个矩形加，我们可以做一个二维差分来解决

然后就是一个二维数点，离线+扫描线即可

code:（不知道为什么其他人最后一个点都过了，就我没过，关键是我的 sub5 比他们优秀，自闭了……）

#include<bits/stdc++.h>
using namespace std;
const int NN = 4e5 + 8;
typedef long long ll;

#define st first
#define ed second

int n,m;



struct Node{
	int x,y,w;
}node[NN];

struct Query{
	ll l,r;
	ll num;
};
vector<Query> q[NN * 63];

struct QUERY{
	ll x, y,num;
	bool operator < (const QUERY &A) const{
		return x < A.x;
	}
}que[NN];

struct Trie{
	struct ND{
		int son[2];
		int val,siz;
	}tree[NN * 63];
	#define son(i,j) tree[i].son[j]
	#define val(i) tree[i].val
	#define siz(i) tree[i].siz
	int cnt;
	void ins(ll x){
		if(cnt == 0) cnt = 1;
		int now = 1;
		while(x){
			if(son(now,x&1) == 0) son(now,x&1) = ++cnt;
			now = son(now,x&1);
			x >>= 1;
		}
	}
	int dfn;
	int dfs(int now){
		siz(now) = 1;
		val(now) = ++dfn;
		if(son(now,0)) siz(now) += dfs(son(now,0));
		if(son(now,1)) siz(now) += dfs(son(now,1));
		return siz(now);
	}
	int query(ll x){
		int now = 1;
		while(x){
			now = son(now,x&1);
			x >>= 1;
		}
		return val(now);
	}
	pair<int,int> get(ll x){
		int now = 1;
		while(x != 1){
			now = son(now,x&1);
			x >>= 1;
		}
		if(now != 0 && siz(now) > 1) return {val(now)+1,val(now)+siz(now)-1};
		else return {-1,-1};
	}
}Tx,Ty;


ll a[NN * 63];
ll ans[NN];
inline ll lowbit(ll x){return x & (-x);}
void add(int x,ll w){
	while(x <= Ty.cnt){
		a[x] += w;
		x += lowbit(x);
	}
}
ll ask(int x){
	ll res = 0;
	while(x > 0){
		res += a[x];
		x -= lowbit(x);
	}
	return res;
}

inline ll read(){
	register int res = 0;
	register char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) res = res * 10 + c - '0',c = getchar();
	return res;
} 

int main(){
	freopen("walpurgis.in","r",stdin);
	freopen("walpurgis.out","w",stdout);
	int sbt = read();
	n = read();m = read();
	for(ll i = 1; i <= n; ++i){
		node[i] = {read(),read(),read()};
	}
	
	for(ll i = 1,x,y; i <= m; ++i){
		que[i] = {read(),read()};
		Tx.ins(que[i].x);Ty.ins(que[i].y);que[i].num = i;
	}
	Tx.dfs(1);Ty.dfs(1);
	for(ll i = 1; i <= m; ++i) que[i] = {Tx.query(que[i].x),Ty.query(que[i].y),que[i].num};
	sort(que+1,que+1+m);
	
	for(int i = 1; i <= n; ++i){
		pair<int,int> mx = Tx.get(node[i].x),my = Ty.get(node[i].y);
		if(mx.st == -1 || my.st == -1) continue;
		q[mx.st  ].push_back({my.st,my.ed,node[i].w});
		q[mx.ed+1].push_back({my.st,my.ed,-node[i].w});
	}
		
	int now = 1;
	for(int i = 1; i <= Tx.cnt; ++i){
		for(auto j : q[i]){
			add(j.l,j.num);
			add(j.r+1,-j.num);
		}
		while(que[now].x == i && now <= m) ans[que[now].num] = ask(que[now].y),++now;
	}
	for(int i = 1; i <= m; ++i) printf("%lld\n",ans[i]);
}
/*
1
5 1
1 2 1
3 4 2
4 5 3
6 3 4
7 1 5
7 8
*/

T4 winter

观察可得，结构一定是确定一个点 \(x\) 作为根，并且对于的儿子 ，其子树要么全部叶向，要么全部根向。

考虑一个浅浅的证明：

• 考虑边的状态让这棵树有了两个上面描述的根，两个根之间的路径上一些边指向第一个根，另一些边指向第二个根。
  发现若这条路径边的方向改为相同，答案会更优，所以就将这两个中心合并为一个

• 若存在多个根，合并为一个会更优。
  因为根的各个子树的外向点权和和内向点权和会乘起来贡献给答案，所以根选取树的带权重心可以更好的分配外向内向的子树大小。

确定了根之后，我们相当于就是对于一些点把它们划分成两个集合，满足两个集合乘积最大，由于度数
\(\leq 36\)，直接 折半搜索+双指针 即可

笑，不想写了