首页 > 其他分享 >【题解】ABC283

【题解】ABC283

时间:2022-12-26 22:23:12浏览次数:44  
标签:单点 标记 题解 每次 text ABC283

\(\text{AtCoder Beginner Contest 283}\)

A Power

无意义题,直接输出。

B First Query Problem

无意义题,维护一个支持单点修改、单点查询的数据结构。(雾)

C Cash Register

无意义题,记录一下能两个零一起输出的个数。

D Scope

每次最右的左括号匹配应当是唯一的,一个栈可以解决这个问题。
每次删除暴力删标记感觉非常不优秀,每次删除实际上是标记值在这个区间的都无用,那记录一下区间覆盖,整个线段树,判断一下如果被标记过是不是被删了。

E Don't Isolate Elements

瞎想了一堆转成一维问题搞搞搞,不需要转化但是也已经对了,没来得及写。
影响只有三行,压成一个状态枚举然后 \(\text{dp}\) 即可。

F Permutation Distance

转成二维平面上 \(n\) 个不共行不共列的点,求对于每个点最小曼哈顿距离。
如果已知大小,就可以二维偏序查最大值了,于是讨论四个方向即可。
强化版应该是加上时间轴,使用 \(\text{cdq}\) 分治。

G Partial Xor Enumeration

明天

Ex Popocount Sum

明天

标签:单点,标记,题解,每次,text,ABC283
From: https://www.cnblogs.com/SoyTony/p/ABC283.html

相关文章

  • Atcoder Beginner Contest ABC 283 Ex Popcount Sum 题解 (类欧几里得算法)
    题目链接令\(p=\lfloor\frac{n-r}m\rfloor\),则我们其实是要对所有\(0\lei\le29\)求\(\sum_{j=0}^p(\lfloor\frac{mj+r}{2^i}\rfloormod\2)\)。右边那个东西如果没......
  • 2022 International Collegiate Programming Contest, Jinan Site 部分题目简要题解
    从这里开始比赛目录傻逼学院负责人ProblemBTorch注意到$a_1,b_1,a_2,b_2$的和不会超过$10^6$考虑胖先生的周期开始的时候,瘦先生的周期在时......
  • USACO22DEC青铜组题解
    T1:CowCollege总学费\(=\)设置的单人学费\(\times\)接受的奶牛数一旦固定单人学费,就能确定接受的奶牛数单人学费可以是哪些值?\(\{c_1,c_2,\cdots,c_n\}\)其中......
  • P3537 [POI2012]SZA-Cloakroom 题解
    题目大意有\(n\)件物品,每件物品有三个属性\(a_i,b_i,c_i(a_i<b_i)\)。再给出\(q\)个询问,每个询问由非负整数\(m,k,s\)组成,问是否能够选出某些物品使得:对......
  • P4928 [MtOI2018]衣服?身外之物! 题解
    题意gcd共有\(n\)件衣服,编号为\(A_1,A_2,\cdotsA_n\)。每一件衣服分别拥有颜色值和清洗时间,他在每一件衣服穿完以后都会将其送去清洗,而这件衣服当天所拥有的舒适感......
  • NSIS编辑时的乱码问题解决方法
    在Windows中文系统中,HMNISEdit下使用非中文和英文,比如韩文、日语或者阿拉伯语等。会发现编辑的文字变成乱码或者问号。     1、在安装的过程中显示乱码。2、......
  • AcWing291.蒙德里安的梦想题解
    题解:蒙德里安的梦想注:本题解内容简陋,多有不周,敬请谅解。如果有问题请在评论区留言。谢谢。由于作者能力有限,这篇题解不会给出太严谨的证明,只是旨在帮助大家更好地理解此......
  • AcWing83场周赛题解
    第一题、奇偶题目链接:https://www.acwing.com/activity/content/problem/content/7862/比较麻烦(本人做法)找出不同字符个数,再判断。#include<iostream>usingnamespac......
  • 洛谷P4146 序列终结者 题解 splay tree
    题目链接:https://www.luogu.com.cn/problem/P4146题目大意:支持:区间更新(+x)区间翻转区间查询(最大值)解题思路:几乎和AcWing2437.Splay这题一模一样。示例程序:#inc......
  • Codeforces 983 D Arkady and Rectangles 题解
    题目链接挺有意思的数据结构题,题面看着像个板子,其实还是有不少学问的。平面上一堆矩形的题目常见套路就是对\(x\)轴扫描线,\(y\)轴线段树维护,这题也不例外。我们先对坐标......