首页 > 其他分享 >2/21 和 2/22 模拟赛总结

2/21 和 2/22 模拟赛总结

时间：2024-02-28 23:00:25浏览次数：24  
标签：21 22 int times MAXN dp left 模拟 MOD

2/21

T1 排序

题意

将 $4n$ 个数分成 $n$ 组，要求对于每组中的四个数 $a,b,c,d$，求 $\max\sum\lvert ab-cd\rvert$。$n\le10^5$，$0\le a_i\le10^7$。

解析

找规律题，评红。将所有数从小到大排序，从中分成两半。小的一半“彩虹桥”式两两配对，大的一半大大配对、小小配对，即是最优答案。

坑点

  1. 数据规模是 $4n$ 的，数组要开到 $4\times10^5$，是吧 @shaanxi_liuyuhe_yyyy
  2. 有乘法和 $10^7$ 规模数据，勿忘开 long long，是吧 @Aapwp_

T2 牛吃草

题意

李云舟有一条长度为 $n$ 的草地，编号 $1$ 到 $n$。每个草地都能放一个喂草机，在第 $i$ 块草地上放一个喂草机能覆盖 $\left[i-w_i+1,i\right]$ 的区间，同一块草地不能重复覆盖。

李云舟想知道，在草地总覆盖率不小于 $s%$ 的前提下，覆盖长度最小的喂草机的最大覆盖长度。

对于 $100%$ 的数据，$n\le5\times10^5$，$1\le s\le100$，$w_{i-1}\ge w_i-1$。

解析

首先，最小值最大，一眼二分答案。

check() 函数内部用到的是 DP。设 $dp[i]$ 表示枚举到第 $i$ 位时的总覆盖面积。令当前检查答案为 $x$，则有转移方程：
$$
dp[i]=\max\left(dp[i-1],\max_{i-w_i\le j\le i-x}\left{dp[j]+i-j\right}\right)
$$

至此，在 gxyzOJ 上，你已经可以拿到 90pts 的高分了！如果你再加一个小优化，即每次循环检查 $dp[i]$ 是否已经不小于 $n\times s%$，是则直接 return 1，还能进一步拿到 95pts 的高分！这数据有待加强

尽管进一步优化的性价比很低，但是为了 AC，我们还是得考虑进一步优化。

进一步优化需要用到单调队列。知道为什么性价比很低了吧

我们注意到题目中给定的一个不起眼的条件：$w_{i-1}\ge w_i-1$。

由此，我们得出：
$$
(i-1)-w_{i-1}\le i-1-(w_i-1)
$$

即：
$$
i-1-w_{i-1}\le i-w_i
$$

这说明，在 $i$ 时的决策范围类似滑动窗口，单调队列优化 DP。时间复杂度 $O(n\log n)$。

评蓝。

坑点

主要集中在单调队列。

  1. deque 一定要先 push_back 一个 $0$ 进去！
  2. 枚举 $i$ 的 for 循环开始时令 $dp[i]=dp[i-1]$，然后取 $\max$ 时就直接和 $dp[i]$ 比较（而不是 $dp[i-1]$）
  3. 令当前检查的答案为 $x$，只有当 $i-x+1\ge0$ 时才转移（95pts $\to$ 100pts 的关键）

二分答案注意：l <= r、l = mid + 1、r = mid - 1、答案记录 mid 而非 l。

心得

考试时想到二分答案却没想到 DP，暴力检查不知为何 WA 多 T 少。感觉每次看 DP 方程都是很容易理解的那种，但考场上推不出来，抑或能推出来但不确定对，也不确定代码的正确性。

实现

放一下 check() 函数的实现吧。二分大家应该都会

bool check(int x) {
	deque<int> q;
	q.push_back(0);
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1];
		while (!q.empty() && q.front() < i - w[i]) q.pop_front();
		if (i - x + 1 > 0) {
			if (!q.empty()) dp[i] = max(dp[i], dp[q.front()] + i - q.front());
			int pos = i - x + 1;
			while (!q.empty() && dp[q.back()] - q.back() <= dp[pos] - pos) q.pop_back();
			q.push_back(pos);
		}
		if (dp[i] >= least) return 1;
	}
	return 0;
}

T3 树上的宝藏

题意

