2023“钉耙编程”中国大学生算法设计超级联赛（1）

189 0 0

作者:scoxty

1001 Hide-And-Seek Game

题意:

给出一颗树，两人在树上特定两点来回走，问最早在那个节点相遇。

分析：

两条路径相交，则一条路径的LCA一定在另一条路径上。我们可以预处理一个dfs时间戳，结合LCA来判断路径相交。
由于本题的点数较小,所以我们可以枚举相交链上的每一个点，然后计算他们在这个点最早相遇的时间，找到其中相遇时间最早的点作为答案输出。
对于相交链上的一个点x,我们可以计算出A到达x的时间满足2k1 · dis(Sa, Ta) + dis(Sa,x)或者2k1. dis(Sa,Ta) + dis(Sa,Ta) + dis(Ta,x)。(其中k为任意正整数)
类似的，B到达x的时间满足2k2 · dis(Sb, Tb) + dis(Sb,x)或者2k2 · dis(Sb, Tb) + dis(Sb, Tb) + dis(Tb, x)。然后两两联立成4个二元一次同余方程，使用拓展欧几里得算法求解最小正整数解即可。注意负数的处理。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 3e4 + 5, M = 6e4 + 5;
int h[N], e[M], ne[M], idx;
int depth[N], f[N][20], fa[N], mark[N], dfn[M], low[M], timestamp;
struct Point
{
	int a, b;
}Data[N][2];
int sum_t, ans_ver;

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int pa)
{
	dfn[u] = ++ timestamp;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		
		if (j == pa)
			continue;
			
		fa[j] = u;	
			
		dfs(j, u);
	}
	low[u] = timestamp;
}

void bfs(int u)
{
	memset(depth, 0x3f, sizeof depth);
	queue<int> q;
	q.push(u);
	depth[0] = 0, depth[u] = 1;
	
	while (q.size())
	{
		int t = q.front();
		q.pop();
		
		for (int i = h[t]; i != -1; i = ne[i])
		{
			int j = e[i];
			
			if (depth[j] > depth[t] + 1)
			{
				depth[j] = depth[t] + 1;
				f[j][0] = t;
				q.push(j);
				
				for (int k = 1; k <= 13; k ++)
					f[j][k] = f[f[j][k - 1]][k - 1];
			}
		}
	}
}

int lca(int a, int b)
{
	if (depth[a] < depth[b])
		swap(a, b);
	
	for (int i = 13; i >= 0; i --)
	{
		if (depth[f[a][i]] >= depth[b])
		{
			a = f[a][i];
		}
	}
	
	if (a == b)
		return a;
	
	for (int i = 13; i >= 0; i --)
	{
		if (f[a][i] != f[b][i])
		{
			a = f[a][i];
			b = f[b][i];
		}
	}
	
	return f[a][0];
}

int exgcd(int a, int b, int &x, int &y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return d;
}

void cal(int u, Point A, Point B)
{
	int a = A.a, b = -B.a, m1 = A.b, m2 = B.b, c = m2 - m1, x, y, d;
	c = (c % B.a + B.a) % B.a; 
	d = exgcd(a, b, x, y);
	if (c % d)
		return;
	a /= d, b /= d, c /= d;
	x *= c, y *= c;
	b = abs(b);
	x = (x % b + b) % b;
	if (x * A.a + m1 < sum_t)
	{
		sum_t = x * A.a + m1;
		ans_ver = u;
	} 
}

