首页 > 其他分享 >ABC334 全套题解

ABC334 全套题解

时间：2023-12-24 13:12:15浏览次数：34  
标签：return int 题解 ABC334 全套 nx ny Read MAXN

A - Christmas Present

简单题。

void slv() {
	int a = Read<int>(), b = Read<int>();
	if (a > b) Puts("Bat");
	else Puts("Glove");
	return;
}

B - Christmas Trees

也是简单题。

constexpr i128 INF = - 1e18;
i128 a, m, l, r;

void slv() {
	a = Read<i128>(), m = Read<i128>(), l = Read<i128>(), r = Read<i128>();
	a -= m * ((a - INF) / m + 10);
	auto calc = [&](i128 pos) -> i128 { return (i128)(pos - a) / m + 1; };
	Write(calc(r) - calc(l - 1), '\n');
	return;
}

C - Socks 2

首先可以发现，如果匹配方案在值域上交叉一定不优，因为可以调整使得不交叉且不劣。

所以对于 \(2n - k\) 是偶数的时候，可以相邻的两两匹配。

对于 \(2n - k\) 是奇数的时候，就是空出来一个不匹配，这个可以先求出最后一个不匹配时的代价，然后调整出每一个不匹配时的代价，最后取 \(\min\) 即可。

constexpr int MAXN = 2e5 + 9;
int n, k, a[MAXN];
vector<int> num;

void slv() {
	n = Read<int>(), k = Read<int>();
	for (int i = 1; i <= k; i ++) a[Read<int>()] --;
	for (int i = 1; i <= n; i ++) {
		num.emplace_back(i);
		if (!a[i]) num.emplace_back(i);
	}
	int ans = 0;
	for (int i = 1; i < num.size(); i += 2)
		ans += num[i] - num[i - 1];
	if (k & 1) {
		int ret = ans;
		for (int i = (int)num.size() - 2; i >= 0; i --) {
			if (i & 1) ret += num[i + 1] - num[i];
			else ret -= num[i + 1] - num[i];
			cmin(ans, ret);
		}
	}
	Write(ans, '\n');
	return;
}

D - Reindeer and Sleigh

基础二分题。先排个序，然后在前缀和上二分就行。

constexpr int MAXN = 2e5 + 9;
int n, q;
ll sum[MAXN];

void slv() {
	n = Read<int>(), q = Read<int>();
	for (int i = 1; i <= n; i ++) sum[i] = Read<ll>();
	sort(sum + 1, sum + n + 1);
	for (int i = 1; i <= n; i ++) sum[i] += sum[i - 1];
	while (q --) {
		ll x = Read<ll>();
		int l = 0, r = n;
		while (l < r) {
			int mid = l + r + 1 >> 1;
			if (sum[mid] <= x) l = mid;
			else r = mid - 1;
		}
		Write(l, '\n');
	}
	return;
}

E - Christmas Color Grid 1

先 dfs 一遍求出每个绿点所属的连通块，然后枚举每个红点，将他染绿后只会影响到相邻 4 个点的连通性，求出将他染绿后的连通块个数，然后求平均值就行。

constexpr int MAXN = 1e3 + 9;
constexpr int dx[] = {0, 0, 1, -1},
			  dy[] = {1, -1, 0, 0};
int n, m, a[MAXN][MAXN], cnt = 0, bel[MAXN][MAXN],
	tot = 0, ans = 0;
char s[MAXN];
bool vis[MAXN][MAXN];

void slv() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i ++) {
		scanf("%s", s + 1);
		for (int j = 1; j <= m; j ++)
			a[i][j] = (s[j] == '.');
	}
	function<void(int, int)> dfs = [&](int x, int y) {
		vis[x][y] = true, bel[x][y] = tot;
		for (int o = 0; o < 4; o ++) {
			int nx = x + dx[o], ny = y + dy[o];
			if (nx < 1 || nx > n || ny < 1
				|| ny > m || a[nx][ny] || vis[nx][ny]) continue;
			dfs(nx, ny);
		}
		return;
	};
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++)
		if (a[i][j]) cnt ++;
		else if (!vis[i][j]) tot ++, dfs(i, j);
	auto qpow = [&](int a, int b) {
		int ans = 1;
		for (; b; b >>= 1, cmul(a, a))
			if (b & 1) cmul(ans, a);
		return ans;
	};
	int inv = qpow(cnt, MOD - 2);
	vector<int> id;
	for (int x = 1; x <= n; x ++) for (int y = 1; y <= m; y ++)
		if (a[x][y]) {
			id.clear();
			for (int o = 0; o < 4; o ++) {
				int nx = x + dx[o], ny = y + dy[o];
				if (nx < 1 || nx > n || ny < 1
					|| ny > m || a[nx][ny]) continue;
				id.emplace_back(bel[nx][ny]);
			}
			sort(id.begin(), id.end());
			id.erase(unique(id.begin(), id.end()), id.end());
			cadd(ans, mul(inv, tot - id.size() + 1));
		}
	Write(ans, '\n');
	return;
}