给定一个 $n$ 个结点的树，每个结点上有一个宝藏，但同一条边的两个结点上的宝藏最多可以拿一个。在树上有一条特殊边，特殊边的两个结点上的宝藏最少拿一个。特殊边可能在任意一条边上。求当特殊边在每条边上时拿宝藏的总方案数对 $998244353$ 取模的值。

对于 $30%$ 的数据，$n\le11$。

对于 $60%$ 的数据，$n\le1000$。

对于 $100%$ 的数据，$n\le3\times10^5$。

解析

30pts 做法：暴力

枚举每一条边，计算每条边成为特殊边的时候有多少种可行的情况。枚举每一个点选与不选，然后判断可行性计算答案。时间复杂度 $O(2nn2)$。

60pts 做法：树形 DP

还是先枚举每一条边，但是统计的时候不能暴力枚举，而是树形 DP。我们砍断特殊边，对于砍断后的两棵树分别作树形 DP。

令 $f[u,0/1]$ 表示 $u$ 的子树内，$u$ 选或不选的方案数为多少。设 $v$ 为 $u$ 的儿子，则有转移方程：

$$
\begin{aligned}
f[u,0]&=\prod_v\left(f[v,0]+f[v,1]\right) \
f[u,1]&=\prod_vf[v,0]
\end{aligned}
$$

设枚举的特殊边两端点为 $a,b$，则我们所求答案即为：
$$
f[a,0]\times f[b,1]+f[a,1]\times f[b,0]+f[a,1]\times f[b,1]
$$

注意因为是由下推上，所以先 DFS，再转移。

100pts 做法：树形 DP + 优化

我们不能再枚举每一条边了，只能预处理。

据某些刷完概率与期望的同学所述，此题做法和洛谷 P4284 [SHOI2014] 概率充电器一题做法相似。总而言之，这种题目的技巧是求出 $g(u)$ 为 $u$ 子树外部的答案。

对于此题，设 $g[u,0/1]$ 代表 $u$ 选或不选，$u$ 子树外部的方案数。

考虑如何求出 $g$。 $u$ 子树外部可以分为两个部分，即 $u$ 的 $fa$ 子树外部和 $u$ 的 $fa$ 子树内部除 $u$ 子树以外的部分。前者即为 $g[fa,0/1]$，后者求法需要用到乘法原理。我们以 $v$ 的视角来看，简而言之，我们在求得 $f$ 的前提下，若 $v$ 拿，则 $u$ 不拿，总拿法数就是 $f[u,0]$，$u$ 子树部分的拿法数就是 $f[v,0]+f[v,1]$；若 $v$ 不拿，则 $u$ 可拿可不拿，转移方程同理可推出。
$$
\begin{aligned}
g[v,1]&=g[u,0]\times\frac{f[u,0]}{f[v,0]+f[v,1]} \
g[v,0]&=g[u,0]\times\frac{f[u,0]}{f[v,0]+f[v,1]}+g[u,1]\times\frac{f[u,1]}{f[v,0]}
\end{aligned}
$$

至于答案，设特殊边的两端点为 $a,b$ 且 $a$ 为 $b$ 的父亲，则答案为：
$$
\left(f[v,0]+f[v,1]\right)\times\frac{f[u,1]}{f[v,0]}\times g[u,1]+f[v,1]\times\frac{f[u,0]}{f[v,0]+f[v,1]}\times g[u,0]
$$

式子推出来，代码就没有难度了。第一次 DFS 计算 $f$，第二次 DFS 计算 $g$。注意 $g$ 是由上推下，所以先转移，再 DFS。时间复杂度 $O(n)$。评蓝。

坑点

  1. 注意 DFS 和转移的顺序
  2. 时刻注意有没有把 $u,v$ 写反
  3. 需要开一个 $fa$ 数组记录结点的父亲
  4. 除法带取模，需要乘法逆元
  5. 乘法逆元需要用快速幂求！exgcd 死活调不过去！

实现

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

constexpr int MAXN = 3e6 + 5, MOD = 998244353;
int n, U[MAXN], V[MAXN];
int f[MAXN][2], g[MAXN][2];
int fa[MAXN];
int head[MAXN], to[MAXN], nxt[MAXN], tot;

inline int power(int a, int b) {
	int res = 1;
	while (b != 0) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res % MOD;
}

int inv(int a) {
	return power(a, MOD - 2);
}

