首页 > 其他分享 >CF1978E Computing Machine 题解

CF1978E Computing Machine 题解

时间:2024-06-22 15:44:57浏览次数:21  
标签:overline int 题解 sum long Machine B1 CF1978E define

好写程度:\(E>D>C\)。

好想程度:\(C>D=E\)。

总结:C 是全场最难。

我们考虑把两个操作对全体的 \(a_i,b_i\) 都做一遍,会发现我们只会做这两遍,不会再有嵌套的了,因为都做过一遍后 \(\{a\}\) 中 0 的数量只会减少,而且即使再做一遍也无法给 \(\{b\}\) 改成不一样的了,比较显然。

下文中令 \(\{a\},\{b\}\) 分别表示修改过的数组,\(\{\overline a\},\{\overline b\}\) 表示原数组。

然后观察我们可以知道,对于任意一对满足 \(r-l>2\) (即区间长度大于等于 4)的 \((l,r)\),\(\{b\}\) 中受影响的只有左右端点,那么 \(\{a\}\) 中受影响的就会是左右边界的各两个字符,所以我们考虑做前缀和,将不受影响的直接前缀和求出,受影响的就直接加上 \(\overline a_l\) 和 \(\overline a_l\),然后结合 \(\overline b\) 和 \(b\) 求出另外两个。

至于区间长度小于 4 的,直接暴力即可。

时间复杂度 \(O(\sum n+\sum q)\)。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define ll long long
#define ull unsigned long long
#define m_p make_pair
#define m_t make_tuple
#define N 200010
using namespace std;
using namespace __gnu_pbds;
int sum[N], n, q;
int A[N], B[N], B1[N];
void all_in()
{ // all in!
	char c;
	for (int i = 1; i <= n; i++)
	{
		cin >> c;
		sum[i] = A[i] = (c == '1');
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> c;
		B1[i] = B[i] = (c == '1');
	}
	return;
}
void mksum()
{
	for (int i = 2; i < n; i++)
		B1[i] |= !(A[i - 1] | A[i + 1]);
	for (int i = 2; i < n; i++)
		sum[i] |= (B1[i - 1] & B1[i + 1]);
	for (int i = 1; i <= n; i++)
		sum[i] += sum[i - 1];
	return;
}
void query()
{
	int x, y;
	while (q--)
	{
		cin >> x >> y;
		if (y == x)
			cout << A[x] << "\n";
		else if (y - x == 1)
			cout << A[x] + A[y] << "\n";
		else if (y - x == 2)
			cout << A[x] + A[y] + ((B[x] & B[y]) | A[x + 1]) << "\n";
		else
			cout << sum[y - 2] - sum[x + 1] + A[x] + A[y] + ((B[x] & B1[x + 2]) | A[x + 1]) + ((B[y] & B1[y - 2]) | A[y - 1]) << "\n";
	}
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--)
	{
		cin >> n;
		all_in();
		mksum();
		cin >> q;
		query();
	}
	return 0;
}

标签:overline,int,题解,sum,long,Machine,B1,CF1978E,define
From: https://www.cnblogs.com/wryyy-233/p/18262380

相关文章

  • [题解]AT_abc267_f [ABC267F] Exactly K Steps
    大家好,我是毒瘤,喜欢用玄学算法过题。发现题解区没有这个做法,于是来发一篇。思路不难发现如果一个点对\((u,v)\)的距离为\(d\),那么在这棵树以\(u\)为根时,\(v\)的深度为\(d\)。于是考虑换根DP。首先思考如何计算答案。显然我们可以将查询离线下来,然后当换根到以\(u\)......
  • BD202301·公园题解
    BD202301·公园题解考虑将整个移动过程分为两个部分:小度和度度熊汇合之前小度和度度熊汇合之后第一部分可以直接用Dijkstra算法直接搞定,第二部分可以考虑反向思考,从N点出发做一次Dijkstra,最后枚举每个汇合点即可得到答案。时间复杂度\(\Theta(nlogn)\)代码如下:#include......
  • [题解]AT_abc264_e [ABC264E] Blackout 2
    思路一道很经典的题,运用了一种叫「时光倒流」的技巧。「时光倒流」本质上就是将所有删边(或删点)的操作,通过倒序循环求值的方式转化为加边(或加点)。「时光倒流」具体实现通常伴随着并查集出现,维护一个连通块的某种性质。首先,我们需要将所有从始至终没有删过的边加入并查集。在这......
  • [题解]AT_abc263_d [ABC263D] Left Right Operation
    思路首先,不难发现最终的序列一定是形如下面的序列:\[l,\dots,l,a_i,a_{i+1},\dots,a_{i+j},r,\dotsr\]那么,我们就可以将其分为三段,每段都单独维护。首先,对于第一段,我们可以枚举出最后一个\(l\)的位置\(x\),那么和为\(x\timesl\)。对于第二段显然可以用前......
  • [题解]AT_abc256_h [ABC256Ex] I like Query Problem
    思路首先可以看一下P4145,在P4145中使用了一种叫势能线段树的Trick。对于势能线段树,我个人的理解是,对于一段区间(或一个点)直接暴力维护,在经过很少的次数后操作将没有意义的题就可以使用势能线段树。在本题中,如果没有推平操作,显然我们可以直接使用势能线段树,时间复杂度可以轻......
  • [题解]AT_abc263_f [ABC263F] Tournament
    先为大家毙掉一个错解思路首先不难发现,如果将整棵比赛的对战图画出来,一定是一个满二叉树。不妨将令一个节点\(u\)的左右儿子编号分别为\(2u\)和\(2u+1\)。然后定义\(dp_{u,d}\)表示将\(u\)为根的子树内的选手全部比赛完,并且\(u\)已经赢了\(d\)场的最大结果。发......
  • [题解]AT_abc237_g [ABC237G] Range Sort Query
    思路将小于等于\(x\)的元素赋为\(1\),其余的赋为\(0\)。那么一个区间内小于等于\(x\)的数量就是区间中\(1\)的数量。那么,将区间升序排列就是将\(1\)先堆在前面,将\(0\)堆到后面;降序排列同理。考虑动态维护\(x\)的位置,记其位置为\(t\)。如果\(l\leqt\leqr\),则......
  • [题解]AT_abc236_f [ABC236F] Spices
    思路首先对所有的\(c\)从小到大排序,然后对于每一个值如果之前能凑出就不选,否则就选。这样做显然是对的。令\(p_1,p_2,\dots,p_{2^n-1}\)表示将\(c\)排序之后,对应原来的下标;\(S\)表示选出数的集合;\(S'\)表示最终选出数的集合。可以证明两个问题:如果\(p_i\)可以被已选......
  • [题解]AT_abc247_f [ABC247F] Cards
    思路对于包含数\(x\)的卡牌,两张之中必定要选择一张,由此想到2-SAT的思想。我们将所有带有\(x\)的卡牌两两连边,每一条边连接的点都表示两点必须选择一个。不难发现,我们这样会得出若干个环。(因为对于每一张卡牌的出边为\(2\),一定会形成环)在每一个环中的选择情况,不会影响答......
  • [题解]AT_abc240_f [ABC240F] Sum Sum Max
    思路题目要求的是\(\max_{a=1}^{n}\{\sum_{i=1}^{a}\sum_{j=1}^{a}{A_j}\}\),所以我们将\(\sum_{i=1}^{a}\sum_{j=1}^{a}{A_j}\)化简一下,得:\[i\timesA_1+(i-1)\timesA_2+\dots+1\timesA_x\]在\(a\)每增加\(1\)时,这个和\(s\)将会变......