首页 > 其他分享 >Codeforces Round 807 (Div. 2)

Codeforces Round 807 (Div. 2)

时间:2023-12-12 14:16:22浏览次数:37  
标签:std int ll Codeforces long cin Div 807 void

基本情况

AB题秒了。

C题搞了半天,搞了一个假的解法,最后还是爆空间了。

D题没想下去。

C. Mark and His Unfinished Essay

Problem - C - Codeforces

错误分析

写出来自己的错解之后没有进一步思考,而是觉得没希望直接做D去了,实则D也没可能半小时写完。

我的错解就是预处理好每个字符串复制后所在的区间,然后查的时候二分找区间,再找字符串。(实则换汤不换药,没有优化空间)。但其实照着这个想法进一步下去,把结构体中的字符串去掉,也就是正解。

using ll = long long;

int n, c, q;

struct Query {
	ll l, r;
	std::string s;
	Query(ll _l, ll _r, std::string _s)
		: l(_l), r(_r), s(_s) {}
	Query() {}
	void print()
	{
		std::cout << "l = " << l << " r = " << r << " s: " << s << std::endl; 
	}
	void find(int ind)
	{
		std::cout << s[ind - l] << std::endl;
	}
}Q[44];

void close_sync()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
}

void search(int x)
{
	int l = 0, r = c, mid;
	while(l <= r)
	{
		mid = l + r >> 1;
		if (Q[mid].r < x)
		{
			l = mid + 1;
		}
		else if (Q[mid].l > x)
		{
			r = mid - 1;
		}
		else
		{
			Q[mid].find(x);
			return ; 
		}
	}
}

void solve()
{
	ll l, r, k;	
	std::string s;
	std::cin >> n >> c >> q >> s;
	Q[0] = Query(1, n, s);
	for (int i = 1; i <= c; i++)
	{
		std::cin >> l >> r;
		std::string temp = "";
		for (int j = 0; j < i; j++)
		{
			if (Q[j].r < l) continue;
			if (Q[j].l > r) break;
			if (Q[j].r >= l && Q[j].l <= l) 
			{
				int start = l - Q[j].l;
				if (Q[j].r < r)
				{
					int num = Q[j].s.size() - start;
					temp += Q[j].s.substr(start, num); 
				}
				else
				{
					int num = r - Q[j].l - start + 1;
					temp += Q[j].s.substr(start, num);
				}
				continue;
			}
			if (Q[j].r <= r && Q[j].l >= l) 
			{
				temp += Q[j].s;
				continue; 
			}
			if (Q[j].r >= r && Q[j].l <= r)
			{
				int start = 0, num = l - Q[j].l + 1;
				temp += Q[j].s.substr(start, num);
				continue; 
			}
		} 
		Q[i] = Query(Q[i - 1].r + 1, Q[i - 1].r + r - l + 1, temp); 
	}
	for (int i = 1; i <= q; i++) std::cin >> k, search(k);
} 

正确思路

我们可以发现,任何一个新增的字符,都是由之前的字符复制过来的。

所以,我们可以想个办法,让一个新增的位置回溯到原字符串中的某一个位置。

可以发现,复制的次数非常小,所以我们可以从后往前遍历每次复制操作。

如果我们所求的目标位置在粘贴区间内,就回溯到原区间的对应位置。

不断回溯,就可以找到答案。

#include<iostream>
#include<algorithm>
#include<map>

using ll = long long;

int n, c, q;
ll l[45], r[45], dif[45], x, len;
char a[200010];

void close_sync()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
}

void solve()
{
	std::cin >> n >> c >> q;
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	len = n;//维护当前长度 
	for (int i = 1; i <= c; i++)
	{
		std::cin >> l[i] >> r[i];
		dif[i] = len - l[i] + 1;//每个粘贴的位置和其对应的原位置之间的差值是一定的,我们把这个差值记下来。
		len += r[i] - l[i] + 1;//维护当前长度  
	}
	for (int i = 1; i <= q; i++)
	{
		std::cin >> x;
		for (int j = c; j; j--) if (x >= l[j] + dif[j] && x <= r[j] + dif[j]) x -= dif[j];//回溯到之前的位置 
		std::cout << a[x] << std::endl; 
	}
} 

int main()
{
 	close_sync();
 	int _; std::cin >> _;
 	while(_--) solve();
	return 0;
}

D. Mark and Lightbulbs

Problem - D - Codeforces

我们考虑这个操作究竟能干什么。
我们可以发现,进行一次操作可以 使 01 分界线移动 \(1\),不会改变 01 的段数。
所以如果 \(s\) 和 \(t\) 的 01 段数不同,或者 \(s_1,t_1\)、\(s_n,t_n\) 不同,就无解。

可以证明存在一种方案使得移动分界线的时候仅仅往同一方向移动,所以就不会有额外的操作出现。
所以就只需要扫一次得到 \(s,t\) 所有的 01 分界线,然后答案就是这些对应两个分界线的差的绝对值的和。