void add_edge(int u, int v) {
	nxt[++tot] = head[u];
	head[u] = tot;
	to[tot] = v;
}

void dfs1(int u, int fno) {
	f[u][0] = f[u][1] = 1;
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v == fno) continue;
		fa[v] = u;
		dfs1(v, u);
		f[u][0] = f[u][0] * ((f[v][0] + f[v][1]) % MOD) % MOD;
		f[u][1] = f[u][1] * f[v][0] % MOD;
	}
}

void dfs2(int u, int fno) {
	for (int i = head[u]; i; i = nxt[i]) {
		int v = to[i];
		if (v == fno) continue;
		g[v][1] = ((g[u][0] * f[u][0]) % MOD * inv((f[v][0] + f[v][1]))) % MOD;
		g[v][0] = ((g[u][0] * f[u][0]) % MOD * inv((f[v][0] + f[v][1]) % MOD) % MOD + (g[u][1] * f[u][1]) % MOD * inv(f[v][0]) % MOD + MOD) % MOD;
		dfs2(v, u);
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i < n; i++) {
		cin >> U[i] >> V[i];
		add_edge(V[i], U[i]);
		add_edge(U[i], V[i]);
	}
	dfs1(1, 0);
	g[1][0] = g[1][1] = 1;
	dfs2(1, 0);
	for (int i = 1; i < n; i++) {
		int a, b;
		if (fa[V[i]] == U[i]) b = V[i], a = U[i];
		else b = U[i], a = V[i];
		cout << ((f[b][1] + f[b][0]) % MOD * f[a][1] % MOD * inv(f[b][0]) % MOD * g[a][1] % MOD + (f[b][1] * f[a][0] + MOD) % MOD * inv((f[b][1] + f[b][0]) % MOD) % MOD * g[a][0] % MOD + MOD) % MOD << '\n';
	}

	return 0;
}

T4 MEX

我就不献丑了。

2/22

T1 打赌

题意

给一个 $R$ 行 $C$ 列的矩阵，将一颗骰子放在左上角。开始时朝上一面为 $1$，朝右一面为 $3$，朝前一面为 $2$。S 型滚动直到右下角。求滚动路径上骰子朝上一面的数字之和。$R,C\le10^5$。

解析

小学数学题，评红。此题过法千万，我简单说一下我考场上的做法。

枚举每一行。记录每行开始和结束时，骰子朝上和朝右一面的值。由于骰子只有 $4$ 个面，所以看 $C\div4$ 的余数，然后再模拟。其实就是小学做法，不想讲了

细节别出错就行，AC 还是很简单哒 ~

T2 舞会

题意

有 $n$ 个男孩和 $n$ 个女孩跳舞，每个男孩和女孩都有一个身高 $h_i$。每个男孩或女孩要么喜欢和比自己低的异性跳舞，要么喜欢和比自己高的异性跳舞。女孩同理。求最多有多少对能在一起跳舞。$n\le10^5$，$1500\le h_i\le2500$。

解析

模拟题，评橙。但正解考场上没写出来

注意一个坑点，只要已经配对的就不能再和别人配。

解法简单，先分别保存男孩和女孩各自喜欢和低或高的异性跳舞的数量，得到 $4$ 个数组。分别从小到大排序。两个 for 循环分别枚举男孩喜欢高、女孩喜欢低和男孩喜欢低、女孩喜欢高，如果身高符合就配。具体看代码。

实现

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

int n, ans;
vector<int> sb, tb, sg, tg;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1, x; i <= n; i++) {
		cin >> x;
		if (x < 0) sb.push_back(~x + 1);
		else tb.push_back(x);
	}
	for (int i = 1, x; i <= n; i++) {
		cin >> x;
		if (x < 0) sg.push_back(~x + 1);
		else tg.push_back(x);
	}
	sort(sb.begin(), sb.end());
	sort(tb.begin(), tb.end());
	sort(sg.begin(), sg.end());
	sort(tg.begin(), tg.end());
	for (int i = 0, j = 0; i < sb.size() && j < tg.size(); i++)
		if (sb[i] > tg[j]) j++, ans++;
	for (int i = 0, j = 0; i < sg.size() && j < tb.size(); i++)
		if (sg[i] > tb[j]) j++, ans++;
	cout << ans << '\n';

	return 0;
}

T3 最小生成树

题意

