【考试总结】小奇模拟赛

\(T1\)

题目描述

给定一棵 \(n\) 个节点的树,求前 \(m\) 条最长路径的长度。

数据范围

序号 \(n\) \(m\) 数据类型
1 10 3 暴力
2 233 23333 暴力
3 2000 300000 暴力
4 2000 300000 暴力
5 50000 1 随机生成
6 7798 17798 随机生成
7 7798 27798 随机生成
8 7798 37798 随机生成
9 50000 300000 1-n 顺序输入的链
10 50000 300000 以 1 为根的菊花图

\(Solution\)

估分:\(70\)

实测:\(40\)

因为写链时脑子抽了居然用了 \(map\) 然后空间炸了,还有判断是否是链那里写错了一点导致第一个点还挂了。。。

对于链:先把 \(1-i(i <= n)\) 的所有链加入堆,然后取出最大的输出,再把这条链删掉上面那条边,扔进堆里

对于菊花图:把每条边排个序,可以构造一个矩形,矩形的 \((x, y)\) 代表的是 \(d[x] + d[y]\) ,\(d[i]\) 是 \(i\) 到 \(1\) 的边权,先把第一行全部扔进堆里,取最大的输出,再把 \((x + 1, y)\) 上的值扔进去

对于暴力:枚举每条链,用 \(LCA\) 维护链的长度

正解:点分治,把每棵子树做超级钢琴的做法,用 \(st\) 表或者线段树维护

\(Code\)

不知道如何下手...照着网上的一篇题解打的