F - Christmas Present 2

设 \(f_i\) 表示送完前 \(i\) 个人的最短距离，转移为：

\[f_{i} \leftarrow \min_{j \in [i - k - 1, i - 1]} \{f_{j} + \operatorname{Distance}(0, j) + \operatorname{Distance}(0, j + 1) + \sum_{k = j + 1}^{i - 1} \operatorname{Distance}(k, k + 1)\} \]

这很明显可以单调队列优化，后面的求和可以前缀和优化。

时间复杂度 \(O(n)\)。

constexpr int MAXN = 2e5 + 9;
int n, k, x[MAXN], y[MAXN],
	q[MAXN], head = 1, tail = 0;
ldb sum[MAXN], f[MAXN];

void slv() {
	n = Read<int>(), k = Read<int>();
	for (int i = 0; i <= n; i ++)
		x[i] = Read<int>(), y[i] = Read<int>();
	x[n + 1] = x[0], y[n + 1] = y[0];
	auto sqr = [&](int x) -> ll { return 1ll * x * x; };
	auto Get_Dis = [&](int i, int j) -> ldb {
		return sqrt(sqr(x[i] - x[j]) + sqr(y[i]- y[j]));
	};
	for (int i = 1; i <= n; i ++)
		sum[i] = Get_Dis(i, i - 1) + sum[i - 1];
	q[++ tail] = 0, f[0] = - sum[1] + Get_Dis(1, 0);
	for (int i = 1; i <= n; i ++) {
		while (head <= tail && q[head] < i - k) head ++;
		int j = q[head];
		f[i] = f[j] + sum[i] - sum[i + 1] + Get_Dis(i, 0) + Get_Dis(i + 1, 0);
		while (head <= tail && f[q[tail]] >= f[i]) tail --;
		q[++ tail] = i;
	}
	printf("%.12Lf\n", f[n]);
	return;
}

G - Christmas Color Grid 2

说说我的做法吧，可能比较唐。

受 E 的启发，我们会做染绿的情况，不会做染红，所以可以看成一张全是红格子的图，要把其中的几个格子染成绿色，求分别不染每一个绿格子的方案数。

这个是可以用分治来做，就是对于一次分治 \([l, r]\)，分治中心是 \(mid\)，先把 \([l, mid]\) 的染色都染上，然后递归 \([mid + 1, r]\)，再撤销染色；然后把 \([mid + 1, r]\) 都染上，然后递归 \([l, mid]\)，再撤销染色。这样当递归到 \(l = r\) 时，就是不染这个格子时连通块的个数。

时间复杂度 \(O(n \log^2 n)\)。太唐了。

constexpr int MAXN = 1e3 + 9;
constexpr int dx[] = {0, 0, 1, -1},
			  dy[] = {1, -1, 0, 0};
int n, m, a[MAXN][MAXN], tot = 0, ans = 0;
vpii pos;
char s[MAXN];

struct Disjoint {
	static constexpr int N = MAXN * MAXN;
	int fa[N], sz[N];
	vector<int> stk;
	
	void Init(int n) {
		stk.clear();
		for (int i = 1; i <= n; i ++)
			fa[i] = i, sz[i] = 1;
		return;
	}
	int Find(int u) {
		return (fa[u] == u) ? u : Find(fa[u]);
	}
	bool Merge(int u, int v) {
		u = Find(u), v = Find(v);
		if (u == v) return false;
		if (sz[u] > sz[v]) swap(u, v);
		fa[u] = v, sz[v] += sz[u];
		stk.emplace_back(u); return true;
	}
	void Reset() {
		int u = stk.back(); stk.pop_back();
		sz[fa[u]] -= sz[u], fa[u] = u; return;
	}
} D;

void slv() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i ++) {
		scanf("%s", s + 1);
		for (int j = 1; j <= m; j ++) if (s[j] == '#')
			pos.emplace_back(i, j), tot ++;
	}
	auto qpow = [&](int a, int b) {
		int ans = 1;
		for (; b; b >>= 1, cmul(a, a))
			if (b & 1) cmul(ans, a);
		return ans;
	};
	int inv = qpow(tot, MOD - 2), cnt = 0;
	D.Init(n * m);
	auto get_id = [&](int x, int y) { return (x - 1) * m + y; };
	function<void(int, int)> solve = [&](int l, int r) {
		if (l == r) {
			cadd(ans, mul(cnt, inv));
			return;
		}
		int mid = l + r >> 1, ct = 0, _cnt = cnt;
		auto Add = [&](int x, int y) {
			a[x][y] = 1, cnt ++;
			for (int o = 0; o < 4; o ++) {
				int nx = x + dx[o], ny = y + dy[o];
				if (nx < 1 || nx > n || ny < 1
					|| ny > m || !a[nx][ny]) continue;
				if (D.Merge(get_id(x, y), get_id(nx, ny)))
					cnt --, ct ++;
			}
			return;
		};
		auto Reset = [&]() {
			for (int i = l; i <= mid; i ++)
				a[pos[i].fir][pos[i].sec] = 0;
			while (ct --) D.Reset(); cnt = _cnt, ct = 0;
			return;
		};
		for (int i = l; i <= mid; i ++)
			Add(pos[i].fir, pos[i].sec);
		solve(mid + 1, r), Reset();
		for (int i = mid + 1; i <= r; i ++)
			Add(pos[i].fir, pos[i].sec);
		solve(l, mid), Reset();
		return;
	};
	solve(0, pos.size() - 1);
	Write(ans, '\n');
	return;
}