给定一个 $N$ 个点的完全图，边 $(u,v)$ 的边权为 $\gcd(u,v)$，求其满足小根堆性质的最小生成树个数对 $100000007$ 取模的值。

对于 $10%$ 的数据，$N\le5$。

对于 $30%$ 的数据，$N\le8$。

对于 $40%$ 的数据，$N\le10$。

对于 $70%$ 的数据，$N\le5000$。

对于 $100%$ 的数据，$N\le20000$。

解析

乍一看很难，实则模板题。评黄。

实际上我本想打表来着

首先，最小生成树的边权和显然一定是 $N-1$，也就是只连互质的数。再加上题中的限制条件，所以对于一个结点 $u$，能成为 $u$ 的父亲的结点一定只有小于 $u$ 且和 $u$ 互质的结点。

读这句话很熟悉有没有？不就是 $\varphi$ 嘛！

考场上想到这里就很激动了，刚好前两天的比赛考素数筛还看了一下线性筛，直接码一个筛法求欧拉函数出来。

至于怎么统计答案，乘法原理，总方案数 = 每个结点的方案数之积，用数学语言就是 $\prod_{i=1}^n\varphi(i)$。

注意：模数是 $10^8+7$！

注意：模数是 $10^8+7$！

注意：模数是 $10^8+7$！

实现

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

constexpr int MAXN = 20005, MOD = 100000007;
int n, phi[MAXN], ans = 1;
vector<int> pri;

void euler(int n) {
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!phi[i]) {
			pri.push_back(i);
			phi[i] = i - 1;
		}
		for (auto j : pri) {
			if (i * j > n) break;
			if (i % j != 0)
				phi[i * j] = phi[i] * phi[j];
			else {
				phi[i * j] = phi[i] * j;
				break;
			}
		}
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> n;
	euler(n);
	for (int i = 2; i <= n; i++) ans = ans * phi[i] % MOD;
	cout << ans << '\n';
	
	return 0;
}

T4 买汽水

题意

有 $N$ 天集训，每天都可以买汽水，第 $i$ 天买汽水的花销为 $p_i$ 元。最多有 $M$ 元可以买汽水，求最大花销。$N\le40$，$M,p_i\le10^8$。

解析

乍一看，这不裸背包么？

一看数据范围，显然不行……

那就 DFS 吧！一看 $N\le40$，暴搜 + 剪枝有希望骗分！

由于数据太水，直接 AC 了。

其实一般暴搜是过不了的，时间复杂度 $O(2^NN)$。但有一个非常牛 X 的剪枝：当我们在任何时候发现当前最大花销已经是 $M$，请直接返回你的 $M$！此时提交你会发现，2000ms $\to$ 2ms，TLE $\to$ AC！

二分：其实我才是正解

还是讲一下正解吧。暴搜保证能过的数据范围是 $N\le20$，而题目的数据范围是 $N\le40$，所以可以劈成两半考虑。对于前一半即 $\left[1,\left\lfloor\frac{N}{2}\right\rfloor\right]$，直接暴搜，记录所有能凑出来的值存入数组 $c$；对于后一半即 $\left(\left\lfloor\frac{N}{2}\right\rfloor,N\right]$，存入数组 $d$。问题转化为求 $\max_{c_i+d_j\le M}\left{c_i+d_j\right}$，可推导出在 $c_i$ 固定时，$d_j$ 在不大于 $M-c_i$ 的前提下越大越好，所以可以二分。时间复杂度 $O(2^{\left\lfloor\frac{N}{2}\right\rfloor-1}N)$。

实现

AC 代码

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

constexpr int MAXN = 45;
int n, m, p[MAXN], ans;

void dfs(int now, int cnt) {
	if (cnt == m) {
		cout << cnt << '\n';
		exit(0);
	}
	for (int i = now; i <= n; i++) {
		if (cnt + p[i] > m) continue;
		dfs(i + 1, cnt + p[i]);
	}
	ans = max(ans, cnt);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> p[i];
	dfs(1, 0);
	cout << ans << '\n';
	
	return 0;
}

正解代码

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

constexpr int MAXN = 45;
int n, p[MAXN];
int m, s, ans;
vector<int> c, d;
unordered_map<int, bool> a, b;