#include<bits/stdc++.h>
#define F(i, x, y) for(int i = x; i <= y; ++i)
using namespace std;
int read();
const int N = 5e4 + 5;
int n, m;
int sum, root, mx, id, l, r;
int head[N], cnt, ver[N << 1], edge[N << 1], nxt[N << 1];
int st[N * 20][21], d[N * 20], size[N], vis[N], dis[N];
struct node{
    int l, r;
}p[N * 20];
struct use{
    int l, r, h, mq;
};
priority_queue<use> q;
bool operator<(use a,use b)
{
    return d[a.h] + d[a.mq] < d[b.h] + d[b.mq];
}
void add(int x, int y, int z)
{
	ver[++ cnt] = y, edge[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;
}
void get_root(int x, int fa)
{
	size[x] = 1; int maxn = 0;
	for(int i = head[x]; i; i = nxt[i])
	{
		int y = ver[i];
		if(vis[y] || y == fa) continue;
		get_root(y, x), size[x] += size[y], maxn = max(maxn, size[y]);
	}
	maxn = max(maxn, sum - size[x]);
	if(maxn < mx) mx = maxn, root = x;
}
void dfs(int x, int fa)
{
	d[++ id] = dis[x], p[id] = {l, r};
	for(int i = head[x]; i; i = nxt[i])
	    if(! vis[ver[i]] && ver[i] != fa)
	    	dis[ver[i]] = dis[x] + edge[i], dfs(ver[i], x);
}
void solve(int x)
{
	vis[x] = 1, d[++ id] = 0, p[id] = {0, 0}, l = r = id;
	for(int i = head[x]; i; i = nxt[i])
	    if(! vis[ver[i]])
	    	dis[ver[i]] = edge[i], dfs(ver[i], x), r = id;
	for(int i = head[x]; i; i = nxt[i])
	    if(! vis[ver[i]])
	        root = 0, sum = size[ver[i]], mx = INT_MAX, get_root(ver[i], 0), solve(root);
}
int query(int l, int r)
{
	int k = log2(r - l + 1);
	return d[st[l][k]] > d[st[r - (1 << k) + 1][k]] ? st[l][k] : st[r - (1 << k) + 1][k];
}
void pre()
{
	F(i, 1, id) st[i][0] = i;
	F(j, 1, 20)
        F(i, 1, id - (1 << j) + 1)
            if(d[st[i][j - 1]] > d[st[i + (1 << j - 1)][j - 1]]) st[i][j] = st[i][j - 1];
            else st[i][j] = st[i + (1 << j - 1)][j - 1];
    F(i, 1, id)
        if(p[i].l) q.push(use{p[i].l, p[i].r, i, query(p[i].l, p[i].r)});
}
int main()
{
    n = read(), m = read();
    for(int i = 1, x, y, z; i < n; ++ i) x = read(), y = read(), z = read(), add(x, y, z), add(y, x, z);
    sum = n, mx = INT_MAX, get_root(1, 0), solve(root), pre();
    F(i, 1, m)
    {
    	use k = q.top(); q.pop(), printf("%d\n", d[k.mq] + d[k.h]);
    	if(k.mq - k.l) q.push(use{k.l, k.mq - 1, k.h, query(k.l, k.mq - 1)});
    	if(k.r - k.mq) q.push(use{k.mq + 1, k.r, k.h, query(k.mq + 1, k.r)});
	}
	return 0;
}
int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

\(T3\)

题目描述

星球上有 \(n\) 个城市,标号为 \(1-n\),用 \(n-1\) 条双向通道连接,保证任意两个城市能互相到达。
生化危机爆发了!但由于*安全能力有限,安全区只包括在标号 \(l\) 到 \(r\) 的城市,你现在在城市 \(x\),想知道最近的安全城市的距离。

数据范围

对于 \(30\%\) 的数据, \(n,q<=1000\);
另有 \(20\%\) 的数据,保证第城市 \(2-n\) 均可直接到达城市 \(1\);
另有 \(10\%\) 的数据,保证城市 i(1<=i<=n-1)可直接到达城市 \(i+1\);
对于 \(100\%\) 的数据, \(n,q<=100000\),\(li<=ri\),任意两个城市的距离小于 \(10^9\)。

\(Solution\)

估分:\(60\)

实测:\(60\)

对于链:如果在 \([l \ ,\ r]\) 里输出 \(0\),不在则取 \(min(d[x][l] \ , \ d[x][r])\),\(d[i][j]\) 表示 \(i \ , \ j\) 之间距离

对于菊花图:用 \(st\) 表维护 \(l-r\) 的每个点到 \(1\) 的路径的 \(min\) 值,分情况讨论即可

对于其他:直接 \(dfs\) ,加个剪枝,当当前距离大于 \(ans\) 时返回,可以水过此题

正解:要用到点分治还是点分树来着,我分不太清这两个,大概就是,拆成很多个子树,在每个子树上都做一个动态加点线段树,维护此子树里在 \(l-r\) 中的点到子树根的最小值,用此最小值加上子树根到 \(x\) 的值,更新 \(ans\),然后再往上跳,找新的子树根

\(Code\)

(正解只存在于口胡233

#include<bits/stdc++.h>
#define ll long long
#define F(i, x, y) for(int i = x; i <= y; ++i)
using namespace std;
ll read();
const int N = 1e6 + 5;
const int M = N << 1;
const ll inf = 1e18 + 5;
int n, q, flag;
ll x, y, z, l, r, ans;
ll head[N], cnt, ver[M], nxt[M];
ll edge[M], d[N], st[N][22], ok[N];
void add(ll x, ll y, ll z)
{
	ver[++ cnt] = y, edge[cnt] = z, nxt[cnt] = head[x], head[x] = cnt;
}
void dfs1(int x, int fa)
{
	for(int i = head[x]; i; i = nxt[i])
	    if(ver[i] != fa)
	        d[ver[i]] = d[x] + edge[i], dfs1(ver[i], x);
}
void solve_1()// 链 
{
	dfs1(1, 0);
	while(q --)
	{
		l = read(), r = read(), x = read();
		if(x < l) printf("%lld\n", d[l] - d[x]);
		else if(x > r) printf("%lld\n", d[x] - d[r]);
		else puts("0");
	}
	exit(0);
}
void solve_2()// 菊花图 
{
	F(i, 2, n) st[i][0] = edge[head[i]];
	F(j, 1, 20)
	    for(int i = 1; i + (1 << j) - 1 <= n; ++ i)
   		    st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
    while(q --)
    {
    	l = read(), r = read(), x = read();
    	int k = log2(r - l + 1); 
    	if(x <= r && x >= l) puts("0");// 如果 x 安全,则输出 0 
    	else if(l == 1) printf("%lld\n", edge[head[x]]);// 如果 1 安全,直接输出到 1 的距离 
		else if(x == 1) printf("%lld\n", min(st[l][k], st[r - (1 << k) + 1][k]));// 如果要求的是 1,则直接找一个最小值 
    	else printf("%lld\n", edge[head[x]] + min(st[l][k], st[r - (1 << k) + 1][k]));// 剩余情况 
	}
	exit(0);
}
void dfs3(ll x, ll fa, ll dis)
{
	if(dis >= ans) return;
	if(x >= l && x <= r)
	{
		ans = min(ans, dis); 
		return;
	}
	for(int i = head[x]; i; i = nxt[i])
	    if(ver[i] != fa)
	    	dfs3(ver[i], x, dis + edge[i]);
}
void solve_3()// 其他
{
	while(q --)
	{
		l = read(), r = read(), x = read();
		ans = inf, dfs3(x, 0, 0);
		printf("%lld\n", ans);
	}
} 
int main()
{
    n = read();
    F(i, 1, n - 1)
	{
		x = read(), y = read(), z = read(), add(x, y, z), add(y, x, z);
		if(abs(x - y) > 1) flag = 1;
	}
	q = read();
	if(! flag) solve_1();
	F(i, 2, n) if(ver[head[i]] != 1) flag = 0;
	if(flag) solve_2();
	solve_3(); 
	return 0;
}
ll read()
{
	ll x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9'){ if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}
上一篇:#0015. 区间因子和


下一篇:Balanced Number 数位dp