首页 > 其他分享 >CSP-S 模拟赛35

CSP-S 模拟赛35

时间：2024-10-11 20:32:37浏览次数：8  
标签：lc int siz ans 35 rc CSP 模拟 mod

CSP-S 模拟赛35

T1

其实是傻逼题。常见的套路是枚举右端点，动态维护左端点的贡献。发现右端点移动一位只会对一种颜色有影响，那么考虑线段树维护区间的答案，区间加减每个颜色即时的贡献即可。

代码：

#include <bits/stdc++.h>
#define N 1000005
#define M 8005
#define int long long
using namespace std;
int n, m;
int c[N], d[M];
int lst[N];
int ps[M];
struct Node {
	int l, r;
	int mx;
	int fg;
} e[N << 2];
#define l(i) e[i].l
#define r(i) e[i].r
#define mx(i) e[i].mx
#define fg(i) e[i].fg
#define lc (p << 1)
#define rc (lc | 1)
void push_up(int p) {
	mx(p) = max(mx(lc), mx(rc));
}
void build(int p, int l, int r) {
	l(p) = l, r(p) = r;
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
}
void push_down(int p) {
	if (fg(p) == 0)
		return;
	fg(lc) += fg(p);
	fg(rc) += fg(p);
	mx(lc) += fg(p);
	mx(rc) += fg(p);
	fg(p) = 0;
} 
void update(int p, int l, int r, int vl) {
	if (l > r || l > r(p) || l(p) > r)
		return;
	if (l <= l(p) && r(p) <= r) {
		mx(p) += vl;
		fg(p) += vl;
		return;
	}
	push_down(p);
	update(lc, l, r, vl);
	update(rc, l, r, vl);
	push_up(p);
}
int ans;

signed main() {
	freopen("flower.in", "r", stdin);
	freopen("flower.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &c[i]);
		lst[i] = ps[c[i]];
		ps[c[i]] = i;
	}
	for (int i = 1; i <= m; i++)
		scanf("%lld", &d[i]);
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		update(1, lst[i] + 1, i, d[c[i]]);
		if (lst[i]) 
			update(1, lst[lst[i]] + 1, lst[i], -d[c[i]]);
		ans = max(ans, mx(1));
	}
	cout << ans << "\n";
	return 0;
}

T2

类似曼哈顿距离的坐标系上问题问题容易考虑曼哈顿转切比雪夫。\((x,y)\rightarrow (x+y,x-y)\) 后贡献变成了 \(\min(|x_1-x_2|,|y_1-y_2|)\)。考虑最优的贡献一定是某两个 \(\neq0\) 的直接距离，那么并查集对距离为 \(0\) 的缩点，然后分别按 \(x,y\) 排序维护最小值再查方案数即可，方案数是并查集 \(siz\) 的乘积。

代码：

