首页 > 其他分享 >[赛记] 暑假集训CSP提高模拟23

[赛记] 暑假集训CSP提高模拟23

时间:2024-08-18 19:16:26浏览次数:11  
标签:cnt 赛记 23 int sum long 2005 CSP dis

进击的巨人 100pts

这题赛时10min打的 $ \Theta(n^2) $ 暴力然后过了,而且还是首A

正解当然不是暴力,而是要推式子;

不难发现,每个 $ 0 $ 会原序列分割成两个互不相同的子序列,且两部分互不影响,于是我们可以分开考虑;

对于一个不包含 $ 0 $ 的一个极大子序列,设其最左区间左端点下标为 $ la $,最右区间右端点下标为 $ ra $(注意这里区间和下标的区别),同时设 $ cnt_i $ 表示从 $ la $ 到 $ i $ 的 $ ? $ 总个数($ la \leq i \leq ra $),则这一个序列的答案(期望)为:

\[ \sum_{l = la}^{ra} \sum_{r = la}^{l - 1} (r - l)^k \times \frac{1}{2^{cnt_r - cnt_l}} \]

对其使用二项式定理($ (x + y)^k = \sum^{k}_{i = 0} C^i_k \ x^i \ y^{k - i} $),可得:

\[ \sum_{l = la}^{ra} \sum_{r = la}^{l - 1} \sum_{i = 0}^{k} C^i_k \ (-l)^i \ r^{k - i} \times 2^{cnt_l} \times \frac{1}{2^{cnt_r}} \]

可以把 $ k $ 提出来,将包含 $ l $ 的项放一起,包含 $ r $ 的项放一起,则:

\[ \sum^{k}_{i = 0} C^i_k \sum^{l = la}_{ra} (-l)^i \ 2^{cnt_l} \times (\sum^{l - 1}_{r = la} r^{k - i} \ \frac{1}{2^{cnt_r}}) \]

注意到后面括号那一堆是可以使用前缀和求的,所以枚举 $ i $ 和 $ l $ 即可,时间复杂度 $ \Theta(nk) $;

当然,也可以将 $ l $ 与 $ r $ 互换位置;