标签：return,int,题解,ABC334,全套,nx,ny,Read,MAXN
From： https://www.cnblogs.com/definieren/p/17924266.html

相关文章

  • 题解 ABC334G【Christmas Color Grid 2】
    先求出初始时绿连通块数量。将一个绿色格子染成红色，会改变绿连通块数量，当且仅当这个绿色格子是孤点或割点。如果是孤点，会使得绿连通块数量减少一；如果是割点，会使得绿连通块数量增加它所在的点双数量减一。根据上述规则可以求出每个绿色格子染红后的绿连通块数量，求平均值即可。时......
  • 题解 ABC334F【Christmas Present 2】
    设\(f_i\)表示假设只有编号为\(1\simi\)的点，此时的答案。\(f_n\)即为所求。显然有：\[f_i=\min\limits_{i-k\lej<i}\{f_j+dis(s\toj+1\toj+2\to\cdots\toi)\}+dis(i\tos)\]当\(i\toi+1\)时，大括号内部全局增加\(dis(i\toi+1)\)，可以全局打标记后单调队列维护。......
  • 题解 ABC334E【Christmas Color Grid 1】
    先求出初始时绿连通块数量。枚举每个红色格子，将其染成绿色本应增加一个绿连通块，但是它每与一个绿连通块相邻，就又会减少一个绿连通块。根据上述规则可以求出每个红色格子染绿后的绿连通块数量，求平均值即可。时间复杂度\(O(nm)\)。//Problem:E-ChristmasColorGrid1//Co......
  • 检查Windows更新问题解决
    在任务栏搜索框输入cmd，点击右侧的“以管理员身份运行”，打开后输入：（建议复制粘贴，防止输入有误出现错误提示等请忽略*）SCconfigwuauservstart=auto回车（Enter按键）SCconfigbitsstart=auto回车（Enter按键）SCconfigcryptsvcstart=auto回车（Enter按键）SCconfigtrustedin......
  • 【题解】洛谷P1068 [NOIP2009 普及组] 分数线划定 （map）
    ##题目描述世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的$150\%$划定，即如果计划录取$m$名志愿者，则面试分数线为排名第$m\times150\%$（向......
  • P3893 [GDOI2014] Beyond 题解
    P3893[GDOI2014]Beyond题解思路称第一个字符串为\(A\)，第二个字符串\(B\)。考虑枚举环长\(L\)，那么如果\(L\)是可行的，当且仅当存在一个位置\(i\)，使得\(A_{1\simi}=B_{L-i+1,L},A_{i+1\simL}=B_{1,L-i}\)，也就是\(A_{1\simL}\)的一个前缀和\(B_{1\s......
  • 【洛谷 P1781】宇宙总统 题解（高精度+结构体排序）
    宇宙总统题目描述地球历公元6036年，全宇宙准备竞选一个最贤能的人当总统，共有个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。输入格式第一行为一个整数，代表竞选总统的人数。接下来有行，分别为第一个候选人到第个候选人的票数。输出格式共两行，第一行是......
  • 题解：【XR-3】核心城市
    题解：【XR-3】核心城市思路一：考虑由特例推广到一般1、很容易想到先考虑一个关键点的情况，然后再推广到一般情况。2、一个点肯定选距离上最平衡的那个点，即树的中心。接着在中心周围贪心的选剩下的(k-1)个关键点即可。3、这里有一个误区：各点到某点的距离最小，是找树的中心而不是重......
  • 闭合区域面积统计 题解
    题目描述计算一个\(10\times10\)矩阵中由\(1\)围成的图形的面积。如下所示，在\(10\times10\)的二维数组中，\(1\)围住了\(15\)个点，因此面积为\(15\)。000000000000001110000000100100000001001000100010100101......
  • CF1881F Minimum Maximum Distance 题解
    因为白点对\(f_i\)没有贡献，所以可以重构出一棵原树的子树，使得所有的叶子都为标记点且标记点数量不变（没有删去标记点）。因为没有标记被删去且结构不变，所以这棵树的答案与原树答案相同。现在，对于所有节点，到它距离最大的标记点一定在叶子上。那么问题就变为：求出树上任意一点到所有......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99