#include <bits/stdc++.h>
#define N 100005
using namespace std;
int n, ans;
struct Node {
	int x, y, id;
} e[N];
bool cmpx(Node a, Node b) {
	return a.x < b.x;
}
bool cmpy(Node a, Node b) {
	return a.y < b.y;
}
int fa[N];
int fnd(int x) {
	if (x == fa[x])
		return x;
	return fa[x] = fnd(fa[x]);
}
int siz[N];
void mge(int x, int y) {
	x = fnd(x), y = fnd(y);
	if (x != y)
		fa[y] = x, siz[x] += siz[y];
}
pair<int, int>t[N << 1];
map<pair<int, int>, int>mp;
int tot;
int main() {
	freopen("sky.in", "r", stdin);
	freopen("sky.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		e[i].x = x + y;
		e[i].y = x - y;
		e[i].id = i;
		fa[i] = i;
		siz[i] = 1;
	}
	sort(e + 1, e + 1 + n, cmpx);
	for (int i = 1; i < n; i++) 
		if (e[i].x == e[i + 1].x)
			mge(e[i].id, e[i + 1].id);
	sort(e + 1, e + 1 + n, cmpy);
	for (int i = 1; i < n; i++) 
		if (e[i].y == e[i + 1].y)
			mge(e[i].id, e[i + 1].id);
	int ds = 0x3f3f3f3f;
	for (int i = 1; i < n; i++)
		if (fnd(e[i].id) != fnd(e[i + 1].id))
			ds = min(ds, e[i + 1].y - e[i].y);
	sort(e + 1, e + 1 + n, cmpx);
	for (int i = 1; i < n; i++)
		if (fnd(e[i].id) != fnd(e[i + 1].id))
			ds = min(ds, e[i + 1].x - e[i].x);
	for (int i = 1; i < n; i++)
		if (fnd(e[i].id) != fnd(e[i + 1].id) && e[i + 1].x - e[i].x == ds) 
			t[++tot] = make_pair(min(e[i].id, e[i + 1].id), max(e[i].id, e[i + 1].id));
	sort(e + 1, e + 1 + n, cmpy);
	for (int i = 1; i < n; i++) 
		if (fnd(e[i].id) != fnd(e[i + 1].id) && e[i + 1].y - e[i].y == ds)
			t[++tot] = make_pair(min(e[i].id, e[i + 1].id), max(e[i].id, e[i + 1].id));
	sort(t + 1, t + 1 + tot);
	tot = unique(t + 1, t + 1 + tot) - t - 1;
	for (int i = 1; i <= tot; i++) {
		int x = t[i].first, y = t[i].second;
		x = fnd(x), y = fnd(y);
		if (mp.count(make_pair(x, y)) || mp.count(make_pair(y, x)))
			continue;
		mp[make_pair(x, y)] = 1;
		mp[make_pair(y, x)] = 1;
		ans += siz[x] * siz[y];
	}
	cout << ds << "\n" << ans << "\n";
	return 0;
}

T3

考虑每个时刻每个位置上的 \(1\) 能否移动，能走记为 \(1\)，不能走记为 \(0\)。那么考虑时间 \(t,t+1\) 之间如何转移。

如果两个 \(1\) 是相邻的，那么第 \(i\) 个 \(1\) 在 \(t\) 时刻可以走一步，\(i+1\) 个 \(1\) 就可以在 \(t+1\) 时刻走一步。也就是说将原串右移一位并在开头补上 \(0\)。

不相邻的情形是两个 \(1\) 相隔 \(k\) 个 \(0\) 时，字符串上的前 \(k\) 个 \(0\) 就变为 \(1\)。那么考虑维护所有 \(0\) 的相对位置，对 "参照系" 的左移相当于右移了字符串，在开头结尾增删可以方便地用 std::deque 维护，第一问的答案就是考虑每个序列 \(1\) 左移到的地点。

对于第二问，考虑每个字符串中每个 \(1\) 的位置 \(p_i\) 意味着 \(p_i\) 时刻之后对逆序对的贡献 \(+1\)，而这个贡献是一段区间，差分即可。

#include <bits/stdc++.h>
#define N 5000006
#define int long long
#define mod 998244353
using namespace std;
int t;
int n;
int a[N];
string s;
int pos[N], cnt;
deque<int>q;
int ans[N];
int sum[N];
int sm, res;
int qpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}
signed main() {
	freopen("chuan.in", "r", stdin);
	freopen("chuan.out", "w", stdout);
	cin >> t;
	cin >> s;
	n = s.size();
	s = " " + s;
	for (int i = 1; i <= n; i++) {
		a[i] = s[i] - '0';
		if (a[i])
			pos[++cnt] = i;
		else
			sm += cnt;
	}
	for (int i = 1; i <= t; i++)
		q.push_back(i);
	for (int i = 1; i <= cnt; i++) {
		while (q.size() && q.back() + i > t)
			q.pop_back();
		q.push_front(1 - i);
		for (int j = 1; j < pos[i] - pos[i - 1] && q.size(); j++) {
			++sum[q.front() + i];
			--sum[min(q.front() + cnt + 1, t + 1)];
			q.pop_front();
		}
		ans[pos[i] - t + q.size()] = 1;
	}
	for (int i = 0; i <= t; i++) {
		if (i > 0)
			sum[i] = (sum[i] + sum[i - 1]) % mod;
		sm = (sm + sum[i]) % mod;
		res ^= (qpow(233, i) * sm % mod);
	}
	for (int i = 1; i <= n; i++)
		cout << ans[i];
	puts("");
	cout << res << "\n";
	return 0;
}