代码是非常简短的

const int N = 2e5 + 10;

char s1[N], s2[N];

void solve()
{
	int n;
	long long ans = 0;
	std::cin >> n; std::cin >> (s1 + 1) >> (s2 + 1);
	if (s1[1] != s2[1] || s1[n] != s2[n]) {std::cout<<"-1\n"; return;}
	std::vector<int> p1, p2;
	for (int i = 2; i <= n; i++)
	{
		if (s1[i] != s1[i - 1]) p1.push_back(i);
		if (s2[i] != s2[i - 1]) p2.push_back(i);
	}
	if (p1.size() != p2.size()) {std::cout<<"-1\n"; return;}
	for (int i = 0; i < p1.size(); i++) ans += std::abs(p1[i] - p2[i]);
	std::cout << ans << '\n';
}

标签:std,int,ll,Codeforces,long,cin,Div,807,void
From: https://www.cnblogs.com/kdlyh/p/17896633.html

相关文章

  • Codeforces 198 B Jumping on Walls
    题面翻译题目描述瓦西亚在和忍者玩电脑游戏。在这个关卡,瓦西亚需要操控忍者走出一个很深的峡谷。峡谷由两面垂直于地面且互相平行的墙组成,它们的高度为\(n\)米。我们将这些墙分成许多\(1\)米长的区域,并从下到上用\(1\)到\(n\)的正整数对它们进行编号。有些地方是安全的,忍者可以......
  • Codeforces Round 914 (Div. 2)
    基本情况A题+2,幸好后面突然悟了。B题体现了读题以及一词多义的重要性。C题不会。看了一下1700分的题目,暂时先放了。A.TheThirdThreeNumberProblemProblem-A-Codeforces推出了规律,\(n\)为偶数的时候,无脑\(a=n\oplus1,b=n\oplus1,c=1\)就行。然而奇数......
  • Codeforces Round 914 (Div. 2)
    CodeforcesRound914(Div.2)A-Forked!解题思路:枚举皇后和国王能被骑士吃到的位置,重合的点数就是答案。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;typedefpair<ll,ll>pii;#definefifirst#definesesecondconstintmod=1e9......
  • 232-父级div,包含子div,子div有点击事件,父div有点击事件,js如何实现,2个点击事件不干扰
    HTML结构<divid="parent"><divid="child"></div></div>JavaScript/jQuery代码:$(document).ready(function(){//父级div的点击事件处理程序$('#parent').on('click',function(){console.log(&#......
  • php 去除图片以及DIV的width、height、style
    1.去掉图片的宽高,去掉DIV的style样式$str='<divstyle="margin:0pxauto;width:740px;"><p><imgwidth="748"height="444"alt=""src="/images/upload/Image/manmiao_0001.jpg"/></p></div......
  • 图片铺满div元素不变形,超出部分隐藏,保留中心部分css代码
    在我们网站更新文章的时候,经常会插入图片,丰富信息。但是我们插入的图片长宽比例并不一定是固定的。我们在调用缩略图的时候,常常会出现图片变形的情况,高和宽不成比例。那么如何让图片不变形,又能铺满div元素呢?我们可以使用css代码中object-fit属性来实现。object-fit属性指定元素的......
  • CodeForces 575F Bulbo
    洛谷传送门CF传送门提供一个傻逼\(O(n^2)\)做法。首先考虑暴力dp,设第\(i\)轮后在\(j\)坐标上的最小花费为\(f_{i,j}\),有:\[f_{i,j}=\minf_{i,k}+|j-k|+\begin{cases}l_i-j&j<l_i\\0&l_i\lej\ler_i\\j-r_i&j>r_i\end{cases}......
  • Codeforces Round 914 (Div. 2)
    CodeforcesRound914(Div.2)A.Forked!#include<bits/stdc++.h>#defineendl'\n'#defineintlonglongusingnamespacestd;voidsolve(){inta,b;intx,y;cin>>a>>b>>x>>y;map<pair<int,in......
  • [Codeforces] CF1793C Dora and Search
    CF1793CDoraandSearch题意给定一个长度为\(n\)的排列\(a\),问是否存在正整数\(l,r\)使得\(a_l,a_r\)均不为\(a_{l...r}\)中的最大值或最小值。思路很明显的双指针,虽然我最开始的思路是二分预处理当前序列的最大值和最小值,并且一旦两段的\(l,r\)中有一个是最大或......
  • [Codeforces] CF1790D Matryoshkas
    CF1790DMatryoshkas题意ZYH的玩具有很多种类,每种玩具都是一段连续的区间(如\([3,4,5]\))ZYH有很多种玩具,但是他不慎把所有玩具的元素乱序混合到了一起。例如玩具\([1,2,3,4]\)和玩具\([2,3]\)混合到一起后可能是\([2,2,3,4,3,1]\)。给定混合后的序列\(a\),SA想知道Z......