bool check(int a, int b)
{
	return dfn[b] <= dfn[a] && dfn[a] <= low[b];
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		memset(h, -1, sizeof h);
		memset(f, 0, sizeof f);
		memset(mark, 0, sizeof mark);
		idx = timestamp = 0;
		
		int n, m;
		cin >> n >> m;
		
		for (int i = 0; i < n - 1; i ++)
		{
			int a, b;
			cin >> a >> b;
			
			add(a, b), add(b, a);
		}
		
		dfs(1, -1);
		bfs(1);
		
		for (int i = 1; i <= m; i ++)
		{
			int sa, ta, sb, tb;
			cin >> sa >> ta >> sb >> tb;
			
			if (sa == sb)
			{
				cout << sa << endl;
				continue;
			}
			
			int la = lca(sa, ta), lb = lca(sb, tb);
			if (depth[la] > depth[lb])
			{
				swap(sa, sb);
				swap(ta, tb);
				swap(la, lb);
			}
			
			if (!check(sa, lb) && !check(ta, lb))
			{
				cout << -1 << endl;
				continue;
			}
			else
			{
				int da = depth[sa] + depth[ta] - 2 * depth[la], db = depth[sb] + depth[tb] - 2 * depth[lb];
				
				int p = sa;
				while (1)
				{
					Data[p][0] = (Point){2 * da, depth[sa] - depth[p]};
					Data[p][1] = (Point){2 * da, 2 * da - (depth[sa] - depth[p])};
					mark[p] = i;
					if (p == la)
						break;
					p = fa[p];
				}
				
				p = ta;
				while (p != la)
				{
					Data[p][0] = (Point){2 * da, da - (depth[ta] - depth[p])};
					Data[p][1] = (Point){2 * da, da + (depth[ta] - depth[p])};
					mark[p] = i;
					p = fa[p];
				}
				
				sum_t = 0x3f3f3f3f;
				ans_ver = -1;
				
				p = sb;
				while (1)
				{
					Point A = (Point){2 * db, depth[sb] - depth[p]};
					Point B = (Point){2 * db, 2 * db - (depth[sb] - depth[p])};
					if (mark[p] == i)
					{
						cal(p, Data[p][0], A), cal(p, Data[p][0], B);
						cal(p, Data[p][1], A), cal(p, Data[p][1], B);
					} 
					if (p == lb)
						break;
					p = fa[p];	
				}
				
				p = tb;
				while (p != lb)
				{
					Point A = (Point){2 * db, db - (depth[tb] - depth[p])};
					Point B = (Point){2 * db, db + (depth[tb] - depth[p])};
					if (mark[p] == i)
					{
						cal(p, Data[p][0], A), cal(p, Data[p][0], B);
						cal(p, Data[p][1], A), cal(p, Data[p][1], B);
					} 
					p = fa[p];
				}
				
				cout << ans_ver << endl;
		 	}	
		}
	}
	
	return 0;
}

1002 City Upgrading

题意：

有一个树状的城市结构，现在需要给一些城市部署路由器，每个路由器覆盖其所在的节点及其相邻节点，问如何以最低成本部署路由器以确保覆盖每个节点？

分析：

树形dp。
定义状态：f[i][j]表示以i为根的子树且状态是j的最小花费。这里j取3，“0，1，2”分别表示在i的父节点放置路由，在i的子节点放置路由，在i处放置路由。
状态转移：
①f[i][0] = (sum_{j})min(f[j][1], f[j][2])
②f[i][2] = (sum_j)min(f[j][0], f[j][1], f[j][2])
③f[i][1] = min(f[j][2] + (sum_k)min(f[k][1], f[k][2])) (k表示除j外的其他子节点)
答案：min(f[root][1], f[root][2])

代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e6 + 5, M = 2e6 + 5;
int h[N], e[M], ne[M], w[N], idx;
LL f[N][3];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int fa)
{
	f[u][2] = w[u];
	
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		
		if (j == fa)
			continue;
			
		dfs(j, u);
			
		f[u][0] += min(f[j][1], f[j][2]);
		f[u][2] += min(min(f[j][0], f[j][1]), f[j][2]);
	}
	
	// 可以借助f[u][0]来算f[u][1] 
	f[u][1] = 2e18;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		f[u][1] = min(f[u][1], f[j][2] + f[u][0] - min(f[j][1], f[j][2]));
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		memset(h, -1, sizeof h);
		memset(f, 0, sizeof f);
		idx = 0;
		
		int n;
		cin >> n;
		
		for (int i = 1; i <= n; i ++)
			cin >> w[i];
			
		for (int i = 0; i < n - 1; i ++)
		{
			int a, b;
			cin >> a >> b;
			
			add(a, b), add(b, a);
		}
		
		dfs(1, -1);
		
		cout << min(f[1][1], f[1][2]) << endl;
	}
	
	return 0;
}

1005 Cyclically Isomorphic

题意：

给出n个字符串s，每个长度均为m，q次询问，每次问能否通过向右右循环移动得到。

分析：

复制一份s得到长度为2m的新串，若两个串能通过循环移动得到，则两者新串的字典序最小的子串应当相同，因此可以hash最小子串，对于每一次询问看hash值是否相同。

代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		
		unordered_map<int, string> mp;
		
		for (int i = 1; i <= n; i ++)
		{
			string s, s2;
			cin >> s;
			
			s2 = s;
			s = s + s;
			
			for (int j = 0; j < m; j ++)
			{
				string s3 = s.substr(j, m);
				if (s2 > s3)
					s2 = s3;
			}
			
			mp[i] = s2;
		}
		
		int q;
		cin >> q;
		
		while (q --)
		{
			int a, b;
			cin >> a >> b;
			
			if (mp[a] == mp[b])
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
		}
	}
	
	return 0;
}

