首页 > 其他分享 >[赛记] 冲刺CSP联训模拟2

[赛记] 冲刺CSP联训模拟2

时间:2024-10-05 15:00:01浏览次数:10  
标签:赛记 int tr long CSP 联训 ls now id

三道计数 + 一道数据结构也是没谁了

这场可是好好锻炼了我的写暴搜能力。。。

挤压 20pts

暴搜20pts;

把最后的答案进行二进制拆解,即 $ ans = 2^i + 2^j + 2^k + ... $,那么答案的平方为 $ \sum_{i = 0}^{30} \sum_{j = 0}^{30} s_i s_j 2^{i + j} $,其中 $ s_i, s_j $ 代表答案二进制拆解后这一位是 $ 1 $ 还是 $ 0 $;

那么我们发现,答案的平方只和答案二进制拆解后的任意两位有关,所以我们直接设 $ f_{k, i, j, 0/1, 0/1} $ 表示考虑到第 $ k $ 个数字,第 $ i $ 位是 $ 0/1 $,第 $ j $ 位是 $ 0/1 $ 的概率即可;

这其实是个概率 $ DP $,从第一步开始其实比较难想

点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const long long mod = 1e9 + 7;
long long n;
long long a[500005], q[500005];
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 f[35][35][2][2], now[2][2];
int main() {
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	long long kk = ksm(1000000000, mod - 2);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		cin >> q[i];
		q[i] = q[i] * kk % mod;
	}
	for (int i = 0; i <= 30; i++) {
		for (int j = 0; j <= 30; j++) {
			f[i][j][0][0] = 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 30; j++) {
			for (int k = 0; k <= 30; k++) {
				for (int l = 0; l <= 1; l++) {
					for (int r = 0; r <= 1; r++) {
						now[l][r] = f[j][k][l][r];
					}
				}
				bool tj = false;
				bool tk = false;
				if ((a[i] >> j) & 1) tj = true;
				if ((a[i] >> k) & 1) tk = true;
				for (int l = 0; l <= 1; l++) {
					for (int r = 0; r <= 1; r++) {
						f[j][k][l][r] = (now[l][r] * (1 - q[i] + mod) % mod + now[l ^ tj][r ^ tk] * q[i] % mod) % mod;
					}
				}
			}
		}
	}
	long long ans = 0;
	for (int i = 0; i <= 30; i++) {
		for (int j = 0; j <= 30; j++) {
			ans = (ans + f[i][j][1][1] * ksm(2, i + j) % mod) % mod;
		}
	}
	cout << ans;
	return 0;
}

工地难题 30pts

暴搜30pts

考虑正解,是个容斥,题解详见[算法] 容斥的例题;

星空遗迹 20pts

$ \Theta(n^3) $ 暴力20pts;

考虑正解,发现可以单调栈维护,满足下面的能够赢上面的,答案就是栈大小最小时对应的元素,于是可以线段树区间修改区间查最小;

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