点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
const long long mod = 998244353;
long long n, k;
char c[200005];
long long cnt[200005];
long long sum[200005];
long long ans;
long long ksm(long long a, long long b) {
	long long ans = 1;
	while(b) {
		if (b & 1) ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}
long long inv[200005];
long long p[200005];
long long fac[200005], fav[200005];
long long C(long long n, long long m) {
	if (m == 0) return 1;
	if (m == n) return 1;
	if (n == 0) return 0;
	if (m > n) return 0;
	return fac[n] * fav[m] % mod * fav[n - m] % mod;
}
long long Lucas(long long n, long long m) {
	if (m == 0) return 1;
	return Lucas(n / mod, m / mod) * C(n % mod, m % mod) % mod;
}
int main() {
	freopen("attack.in", "r", stdin);
	freopen("attack.out", "w", stdout);
	scanf("%lld %lld", &n, &k);
	scanf("%s", c + 1);
	n++;
	c[n] = '0';
	p[0] = 1;
	fac[0] = 1;
	inv[0] = 1;
	fav[0] = 1;
	for (long long i = 1; i <= n; i++) {
		p[i] = p[i - 1] * 2 % mod;
		inv[i] = ksm(p[i], mod - 2);
		fac[i] = fac[i - 1] * i % mod;
		fav[i] = ksm(fac[i], mod - 2);
	}
	long long ls = 1;
	for (long long i = 1; i <= n; i++) {
		cnt[i] = cnt[i - 1];
		if (c[i] == '?') cnt[i]++;
		if (c[i] == '0') {
			cnt[i] = 0;
			for (long long j = 0; j <= k; j++) {
				if (ls > 1) sum[ls - 2] = 0;
				for (long long l = ls - 1; l <= i - 1; l++) {
					sum[l] = (sum[l - 1] + ksm(-l, j) * p[cnt[l]] % mod) % mod;
				}
				long long su = 0;
				for (long long r = ls - 1; r <= i - 1; r++) {
					su = (su + ksm(r, k - j) * inv[cnt[r]] % mod * sum[r - 1] % mod) % mod;
				}
				ans = (ans + su * Lucas(k, j) % mod + mod) % mod;
			}
			ls = i + 1;
		}
	}
	printf("%lld", ans);
	return 0;
}

Wallpaper Collection -pts

赛时根本没看;

像这种一眼望去没啥思路的题,一般就是DP;

首先转化题意:在每行都找一个不空的矩形,使它们互有交集;

考虑最暴力的DP;

设 $ f_{i, L, R} $ 表示考虑了前 $ i $ 行,第 $ i $ 行选择的区间为 $ [L, R] $ 时,最大的喜爱值之和,转移直接枚举下一行的 $ [L'. R'] $ 即可,复杂度 $ \Theta(nm^4) $ 。(from 题解);

很显然,这是过不了的;

其实我们会发现,找出满足题意的最大值,就相当于从上往下走一条路径(当然也可以向左或右走),经过的点的和的最大值;

那么我们考虑变一个状态设计;

设 $ f_{i, j} $ 表示考虑前 $ i $ 行,第 $ i $ 行从 $ j $ 这个点走下来(即 $ j $ 为第 $ i $ 行的起始点)的最大值;

我们用 $ k $ 去枚举 $ i - 1 $ 行符合条件的 $ j $,那么有状态转移方程:

  1. 当 $ k \leq j $ 时;

\[ f_{i, j} = \max_{k \leq j}(\sum_{x = k}^{j} a_{i, x} + f_{i - 1, k}) \]

  1. 当 $ k > j $ 时;

\[ f_{i, j} = \max_{k > j}(\sum_{x = j}^{k} a_{i, x} + f_{i - 1, k}) \]

这个是 $ \Theta(nm^3) $ 的;

考虑优化一下式子中的 $ \sum $,那么我们设 $ sum_i = \sum_{j = 1}^{m} a_{i, j} \ \ s_{i, j} = \sum_{k = 1}^{j} a_{i, k} \ \ t_{i, j} = \sum_{k = j}^{m} a_{i, k} $,则原状态转移方程可改写为:

\[ f_{i, j} = \max_{k \leq j}(sum_i - \min_{x = 1}^{k - 1} s_{i, x} - \min_{x = j + 1}^{m} t_{i, x} + f_{i - 1, k}) \]

另一种情况同理;

这个是 $ \Theta(nm^3) $ 的;

考虑省去 $ k $ 的枚举;

我们发现,式子中 $ s_{i, k - 1} \ \ t_{i, j + 1} $ 这两项需要找到最小值,所以我们维护一个前缀最小值,一个后缀最小值,这样对于这两项就可以 $ \Theta(1) $ 查询了,但我们还需要维护 $ f_{i - 1, k} $;

将原式中包含 $ k $ 的项单拿出来,我们会得到:

\[ f_{i, j} = \max_{k \leq j}(sum_i - mint_{i, j + 1} + (mins_{i, k - 1} + f_{i - 1, k})) \]

发现我们只需维护后面括号内的最大值即可,所以可以在枚举 $ j $ 的过程中维护;

时间复杂度:$ \Theta(nm) $;

细节看代码:

点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m;
int a[2005][2005];
long long f[2005][2005];
long long sum[2005];
long long s[2005][2005], t[2005][2005];
long long mins[2005][2005], mint[2005][2005];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			sum[i] += a[i][j];
		}
	}
	memset(mins, 0x3f, sizeof(mins));
	memset(mint, 0x3f, sizeof(mint));
	for (int i = 1; i <= n; i++) {
		mins[i][0] = mins[i][m + 1] = mint[i][0] = mint[i][m + 1] = 0; //注意这里,最小值可以为0(不选);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			s[i][j] = s[i][j - 1] + a[i][j];
			mins[i][j] = min(mins[i][j - 1], s[i][j]);
		}
		for (int j = m; j >= 1; j--) {
			t[i][j] = t[i][j + 1] + a[i][j];
			mint[i][j] = min(mint[i][j + 1], t[i][j]);
		}
	}
	memset(f, 0xcf, sizeof(f));
	for (int i = 1; i <= m; i++) f[0][i] = 0;
	for (int i = 1; i <= n; i++) {
		long long ma = -0x3f3f3f3f3f3f3f3f;
		long long maa = -0x3f3f3f3f3f3f3f3f;
		for (int j = 1; j <= m; j++) {
			ma = max(ma, f[i - 1][j] - mins[i][j - 1]);
			f[i][j] = max(f[i][j], sum[i] - mint[i][j + 1] + ma);
		}
		for (int j = m; j >= 1; j--) {
			if (maa == -0x3f3f3f3f3f3f3f3f) {
				maa = f[i - 1][j] - t[i][j + 1];
				continue;
			}
			f[i][j] = max(f[i][j], sum[i] - mins[i][j - 1] + maa);
			maa = max(maa, f[i - 1][j] - mint[i][j + 1]);
		}
	}
	long long ans = -0x3f3f3f3f3f3f3f3f;
	for (int j = 1; j <= m; j++) {
		ans = max(ans, f[n][j]);
	}
	cout << ans;
	return 0;
}

