首页 > 其他分享 >Educational Codeforces Round 149 (Rated for Div. 2) 题解

Educational Codeforces Round 149 (Rated for Div. 2) 题解

时间:2023-05-26 19:13:44浏览次数:48  
标签:Educational Rated 1837 contest 题解 codeforces 括号 https com

https://codeforces.com/contest/1837

https://codeforces.com/contest/1837/problems

利益相关:上紫祭。

真的不要以为这道题放在 F 就不敢做。

压线过题的感觉真好。

image

image

image

ABC 题都过水,就不写了。

代码丢在这里:

A:https://codeforces.com/contest/1837/submission/207156920

B:https://codeforces.com/contest/1837/submission/207180946

C:https://codeforces.com/contest/1837/submission/207186832

D. Bracket Coloring

首先猜测一个结论:\(k \leq 2\),其中 \(k\) 是答案的颜色种数。

然后可以写一个程序验证:比如说对于每一个长度为 \(10\) 的,( 数量和 ) 数量均为 \(5\),然后枚举染色验证即可。

接下来讲如何构造方案(其实构造方案就可以证明结论):

如果左括号数量不等于右括号数量,就直接暴毙,输出 \(-1\) 即可。

否则如果 \(s\) 本身就是 beautiful 的,\(k = 1\)。

否则 \(k = 2\)。

构造策略:

枚举每一个左括号(下标为 \(x\)),贪心找还没有染色的最右边的右括号(下标为 \(y\)),就将 \(x, y\) 都染为颜色 \(1\)。

剩下的染为颜色 \(2\)。

标签:Educational,Rated,1837,contest,题解,codeforces,括号,https,com
From: https://www.cnblogs.com/RB16B/p/17435599.html

相关文章

  • 宏 GENERATED_UCLASS_BODY() 与 GENERATED_BODY() 简析
    继承自UE4引擎的类会生成一些宏代码。这此宏代码的作用就是帮助生成构造函数和相关成员函数UCLASS()classSECTION1_APIASUsableActor:publicAActor{ GENERATED_BODY() public: };UCLASS()classSURVIVALGAME_APIASUsableActor:publicAActor{ GENERATED_U......
  • Educational Codeforces Round 63 (Rated for Div. 2) A,B,C
    A.ReverseaSubstring传送门就是找不满足升序排列的字母,输出就行了。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintmaxn=3e5+10;chars[maxn];intmain(){#ifndefONLINE_JUDGEfreopen("in","r",stdin);#endif//ONL......
  • 华为OD机试 本篇题解:找数字 or 找等值元素
    最近更新的博客华为od2023|什么是华为od,od薪资待遇,od机试题清单 https://dream.blog.csdn.net/article/details/128980730华为OD机试真题大全,用Python解华为机试题|机试宝典 https://dream.blog.csdn.net/article/details/129221789【华为OD机试】全流程解析......
  • ubauntu18.04下出现Invalid YAML: inconsistent indentation: version: 2问题解决
    在配置网卡信息时候遇到如上问题查询后有几种可能错误的地方:未能通过yaml语法和缩进,YAML在解释命令、配置参数这方面十分注重语法和缩进,只有适当缩进才能够解析YAML配置网络配置出现故障,IP地址的网关不正确,或者掩码配置失误那么我们现在在网络配置正确前提下最重要就是了解缩进工作......
  • Educational Codeforces Round 149 (Rated for Div. 2)
    EducationalCodeforcesRound149(RatedforDiv.2)A-GrasshopperonaLine思路:只有两种情况,x整除k时为x-1和1,否则为xvoidsolve(){intx,k;cin>>x>>k;if(x%k==0){cout<<"2\n"<<x-1<<&qu......
  • P4557 [JSOI2018]战争 题解
    闵可夫斯基和前言入门建议看吉老师(吉如一)的计算几何入门到放弃。感觉应该是讲的最通俗易懂的了。本文借鉴了Winxp的博客,以及吉老师视频中的思路。写这篇博客的初衷是因为我作为一个初学者,此题里的题解对我来说理解起来不算太难,但是实现起来细节比较多,题解里也没有很详细地去解......
  • P4288 [SHOI2014]信号增幅仪 题解
    感谢审核人Description给定\(n\)个点,椭圆长轴的方向\(a\)和放大倍数\(p\),求覆盖全部点的最小椭圆的半短轴长度。Solution让我们求最小覆盖椭圆,但是椭圆不具有什么好的性质,我们可以把椭圆转化成圆来做,这样,题目就转化成了最小覆盖圆,这个用随机增量法来做就可以了。接下来......
  • UVA10902 Pick-up Sticks 题解
    Description按顺序给出\(n\)个棍子两个端点的坐标。如果后来的棍子与前边的棍子相交,则说后面的把前面的挡住了。问最后有多少个棍子没被挡住。\(n\leq10^5\),且答案不超过\(1000\)。Solution叉积基本运用。定义:\(\overrightarrow{a}\times\overrightarrow{b}=|\over......
  • SP898 Transmitters 题解
    Description给定\(n\)个点的坐标、半圆的半径以及坐标。问半圆怎么放能覆盖最多的点,输出最多个数。Solution计算几何入门题。首先显然距离圆心超过半径的点是一定不会被覆盖的,舍去。再者我们考虑,半圆的放法是有无限多种的,我们要考虑哪些是有用的。我们可以想到,最优的半圆一......
  • P8943 Deception Point 题解
    Description题目给的很详细了。Solution首先\(n\)个点\(n\)条边,我们很容易就想到基环树(比正常的树多了一条边,形成了一个环),不会也没关系,这题跟基环树其实关系不大。首先,我们可以发现题目中说明了这个环不是一个四元及以下的环,这代表着如果\(A\)提前进入了这个环,那么他......