点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int n, q;
char s[500005];
char win(char x, char y) {
	if (x == y) return x;
	if ((x == 'R' && y == 'S') || (x == 'S' && y == 'R')) return 'R';
	if ((x == 'S' && y == 'P') || (x == 'P' && y == 'S')) return 'S';
	if ((x == 'P' && y == 'R') || (x == 'R' && y == 'P')) return 'P';
}
int f[500005];
namespace SEG{
	inline int ls(int x) {
		return x << 1;
	}
	inline int rs(int x) {
		return x << 1 | 1;
	}
	struct sss{
		int l, r, lz;
		pair<int, int> mi;
	}tr[3000005];
	inline void push_up(int id) {
		tr[id].mi = min(tr[ls(id)].mi, tr[rs(id)].mi);
	}
	inline void push_down(int id) {
		if (tr[id].lz) {
			tr[ls(id)].lz += tr[id].lz;
			tr[rs(id)].lz += tr[id].lz;
			tr[ls(id)].mi.first += tr[id].lz;
			tr[rs(id)].mi.first += tr[id].lz;
			tr[id].lz = 0;
		}
	}
	void bt(int id, int l, int r) {
		tr[id].l = l;
		tr[id].r = r;
		if (l == r) {
			tr[id].mi = {f[l], l};
			return;
		}
		int mid = (l + r) >> 1;
		bt(ls(id), l, mid);
		bt(rs(id), mid + 1, r);
		push_up(id);
	}
	void add(int id, int l, int r, int d) {
		if (tr[id].l >= l && tr[id].r <= r) {
			tr[id].mi.first += d;
			tr[id].lz += d;
			return;
		}
		push_down(id);
		int mid = (tr[id].l + tr[id].r) >> 1;
		if (l <= mid) add(ls(id), l, r, d);
		if (r > mid) add(rs(id), l, r, d);
		push_up(id);
	}
	pair<int, int> ask(int id, int l, int r) {
		if (tr[id].l >= l && tr[id].r <= r) {
			return tr[id].mi;
		}
		push_down(id);
		int mid = (tr[id].l + tr[id].r) >> 1;
		if (r <= mid) return ask(ls(id), l, r);
		else if (l > mid) return ask(rs(id), l, r);
		else return min(ask(ls(id), l, mid), ask(rs(id), mid + 1, r));
	}
}
using namespace SEG;
int main() {
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
	}
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (s[i] == s[i - 1]) {
			f[i] = f[i - 1];
			continue;
		}
		if (win(s[i], s[i - 1]) == s[i]) {
			f[i] = f[i - 1] - 1;
			continue;
		}
		if (win(s[i], s[i - 1]) == s[i - 1]) {
			f[i] = f[i - 1] + 1;
			continue;
		}
	}
	bt(1, 1, n);
	int ss, l, r;
	char y;
	for (int i = 1; i <= q; i++) {
		cin >> ss >> l;
		if (ss == 1) {
			cin >> y;
			if (y == s[l]) continue;
			if (l > 1) {
				int ls = 0;
				if (s[l - 1] == s[l]) ls = 0;
				else if (win(s[l - 1], s[l]) == s[l - 1]) ls = 1;
				else if (win(s[l - 1], s[l]) == s[l]) ls = -1;
				int now = 0;
				if (s[l - 1] == y) now = 0;
				else if (win(s[l - 1], y) == s[l - 1]) now = 1;
				else if (win(s[l - 1], y) == y) now = -1;
				add(1, l, n, now - ls);
			}
			if (l < n) {
				int ls = 0;
				if (s[l + 1] == s[l]) ls = 0;
				else if (win(s[l], s[l + 1]) == s[l]) ls = 1;
				else if (win(s[l], s[l + 1]) == s[l + 1]) ls = -1;
				int now = 0;
				if (y == s[l + 1]) now = 0;
				else if (win(s[l + 1], y) == y) now = 1;
				else if (win(s[l + 1], y) == s[l + 1]) now = -1;
				add(1, l + 1, n, now - ls); 
			}
			s[l] = y;
		}
		if (ss == 2) {
			cin >> r;
			cout << s[ask(1, l, r).second] << '\n';
		}
	}
	return 0;
}

标签:赛记,int,tr,long,CSP,联训,ls,now,id
From: https://www.cnblogs.com/PeppaEvenPig/p/18447856