1009 Assertion

题意:

Alice断言：m个物品分成n组，一定存在一组物品一定大于等于d。判断Alice的话对不对。

分析：

抽屉原理，至少有一堆有有(lfloor frac{m-1}{n} rfloor) + 1个物品，判断(lfloor frac{m-1}{n} rfloor) + 1于d的大小关系即可

代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m, d;
		cin >> n >> m >> d;
		
		int res = (m - 1) / n + 1;
		if (res >= d)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	
	return 0;
 }

1010 Easy problem I

题意：

分析：

我们可以用线段树同时维护两个状态: ai >= x部分和ai <= x部分
①ai >= x,直接用线段树维护区间和s1。同时，我们可以维护一个区间最小值判断是否发生状态转移，以及维护一个未发生状态转移的数量。
②ai < x,我们的操作实际上是对现有元素符号取反并加上x。每次操作会将(x_1 - x_2 + x_3 - ... + x_{j-1} - ai)变化为(-x_1 + x_2 - x_3 - ... - x_{j-1} + x_j + a_i) ,这时可以发现ai的数值不发生变化，只有符号改变, x标记可以直接叠加维护，所以也可以通过线段树维护。
根据(x_{j-1}) ≤ (x_j)的性质，发现如果(a_i) < (x_{j-1}), 修改后的|(a_i) - (x_{j-1})|≤ (x_{j-1}) ≤ (x_j), 所以从(a_i) ≥ x转变为(a_i) < x的情况后就不会改变,所以转变总的次数是有限的。
综上，直接将树分为两类，分别通过线段树维护，并在分界点暴力转移状态。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2e6 + 5;
struct Tree
{
	int l, r;
	LL s1, s2; \s1表示状态变化前的和，s2表示状态变化后的和 
	LL minv, cnt, lazy1, lazy2, lazy3; \ lazy1维护状态变化后的符号，lazy2维护状态变化前的变化量，lazy3维护状态变化后的变化量 
}tr[N << 2];
LL w[N];

void pushup(int u)
{
	tr[u].lazy2 = tr[u].lazy3 = 0;
	tr[u].lazy1 = 1;
	tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv);
	tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt; 
	tr[u].s1 = tr[u << 1].s1 + tr[u << 1 | 1].s1;
	tr[u].s2 = tr[u << 1].s2 + tr[u << 1 | 1].s2;
}

void update1(int u, int v)
{
	tr[v].minv -= tr[u].lazy2;
	tr[v].s1 -= tr[v].cnt * tr[u].lazy2;
	tr[v].lazy2 += tr[u].lazy2;
}

void update2(int u, int v)
{
	tr[v].s2 = (tr[v].r - tr[v].l + 1 - tr[v].cnt) * tr[u].lazy3 + tr[u].lazy1 * tr[v].s2;
	tr[v].lazy3 = tr[u].lazy3 + tr[u].lazy1 * tr[v].lazy3;
	tr[v].lazy1 *= tr[u].lazy1;
}

void pushdown(int u)
{	
	if (tr[u].lazy2)
	{
		update1(u, u << 1);
		update1(u, u << 1 | 1);
	} 
	if (tr[u].lazy3)
	{
		update2(u, u << 1);
		update2(u, u << 1 | 1);
	}
	tr[u].lazy2 = tr[u].lazy3 = 0;
	tr[u].lazy1 = 1;
}

void build(int u, int l, int r)
{
	if (l == r)
	{
		tr[u] = {l, r, w[l], 0, w[l], 1, 1, 0, 0};
		return;
	}
	tr[u] = {l, r};
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void motify(int u, int l, int r, LL x)
{
	if (l <= tr[u].l && tr[u].r <= r)
	{
		if (tr[u].minv >= x)
		{
			tr[u].minv -= x;
			tr[u].s1 -= tr[u].cnt * x;
			tr[u].s2 = (tr[u].r - tr[u].l + 1 - tr[u].cnt) * x - tr[u].s2;
			tr[u].lazy2 += x;
			tr[u].lazy3 = x - tr[u].lazy3;
			tr[u].lazy1 *= -1;
		}
		else
		{
			if (tr[u].l == tr[u].r)
			{
				tr[u].s2 = x - tr[u].s1;
				tr[u].cnt = tr[u].s1 = 0;
				tr[u].minv = 2e18;
			}
			else
			{
				pushdown(u);
				int mid = tr[u].l + tr[u].r >> 1;
				if (l <= mid)
					motify(u << 1, l, r, x);
				if (r > mid)
					motify(u << 1 | 1, l, r, x);
				pushup(u);
			}
		}
		return;
	}
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if (l <= mid)
		motify(u << 1, l, r, x);
	if (r > mid)
		motify(u << 1 | 1, l, r, x);
	pushup(u);
}

LL query(int u, int l, int r)
{
	if (l <= tr[u].l && tr[u].r <= r)
		return tr[u].s1 + tr[u].s2;
		
	pushdown(u);
	LL s = 0;
	int mid = tr[u].l + tr[u].r >> 1;
	if (l <= mid)
		s = query(u << 1, l, r);
	if (r > mid)
		s += query(u << 1 | 1, l, r);
		
	return s;
	
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		
		for (int i = 1; i <= n; i ++)
			cin >> w[i];
			
		build(1, 1, n);
		
		while (m --)
		{
			int op, l, r, x;
			cin >> op;
			
			if (op == 1)
			{
				cin >> l >> r >> x;
				
				motify(1, l, r, x);
			}
			else
			{
				cin >> l >> r;
				
				cout << query(1, l, r) << endl;
			}
		}
	}
	
	return 0;
}