T4

平方题拆开平方，考虑边 \((u,fa_u)\) 的贡献。

对于一条边平方的部分，贡献是 \(siz_u(n-siz_u)\)。

对于两条边的乘积：

  • \(v\) 在 \(u\) 子树内，贡献是 \(2w_u\times w_v\times (n-siz_u)\times siz_v\)。
  • \(v\) 是 \(u\) 祖先，贡献是 \(2w_u\times w_v\times (n-siz_v)\times siz_u\)。
  • 否则贡献是 \(2w_u\times w_v\times siz_u\times siz_v\)。

对于每个 \(u\)，考虑所有 \(v\) 的贡献。维护和 \(v\) 相关的 \(siz_v\times w_v\) 和 \(w_v\) 即可。线段树/树状数组。

代码：

#include <bits/stdc++.h>
#define N 100005
#define int long long
#define mod 1000000007
using namespace std;
int n;
int val[N];
int s1[N], s2[N];
int smt, f[N];
namespace Mp {
	struct Node {
		int to, nxt;
	} e[N << 1];
	int head[N], cnt;
	void add(int u, int v) {
		e[++cnt].to = v;
		e[cnt].nxt = head[u];
		head[u] = cnt;
	}
	int dfn[N], tot, rk[N];
	int siz[N];
	void dfs1(int x) {
		siz[x] = 1;
		for (int i = head[x]; i; i = e[i].nxt) {
			int y = e[i].to;
			dfs1(y);
			siz[x] += siz[y];
		}
	}
	void dfs2(int x) {
		dfn[x] = ++tot;
		rk[tot] = x;
		s1[x] = (s1[f[x]] + siz[x] * val[x] % mod) % mod;
		s2[x] = (s2[f[x]] + val[x]) % mod;
		for (int i = head[x]; i; i = e[i].nxt) {
			int y = e[i].to;
			dfs2(y);
		}
	}
}
namespace Seg {
	struct Node {
		int l, r;
		int s1, f1, s2, f2;
	} e[N << 2];
	#define l(i) e[i].l
	#define r(i) e[i].r
	#define s1(i) e[i].s1
	#define f1(i) e[i].f1
	#define s2(i) e[i].s2
	#define f2(i) e[i].f2
	#define lc (p << 1)
	#define rc (lc | 1)
	void push_up(int p) {
		s1(p) = (s1(lc) + s1(rc)) % mod;
		s2(p) = (s2(lc) + s2(rc)) % mod;
	}
	void build(int p, int l, int r) {
		l(p) = l, r(p) = r;
		if (l == r) {
			s1(p) = s1[Mp::rk[l]];
			s2(p) = s2[Mp::rk[l]];
			return;
		}
		int mid = (l + r) >> 1;
		build(lc, l, mid);
		build(rc, mid + 1, r);
		push_up(p);
	}
	void push_down(int p) {
		if (f1(p)) {
			f1(lc) = (f1(lc) + f1(p)) % mod;
			f1(rc) = (f1(rc) + f1(p)) % mod;
			s1(lc) = (s1(lc) + f1(p) * (r(lc) - l(lc) + 1) % mod) % mod;
			s1(rc) = (s1(rc) + f1(p) * (r(rc) - l(rc) + 1) % mod) % mod;
		}
		if (f2(p)) {
			f2(lc) = (f2(lc) + f2(p)) % mod;
			f2(rc) = (f2(rc) + f2(p)) % mod;
			s2(lc) = (s2(lc) + f2(p) * (r(lc) - l(lc) + 1) % mod) % mod;
			s2(rc) = (s2(rc) + f2(p) * (r(rc) - l(rc) + 1) % mod) % mod;
		}
		f1(p) = f2(p) = 0;
	}
	void update(int p, int l, int r, int v1, int v2) {
		if (l > r || l > r(p) || l(p) > r)
			return;
		if (l <= l(p) && r(p) <= r) {
			s1(p) = (s1(p) + v1 * (r(p) - l(p) + 1) % mod) % mod;
			s2(p) = (s2(p) + v2 * (r(p) - l(p) + 1) % mod) % mod;
			f1(p) = (f1(p) + v1) % mod;
			f2(p) = (f2(p) + v2) % mod;
			return;
		}
		push_down(p);
		update(lc, l, r, v1, v2);
		update(rc, l, r, v1, v2);
		push_up(p);
	}
	int query1(int p, int x) {
		if (l(p) == r(p) && l(p) == x) 
			return s1(p);
		push_down(p);
		int mid = (l(p) + r(p)) >> 1;	
		if (x <= mid)
			return query1(lc, x);
		return query1(rc, x);
	}
	int query2(int p, int x) {
		if (l(p) == r(p) && l(p) == x) 
			return s2(p);
		push_down(p);
		int mid = (l(p) + r(p)) >> 1;	
		if (x <= mid)
			return query2(lc, x);
		return query2(rc, x);
	}
}
namespace BIT {
	int tree[N];
	int lowbit(int x) {
		return x & (-x);
	}
	void add(int x, int v) {
		while (x <= n) {
			tree[x] += v;
			tree[x] %= mod;
			x += lowbit(x);
		}
	}
	int ask(int x) {
		int ans = 0;
		while (x) {
			ans += tree[x];
			ans %= mod;
			x -= lowbit(x);
		}
		return ans;
	}
}
int query(int x, int w) {
	int tmp = 0, sz = 0;
	sz = (BIT::ask(Mp::dfn[x] + Mp::siz[x] - 1) - BIT::ask(Mp::dfn[x]) + mod) % mod;
	int ans = 2 * w % mod * (n - Mp::siz[x]) % mod * sz % mod;
	int sv = Seg::query1(1, Mp::dfn[f[x]]);
	tmp = (tmp + Seg::query2(1, Mp::dfn[f[x]]) * n % mod - sv + mod) % mod;
	tmp = ((tmp + smt - sv - sz - Mp::siz[x] * val[x] % mod) % mod + mod) % mod;
	ans = (ans + 2 * tmp % mod * Mp::siz[x] % mod * w % mod) % mod;
	return ans;
}
void update(int x, int w) {
	Seg::update(1, Mp::dfn[x], Mp::dfn[x] + Mp::siz[x] - 1, Mp::siz[x] * w % mod, w);
	BIT::add(Mp::dfn[x], Mp::siz[x] * w % mod);
	smt = (smt + Mp::siz[x] * w % mod) % mod;
	val[x] = (val[x] + w) % mod;
}
int qpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ans;
}
int ans, T;
signed main() {
	freopen("revive.in", "r", stdin);
	freopen("revive.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	cin >> n >> T;
	for (int i = 2; i <= n; i++) {
		cin >> f[i] >> val[i];
		Mp::add(f[i], i);
	}
	Mp::dfs1(1);
	Mp::dfs2(1);
	Seg::build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		smt = (smt + Mp::siz[i] * val[i] % mod) % mod;
		BIT::add(Mp::dfn[i], Mp::siz[i] * val[i] % mod);
	}
	for (int i = 2; i <= n; i++) 
		ans = (ans + query(i, val[i])) % mod;
	ans = ans * qpow(2, mod - 2) % mod;
	for (int i = 2; i <= n; i++)
		ans = (ans + val[i] * val[i] % mod * Mp::siz[i] % mod * (n - Mp::siz[i]) % mod) % mod;
	cout << ans << "\n";
	while (T--) {
		int x, w;
		cin >> x >> w;
		ans = (ans - val[x] * val[x] % mod * Mp::siz[x] % mod * (n - Mp::siz[x]) % mod + mod) % mod;
		ans = (ans + query(x, w)) % mod;
		update(x, w);
		ans = (ans + val[x] * val[x] % mod * Mp::siz[x] % mod * (n - Mp::siz[x]) % mod) % mod;		
		cout << ans << "\n";
	}
	return 0;
}