相关文章

  • [DMY]2024 CSP-S 模拟赛 Day 10
    赛时对于T1,看懂题面以后感觉很可做。首先明确正解复杂度应该是基于\(N\)额度线性做法。把输入按照开始时间排序,然后依次处理。赛时考虑到一个元素在覆盖过程中遇到其他元素时无法确定时间先后,确定后想要找到该元素的当前位置和重新覆盖有些困难,写了1h以后先放弃了。舍远......
  • [赛记] 多校A层冲刺NOIP2024模拟赛01【衡中】
    构造字符串50pts错解50pts;考虑正解,对于题目中的要求,我们可以转换成若干个相等与不等的操作,若相等则用并查集合并一下,不等则连边,若同块连边则无解,否则从前往后遍历赋值,每次找所连边其它块值的$\operatorname{mex}$即可;时间复杂度:$\Theta(nm\alpha(n))$;点击查看代码#i......
  • [赛记] 冲刺CSP联训模拟1[衡中]
    几何100pts赛时打的$DP$没有用bitset优化过了,也是放过了暴力;考虑设状态$f_{i,j,k}$表示考虑到第$i$位,到第$j$位$x$和第$k$位$y$可不可取,直接转移即可;时间复杂度:$\Theta(|s||x||y|)$,应该是过不了的;点击查看暴力#include<iostream>#incl......
  • [赛记] csp-s模拟7
    median50pts错解50pts(有重复的数就不行);赛时想容斥了,其实不用容斥(好像也不能容斥);题解做法:将每个数存一个二元组,按大小排序,枚举每一个数作为中位数,再枚举每个位置的种类,看它前面和后面有多少这些种类的数,乘起来即可;这样就巧妙地避免了重复的情况,如果直接枚举,则有相同的数会被重......
  • [赛记] csp-s模拟6
    一般图最小匹配35pts纯纯的错解35pts;考虑将原数列排序,那么我们选的边就只能是相邻两个点的;发现这玩意能够递推(赛时没发现),所以直接$DP$,设$f_{i,j}$表示当前考虑到第$i$位,有$j$条边被选的最小权值,转移时考虑第$i$个点连不连第$i-1$个点即可;时间复杂......
  • 冲刺 CSP 联训模拟2
    题面温馨提示代码中的变量名可能与题意、题解不同。代码不删缺省源,可以直接拿来对拍。T1挤压Solution众所周知,异或是一种按位运算,不好进行十进制的数间合并。我们考虑将每个数拆分为二进制的形式进行处理。此时,对于每一种情况,假设表示\(2^i\)二进制位的值为\(b_i\),我......
  • 冲刺 CSP 联训模拟 2
    T1挤压概率期望,二进制拆位看到异或想到拆位算贡献\[\begin{aligned}ans&=\sum_xx^2P(x)\\&=\sum_x(b_1+b_2+...+b_{30})^2P(x)\\\(b_i表示\x\二进制下\i\位的值)\\&=\sum_x(b_1b_1+b_1b_2+...b_{30}b_{29}+b_{30}b_{30})P(x)\\&=\sum_i^{30}\sum_j^{30......
  • 代码源CSP-S模拟赛Day7-9赛后总结
    代码源CSP-S模拟赛Day7-9赛后总结Day7赛时先扫一遍题,T1显然数位dp,感觉放在T1应该不难,而且题面有一种很亲切的感觉,感觉很可做。T2简单思考一下发现最终合成的数就是\(a_1\),\(a_2\),\(a_3\)……,\(a_n\)这n个数填正负号再加上一个k的倍数,估计会有一些比较智慧的手法,感觉很......
  • CSP-S 模拟赛34
    CSP-S模拟赛34T1考虑对原序列将\(k\)的左右分成两个序列。simple的想法是分别从\(1\)开始跑前缀和,每一次总跑到下一个小于它的点,然后依次类推。发现这样做碰到序列最小值之后难以继续。然而我们发现这样跑点的过程从前往后和从后往前是等价的。这样考虑的原因是发现这样......
  • CSP-S 模拟赛 32
    CSP-S模拟赛32rnk25,\(0+0+9+0=9\)。T1[CF1578K]KingdomofIslands还没改出来。T2[CF1578L]Labyrinth警钟嚼烂:改代码改干净。首先考虑如果从\(a\)走到\(b\),人最胖是多少。毫无疑问,这是一个最大生成树问题。在这个基础上考虑原问题,我们发现由于人会越来越胖,一定有边......