void dfs1(int x) {
	if (s > m) return;
	if (x > n >> 1) {
		if (!a[s]) {
			a[s] = 1;
			c.push_back(s);
		}
		return;
	}
	dfs1(x + 1);
	s += p[x];
	dfs1(x + 1);
	s -= p[x];
}

void dfs2(int x) {
	if (s > m) return;
	if (x > n) {
		if (!b[s]) {
			b[s] = 1;
			d.push_back(s);
		}
		return;
	}
	dfs2(x + 1);
	s += p[x];
	dfs2(x + 1);
	s -= p[x];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> p[i];
	dfs1(1);
	dfs2((n >> 1) + 1);
	sort(d.begin(), d.end());
	for (int i = 0; i < d.size(); i++) {
		int j = upper_bound(d.begin(), d.end(), m - c[i]) - d.begin();
		if (c[i] + d[j] <= m) ans = max(ans, c[i] + d[j]);
	}
	cout << ans << '\n';
	
	return 0;
}

标签：21,22,int,times,MAXN,dp,left,模拟,MOD
From： https://www.cnblogs.com/laoshan-plus/p/18042249

相关文章

  • 2.22
    今天需要实现一个研究生调剂管理信息系统，一开始以为是单表多次的增删改查，后来发现一次操作涉及到多表的联合，本次需要学生浏览调剂计划后在申请，这就要求我们本来就存在调剂计划，或者是我们需要优先选择编辑研究院页面，然后没有做好的一点就是在对实体类命名时，最好是前后端一致，与数据......
  • 洛谷题单指南-二分查找与二分答案-P2249 【深基13.例1】查找
    原题链接：https://www.luogu.com.cn/problem/P2249题意解读：找有序数组中某个数第一次出现的位置，二分模版题，由于是二分板块的第一题，有必要对二分的各种模版进行介绍。解题思路：关于二分的一切：1、二分的本质二分的本质，是通过某种判定把目标范围划分成两个区间二分问题通常有两......
  • 2024/2/22
    我们的一条数据项目包括，收入（指出）、说明、日期、金额四项，所以我们要自定义一个适配器这里适配器的一个列表的各个单位的类型是一个打包好的类的类型。这个类也是自己创建的packagecom.example.myapplication;publicclasscostList{privateString_id;private......
  • 2024/2/21
    今天根据黑马的视频来完成一些小练习用js来：1.切换图片2.在文本后添加文字3.使所有的复选框被选中<%@pagecontentType="text/html;charset=UTF-8"pageEncoding="UTF-8"%><!DOCTYPEhtml><html><head><title>JSP-HelloWorld</title></......
  • 20240228
    https://blog.csdn.net/m0_69752994/article/details/134107424https://blog.csdn.net/weixin_37845646/article/details/104686072用三极管代替IO口的通断效果。......
  • 2024.02.22
    1.原始jsp模板查看初始jsp创建模板：File---Setting---Editor---FileandCodeTemplates---Other---Jspfiles---JspFile.jsp，可在⑤处重新定义jsp模板，编写完成后，Apply，OK，下次在新建jsp文件时，即可建立所定义模板的jsp页面。 2.重新定义jsp页面模板    File---Sett......
  • Vue学习笔记21-列表排序
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0"><title>列表排序</title><script......
  • 模拟ftp服务器
    client.cintget_cmd_type(char*cmd){//比较输入的指令，找到对应的就返回相对应的指令。if(!strcmp("ls",cmd))returnLS;if(!strcmp("lls",cmd))returnLLS;if(!strcmp("pwd",cmd))returnPWD;if(!strcmp("......
  • NFLS 省选模拟 过路费
    前言这道题正向思考是比较难以想出来的，蕴含了一类解题的思路，同时也可以当作一类板子题记忆。题面Link给定一个有向图，求\(s\)到\(t\)的最短路径。特殊点在于，对于一条路径，如果经过的边数小于等于\(k\)，那么该路径总长度为构成该路径的所有边的长度之和；否则为该路径上最长的......
  • 22国庆集训笔记
    Day-1没要到假期作业/ll/ll/ll只写了当天的作业。感觉要寄。Day0早上现跑到学校里要作业。结果还被保安撵回去写了假条然后就是漫长的乘车之旅，从\(8:30\)一直到\(16:00\)。发现车上的人比我卷多了，个个都通宵写作业/kk电脑在箱子里，不能写代码，有点难受。最后还是向hjr......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99