标签：lc,int,siz,ans,35,rc,CSP,模拟,mod
From： https://www.cnblogs.com/Rock-N-Roll/p/18459291

相关文章

  • 『模拟赛』多校A层冲刺NOIP2024模拟赛05
    Rank烂。A.好数（number）签，唐，没签上。考虑之前几次类似的题方法都是选\(k-1\)的方案存起来以使总复杂度除以一个\(n\)，故考虑记共\(n^2\)个两两组合之和，枚举当前点\(i\)前面的点，找是否有值为它们的差的组合，复杂度\(\mathcal{O(n^2)}\)，用map记再挂个\(\logn\)。赛......
  • 多校A层冲刺NOIP2024模拟赛05
    T1、好数（number）签到题把选三个数相加拆为选择一个数，然后看前面有没有能用两个数组合出答案。$O(n^2)$。码(#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<int,int>pii;#definemkmake_pair#de......
  • [10.11]CSP-S模拟赛
    宝贵经验：写题的时候想出时间正确的方法后千万注意计算空间，能不用数组的地方就不要用，否则可能会像我一样：\(35\to15\to0\)赛前小L说比上次简单。赛时T1一开始没有思路，但是注意到了两个关键条件：询问数\(\le300\)\(n,m\le10^9\)然后想到正解绝对不是去直接修改。注......
  • c语言模拟实现库函数 strlen strcpy strcat strcmp strstr
    一、模拟实现库函数strlen解释：strlen是求字符串长度的，求出的长度是不可能为负数所以返回类型设置为size_t也是合情合理的 typedefunsignedintsize_t\注意字符串已经'\0'作为结束标志，strlen函数返回的是在字符串中'\0'前面出现的字符个数（不包含'\0')。size_......
  • coduck 复赛模拟赛三 补题报告 侯锦呈
    自测160分第一题30分第二题100分第三题30分(后来100分 自己改的)第四题0分第一题十五的月亮题目描述假设一个每个月都是30天，用0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1表示一个月30天中的月亮......
  • 10.11 模拟赛（云智计划 模拟测#26）
    S---【云智计划】---6月23日---模拟测#26div1【补题】-比赛-梦熊联盟(mna.wang)S---【云智计划】---6月23日---模拟测#26div2【补题】-比赛-梦熊联盟(mna.wang)复盘A。看到\(n\)为偶数思路秒出。10min过样例。B。好像不太会做啊。模拟了样例2，猜出了一个很优的......
  • csp-s真题题解
    csp题目讲解P8818[CSP-S2022]策略游戏学习笔记感觉非常复杂？对于现在的我还是有深度的，首先第一个大坑就是并不需要真的求出c矩阵，这个题意就是让你在区间中选数，但要求乘积最大，所以要分讨。你假定\(a_i\ge0\)，那这时如果\(min(b_i)\ge0\)取\(max(a_i)\)，否则取\(min(a_i\ge......
  • [45] (多校联训) A层冲刺NOIP2024模拟赛05
    这是什么午休，大黄突然走进来大黄：闪电特效！其他人：？大黄：5k!其他人：？？？大黄：【闪电特效】【闪电特效】男人中的男人【闪电特效】【闪电特效】雄性中的雄性【闪电特效】【闪电特效】巅峰！【闪电特效】【闪电特效】A.好数简单变形一下\[f_i+f_j+f_k=c\]\[f_j+f_k=c-f_i\]然......
  • 多校A层冲刺NOIP2024模拟赛05
    咋是计数专场啊，讨厌计数！就会一个签到题，恼了。rank21,T1100pts,T20pts,T320pts,T40ptsdp设计状态不行。T3典型的背包没看出来，T2简单dp不会设计状态。有一些套路还是要学好数（number）签到题。假设一个数\(a_i\)是好数，那么一定有\(a_i=a_x+a_y+a_z(x\ley\lez)\)用一个b......
  • 多校A层冲刺NOIP2024模拟赛05
    多校A层冲刺NOIP2024模拟赛05\(T1\)A.好数（number）\(100pts/100pts\)枚举两数之和，开个桶维护即可。点击查看代码inta[5010];unordered_map<int,bool>s;intmain(){ freopen("number.in","r",stdin); freopen("number.out","w",stdout)......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99