1012 Play on Tree

题意：

随机选择一个节点作为根节点，进行树上删边游戏（每一轮选择一个节点x并删除它及其子树，删除根节点的输），问获胜的概率。

分析：

树上删边游戏+换根dp。
树上删边游戏：https://blog.csdn.net/wu_tongtong/article/details/79311284
换根dp：https://zhuanlan.zhihu.com/p/437753260
对于每棵树的SG函数，可以发现SG(u) = (SG(v1) + 1) xor (SG(v2) + 1) xor ... xor (SG(vk) + 1)
先计算出一个根节点的SG然后通过换根的方式计算其他节点作为根节点的SG：SG2(v) = SG(v) xor ((SG2(u) xor (SG(v) + 1)) + 1)
最后概率为：(frac{sum_i^n{SG2(i) > 0}}{n})

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 2e5 + 5, M = 4e5 + 5, mod = 1e9 + 7;
int h[N], e[M], ne[M], idx;
int f1[N], f2[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

LL qmi(LL m, LL k)
{
	LL res = 1, t = m;
	while (k)
	{
		if (k & 1)
			res = res * t % mod;
		t = t * t % mod;
		k >>= 1;
	}
	return res;
}

void dfs1(int u, int fa)
{
	f1[u] = 0;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		
		if (j == fa)
			continue;
			
		dfs1(j, u);
		
		f1[u] ^= (f1[j] + 1);
	}
}

void dfs2(int u, int fa)
{
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		
		if (j == fa)
			continue;
		
		f2[j] = f1[j] ^ ((f2[u] ^ (f1[j] + 1)) + 1);
		
		dfs2(j, u);
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		memset(h, -1, sizeof h);
		memset(f1, 0, sizeof f1);
		memset(f2, 0, sizeof f2);
		idx = 0; 
		
		int n;
		cin >> n;
		
		for (int i = 0; i < n - 1; i ++)
		{
			int a, b;
			cin >> a >> b;
			
			add(a, b), add(b, a);
		}
		
		dfs1(1, -1);
		
		f2[1] = f1[1];
		dfs2(1, -1);
		
		LL m = 0;
		for (int i = 1; i <= n; i ++)
			if (f2[i])
				m ++;
		
		cout << (m * qmi(n, mod - 2)) % mod << endl;
	}
	
	return 0;
}

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/scoxty/p/17569867.html

标签：算法数据结构

你还没有登录，请先登录或注册！

还没有人评论，欢迎说说您的想法！

2023“钉耙编程”中国大学生算法设计超级联赛（1）

2023“钉耙编程”中国大学生算法设计超级联赛（1）

1001 Hide-And-Seek Game

题意:

分析：

代码：

1002 City Upgrading

题意：

分析：

代码:

1005 Cyclically Isomorphic

题意：

分析：

代码：

1009 Assertion

题意:

分析：

代码：

1010 Easy problem I

题意：

分析：

代码：

1012 Play on Tree

题意：

分析：

代码：

相关课程

热门标签

2023“钉耙编程”中国大学生算法设计超级联赛（1）

2023“钉耙编程”中国大学生算法设计超级联赛（1）

1001 Hide-And-Seek Game

题意:

分析：

代码：

1002 City Upgrading

题意：

分析：

代码:

1005 Cyclically Isomorphic

题意：

分析：

代码：

1009 Assertion

题意:

分析：

代码：

1010 Easy problem I

题意：

分析：

代码：

1012 Play on Tree

题意：

分析：

代码：

相关课程

热门标签

推荐文章