樱花庄的宠物女孩 30pts

树的特殊性质很好打,在此不再赘述;

考虑正解;

我们发现,如果人到了箱子旁边,那么他会一直拉着箱子走;

那么我们可以先用BFS(其实就是最短路)处理出人从起点到与1相邻的每个点的最小步数,并将这些值存储在一个数组中;

下一步,我们要让人带着箱子从这些点走;

我们发现,其实我们关心的是一个三元组 $ (u, v, k) $,分别表示人在点 $ u $,箱子在点 $ v $ 时的最小步数 $ k $;

发现这其实是一条有向边在某一时刻的状态;

所以我们要将处理对象从点转换成边;

具体实现上,我们从1开始再进行一次BFS,每次去更新与1相邻的边的相邻的边的状态,最后从n处统计一下答案即可;

这里可以将边看成点,会方便一些;

注意更新时,我们要每次取出队列中 $ k $ 值最小的进行更新(类似最短路),这里有两种方法,一种是用优先队列,另一种是用双指针的方法(因为发现我们处理人从起点到与1相邻的每个点的最小步数时这个最小步数是递增的)去维护,复杂度上前者 $ \Theta(n \log n) $,后者 $ \Theta(n) $,我的代码实现上是用的后者,但前者更好打;

点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n, m, x;
struct sss{
	int f, t, ne;
}e[2000005];
int h[2000005], cnt;
void add(int u, int v) {
	e[++cnt].t = v;
	e[cnt].f = u;
	e[cnt].ne = h[u];
	h[u] = cnt;
}
int dis[2000005], vis[2000005];
int rem[2000005], val[2000005];
void dij(int x) {
	memset(dis, 0x3f, sizeof(dis));
	dis[x] = 0;
	queue<int> q;
	q.push(x);
	while(!q.empty()) {
		int t = q.front();
		q.pop();
		for (int i = h[t]; i; i = e[i].ne) {
			int u = e[i].t;
			if (u != 1 && dis[u] > dis[t] + 1) {
				dis[u] = dis[t] + 1;
				q.push(u);
			}
			if (u == 1) {
				rem[++rem[0]] = ((i & 1) ? (i + 1) : (i - 1)); //存反向边,因为下一步要从1开始BFS;
				val[rem[0]] = dis[t];
			}
		}
	}
}
void bfs() {
	memset(dis, 0x3f, sizeof(dis));
	memset(vis, 0, sizeof(vis));
	queue<int> q; //队列中存的是边的编号;
	int now = 1;
	for (int i = 1; i <= rem[0]; i++) {
		dis[rem[i]] = val[i]; //先将已知的初始化;
	}
	while(!q.empty() || now <= rem[0]) {
		if (q.empty()) {
			if (now <= rem[0]) {
				q.push(rem[now++]);
			}
		} else {
			int t = q.front();
			q.pop();
			if (vis[e[t].t] == 2) continue;
			vis[e[t].t]++;
			while(now <= rem[0] && dis[rem[now]] == dis[t]) {
				q.push(rem[now++]);
			}
			for (int i = h[e[t].t]; i; i = e[i].ne) {
				int u = e[i].t;
				if (u == e[t].f) continue;
				if (dis[i] > dis[t] + 1) {
					dis[i] = dis[t] + 1;
					q.push(i);
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> x;
	int xx, yy;
	for (int i = 1; i <= m; i++) {
		cin >> xx >> yy;
		add(xx, yy);
		add(yy, xx);
	}
	dij(x);
	bfs();
	int ans = 0x3f3f3f3f;
	for (int i = h[n]; i; i = e[i].ne) { //注意这里枚举的是有向边;
		ans = min(ans, dis[i]);
	}
	if (ans == 0x3f3f3f3f) {
		cout << "No";
		return 0;
	}
	cout << "Yes" << endl << ans;
	return 0;
}

标签:cnt,赛记,23,int,sum,long,2005,CSP,dis
From: https://www.cnblogs.com/PeppaEvenPig/p/18365953

相关文章

  • CSP-J/S2023游记
    过了将近一年才回来补游记比赛前Day-22光速报名Day-21~0国庆假期+痛苦的whkDay1CSP-J早上乘出租车风驰电掣赶到连大,在门口等半天发现已经可以进去了。一路踩着爆浆的银杏到了日新楼门口,看到由无数人头组成的一片乌云,以及一辆挂着横幅的黄色校车。CL排场挺大进了考场,......
  • 023、Vue3+TypeScript基础,使用defineProps限制父传子的数据类型,并用v-for显示
    01、index.js代码如下://定义一个接口,用于限制person对象的具体属性exportinterfacePersonInter{id:string;name:string;age:number;}exporttypePersons=Array<PersonInter>;02、App.vue代码如下:<template><divclass="app">&......
  • 【动态规划、dp】[CSP-J 2022] 上升点列 题解
    题目描述在一个二维平面内,给定nnn个整数点(xi......
  • day23-测试自动化之Appium的滑动和拖拽事件、高级手势ActionChains、手机操作API
    目录一、滑动和拖拽事件    1.1.应用场景    1.2.swipe滑动事件    1.3.scroll滑动事件    1.4.drag_and_drop拖拽事件    1.5.滑动和拖拽事件的选择二、高级手势ActionChains    2.1.应用场景    2.2.使用......
  • [C++ Error] f0201.cpp(11): E2379 Statement missing ;
    错误解释:这个错误表明在C++源代码文件f0201.cpp的第11行出现了一个语法错误,具体是缺少了一个分号;。C++语言规定语句的结束需要使用分号;,如果一个语句缺少了它,编译器就会抛出这样的错误。解决方法:打开f0201.cpp文件``,定位到第11行。检查那一行的代码,确保每个语句后面都有分号;......
  • 723java jsp SSM医院住院管理系统(源码+文档+运行视频+讲解视频)
    项目技术:SSM+Maven+Vue等等组成,B/S模式+Maven管理等等。环境需要1.运行环境:最好是javajdk1.8,我们在这个平台上运行的。其他版本理论上也可以。2.IDE环境:IDEA,Eclipse,Myeclipse都可以。推荐IDEA;3.tomcat环境:Tomcat7.x,8.x,9.x版本均可4.硬件环境:windows7/8/10......
  • 『模拟赛』暑假集训CSP提高模拟23
    Rank玩蓝图玩的A.进击的巨人(原题都是牛客的,没号所以不挂了)赛事看到概率期望一眼润,但是又可惜暴力分,遂打(最坏情况下)\(\mathcal{O(n^2)}\)暴力,结果很给力啊,调出来小样例后大样例嗖的一下就过了,惊喜了属于是,喜提100pts。事实上跑这么快是因为0的数量很平均,导致复杂度大......
  • [赛记] 暑假集训CSP提高模拟22 23
    连通块66pts老套路,删边改加边;但改完以后不知道怎么求最长路径了,当时也想到了维护直径,但不知道咋干;具体地,用并查集维护连通性,每次合并时需要维护新的直径,不难发现,新的直径的两个端点一定在原来的两个直径的四个端点中选;于是只有六种情况,枚举一下即可;我们要直径有啥用呢?当我们......
  • [考试记录] 2024.8.17 csp-s模拟赛21
    T1Set解析思考+组合题场上只能想到暴力01背包再加上bitset优化,很好打。本应该有60pts(?或者更多),不曾想由于spj的一些未知原因喜提systemerror,全部cancelled。喜提0pts。......
  • 【漫谈C语言和嵌入式004】深入理解RS232、RS422和RS485:嵌入式系统中的串行通信协议
            在嵌入式系统设计中,串行通信协议是设备间数据传输的重要方式。其中,RS232、RS422和RS485是三种常用的标准。这些协议不仅在工业控制、仪器仪表、网络通信等领域得到广泛应用,也在许多嵌入式系统项目中扮演着重要角色。在本文中,我们将深入探讨这三种串行通信标准......